Упаковка текстов

[Shadow Maker]

Мож кто делал специализированную процедуру? Наиболее в тему мне кажется упаковка по словарю будет. Поделитесь плиз процедурами...

[Vitamin]

Делал как-то реализацию LZ78. Для более-менее оптимального варианта пришлось дорабатывать напильником. Сверху хаффман/арифметика хорошо ложится

[Barmaley_m]

Под компрессию текстов хорошо подходит (и широко используется) метод Лемпеля-Зива.

http://ru.wikipedia.org/wiki/LZ77

Данный алгоритм впервые реализован на Speccy Andrew Strikes Code в компрессоре LPC. Более поздние и более прогрессивные компрессоры тоже всегда использовали этот алгоритм.

[Shadow Maker]

Меня не интересуют описания, предложения, концепции и прочее. Если бы я хотел это написать САМ - я бы это сам и написал. Готовые процедуры есть для работы с упаковкой? Не хочу хрустом...

[Vitamin]

Не хочу хрустом...
RIP/RAR попробуй. И готовое и сравнить есть с чем.


Готовые процедуры есть для работы с упаковкой?
Из своего готового-опубликованного вспоминаю только арифметическое сжатие. Но это только на второй проход после словарного.

[Shadow Maker]

RIP/RAR попробуй. И готовое и сравнить есть с чем.
Слишком медленно.

[GriV]

Уважаемый не много ли хотите???
Либо вам быстро либо вам много.
Rip должен хорошо тексты жать.

[Barmaley_m]

Shadow Maker, что значит "специализированную процедуру"?
Под что конкретно специализированную?
Под тексты?
Так практически все универсальные методы сжатия дают лучшие результаты именно на текстах (благодаря использованию методов семейства LZ).

Что ты понимаешь под "упаковкой по словарю"?

[Shadow Maker]

Понимаю упаковку по наиболее употребимым текстовым последовательностям. Специализированную на упаковку и вывод текстов, то есть чтобы можно было без "распаковали на место, потом оттуда напечатали", а чтобы на лету символы выдавал. Поэтому собственно процедура должна быть шустрой и хрусты и тем паче рипы не подходят.

[axor]

Понимаю упаковку по наиболее употребимым текстовым последовательностям. Специализированную на упаковку и вывод текстов, то есть чтобы можно было без "распаковали на место, потом оттуда напечатали", а чтобы на лету символы выдавал. Поэтому собственно процедура должна быть шустрой и хрусты и тем паче рипы не подходят.
Найдешь/напишешь такой упаковщик, поделись плиз. Тоже актуально. В Вере, например, буфер под распаковку текстов "скушал" около 4 Кб памяти :(

[Shadow Maker]

В принципе в теории и хрустовый депакер можно под это переделать, но я к сожалению слаб в пакерах вааще...

[Vitamin]

Специализированную на упаковку и вывод текстов, то есть чтобы можно было без "распаковали на место, потом оттуда напечатали", а чтобы на лету символы выдавал.
Имхо, здесь вариантов не особо много:
1) хаффман: относительно сложно, плюс память на дерево нужна
2) арифметическое: еще сложнее и тоже надо памяти
3) токенизация (подозреваю, что это то, что требуется)
4) простейший LZ-based упаковщик с небольшим окном.

3 и 4 варианты могут хранить свой контекст на стеке, т.е. минимум лишней памяти. Но необходим препроцессинг и невысокий уровень сжатия будет.

[Shadow Maker]

А у хруста какой метод распаковки? Он пользуется уже распакованными данными?

Добавлено через 1 минуту

3 и 4 варианты могут хранить свой контекст на стеке, т.е. минимум лишней памяти. Но необходим препроцессинг и невысокий уровень сжатия будет.
М? Зачем для токенизации препроцессинг?

[Vitamin]

А у хруста какой метод распаковки? Он пользуется уже распакованными данными?
LZ77-based. Ссылки назад- классический вариант.


М? Зачем для токенизации препроцессинг?
Ну можно конечно вручную токены выделить, да машина с этим всяко лучше справится:)

[Shadow Maker]

А, ты вон о чем. Ясно... Токенизатор чтоли правда написать...

[Vitamin]

Токенизатор чтоли правда написать...
С небольшими доработками ты получишь почти LZ78 (LZW) упаковщик :D

[Barmaley_m]

Кстати говоря, если необходимо распаковывать данные по мере их поступления, то следует обратить внимание на реализации упаковки в модемах... Всякие там V42-bis и тому подобное. Думаю, что на эту тему можно даже сорцы найти (на C).

Добавлено через 1 минуту
А вообще, Shadow Maker, моя тебе рекомендация - не изобретать велосипед, а реализовать, как тебе тут рекомендуют, один из классических методов: LZ77, например. Тот же ASC LZSSPAC имел окно в 4 килобайта, а как круто жал игры для своего времени!

Добавлено через 3 минуты
Еще один довод в пользу чистого LZ77: раскомпрессор быстрый и короткий получается (см. декомпрессор ASC LZSSPAC). Раскомпрессия же кодов Хаффмана требует битовых сдвигов и потому тормозит.

[Shadow Maker]

Опять не в тему. LZ77 = ссылки назад на распакованное. Как я уже сказал - мне надо распаковывать на лету! Без ссылок на распакованное!

Вообще, просил конкретные тексты - а мне тут лечат какую-то ботву... Закрыто в общем.

[GriV]

Самый простой и эффективный тогда - модифицированный RLE
Первый бит =0 - была компрессия, следом идёт указание количества байт и сам байт. Первый бит=1 значит байт не упакован. Ну и сам байт следом.
Очень потоковый, нет никакой более информации ДО.
Или вообще брать чистый RLE. Во всех остальных случаях опять уйдёшь к LZ* методам.
Или бери готовое дерево частот и чистый Хаффман. Как то не представляю что ещё тут можно придумать. Все мне известные пакеры кроме RIP используют LZ* методики