fk0легенда (06.12.2017 11:30, просмотров: 911) ответил SciFi на В общем, я долго гуглил, но так и не нашёл. Задача: сжать при сборке программы, поместить в ПЗУ. Для разжимания использовать не более 100 байт ОЗУ (условно). Все LZ сразу идут лесом. Всё, что осталось, - УГ. Пичалька :-( Хоть сам пиши, а так не
Буфер для LZ не нужен от вообще. Если это не LZW со словарем или не zip с деревьями и хешами. Другое дело, ты наверное разжимать хочешь маленькие кусочки и с середины, а LZ жмёт поток. Но словарь в LZW может быть статическим, в ПЗУ. И уже всё получается. Просто алгоритм сжатия должен 1) отдельно построить словарь, 2) сжать используя только его (а не отсылки к ранее сжатому тексту). Не обязательно такой алгоритм называть LZW и не обязательно строить сам словарь по методу LZW. Может быть эффективнее будет весь текст разбить на пары, триплеты и четверки (максимум) байт, отсортировать по частоте использования и кодировать потом каждую последовательность отдельным словом, код которого примерно прямо пропорционален частоте. При этом можно просматривать, при кодировании, несколько параллельных ветвей (в данном месте кодируется двойка или тройка, уже разветвление, и так далее) и выбирать на какой-то небольшой глубине просмотра наиболее оптимальную. Далее кодовые слова, 16-битные допустим (поэтому эффективность кодирования двоек нулевая, а единичных символов -- ниже нуля) кодируется либо алгоритмом Хаффмана со статической таблицей (следовательно декодер простейший и работает по таблице из ПЗУ), либо арифметическим кодером, либо современными range-кодерами (их сильно ускорили, тут то ли я, то ли Евгений писали, на сахаре), но тоже таблица частот фиксированная и модель 0-го порядка (только по частоте, без контекста, иначе память нужна). Либо даже кодами Голомба (Райса), от распределения зависит.
Есть еще вариант, когда LZ кодирует не по разжатому и ранее просмотренному тексту, а по сжатому (т.е. ссылки ведут в сжатый текст).
[ZX]