>Алгоритм Лемпеля-зива не «ищет повторные данные в потоке»,А английская вика например пишет именно так. Хоть я и взял из головы, но перепроверился по вике. Цитирую http://en.wikipedia.org/wiki/LZ77_and_LZ78
LZ77 algorithms achieve compression by replacing portions of the data with references to matching data that have already passed through both encoder and decoder. A match is encoded by a pair of numbers called a length-distance pair.
В общем то это было грубое описание смысла деятельности таких схем. Общий смысл такой схемы - найти совпадения в потоке данных и закодировать длинные совпадения более короткими ссылками на совпадения. Ежу понятно что есть over 9000 способов это сделать, но это уже детали. Чем более длинное совпадение нашлось - тем лучше сжатие. Разные степени сжатия делаются достаточно просто - компрессор на малых степенях сжатия не ищет лучшее из возможных совпадение а кодирует "уже достаточное", забив в некоторый момент на попытки улучшить длину совпадения для экономии времени. Сколько именно считается за "уже достаточно" и есть параметр степени сжатия (всякие -1 и -9 крутят у LZ-based вот этот вот параметр как правило). Ну и ессно чем больше словарь - тем больше шансов наловить совпадений текущих данных с предыдущими.
>по крайней мере, в базовой реализации.
А базовый - это у вас который? LZ77? LZ78? LZSS? Что-то не припоминаю так сходу кто именно из LZ* на биты входной поток раскладывает. И что за код? Позиция в словаре?
>Это сильно упрощённо, конечно. :)
Спасибо за рассказы про LZ-based, ага. Правда вот насчет битового потока - интересно что за LZ это был? Который именно при чтении битами оперирует.То что есть стратегии записи выходного потока как bit stream без выравнивания на байты (так компактнее) и с выравнианием на оные (как првило для скорости, - LZO и подобные).
Но все (?) LZ-образные компрессоры которые я видел, читали со входа именно байты и совпадения искались побайтово. Да и логично в общем то - для удобства обычно real-world данные выровнены на байты, на оперирование битовыми потоками идут только в крайних случаях (для максимальной компактности и ессно в ущерб скорости обработки потока).
>LZ* - используются разные настройки словаря,
А также можно крутить как параметр сжатия то что считается за достаточную длину совпадения после которой компрессор кладет на попытки удлинить совпадение.
>плюс возможно использование уже готового словаря ("мультимедийное сжатие RAR").
Для звука насколько я знаю есть еще техники типа кодирования не абсолютных значений (которые всегда разные) а разницы с предыдущим отсчетом (дельты относительно небольшие и могут повторяться, после такого препроцессинга можно отдать сие даже обычному LZ и он уже не стушуется на таком потоке а из него можно перестроить без потерь и оригинал). Правда это только одна из техник. Бывает и еще два вагона. Как правило поток преобразуется или расщепляется на несколько потоков дабы получить более-менее совпадающие данные которые можно сжать.
>А так, простенький LZ-архиватор пишется на голом Си за два часа:
Да я в курсе - писал несколько декомпрессоров LZ-подобных алгоритмов.На сях и асме.Правда предпочитал подвиды которые не требуют для декомпрессии словарь. Кто же так не развлекается?Разве что те кто для этого слишком тупы, типа жабистов :)
>час курения алгоритма, полчаса кодинг, полчаса дебаг. :)
С 1 поправочкой. Качественные полные тесты что связка компрессор+декомпрессор никогда не лажается могут занимать намного больше времени чем полчаса. Более того - немало движков обнаруживали проблемы в редких ситуациях аж через годы.
