Мож кто делал специализированную процедуру? Наиболее в тему мне кажется упаковка по словарю будет. Поделитесь плиз процедурами...
Вид для печати
Мож кто делал специализированную процедуру? Наиболее в тему мне кажется упаковка по словарю будет. Поделитесь плиз процедурами...
Делал как-то реализацию LZ78. Для более-менее оптимального варианта пришлось дорабатывать напильником. Сверху хаффман/арифметика хорошо ложится
Под компрессию текстов хорошо подходит (и широко используется) метод Лемпеля-Зива.
http://ru.wikipedia.org/wiki/LZ77
Данный алгоритм впервые реализован на Speccy Andrew Strikes Code в компрессоре LPC. Более поздние и более прогрессивные компрессоры тоже всегда использовали этот алгоритм.
Меня не интересуют описания, предложения, концепции и прочее. Если бы я хотел это написать САМ - я бы это сам и написал. Готовые процедуры есть для работы с упаковкой? Не хочу хрустом...
Уважаемый не много ли хотите???
Либо вам быстро либо вам много.
Rip должен хорошо тексты жать.
Shadow Maker, что значит "специализированную процедуру"?
Под что конкретно специализированную?
Под тексты?
Так практически все универсальные методы сжатия дают лучшие результаты именно на текстах (благодаря использованию методов семейства LZ).
Что ты понимаешь под "упаковкой по словарю"?
Понимаю упаковку по наиболее употребимым текстовым последовательностям. Специализированную на упаковку и вывод текстов, то есть чтобы можно было без "распаковали на место, потом оттуда напечатали", а чтобы на лету символы выдавал. Поэтому собственно процедура должна быть шустрой и хрусты и тем паче рипы не подходят.
В принципе в теории и хрустовый депакер можно под это переделать, но я к сожалению слаб в пакерах вааще...
Имхо, здесь вариантов не особо много:
1) хаффман: относительно сложно, плюс память на дерево нужна
2) арифметическое: еще сложнее и тоже надо памяти
3) токенизация (подозреваю, что это то, что требуется)
4) простейший LZ-based упаковщик с небольшим окном.
3 и 4 варианты могут хранить свой контекст на стеке, т.е. минимум лишней памяти. Но необходим препроцессинг и невысокий уровень сжатия будет.
А, ты вон о чем. Ясно... Токенизатор чтоли правда написать...
Кстати говоря, если необходимо распаковывать данные по мере их поступления, то следует обратить внимание на реализации упаковки в модемах... Всякие там V42-bis и тому подобное. Думаю, что на эту тему можно даже сорцы найти (на C).
Добавлено через 1 минуту
А вообще, Shadow Maker, моя тебе рекомендация - не изобретать велосипед, а реализовать, как тебе тут рекомендуют, один из классических методов: LZ77, например. Тот же ASC LZSSPAC имел окно в 4 килобайта, а как круто жал игры для своего времени!
Добавлено через 3 минуты
Еще один довод в пользу чистого LZ77: раскомпрессор быстрый и короткий получается (см. декомпрессор ASC LZSSPAC). Раскомпрессия же кодов Хаффмана требует битовых сдвигов и потому тормозит.
Опять не в тему. LZ77 = ссылки назад на распакованное. Как я уже сказал - мне надо распаковывать на лету! Без ссылок на распакованное!
Вообще, просил конкретные тексты - а мне тут лечат какую-то ботву... Закрыто в общем.
Самый простой и эффективный тогда - модифицированный RLE
Первый бит =0 - была компрессия, следом идёт указание количества байт и сам байт. Первый бит=1 значит байт не упакован. Ну и сам байт следом.
Очень потоковый, нет никакой более информации ДО.
Или вообще брать чистый RLE. Во всех остальных случаях опять уйдёшь к LZ* методам.
Или бери готовое дерево частот и чистый Хаффман. Как то не представляю что ещё тут можно придумать. Все мне известные пакеры кроме RIP используют LZ* методики