Jump to content

    

Сжать битовое представление больших текстовых символов

35 минут назад, jcxz сказал:

А зачем простой алгоритм на сжатие? Вам же вроде для распаковки нужно было. А сжимать можно не спеша, сложным алгоритмом.

И чем не подошли те алгоритмы, которые я описывал? Там вроде всё просто должно было получиться.

Первый алгоритм и использую. Я же его и описал в начале темы. А потом вы.
Предложите алгоритм сложной упаковки, простой распаковки для 32-битового слова.

Share this post


Link to post
Share on other sites
1 час назад, ViKo сказал:

Предложите алгоритм сложной упаковки, простой распаковки для 32-битового слова.

Распаковка:

//data = 0...0xFFFF
//если бит15==0 - распаковка по таблице t
//если бит15==1 - распаковка групп битов; тогда бит0 - начальное значение самой младшей группы битов
u32 Unpack(uint data)
{
  enum {NB = 3, NG = (14 + NB - 1) / NB}; //NB - разрядность счётчика длины группы битов
  enum {NM = ...}; //вычисленная упаковщиком минимальная ширина группы пикселов для любой строки шрифта из всех закодированных по методу групп битов; должна быть >=1
  static u32 const t[] = {/* строки пикселей, которые не удалось сжать по методу групп битов */};
  s32 res;
  if (data & B15) { //строки пикселей сжатые по методу групп битов
    uint i, n = 32 - NM * NG;
    for (res = data << 31, data += (2u << NB * NG) - B15; ; res = res >> 1 ^ B31) {
      res >>= i = (data >> 1 & (1 << NB) - 1) + NM - 1;
      n -= i;
      data >>= NB;
      if (data < B2) break;
    }
    res = (u32)res >> n;
  } else res = t[data];
  return res;
}

data - очередная упакованная строка пикселей шрифта. Надеюсь понятно, что B... - битовые маски типа:

#define B0  0x00000001ul
#define B1  0x00000002ul
#define B2  0x00000004ul
#define B3  0x00000008ul
#define B4  0x00000010ul
#define B5  0x00000020ul

Соответствующий алгоритм упаковки - на самостоятельную проработку, домашнее задание :wink:

Share this post


Link to post
Share on other sites

jcxz, вы бы словами описали идею. Похоже на то, что уже говорили.
В идеале - закодировать 32-битовую последовательность одним байтом (учитывая моё описание выше - 7-битовым словом, а старший бит будет всегда 1), предполагая, что последовательности одинаковых битов в 32-байтовом слове стандартизованы.

Share this post


Link to post
Share on other sites
В 15.05.2020 в 10:58, ViKo сказал:

А какой там принцип сжатия? Что-то с наскоку не откопал.
Например. Для одной строки растра символа задаётся начальный бит - 0 или 1, затем количество идущих подряд нулей или единиц, затем количество идущих подряд единиц или нулей, и т.д.

Там 2 варианта - какойто BW и RLE. Я пользовался RLE. только как я понял это не просто RLE, а со словарем - составляет каталог популярных последовательнотей. Есть отдельный оптимизатор, который сжимает упакованый фонт, более оптимальным словарем.
Там совсем немного сорсов, и прежде чем свое велосипедить, имхо, лучше ознакомиться с тем что они сделали

Edited by AlexRayne

Share this post


Link to post
Share on other sites
3 часа назад, ViKo сказал:

jcxz, вы бы словами описали идею. Похоже на то, что уже говорили.

Ну да. Оно и есть. Я думал Вы просили реализацию алгоритма.

3 часа назад, ViKo сказал:

В идеале - закодировать 32-битовую последовательность одним байтом (учитывая моё описание выше - 7-битовым словом, а старший бит будет всегда 1), предполагая, что последовательности одинаковых битов в 32-байтовом слове стандартизованы.

Если уникальных строк пикселей будет не более 128 - то получится.

Share this post


Link to post
Share on other sites
В 17.05.2020 в 08:40, ViKo сказал:

Я тем временем теоретически ужиматель придумал. Кодирую символ в виде набора строк. Строки кодируются числами 128 - 255 (128 видов строк, думаю, хватит на любые символы, реально будет намного меньше). Числа 3 - 127 задают количество строк с одинаковым кодом (многие строки повторяются), задаются перед кодом строки, если нужно. Число 0 задаёт конец строк символа. 1 и 2 - можно в качестве количества строк использовать, но нет смысла. Может, для чего-то иного. Например, инвертировать строку (заменить нули на единицы) или обратить (рисовать задом наперёд). 

Вот как саму 32-битовую строку сжать, простого алгоритма не изобрёл. 

О, я тут немного призадумался :biggrin: Кодировать толщину линии (5-6-7 пикселей в зависимости от наклона) одним словом. Задавать номер строки в массиве строк символов и сдвиг этой строки (допустим, вправо). Чтобы не кодировать одинаковые строки, только сдвинутые вбок. Годится для символов с наклонными одиночными линиями: 2, 4, 7.
Впрочем, это использовать не буду. Запутаюсь в ручном кодировании. И для строк с двумя линиями слева и справа - не пригодится. 

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now