Об алгоритмах сжатия данных
Подготовил к участию в конкурсе Long Text Compression Benchmark вариант алгоритма сжатия данных на основе PPM.
По современному состоянию дел, этот алгоритм может конкурировать с распространёнными архиваторами типа WinRar и 7zip, но не может конкурировать с более современными алгоритмами из семейства PAQxxx, использующими Context Mixing ( Read more... )
Тэг бы хоть поправил бы )))
Я вообще то "сварщик" не очень настоящий в сжатии. Точнее, это вотчина математиков чистых больше, чем программистов. Я использую для сжатия чисто текста, 1) каскадные словари 2) и уже словари - жму дополнительно лослессом до упора, как и собственно сам текст. Общий смысл. Перевести все слова которые играют хоть какую либо статистическую роль (а для этого надо иметь набор текстов более 2-3 гиг, что немного, но в целом уже достаточно для работы), после чего основные "словесы" отправляются в словарь. Это само по себе обеспечивает неплохой коэфициент сжатия. С учетом того, что это даже не сжатие как таковое. Остальное - это именно работа с форматом файла. Который сам по себе достаточно своеобразный. Он требует очень многого, вплоть до "сервисных меток" в тексте. Ибо вариант номер два, распаковывать в память не только словари, но и текст, с переводом его в "обычный вид". Так как сам по себе формат, чем то напоминает непрерывный архив в раре. То есть нет возможности найти конкретное место (или в случае винрара - файл) в любом режиме отличного от последовательного. На данный момент используется система 1(2-2-4 бита)+3. То есть после считывания байта он разбирается и исходя из первого и последующих бит - интерпретируется так, или иначе, это сужает диапазон, но при этом обеспечивает более вменяемое для чтения пространство. Упрощенно, если он входит в диапазон менее 128 - он считается управляющим, и там находятся спецкоманды. Отвечают за форматирование, сервисные метки, переключение между словарями (если текст содержит несколько языков, например), а так же набор тэгов. Так как сам формат близок по своему внутреннему виду на фб2, то это на ровном месте только этим позволяет сильно ужать общий размер файлов. Вторая часть используется для пунктуации и одиночных символов которые занимают наиболее частое повторение. о, и, я, в, на, и так далее. К слову, в управляющих кодах есть режим форматирования, то есть там указывается каким будет вид следующего слова. Например, вот или Вот, или ВОТ, и прочее. Это просто для уменьшения размена основного словаря, так как в целом хватает места для маневра. Вторая часть из 3 байт - используется как жесткий индекс слова (если словари и текст различаются версиями, это приводит к неприятным последствиям, это одно из ограничений, которое решаемо встроенным словарём в книгу, но это чисто вспомогательный вариант, если большой обьем текста с уникальными словами. Типа герой Залупоголовкрючкотворный). Ну, это если быстро и вкратце пробежаться. Там хватает достаточно интересных вариантов и помимо этого. И полученное уже жмётся другими лослессами (не скажу что бы очень эффективно, но свои 10-15% таки выгрызают, это к слову винрар, более мощные и современные дают результаты получше, но у них частая проблема в том, что они "не прилизаны" для работы.
Как то так.
ЗЫ. Чуть не забыл. Почему каскадный. Потому как слова образуют часто устойчивые словесные "штампы", которые проходятся приблизительно по такому же правилу, как и просто слова. Грубо говоря даже если взять эту фразу, мы получаем "грубо говоря", "даже если", и "даже если взять" (на самом деле - больше). Для кодирования одного слова вне зависимости от его длинны уходит от 1 до 4 байт. То есть "сжатие" "даже если" - не дает никакого сжатия. А вот уже после использования второго слоя - это даёт двухкратное сжатие. Ессно, для работы программы "на лету" надо довольно приличные процессорные и главное, по памяти объёмы. К слову, я пока думаю, не использовать ли "быстрый" словарь на 2 байта, вместо 3. Это конечно очень небольшой словарь, на 65 тыс слов, но его достаточно для приличной экономии памяти. Но так как это крайне лютое дело, пока эту багоносную фичу не использую.
Reply
Я с этим тэгом провозился час. Редактор ЖЖ превратился в сраное говно, в новой версии просто невозможно писать html-тэги, нет такой возможности больше. Как ты с этим борешься?
Reply
Открываешь "НАПИСАТЬ" - и там в пулл дауне лежит "использовать старый редактор". Кликаешь, и радуешься что это говно не надо пользовать. Но вскоре боюсь посты придется писать чисто в семаджике, потому как старые варианты ёбанная жижа отрубает через годик.
Reply
Это же какой-то позор, делали бы что-то хорошее, но нет - они превращают ЖЖ в какой-то твиттер.
Reply
Reply
В новом редакторе не работают HTML-теги, а не хэштеги записи.
Reply
Reply
А что будет, когда индусы наворотят ещё "улучшений"...
Reply
Владя, бро, напиши ПОДЧЕРКНУТЫЙ текст, без "кнопочеГ". Ага )))
Reply
Reply
Reply
Мы все сварщики :)
Твоё описание словарного кодирования похоже на то, как работает LZMA в 7zip. Там куча частных случаев описания смещений с помощью комбинации битов, как и у тебя. Отличие в том, что в LZMA нет словаря в чистом виде, а ссылки даются на просмотренную часть входного буфера.
Я с удивлением обнаружил, что LZMA это комбинация PPM и LZ, ссылки на подстроки даются в контексте первого символа, который записывается в модели PPM первого порядка. За счёт этого степень сжатия увеличивается по сравнению с чистым LZ, а скорость остаётся как у чистого LZ. Интересный с практической точки зрения вариант, но это не мой путь.
А с PPM и Context Mixing ты не экспериментировал?
Reply
Словарь это очень и очень "тяжелая" штука.
Винрар к слову, идет к уровню что на 1024 мегабайт кода, надо 6144 мегабайт для создания словаря. У меня же, есть пару других режимов. В одном, хватит и 4 мегабайт, во втором, для 40 мегабайтного чистого текста, тебе понадобится 19 гигабайт. Но последний, работает просто как огонь. Разрешение буквы, равно индексу поиска. Поэтому поиск "есть или нет это слово в словаре" отсутсвует, как таковой. Ценой просто феерической нагрузки на ОЗУ. Карта слов выходит трёхмерная. Ну ты понял что это означает.
Не работает вменяемо. Просто не работает. Искажения от первичного сжатия. А вот уровнем выше - это уже я нуб, это... Математика умеет много гитик©АБСтугацкие, Град Обречённый.
В общем, вилка, либо я матан не тяну, либо матан не тянет прогерство. )))
Reply
Во вторичном компрессоре есть нюансы с вероятностями символов / слов, которые, если их не учесть, сильно ухудшают степень сжатия. С виду это мелочи, но влияние катастрофическое.
Возможно, я могу указать место косяка, если ты подробнее опишешь архитектуру.
Reply
Проще будет слить сырцы, когда я их таки всё же перенесу целиком и полностью на 19-23 студию. При этом убив откровенно тухлые ответвления (кои в силу забагованности или неэффективности там висят еще).
Ты немного не так смотришь. На самом деле, повторюсь, никакого сжатия по факту нету. Я просто меняю представление. Ну грубо говоря, вместо того что бы писать фразу "вместо того что бы писать фразу" пишу "132486" при первом проходе (где каждое число - это просто ссылка на индекс в словаре), а после ищу схожие паттерны во вторичном контуре (132486), и если таковой есть, тупо даю ссылку на ЭТОТ индекс. Например, 115. В итоге вместо "вместо того что бы писать фразу" я пишу "115". Распаковка - работает наоборот беру 115 из него из вторичного контура получаю 132486, а это уже с помощью словаря превращаю в фразу "вместо того что бы писать фразу". Никаких алгоритмов сжатия, на этот момент не используется вовсе (ну если не считать варианта РЛЕ очень сильно извращенного и в широком смысле). Так то да, уменьшение размера имеется, но это не вызвано сжатием в классическом понимании. Что, к слову, даёт возможность уже поработать именно архиваторам, так как они будут своего мнения по поводу как и что можно "дожать" в таком вот наборе индексов. Достигая еще большего сжатия, точнее, меньшего размера через сжатие.
Reply
То есть, это не алгоритм сжатия целиком, а один из его этапов, как ты и сказал.
Reply
Leave a comment