Комментарии 45
А ничего, что к каждому архиву нужно будет цеплять огроменный словарь, где слова закодированы буковками?
Словарь тоже закодирован.
Другим словарем?
Алфавитом, смотри пример, цветом разметил.
— Красный — алфавит, единственный раздел, где буковки представлены в явном виде.
— Зелёный — закодированный алфавитом словарь. Здесь вместо индексов будет бит-код.
— Синий — раздел с данными заглавных, тут всё понятно вроде.
— Жёлтый — сам текст, закодированный словарём. Вместо индексов опять бит-код.
— Красный — алфавит, единственный раздел, где буковки представлены в явном виде.
— Зелёный — закодированный алфавитом словарь. Здесь вместо индексов будет бит-код.
— Синий — раздел с данными заглавных, тут всё понятно вроде.
— Жёлтый — сам текст, закодированный словарём. Вместо индексов опять бит-код.
Ряд особенностей которые тут не учтены, а нужно.
1. Если ты считаешь это сразу архиватором, то он будем минимум двух проходным т.е. ты сначала «нормализуешь» текст и «смотришь» частотность, а после уже делаешь подмены.
Хотя правильно это называть препроцессор, и после скармливать серьёзным архиваторам типа 7zip. Причем, возможно, лучший результат будет не от родного метода zlma, а от ppmd. Но разница не очень значительна.
2. Наплодил лишние сущности разбиением, тем самым сильно увеличив словарь. Не вижу никакой причины делать 3 места в словаре под «Не», «По» и «Седа» при том, что оно встретится несколько раз, и это ничем не лучше чем сразу одним местом в хвосте словаря для «НеПоСеда».
3. Именно «война и мир» имеет множество французкого в прямой речи (т.е. алфавит больше англ).
А в общем рвение, мягко говоря, удивило, но: правильной дорогой идете, товарищ!
Правда стоит подумать, как не таскать персональный словарь для каждой книги, и наступит персональное счастье. Но даже без этого, можно получить от 2(в худшем) до 10(в лучшем) крат уменьшение, при возможности дополнительного сжатия.
Сейчас проверил:
Война и мир, всего слов 226124, уникальных 31277, средняя длина 5.124 (подразумевается словоформы и иностранные тоже)
Мастер и Маргарита, всего слов 112619, уникальных 23828, средняя длина 5.320
1. Если ты считаешь это сразу архиватором, то он будем минимум двух проходным т.е. ты сначала «нормализуешь» текст и «смотришь» частотность, а после уже делаешь подмены.
Хотя правильно это называть препроцессор, и после скармливать серьёзным архиваторам типа 7zip. Причем, возможно, лучший результат будет не от родного метода zlma, а от ppmd. Но разница не очень значительна.
2. Наплодил лишние сущности разбиением, тем самым сильно увеличив словарь. Не вижу никакой причины делать 3 места в словаре под «Не», «По» и «Седа» при том, что оно встретится несколько раз, и это ничем не лучше чем сразу одним местом в хвосте словаря для «НеПоСеда».
3. Именно «война и мир» имеет множество французкого в прямой речи (т.е. алфавит больше англ).
А в общем рвение, мягко говоря, удивило, но: правильной дорогой идете, товарищ!
Правда стоит подумать, как не таскать персональный словарь для каждой книги, и наступит персональное счастье. Но даже без этого, можно получить от 2(в худшем) до 10(в лучшем) крат уменьшение, при возможности дополнительного сжатия.
Сейчас проверил:
Война и мир, всего слов 226124, уникальных 31277, средняя длина 5.124 (подразумевается словоформы и иностранные тоже)
Мастер и Маргарита, всего слов 112619, уникальных 23828, средняя длина 5.320
>Наплодил лишние сущности разбиением
В вашем способе сильно увеличится блок заглавных. Нужно будет хранить данные о их размещении в словах.
В вашем способе сильно увеличится блок заглавных. Нужно будет хранить данные о их размещении в словах.
Я бы ввёл три спецсимвола: «следующая буква — заглавная», «следующие две буквы — заглавные», «все следующие буквы до конца слова — заглавные».
Это для словаря или для текста? В словаре сейчас вообще нет прописных букв.
Для словаря. Странно написанные слова либо встречаются в одном экземпляре, либо пишутся всегда одинаково МГц, кВт, КВРБ — их стоит хранить как есть.
В тексте нужен признак того, что слово начинается с одной заглавной буквы, и какая-то разметка, для обозначения строк полностью состоящих из заглавных букв.
В тексте нужен признак того, что слово начинается с одной заглавной буквы, и какая-то разметка, для обозначения строк полностью состоящих из заглавных букв.
> В вашем способе сильно увеличится блок заглавных.
Именно в моём способе(одном из них) заглавных нет вообще, они кодируются иначе. Причина довольно проста — их очень мало.
Например в Мастер и Маргарита всего 597881 символа из них только 14527 заглавные (допускаю небольшие отклонения в зависимости от издания).
Но в посте описаны одновременно 2 способа, и символьный с оптимизацией бит и сразу словоформами, но как именно они должны взаимодействовать не очень понятно.
Возможно из-за этого получилась путаница и проблема с реализацией?
Именно в моём способе(одном из них) заглавных нет вообще, они кодируются иначе. Причина довольно проста — их очень мало.
Например в Мастер и Маргарита всего 597881 символа из них только 14527 заглавные (допускаю небольшие отклонения в зависимости от издания).
Но в посте описаны одновременно 2 способа, и символьный с оптимизацией бит и сразу словоформами, но как именно они должны взаимодействовать не очень понятно.
Возможно из-за этого получилась путаница и проблема с реализацией?
>от 2 до 10 крат уменьшение
это на вскидку или расчёты?
это на вскидку или расчёты?
> это на вскидку или расчёты?
Это статистика. Как можно заметить, у меня её довольно много, потому как важно понимать, что именно ты получаешь.
При этом «и» и «в», в большинстве проверенного мною, всегда лидируют, и если неправильно кодировать, даже двумясимволамибайтами получится увеличение.
Это статистика. Как можно заметить, у меня её довольно много, потому как важно понимать, что именно ты получаешь.
Например топ25 слов по частоте в МиМ
5014 и
3642 в
2026 не
2003 на
1750 что
1290 с
1151 он
969 а
864 я
840 как
710 но
699 к
688 его
644 это
594 же
528 из
528 у
475 по
468 за
467 было
441 все
421 маргарита
411 так
408 вы
395 она
3642 в
2026 не
2003 на
1750 что
1290 с
1151 он
969 а
864 я
840 как
710 но
699 к
688 его
644 это
594 же
528 из
528 у
475 по
468 за
467 было
441 все
421 маргарита
411 так
408 вы
395 она
При этом «и» и «в», в большинстве проверенного мною, всегда лидируют, и если неправильно кодировать, даже двумя
Потому и оставил до лучших времён, когда будет время изучить префиксное кодирование. А насчёт
>Не таскать с собой персональный словарь
думаю об онлайн-архиваторе. Пусть огромные словари с общими словами хранятся на удалённом сервере. Что на этот счёт говорит статистика?
>Не таскать с собой персональный словарь
думаю об онлайн-архиваторе. Пусть огромные словари с общими словами хранятся на удалённом сервере. Что на этот счёт говорит статистика?
> думаю об онлайн-архиваторе.
Мысль об онлайн архивации меня не посещала. Наверно, потому, что подразумевается самодостаточный оффлайн архиватор.
Но мысль может быть интересна, при определенных условиях. Надо обдумать.
А в целом статистика говорит, что словарь не такой большой как кажется. Если правильно организован и тоже сжат. ВинЗип22 например вести 200Мб.
Кстати еще статистика говорит, о том, что словарь очень сильно раздувают ошибки, опечатки, неверные переносы. В если провестиработу над ошибкамикоррекцию словарь может стать меньше на 5-20%.
Мысль об онлайн архивации меня не посещала. Наверно, потому, что подразумевается самодостаточный оффлайн архиватор.
Но мысль может быть интересна, при определенных условиях. Надо обдумать.
А в целом статистика говорит, что словарь не такой большой как кажется. Если правильно организован и тоже сжат. ВинЗип22 например вести 200Мб.
Кстати еще статистика говорит, о том, что словарь очень сильно раздувают ошибки, опечатки, неверные переносы. В если провести
А можно ли идею архивирования использовать для поиска ошибок?
То есть если небольшой участок текста сжимается хуже чем другие, то в нем скорее всего есть ошибка.
Единичные ошибки почти не влияют на размер. Скорее для поиска вставок на другом языке подойдёт.
А можно ли идею архивирования использовать для поиска ошибок?
То есть если небольшой участок текста сжимается...
Можно проще — смотреть «хвост» частотной сортировки. Ну или автоматизировать — сравниванием по словарю. Т.е. не доходя со сжатия.
Но само сжатие как признак не подходит, они и так варьируется от автора к автору.
Здравый смысл на этот счет говорит, что можно просто хранить на удаленном сервере весь документ и передавать ссылку. Сжатие будет охренительное: что угодно — в 128 бит.
«В песочнице только месяц назад наконец утонул мой дебют про программирование на кириллице.»
А ссылку на статью можно?
А ссылку на статью можно?
А надо ли? Там нет программирования по сути.
Тут во многих статьях нет кода)
А про статью любопытно посмотреть.
А про статью любопытно посмотреть.
Если это можно назвать статьёй )
habrahabr.ru/post/349562
habrahabr.ru/post/349562
Автор, отсыпь.
Такие штуки могут подходить для кодирования списков, таблиц, справочников. Мне кажется, что телефонный справочник с именами и фамилиями (но не с названиями организаций), можно будет закодировать лучше более привычных алгоритмов. Правда такая гипотеза требует проверки.
Чем данный подход лучше использования других словарных методов сжатия?
К сожалению, не взлетит. Вот именно эта «светлая» идея регулярно приходит в голову разным людям чуть ли не ежегодно. Сначала автор понимает, что выгоднее сжимать слова вместо символов, потом прикидывает, что к каждому отдельному файлу лучше прикладывать отдельный словарь (а иначе сжатие окажется заведомо неоптимальным, расходы на хранение словаря компенсируются перечислением в нём лишь реально обнаруженных слов)…
Затем становится ясно, что помещать в словарь элементы, которые в исходном тексте разделены пробелами, нелогично: чем пробел так замечателен? А если в тексте часто встречается сочетание «ский ди», почему бы не вставить его? Так мы приходим к алгоритму автоматического создания словаря. И в конечном итоге получаем обычный LZW.
Затем становится ясно, что помещать в словарь элементы, которые в исходном тексте разделены пробелами, нелогично: чем пробел так замечателен? А если в тексте часто встречается сочетание «ский ди», почему бы не вставить его? Так мы приходим к алгоритму автоматического создания словаря. И в конечном итоге получаем обычный LZW.
Был ещё такой архиватор HA, заточенный как раз под тексты.
Был ещё такой архиватор HA, заточенный как раз под тексты.
Интересно не знал про такой.
Для 95го он был очень хорош, но сейчас не актуален. Запускается с бубном, пришлось запускать на 32 битной машине.
Распространеные 7z(ppmd) и zipx сжимают сильнее.
Я как‐то не натыкался на zipx и HA, но когда‐то смотрел, чем можно сжимать логи сборки. Получил, что paq8p сжимает лучше всего (но очень долго и вообще приложение напоминает PoC), более адекватный zpaq немного отстаёт, но прямо следом за PAQ идёт 7z+ppmd:
14M дек 24 2008 app-office:openoffice-3.0.0:20081221-185207.log
1,1M дек 24 2008 app-office:openoffice-3.0.0:20081221-185207.log.F
010K дек 24 2008 app-office:openoffice-3.0.0:20081221-185207.log.lzop
001K дек 24 2008 app-office:openoffice-3.0.0:20081221-185207.log.lha
839K дек 24 2008 app-office:openoffice-3.0.0:20081221-185207.log.jar
837K дек 24 2008 app-office:openoffice-3.0.0:20081221-185207.log.zip
807K дек 24 2008 app-office:openoffice-3.0.0:20081221-185207.log.gz
777K мар 13 2014 app-office:openoffice-3.0.0:20081221-185207.log.zpaq
616K фев 10 2009 app-office:openoffice-3.0.0:20081221-185207.log.rar
615K дек 29 2008 app-office:openoffice-3.0.0:20081221-185207.log.lrz
584K дек 24 2008 app-office:openoffice-3.0.0:20081221-185207.log.pbz2
576K дек 24 2008 app-office:openoffice-3.0.0:20081221-185207.log.bz2
565K дек 24 2008 app-office:openoffice-3.0.0:20081221-185207.log.xz
564K июн 14 2010 app-office:openoffice-3.0.0:20081221-185207.log.xz9
564K июл 27 2014 app-office:openoffice-3.0.0:20081221-185207.log.xz9.2
515K дек 24 2008 app-office:openoffice-3.0.0:20081221-185207.log.lzma
430K дек 24 2008 app-office:openoffice-3.0.0:20081221-185207.log.7pmd
430K июл 27 2014 app-office:openoffice-3.0.0:20081221-185207.log.7pmd.2
389K фев 24 2015 app-office:openoffice-3.0.0:20081221-185207.log.8a.zpaq
286K мар 13 2014 app-office:openoffice-3.0.0:20081221-185207.log.6.zpaq
286K фев 24 2015 app-office:openoffice-3.0.0:20081221-185207.log.8.zpaq
210K фев 24 2015 app-office:openoffice-3.0.0:20081221-185207.log.paq8pУ меня даже времена сохранились:
xz -k app-office:openoffice-3.0.0:20081221-185207.log 4,99s user 0,13s system 97% cpu 5,256 total
bzip2 -9 app-office:openoffice-3.0.0:20081221-185207.log -k 2> bzip2 11,04s user 0,04s system 99% cpu 11,099 total
gzip -9 > app-office:openoffice-3.0.0:20081221-185207.log.gz 0,72s user 0,01s system 98% cpu 0,746 total
lzma -9 > app-office:openoffice-3.0.0:20081221-185207.log.lzma 31,02s user 0,28s system 99% cpu 31,461 total
7z -m0=ppmd -mx=9 -ms a app-office:openoffice-3.0.0:20081221-185207.log.7pmd 2,80s user 0,32s system 99% cpu 3,129 total
lzop -9 > app-office:openoffice-3.0.0:20081221-185207.log.lzop 2,05s user 0,02s system 98% cpu 2,095 total
zip app-office:openoffice-3.0.0:20081221-185207.log.zip 0,40s user 0,02s system 100% cpu 0,410 total
lha a app-office:openoffice-3.0.0:20081221-185207.log.lha 0,81s user 0,03s system 99% cpu 0,842 total
pbzip2 -9kc app-office:openoffice-3.0.0:20081221-185207.log > 19,68s user 0,29s system 177% cpu 11,281 total
freeze -c app-office:openoffice-3.0.0:20081221-185207.log > 0,70s user 0,01s system 99% cpu 0,713 total
fastjar -cf app-office:openoffice-3.0.0:20081221-185207.log.jar 0,50s user 0,03s system 99% cpu 0,529 total
lrzip -M app-office:openoffice-3.0.0:20081221-185207.log 5,60s user 0,33s system 167% cpu 3,538 total
rar a app-office:openoffice-3.0.0:20081221-185207.log.rar 4,54s user 0,13s system 98% cpu 4,759 total
----
zpaq a app-office:openoffice-3.0.0:20081221-185207.log{.zpaq,} 0,60s user 0,08s system 87% cpu 0,782 total
zpaq -method 6 a app-office:openoffice-3.0.0:20081221-185207.log{.6.zpaq,} 64,16s user 0,38s system 99% cpu 1:04,97 total
----
7z -m0=ppmd -mx=9 -ms a 0,91s user 0,08s system 99% cpu 1,000 total
xz -9 < app-office:openoffice-3.0.0:20081221-185207.log > 3,89s user 0,10s system 100% cpu 3,990 total
----
zpaq -method 8 a app-office:openoffice-3.0.0:20081221-185207.log{.8.zpaq,} 64,52s user 0,30s system 100% cpu 1:04,77 total
zpaq -method 8a a app-office:openoffice-3.0.0:20081221-185207.log{.8a.zpaq,} 70,29s user 1,22s system 371% cpu 19,275 total
~/bin/paq8p -8 app-office:openoffice-3.0.0:20081221-185207.log 916,69s user 1,86s system 100% cpu 15:17,34 total(времена, разделённые ----, сравнивать не имеет смысла: разные конфигурации или машины).
более адекватный zpaq немного отстаётСамособой, zpaq многопоточный. И это попытка стандартизировать разнообразие паков, собрав все лучшие наработки. Закономерно и правильно, иначе какой смысле второй десяток лет возиться с архиватором которым пользуются только разработчики ;)
Вторая строка, расширение F — что за зверь?
PS:
А вообще надо бы оформить в единое целое, у меня где-то тоже были результаты архиваций разными, вот только время исполнения точно утеряно.
Вот именно эта «светлая» идея регулярно приходит в голову разным людям чуть ли не ежегодно.
Но после всё убивает давно заложенное:
К сожалению, не взлетит
И причин тому находится множество от «всё придумано до нас» до «на введение нового стандарта надо слишком много денег».
Вот только если б это было правдой после zip, не появился бы rar, а после него 7z.
PS:
LZW использует иной подход чем описан в этой и, частично, предыдущей статье. А потому если развивать это направление скорее можно прийти к paq8pxd18 или paq8hp12, чем к LZW.
Да я не лётчик, какие новые стандарты? Рынок IT вообще какая то оч рандомная вещь, кто взлетит — дело случая. До стандарта HTML каждая контора юзала свою разметку, тысячи их. Просто интересно, есть идеи, я и делаю.
Ну я же не на общие темы рассуждаю (типа «новое побеждает старое»), а про конкретный предложенный алгоритм, который уже неоднократно всплывал на моей памяти, и представляет собой по сути ручное создание словаря Далем/Ожеговым вместо автоматической процедуры — более оптимальной и надёжной.
Вот как раз на счёт оптимальности — сомнения.
Возможно не достаточно понятно выразился.
Сама по себе цепочка LZ LZW (LZSS) LZMA(2) не развивалась бы, если б всё было хорошо. В частности можно посмотреть-почитать ветку обсуждения об изменениях в 7z, в частности использование препроцессоров под определенные типы файлов.
PS:
В этой теме делаются попытки предложить и даже реализовать, что-то новое (на уровне «школьник»). Причем идеи развиваются, достаточно быстро, и возможно в следующей статье он уже предложит, то до чего еще не додумались.
Возможно не достаточно понятно выразился.
Сама по себе цепочка LZ LZW (LZSS) LZMA(2) не развивалась бы, если б всё было хорошо. В частности можно посмотреть-почитать ветку обсуждения об изменениях в 7z, в частности использование препроцессоров под определенные типы файлов.
PS:
В этой теме делаются попытки предложить и даже реализовать, что-то новое (на уровне «школьник»). Причем идеи развиваются, достаточно быстро, и возможно в следующей статье он уже предложит, то до чего еще не додумались.
Идея препроцессора под конкретные типы файлов совершенно здравая, и опция «мультимедийное сжатие» в WinRAR тоже не вчера появилась.
Я не хочу быть критиком, который видит во всём ненужное старьё, но всё же в текущей конкретной статье нам предлагают откровенный шаг назад: вместо автоматического анализа частотности цепочек просто взять словарь, в котором цепочки разбиты просто по критерию «нашли пробел». Не rocket science.
Ну а если абстрактно рассуждать, то размышлять вообще полезно, конечно, и я рад, что автор задумывается о таких вещах.
Я не хочу быть критиком, который видит во всём ненужное старьё, но всё же в текущей конкретной статье нам предлагают откровенный шаг назад: вместо автоматического анализа частотности цепочек просто взять словарь, в котором цепочки разбиты просто по критерию «нашли пробел». Не rocket science.
Ну а если абстрактно рассуждать, то размышлять вообще полезно, конечно, и я рад, что автор задумывается о таких вещах.
Всё таки закодировал. Пока что целым числом байт, то есть если, например, словарь состоит из 512 слов, на каждое слово в тексте будет отведено два байта, и у первого в начале присобачится нос из 7 нулей. Нерационально, но выигрыш уже есть. МиМ сократился с 1.4 МБ до 1.0 МБ. Сам текст программы (все исходники в одном файле) удалось сжать ещё лучше — с 11.7КБ до 7.7КБ. И это с огромными нулевыми носами. Пытался сжать VK_100M, но не дождался конца, комп слишком разогрелся. А жаль, там так много одинаковых имён и паролей типа qwerty.
Обновил гит github.com/2che/litback
Обновил гит github.com/2che/litback
VK_100M это база паролей? Не нашел, что б скачать. Всё битое, хотя не особо старался.
Если судить по страничному образцу, будет много уникалов. Например из-за имеилов, то есть это явно не «литературный» случай.
И наверно, есть смысл сделать обработку перед словарным методом, отсечь логины у имеилов. Но это надо проверять что будет лучше 3х или 2х проходный вариант.
Если судить по страничному образцу, будет много уникалов. Например из-за имеилов, то есть это явно не «литературный» случай.
И наверно, есть смысл сделать обработку перед словарным методом, отсечь логины у имеилов. Но это надо проверять что будет лучше 3х или 2х проходный вариант.
Убрал носы. Теперь длина кодового слова не привязана к байтам, хотя всё ещё фиксирована.
Результаты:
Результаты:
- Мастер&Маргарита: с 1.4МБ до 772.2КБ (в 1.85 раз)
- Текст программы: с 11.7КБ до 7.0КБ (в 1.67 раз)
- Преступление&наказание: с 2.2МБ до 1.2МБ (в 1.83 раз)
- Рецепт жареного супа: с 1.4КБ до 940 байт (в 1.52 раз)
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Литературный архиватор