Литературный архиватор

    Прежде всего, поздравляю всех православных и им сочувствующих с пасхой и окончанием великого поста, всех остальных — с наступлением весны. В песочнице только месяц назад наконец утонул мой дебют про программирование на кириллице. Не знаю, что привлекло внимание читателей к зелени, но комментировали простынями, как настоящую статью. В своей простыне TrllServ предложил использовать задумку для архивации. Обожаю людей, которые умеют находить практическое применение идеям. Развернув блокнот, я попробовал набросать алгоритм на основе свойства своей кодировки, а именно — однозначной типизации символа по первым битам. Сжимать таким алгоритмом удобно именно текст, то есть статьи, книги или копипасты из интернетов — то, что состоит из слов, и где регистр букв имеет грамматическое значение. Впоследствии к простому алгоритму добавились средние, основанные на правилах русского языка, и всё это собралось в одну сложную программу, эффективно сжимающую учебник литературы. Назовём его «Литературный архиватор».

    Методы архивации


    1. Как было сказано, текст состоит из слов. В экспериментальных архиваторах символы всегда заменяются последовательностями битов, потому что их немного, и коды занимают в памяти меньший объём.

      А = 00, Б = 01, В = 10, Г = 110

      Когда нужно сжать огромную книгу, где каждая буква встречается миллионы раз, сохранённая память также огромна. Однако, такой метод работает не только с символами. Слова — тоже повторяющиеся единицы текста, и их не так много, как кажется. В словаре Даля около 200 000 слов, а среднестатистический аноним в повседневной речи использует не более 3-4 тысяч. Конечно, в русском языке слова могут склонятся, спрягаться и т.д., но, если верить tribayana.ru/?p=4143, в «Войне и мире» Л. Н. Толстого встречается только 38873 оригинальных лексемы. При одном регистре (см. метод 2) и фиксированной длине кода каждое слово будет кодироваться двумя байтами. Неплохо, если исходный файл записан в UTF-8, где два байта — это кириллическая графема. Средняя длина слова в русском языке — 7,2 букв. То есть получается выигрыш в 7,2 раз. В статье список встречаемых в файле слов обозван «словарём».

      «батя» = 0, «суп» = 10, «травы» = 11
    2. Если взялся делать архиватор, ограничивай кодировку. В обычных случаях нам не нужны все символы юникода, чтобы закодировать файл. Чаще всего пригодятся только страница ASCII и русский алфавит. 256 символов — не так много, но TrllServ не зря заглянул в песочницу. Буквы бывают заглавные и строчные. Забудем пока про иероглифы. Если строчные буквы — основа текста, то прописные чаще всего стоят по одной в каждом предложении. При этом, если строить кодовую таблицу по обычным правилам, им придётся выделить довольно длинные битовые последовательности (при префиксном кодировании), и, что ещё хуже, «словарь» наполнится одинаковыми словами, отличающимися лишь регистром. Много памяти потратится впустую. Для нас «Ё» и «ё» — одна и та же буква, а для машины — два совсем разных значения из кодовой таблицы. Чтобы не плодить лишние слова, все наши буквы уже хранятся в самом архиваторе попарно. Все заглавные он опускает до строчных. Вместе с этим помечаются слова текста, где стояли заглавные, и сохраняется их количество в каждом слове. Заглавные здесь всегда стоят в начале слова, «ВерблюжийСтиль» режется на отдельные лексемы: «Верблюжий» и «Стиль». Так что номер слова в тексте с числом заглавных в нём декодируются однозначно.

      «Начало» — 1
      «КАПС» — 4
      «ЗАЕдает» — 3
      «ОпТОвИк»: «Оп» — 1, «ТОв» — 2, «Ик» — 1

    3. Каждый небуквенный знак (арифметический или пунктуационный) кодируется отдельной лексемой (из одного символа). Только пробел кодируется особо. Слова почти всегда разделены пробелами, вручную вставлять каждый — бессмысленно. Достаточно установить стандарт: при декодировании между двумя словами подразумевается один пробел, если не указано иное. А иное как раз указывается с помощью знака пробела в архиве. Есть несколько таких исключений:
      • Череда пробелов (больше 1) в архиве означает такую же череду пробелов в тексте. Полезно при сжатии python-скриптов со строгими отступами.

        «слово1____слово2» -> «cлово1» + "____" + «слово»
        * подчёркивание здесь — пробелы
      • Пробел между двумя словами в архиве означает отсутствие пробела между ними в тексте. Да, вот так. Костыль к верблюжьему стилю.

        «ЗаББоЧеРГ» -> «за» + " " + «ббо» + " " + «че» + " " + «рг»
        * все 4 слова помечаются, сохраняется число заглавных для каждого
      • По умолчанию небуквенные знаки «крепятся» вплотную к слову, стоящему слева, и отделяются пробелом от слова (или знака) стоящего справа. Знак пробела в архиве меняет правила.

        «селитра-,_сахар» -> «селитра» + "," + «сахар»
        «запятая_,_сэр» -> «запятая» + " " + "," + «сэр»
        «эй-,-жлоб!» -> «эй» + "," + " " + «жлоб» + "!"
        «затролил_,-школник» -> «затролил» + " " + "," + " " + «школник»

        * здесь "_" — пробел, а "-" — его отсутствие. Из за особенностей Хабра автоисправлять.
      • Одинокий пробел в самом начале архива (первым символом) означает одинокий пробел в начале текста.

        [начало текста] " первыйн" -> [начало архива] " " + «первыйн»

      Череда пробелов заменяет одиночные автоматические пробелы.
    4. Цифры кодируются как буквы, числа — как слова. Буквы с цифрами сцепляются вместе. Менять регистр у цифр возможности нет.

      «265» -> «265»
      «228статья» -> «228статья»
      «адын1111шмель» -> «адын1111шмель»


    Данные 4 метода обеспечивают «сворачивание» исходного файла без потерь и искажений.

    Общий алгоритм


    Итак, что происходит?

    1. Текст читается из исходного файла и параллельно режется парсером, составляется «словарь», на место самих слов текста подставляются «словарные» индексы. В это же время высчитывается частота встречаемости каждого «словарного» слова, и собираются метки заглавных букв.
    2. «Словарь» сортируется по частоте встречаемости. В реализации программы для ускорения сортируется подстановочный список индексов.
    3. Образуется «алфавит» — список всех существующих в тексте символов, он сортируются по частоте встречаемости символов в «словаре». Вместо символов в «словарь» подставляются индексы «алфавита». В реализации также сортируется подстановочный список.
    4. «алфавит» и «словарь» кодируются любым способом, например, по Хаффману.
    5. Открывается файл-архив для записи. Вводится кодовая таблица упорядоченного «алфавита». Конец отделяется вертикальной табуляцией.
    6. С помощью кодовой таблицы «алфавита» побитово вводится кодовая таблица «словаря». Конец отделяется вертикальной табуляцией.
    7. Вводятся индексы заглавных и их количество для тех слов, где их несколько. Конец отделяется вертикальной табуляцией.
    8. С помощью кодовой таблицы «словаря» побитово вводится текст.

    Реализация


    Фигура печальная. Пока я писал код, он запутался. В статье алгоритм выглядит просто, но понятный машине, он стал не понятный человеку. Все подстановки и индексы на деле — ужасная пирамида указателей. Сделал всё что смог, а смог почти всё. Программа работает и почти готова, в ней не реализован лишь сам алгоритм префиксного кодирования «словаря» и «алфавита» — не самая сложная, но самая главная часть. Без неё приложение работает и правильно выполняет остальные функции, но размер архива уменьшается незначительно. Почему ниасилил? Да, стыдно. Заблудился в массивах указателей, потому и не закодировал. Чтобы распутать и рефакторить своё творение, нужно время, а у людей моей специализации его сейчас катастрофически не хватает. Курс минобра: меньше знаний — больше типовых тестов для подготовки. Можно было бы закончить проект вместе с коллегами, попросить их о помощи, но, как оказалось, алгоритм архиватора для большинства из них смертелен. Впрочем, покажу что есть. «Войну и мир» без «ознакомительной части» я не нашёл, поэтому выточил архив «Мастера и Маргариты». Меньше страниц — больше смысла.

    исходный размер: 1,4 МБ.
    размер архива: 1,6 МБ.


    Эврика! Архиватор увеличил размер файла. Без кодирования он бессмыслен. Лучше рассмотрим конкретный пример.
    Две строки с упомянутыми исключениями:

    JLK ijo,ewrt lhuiOij jfds + huk uih EGE!*
    897 y98 uih — 124 jfds JLK


    превратились в это:



    Разумеется, ни о каком сжатии без должного кодирования речи не идёт, зато наглядно показана структура архива (суть).

    В общем, если, пока идут экзамены, найдётся добрый аноним, который обожает танцы с бубнами и готов написать костыль для костылей, вот исходники на Си.

    P. S. Реализация готова.

    С любовью.
    AdBlock похитил этот баннер, но баннеры не зубы — отрастут

    Подробнее
    Реклама

    Комментарии 45

      0
      А ничего, что к каждому архиву нужно будет цеплять огроменный словарь, где слова закодированы буковками?
        0
        Словарь тоже закодирован.
          0
          Другим словарем?
            0
            Алфавитом, смотри пример, цветом разметил.
            — Красный — алфавит, единственный раздел, где буковки представлены в явном виде.
            — Зелёный — закодированный алфавитом словарь. Здесь вместо индексов будет бит-код.
            — Синий — раздел с данными заглавных, тут всё понятно вроде.
            — Жёлтый — сам текст, закодированный словарём. Вместо индексов опять бит-код.
        +3
        Ряд особенностей которые тут не учтены, а нужно.
        1. Если ты считаешь это сразу архиватором, то он будем минимум двух проходным т.е. ты сначала «нормализуешь» текст и «смотришь» частотность, а после уже делаешь подмены.
        Хотя правильно это называть препроцессор, и после скармливать серьёзным архиваторам типа 7zip. Причем, возможно, лучший результат будет не от родного метода zlma, а от ppmd. Но разница не очень значительна.
        2. Наплодил лишние сущности разбиением, тем самым сильно увеличив словарь. Не вижу никакой причины делать 3 места в словаре под «Не», «По» и «Седа» при том, что оно встретится несколько раз, и это ничем не лучше чем сразу одним местом в хвосте словаря для «НеПоСеда».
        3. Именно «война и мир» имеет множество французкого в прямой речи (т.е. алфавит больше англ).

        А в общем рвение, мягко говоря, удивило, но: правильной дорогой идете, товарищ!
        Правда стоит подумать, как не таскать персональный словарь для каждой книги, и наступит персональное счастье. Но даже без этого, можно получить от 2(в худшем) до 10(в лучшем) крат уменьшение, при возможности дополнительного сжатия.

        Сейчас проверил:
        Война и мир, всего слов 226124, уникальных 31277, средняя длина 5.124 (подразумевается словоформы и иностранные тоже)
        Мастер и Маргарита, всего слов 112619, уникальных 23828, средняя длина 5.320
          0
          >Наплодил лишние сущности разбиением
          В вашем способе сильно увеличится блок заглавных. Нужно будет хранить данные о их размещении в словах.
            0
            Я бы ввёл три спецсимвола: «следующая буква — заглавная», «следующие две буквы — заглавные», «все следующие буквы до конца слова — заглавные».
              0
              Это для словаря или для текста? В словаре сейчас вообще нет прописных букв.
                0
                Для словаря. Странно написанные слова либо встречаются в одном экземпляре, либо пишутся всегда одинаково МГц, кВт, КВРБ — их стоит хранить как есть.
                В тексте нужен признак того, что слово начинается с одной заглавной буквы, и какая-то разметка, для обозначения строк полностью состоящих из заглавных букв.
              0
              > В вашем способе сильно увеличится блок заглавных.
              Именно в моём способе(одном из них) заглавных нет вообще, они кодируются иначе. Причина довольно проста — их очень мало.
              Например в Мастер и Маргарита всего 597881 символа из них только 14527 заглавные (допускаю небольшие отклонения в зависимости от издания).

              Но в посте описаны одновременно 2 способа, и символьный с оптимизацией бит и сразу словоформами, но как именно они должны взаимодействовать не очень понятно.
              Возможно из-за этого получилась путаница и проблема с реализацией?
                0
                Сначала словоформы, затем оптимизация бит.
              0
              >от 2 до 10 крат уменьшение
              это на вскидку или расчёты?
                0
                > это на вскидку или расчёты?
                Это статистика. Как можно заметить, у меня её довольно много, потому как важно понимать, что именно ты получаешь.
                Например топ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 она

                При этом «и» и «в», в большинстве проверенного мною, всегда лидируют, и если неправильно кодировать, даже двумя символамибайтами получится увеличение.
                  0
                  Потому и оставил до лучших времён, когда будет время изучить префиксное кодирование. А насчёт
                  >Не таскать с собой персональный словарь
                  думаю об онлайн-архиваторе. Пусть огромные словари с общими словами хранятся на удалённом сервере. Что на этот счёт говорит статистика?
                    0
                    > думаю об онлайн-архиваторе.
                    Мысль об онлайн архивации меня не посещала. Наверно, потому, что подразумевается самодостаточный оффлайн архиватор.
                    Но мысль может быть интересна, при определенных условиях. Надо обдумать.

                    А в целом статистика говорит, что словарь не такой большой как кажется. Если правильно организован и тоже сжат. ВинЗип22 например вести 200Мб.

                    Кстати еще статистика говорит, о том, что словарь очень сильно раздувают ошибки, опечатки, неверные переносы. В если провести работу над ошибкамикоррекцию словарь может стать меньше на 5-20%.
                      0

                      А можно ли идею архивирования использовать для поиска ошибок?
                      То есть если небольшой участок текста сжимается хуже чем другие, то в нем скорее всего есть ошибка.

                        0
                        Единичные ошибки почти не влияют на размер. Скорее для поиска вставок на другом языке подойдёт.
                          0
                          А можно ли идею архивирования использовать для поиска ошибок?
                          То есть если небольшой участок текста сжимается...

                          Можно проще — смотреть «хвост» частотной сортировки. Ну или автоматизировать — сравниванием по словарю. Т.е. не доходя со сжатия.

                          Но само сжатие как признак не подходит, они и так варьируется от автора к автору.
                            0

                            Хвост покажет опечатки внутри слов.
                            Коэффициент сжатия можно использовать для поиска лишних пробелов или неправильного соответствия окончаний, например, "крепкое кофе"

                        +2

                        Здравый смысл на этот счет говорит, что можно просто хранить на удаленном сервере весь документ и передавать ссылку. Сжатие будет охренительное: что угодно — в 128 бит.

                          0
                          Вы только что заново изобрели магнет-ссылки. :)
                            0

                            Я? Нет, я ничего не изобретал, все было до меня.

                  0
                  «В песочнице только месяц назад наконец утонул мой дебют про программирование на кириллице.»
                  А ссылку на статью можно?
                    0
                    А надо ли? Там нет программирования по сути.
                      0
                      Тут во многих статьях нет кода)
                      А про статью любопытно посмотреть.
                  0
                  Автор, отсыпь.
                    0
                    Такие штуки могут подходить для кодирования списков, таблиц, справочников. Мне кажется, что телефонный справочник с именами и фамилиями (но не с названиями организаций), можно будет закодировать лучше более привычных алгоритмов. Правда такая гипотеза требует проверки.
                      0
                      Да, вот тоже думаю про бд с множеством одинаковых данных (имена, издательства, типы и т.п.)
                      А ещё коды на гитах: одинаковые операторы, названия функций… Серверам с миллионами проектов винчестеры то нужны не маленькие.
                      0

                      Чем данный подход лучше использования других словарных методов сжатия?

                        +2
                        К сожалению, не взлетит. Вот именно эта «светлая» идея регулярно приходит в голову разным людям чуть ли не ежегодно. Сначала автор понимает, что выгоднее сжимать слова вместо символов, потом прикидывает, что к каждому отдельному файлу лучше прикладывать отдельный словарь (а иначе сжатие окажется заведомо неоптимальным, расходы на хранение словаря компенсируются перечислением в нём лишь реально обнаруженных слов)…
                        Затем становится ясно, что помещать в словарь элементы, которые в исходном тексте разделены пробелами, нелогично: чем пробел так замечателен? А если в тексте часто встречается сочетание «ский ди», почему бы не вставить его? Так мы приходим к алгоритму автоматического создания словаря. И в конечном итоге получаем обычный LZW.
                          0
                          Был ещё такой архиватор HA, заточенный как раз под тексты.
                            0
                            Был ещё такой архиватор HA, заточенный как раз под тексты.

                            Интересно не знал про такой.
                            Для 95го он был очень хорош, но сейчас не актуален. Запускается с бубном, пришлось запускать на 32 битной машине.
                            Распространеные 7z(ppmd) и zipx сжимают сильнее.
                            image
                              0

                              Я как‐то не натыкался на 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

                              (времена, разделённые ----, сравнивать не имеет смысла: разные конфигурации или машины).

                                0
                                более адекватный zpaq немного отстаёт
                                Самособой, zpaq многопоточный. И это попытка стандартизировать разнообразие паков, собрав все лучшие наработки. Закономерно и правильно, иначе какой смысле второй десяток лет возиться с архиватором которым пользуются только разработчики ;)

                                Вторая строка, расширение F — что за зверь?
                                PS:
                                А вообще надо бы оформить в единое целое, у меня где-то тоже были результаты архиваций разными, вот только время исполнения точно утеряно.
                            0
                            Вот именно эта «светлая» идея регулярно приходит в голову разным людям чуть ли не ежегодно.

                            Но после всё убивает давно заложенное:
                            К сожалению, не взлетит

                            И причин тому находится множество от «всё придумано до нас» до «на введение нового стандарта надо слишком много денег».

                            Вот только если б это было правдой после zip, не появился бы rar, а после него 7z.

                            PS:
                            LZW использует иной подход чем описан в этой и, частично, предыдущей статье. А потому если развивать это направление скорее можно прийти к paq8pxd18 или paq8hp12, чем к LZW.
                              0
                              Да я не лётчик, какие новые стандарты? Рынок IT вообще какая то оч рандомная вещь, кто взлетит — дело случая. До стандарта HTML каждая контора юзала свою разметку, тысячи их. Просто интересно, есть идеи, я и делаю.
                                0
                                Да и сейчас разметок куча. Всё ещё используется SGML и TeX, а из более популярных — MediaWiki и MarkDown.
                                0
                                Ну я же не на общие темы рассуждаю (типа «новое побеждает старое»), а про конкретный предложенный алгоритм, который уже неоднократно всплывал на моей памяти, и представляет собой по сути ручное создание словаря Далем/Ожеговым вместо автоматической процедуры — более оптимальной и надёжной.
                                  0
                                  Вот как раз на счёт оптимальности — сомнения.
                                  Возможно не достаточно понятно выразился.
                                  Сама по себе цепочка LZ LZW (LZSS) LZMA(2) не развивалась бы, если б всё было хорошо. В частности можно посмотреть-почитать ветку обсуждения об изменениях в 7z, в частности использование препроцессоров под определенные типы файлов.
                                  PS:
                                  В этой теме делаются попытки предложить и даже реализовать, что-то новое (на уровне «школьник»). Причем идеи развиваются, достаточно быстро, и возможно в следующей статье он уже предложит, то до чего еще не додумались.
                                    +1
                                    Идея препроцессора под конкретные типы файлов совершенно здравая, и опция «мультимедийное сжатие» в WinRAR тоже не вчера появилась.

                                    Я не хочу быть критиком, который видит во всём ненужное старьё, но всё же в текущей конкретной статье нам предлагают откровенный шаг назад: вместо автоматического анализа частотности цепочек просто взять словарь, в котором цепочки разбиты просто по критерию «нашли пробел». Не rocket science.

                                    Ну а если абстрактно рассуждать, то размышлять вообще полезно, конечно, и я рад, что автор задумывается о таких вещах.
                              0
                              Всё таки закодировал. Пока что целым числом байт, то есть если, например, словарь состоит из 512 слов, на каждое слово в тексте будет отведено два байта, и у первого в начале присобачится нос из 7 нулей. Нерационально, но выигрыш уже есть. МиМ сократился с 1.4 МБ до 1.0 МБ. Сам текст программы (все исходники в одном файле) удалось сжать ещё лучше — с 11.7КБ до 7.7КБ. И это с огромными нулевыми носами. Пытался сжать VK_100M, но не дождался конца, комп слишком разогрелся. А жаль, там так много одинаковых имён и паролей типа qwerty.
                              Обновил гит github.com/2che/litback
                                0
                                VK_100M это база паролей? Не нашел, что б скачать. Всё битое, хотя не особо старался.
                                Если судить по страничному образцу, будет много уникалов. Например из-за имеилов, то есть это явно не «литературный» случай.
                                И наверно, есть смысл сделать обработку перед словарным методом, отсечь логины у имеилов. Но это надо проверять что будет лучше 3х или 2х проходный вариант.
                                0
                                Убрал носы. Теперь длина кодового слова не привязана к байтам, хотя всё ещё фиксирована.
                                Результаты:
                                • Мастер&Маргарита: с 1.4МБ до 772.2КБ (в 1.85 раз)
                                • Текст программы: с 11.7КБ до 7.0КБ (в 1.67 раз)
                                • Преступление&наказание: с 2.2МБ до 1.2МБ (в 1.83 раз)
                                • Рецепт жареного супа: с 1.4КБ до 940 байт (в 1.52 раз)
                                  0
                                  Убрал носы.… Результаты:
                                  Для понимания, было бы очень интересно и полезно рядом видеть цифры насколько сжимает 7z в методами PPMd и ZLMA в однопоточном.
                                  При чём как с носами так и без. Результаты могут заметно меняться.

                                Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

                                Самое читаемое