Об алгоритмах сжатия данных
Подготовил к участию в конкурсе Long Text Compression Benchmark вариант алгоритма сжатия данных на основе PPM.
По современному состоянию дел, этот алгоритм может конкурировать с распространёнными архиваторами типа WinRar и 7zip, но не может конкурировать с более современными алгоритмами из семейства PAQxxx, использующими Context Mixing ( Read more... )
Тэг бы хоть поправил бы )))
Я вообще то "сварщик" не очень настоящий в сжатии. Точнее, это вотчина математиков чистых больше, чем программистов. Я использую для сжатия чисто текста, 1) каскадные словари 2) и уже словари - жму дополнительно лослессом до упора, как и собственно сам текст. Общий смысл. Перевести все слова которые играют хоть какую либо статистическую роль (а для этого надо иметь набор текстов более 2-3 гиг, что немного, но в целом уже достаточно для работы), после чего основные "словесы" отправляются в словарь. Это само по себе обеспечивает неплохой коэфициент сжатия. С учетом того, что это даже не сжатие как таковое. Остальное - это именно работа с форматом файла. Который сам по себе достаточно своеобразный. Он требует очень многого, вплоть до "сервисных меток" в тексте. Ибо вариант номер два, распаковывать в память не только словари, но и текст, с переводом его в "обычный вид". Так как сам по себе формат, чем то напоминает непрерывный архив в раре. То есть нет возможности найти конкретное место (или в случае винрара ( ... )
Reply
Да, такое определение наиболее близко. Проблема в том, что я "выбираю" (уменьшаю) избыточность, поэтому, кмк, архиваторы то настолько менее эффективно и работают с моим "текстом". Так как избыточность текстовая уже выбрана конкретно мной. А им остается жать ну... Грубо говоря "белый шум". Что то сжать могут, но это не так эффективно как жать к примеру, "таблицу настройки телевизора".
К слову о "белом шуме", точнее аспекте который он поднимает одной своей частью. Я хотел использовать (точнее хочу, но это та еще ересь), использование псевдослучайных чисел и последовательностей для кодировки полученных текстов. Ну, понятно, что в теории книгу можно будет "сжать" до 4-8 байт (в идеале, сферическом :) ), что поставит вопрос о том, надо ли вообще архивировать )))) Но, конечно, так легко не будет, поэтому увы))) Да и сам алгоритм выходит не самым простым, если честно, а уж словарь для подстановок для словаря слов и вовсе выглядит вполне нормальным и четким издевательством над здравым смыслом и логикой. Но... Но все же им можно закодировать ( ... )
Reply
Reply
А... Ну в целом да. Действительно, ведь по сути я не интерпретирую, а компилирую текст. Причем, он сам по себе идет уже с моим форматом (не шибко с широкими возможностями но)...
И к слову о рандоме. Вот хорошая работа с сидерством - https://archive.scene.org/pub/parties/2009/breakpoint09/in4k/rgba_tbc_elevated_2016.zip
Скачай, распакуй и зацени. На размер тоже обрати внимание.
Reply
Если по ссылке идёт некая реализация этой идеи - это прикольно. Ща заценю.
Посмотрел. Прекрасное! Это особый вид искусства.
Reply
К слову, про "ненастоящих". Ты не назовёшь мне, те ВУЗ, которые прям сходу кроме эйлера, начинают грузить кватернионами, или структурой сжатия файлов? Что то такое не помню. Всё сами, всё сами. А в ответ - айтишнеги зажрались. Пидорасы.
Так то бери, курс Фихтенгольца, том три. Там основы 3д. 69 год. Привет (!!!!)
Reply
Reply
Угу. Лично я надыбал в своей библиотеке доставшейся от отца, в сборнике из 21 тома по вышке - угадай в каком томе? Веерно. Плюс в самом конце и скороговоркой.
А ты попробуй сейчас прогить не понимая (я не говорю даже про не зная) что такое кватернионы и какие у них плюсы, минусы и суровые ограничения. Особенно - ограничения. Они есть, и они крайне важны (например, для анимации). Интерполяция поворота на градус свыше 180 либо невозможна, либо приводит к закономерному "результат не определен".
Пригождается для... Ну вот к примеру...
Reply
Reply
Фигня. Как раз таки абстракция понимается в разы проще и лучше. Просто надо немножко перестать думать как привык. Это то еще извращение, но если смогешь - то вопросов не будет в принципе )
Reply
Reply
Эммм... Ну не надо уже так драматизировать то... Но в целом да. Малость надо поломать привычные "стези мышления" )))
Reply
Reply
А ты общался с кем-то из этих людей: Дмитрий Шкарин, Ратушняк, Ватолин, Евгений Шелвин?
Я лет 15 назад с ними в разной степени общался в Фидо, когда они экспериментировали с рекордсменом того времени PAQ, а я клепал свой PPM. Контакты с ними я потерял. Ватолин до сих пишет статьи по сжатию данных на Хабр. Шелвин, как выяснилось гуглением, живёт где-то в Харькове, и ему, я подозреваю, не до науки. А общались с ним больше всего...
Я бы сейчас позадавал вопросики про Context Mixing, да даже про RangeCoder... Не с кем стало общаться и обсуждать.
У тебя есть какой-то мессенджер, типа Вконтакте? В ЖЖ неудобно как-то.
Reply
Увы не. Не моё. Ну тут больше матана, чем прогерства. Хоть и геймдев что то туда же но не так.
По поводу остального - лови. Я докину Арушу, а то охуел )))
Как развитие алгоритмов сжатия остановилось 20 лет назад, или о новом конкурсе на 200 тысяч евро / Хабр
( ... )
Reply
Reply
Leave a comment