Comments 45
— Красный — алфавит, единственный раздел, где буковки представлены в явном виде.
— Зелёный — закодированный алфавитом словарь. Здесь вместо индексов будет бит-код.
— Синий — раздел с данными заглавных, тут всё понятно вроде.
— Жёлтый — сам текст, закодированный словарём. Вместо индексов опять бит-код.
1. Если ты считаешь это сразу архиватором, то он будем минимум двух проходным т.е. ты сначала «нормализуешь» текст и «смотришь» частотность, а после уже делаешь подмены.
Хотя правильно это называть препроцессор, и после скармливать серьёзным архиваторам типа 7zip. Причем, возможно, лучший результат будет не от родного метода zlma, а от ppmd. Но разница не очень значительна.
2. Наплодил лишние сущности разбиением, тем самым сильно увеличив словарь. Не вижу никакой причины делать 3 места в словаре под «Не», «По» и «Седа» при том, что оно встретится несколько раз, и это ничем не лучше чем сразу одним местом в хвосте словаря для «НеПоСеда».
3. Именно «война и мир» имеет множество французкого в прямой речи (т.е. алфавит больше англ).
А в общем рвение, мягко говоря, удивило, но: правильной дорогой идете, товарищ!
Правда стоит подумать, как не таскать персональный словарь для каждой книги, и наступит персональное счастье. Но даже без этого, можно получить от 2(в худшем) до 10(в лучшем) крат уменьшение, при возможности дополнительного сжатия.
Сейчас проверил:
Война и мир, всего слов 226124, уникальных 31277, средняя длина 5.124 (подразумевается словоформы и иностранные тоже)
Мастер и Маргарита, всего слов 112619, уникальных 23828, средняя длина 5.320
В вашем способе сильно увеличится блок заглавных. Нужно будет хранить данные о их размещении в словах.
В тексте нужен признак того, что слово начинается с одной заглавной буквы, и какая-то разметка, для обозначения строк полностью состоящих из заглавных букв.
Именно в моём способе(одном из них) заглавных нет вообще, они кодируются иначе. Причина довольно проста — их очень мало.
Например в Мастер и Маргарита всего 597881 символа из них только 14527 заглавные (допускаю небольшие отклонения в зависимости от издания).
Но в посте описаны одновременно 2 способа, и символьный с оптимизацией бит и сразу словоформами, но как именно они должны взаимодействовать не очень понятно.
Возможно из-за этого получилась путаница и проблема с реализацией?
это на вскидку или расчёты?
Это статистика. Как можно заметить, у меня её довольно много, потому как важно понимать, что именно ты получаешь.
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Мб.
Кстати еще статистика говорит, о том, что словарь очень сильно раздувают ошибки, опечатки, неверные переносы. В если провести
А можно ли идею архивирования использовать для поиска ошибок?
То есть если небольшой участок текста сжимается хуже чем другие, то в нем скорее всего есть ошибка.
А можно ли идею архивирования использовать для поиска ошибок?
То есть если небольшой участок текста сжимается...
Можно проще — смотреть «хвост» частотной сортировки. Ну или автоматизировать — сравниванием по словарю. Т.е. не доходя со сжатия.
Но само сжатие как признак не подходит, они и так варьируется от автора к автору.
Здравый смысл на этот счет говорит, что можно просто хранить на удаленном сервере весь документ и передавать ссылку. Сжатие будет охренительное: что угодно — в 128 бит.
А ссылку на статью можно?
А про статью любопытно посмотреть.
habrahabr.ru/post/349562
Чем данный подход лучше использования других словарных методов сжатия?
Затем становится ясно, что помещать в словарь элементы, которые в исходном тексте разделены пробелами, нелогично: чем пробел так замечателен? А если в тексте часто встречается сочетание «ский ди», почему бы не вставить его? Так мы приходим к алгоритму автоматического создания словаря. И в конечном итоге получаем обычный LZW.
Был ещё такой архиватор 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.
Возможно не достаточно понятно выразился.
Сама по себе цепочка LZ LZW (LZSS) LZMA(2) не развивалась бы, если б всё было хорошо. В частности можно посмотреть-почитать ветку обсуждения об изменениях в 7z, в частности использование препроцессоров под определенные типы файлов.
PS:
В этой теме делаются попытки предложить и даже реализовать, что-то новое (на уровне «школьник»). Причем идеи развиваются, достаточно быстро, и возможно в следующей статье он уже предложит, то до чего еще не додумались.
Я не хочу быть критиком, который видит во всём ненужное старьё, но всё же в текущей конкретной статье нам предлагают откровенный шаг назад: вместо автоматического анализа частотности цепочек просто взять словарь, в котором цепочки разбиты просто по критерию «нашли пробел». Не rocket science.
Ну а если абстрактно рассуждать, то размышлять вообще полезно, конечно, и я рад, что автор задумывается о таких вещах.
Обновил гит github.com/2che/litback
Если судить по страничному образцу, будет много уникалов. Например из-за имеилов, то есть это явно не «литературный» случай.
И наверно, есть смысл сделать обработку перед словарным методом, отсечь логины у имеилов. Но это надо проверять что будет лучше 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 раз)
Литературный архиватор