09.04.2018 19:48
2che 45 3000 Источник
Прежде всего, поздравляю всех православных и им сочувствующих с пасхой и окончанием великого поста, всех остальных — с наступлением весны. В песочнице только месяц назад наконец утонул мой дебют про программирование на кириллице. Не знаю, что привлекло внимание читателей к зелени, но комментировали простынями, как настоящую статью. В своей простыне 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. Реализация готова.

С любовью.

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


  1. Klenov_s
    09.04.2018 23:58
    #10748036
    +1

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


    1. 2che Автор
      10.04.2018 00:15
      #10748042

      Словарь тоже закодирован.


      1. Klenov_s
        10.04.2018 01:13
        #10748076

        Другим словарем?


        1. 2che Автор
          10.04.2018 01:20
          #10748080

          Алфавитом, смотри пример, цветом разметил.
          — Красный — алфавит, единственный раздел, где буковки представлены в явном виде.
          — Зелёный — закодированный алфавитом словарь. Здесь вместо индексов будет бит-код.
          — Синий — раздел с данными заглавных, тут всё понятно вроде.
          — Жёлтый — сам текст, закодированный словарём. Вместо индексов опять бит-код.


  1. TrllServ
    10.04.2018 00:08
    #10748038

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

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

    Сейчас проверил:
    Война и мир, всего слов 226124, уникальных 31277, средняя длина 5.124 (подразумевается словоформы и иностранные тоже)
    Мастер и Маргарита, всего слов 112619, уникальных 23828, средняя длина 5.320


    1. 2che Автор
      10.04.2018 00:24
      #10748052

      >Наплодил лишние сущности разбиением
      В вашем способе сильно увеличится блок заглавных. Нужно будет хранить данные о их размещении в словах.


      1. Zenitchik
        10.04.2018 00:28
        #10748054

        Я бы ввёл три спецсимвола: «следующая буква — заглавная», «следующие две буквы — заглавные», «все следующие буквы до конца слова — заглавные».


        1. 2che Автор
          10.04.2018 00:33
          #10748056

          Это для словаря или для текста? В словаре сейчас вообще нет прописных букв.


          1. Zenitchik
            10.04.2018 00:42
            #10748062

            Для словаря. Странно написанные слова либо встречаются в одном экземпляре, либо пишутся всегда одинаково МГц, кВт, КВРБ — их стоит хранить как есть.
            В тексте нужен признак того, что слово начинается с одной заглавной буквы, и какая-то разметка, для обозначения строк полностью состоящих из заглавных букв.


      1. TrllServ
        10.04.2018 00:46
        #10748064

        > В вашем способе сильно увеличится блок заглавных.
        Именно в моём способе(одном из них) заглавных нет вообще, они кодируются иначе. Причина довольно проста — их очень мало.
        Например в Мастер и Маргарита всего 597881 символа из них только 14527 заглавные (допускаю небольшие отклонения в зависимости от издания).

        Но в посте описаны одновременно 2 способа, и символьный с оптимизацией бит и сразу словоформами, но как именно они должны взаимодействовать не очень понятно.
        Возможно из-за этого получилась путаница и проблема с реализацией?


        1. 2che Автор
          10.04.2018 01:03
          #10748070

          Сначала словоформы, затем оптимизация бит.


    1. 2che Автор
      10.04.2018 01:08
      #10748072

      >от 2 до 10 крат уменьшение
      это на вскидку или расчёты?


      1. TrllServ
        10.04.2018 01:34
        #10748084

        > это на вскидку или расчёты?
        Это статистика. Как можно заметить, у меня её довольно много, потому как важно понимать, что именно ты получаешь.

        Например топ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 она


        1. 2che Автор
          10.04.2018 01:44
          #10748088

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


          1. TrllServ
            10.04.2018 02:08
            #10748094

            > думаю об онлайн-архиваторе.
            Мысль об онлайн архивации меня не посещала. Наверно, потому, что подразумевается самодостаточный оффлайн архиватор.
            Но мысль может быть интересна, при определенных условиях. Надо обдумать.

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

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


            1. Deosis
              10.04.2018 08:06
              #10748148

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


              1. 2che Автор
                10.04.2018 09:20
                #10748204

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


              1. TrllServ
                10.04.2018 09:31
                #10748214

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

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

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


                1. Deosis
                  11.04.2018 08:36
                  #10749536

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


          1. lair
            10.04.2018 12:02
            #10748400

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


            1. berez
              10.04.2018 16:32
              #10748788

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


              1. lair
                10.04.2018 16:34
                #10748796

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


  1. movis08
    10.04.2018 08:41
    #10748170

    «В песочнице только месяц назад наконец утонул мой дебют про программирование на кириллице.»
    А ссылку на статью можно?


    1. 2che Автор
      10.04.2018 09:15
      #10748198

      А надо ли? Там нет программирования по сути.


      1. movis08
        10.04.2018 10:52
        #10748308

        Тут во многих статьях нет кода)
        А про статью любопытно посмотреть.


        1. 2che Автор
          10.04.2018 12:42
          #10748452

          Если это можно назвать статьёй )
          habrahabr.ru/post/349562


  1. hd_keeper
    10.04.2018 11:10
    #10748340
    +1

    Автор, отсыпь.


  1. we1
    10.04.2018 11:30
    #10748372

    Такие штуки могут подходить для кодирования списков, таблиц, справочников. Мне кажется, что телефонный справочник с именами и фамилиями (но не с названиями организаций), можно будет закодировать лучше более привычных алгоритмов. Правда такая гипотеза требует проверки.


    1. 2che Автор
      10.04.2018 12:51
      #10748470

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


  1. masai
    10.04.2018 12:48
    #10748466

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


  1. rg_software
    10.04.2018 14:26
    #10748570

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


    1. hd_keeper
      10.04.2018 15:49
      #10748700

      Был ещё такой архиватор HA, заточенный как раз под тексты.


      1. TrllServ
        10.04.2018 21:27
        #10749170

        Был ещё такой архиватор HA, заточенный как раз под тексты.

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


        1. ZyXI
          12.04.2018 00:58
          #10750742

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

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


          1. TrllServ
            12.04.2018 02:05
            #10750772

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

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


    1. TrllServ
      10.04.2018 21:37
      #10749180

      Вот именно эта «светлая» идея регулярно приходит в голову разным людям чуть ли не ежегодно.

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

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

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

      PS:
      LZW использует иной подход чем описан в этой и, частично, предыдущей статье. А потому если развивать это направление скорее можно прийти к paq8pxd18 или paq8hp12, чем к LZW.


      1. 2che Автор
        10.04.2018 23:03
        #10749306

        Да я не лётчик, какие новые стандарты? Рынок IT вообще какая то оч рандомная вещь, кто взлетит — дело случая. До стандарта HTML каждая контора юзала свою разметку, тысячи их. Просто интересно, есть идеи, я и делаю.


        1. hd_keeper
          11.04.2018 10:45
          #10749642

          Да и сейчас разметок куча. Всё ещё используется SGML и TeX, а из более популярных — MediaWiki и MarkDown.


      1. rg_software
        11.04.2018 05:05
        #10749460

        Ну я же не на общие темы рассуждаю (типа «новое побеждает старое»), а про конкретный предложенный алгоритм, который уже неоднократно всплывал на моей памяти, и представляет собой по сути ручное создание словаря Далем/Ожеговым вместо автоматической процедуры — более оптимальной и надёжной.


        1. TrllServ
          11.04.2018 07:42
          #10749504

          Вот как раз на счёт оптимальности — сомнения.
          Возможно не достаточно понятно выразился.
          Сама по себе цепочка LZ LZW (LZSS) LZMA(2) не развивалась бы, если б всё было хорошо. В частности можно посмотреть-почитать ветку обсуждения об изменениях в 7z, в частности использование препроцессоров под определенные типы файлов.
          PS:
          В этой теме делаются попытки предложить и даже реализовать, что-то новое (на уровне «школьник»). Причем идеи развиваются, достаточно быстро, и возможно в следующей статье он уже предложит, то до чего еще не додумались.


          1. rg_software
            11.04.2018 10:26
            #10749624

            Идея препроцессора под конкретные типы файлов совершенно здравая, и опция «мультимедийное сжатие» в WinRAR тоже не вчера появилась.

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

            Ну а если абстрактно рассуждать, то размышлять вообще полезно, конечно, и я рад, что автор задумывается о таких вещах.


  1. 2che Автор
    10.04.2018 23:26
    #10749328

    Всё таки закодировал. Пока что целым числом байт, то есть если, например, словарь состоит из 512 слов, на каждое слово в тексте будет отведено два байта, и у первого в начале присобачится нос из 7 нулей. Нерационально, но выигрыш уже есть. МиМ сократился с 1.4 МБ до 1.0 МБ. Сам текст программы (все исходники в одном файле) удалось сжать ещё лучше — с 11.7КБ до 7.7КБ. И это с огромными нулевыми носами. Пытался сжать VK_100M, но не дождался конца, комп слишком разогрелся. А жаль, там так много одинаковых имён и паролей типа qwerty.
    Обновил гит github.com/2che/litback


    1. TrllServ
      11.04.2018 00:54
      #10749418

      VK_100M это база паролей? Не нашел, что б скачать. Всё битое, хотя не особо старался.
      Если судить по страничному образцу, будет много уникалов. Например из-за имеилов, то есть это явно не «литературный» случай.
      И наверно, есть смысл сделать обработку перед словарным методом, отсечь логины у имеилов. Но это надо проверять что будет лучше 3х или 2х проходный вариант.


  1. 2che Автор
    11.04.2018 16:05
    #10750006

    Убрал носы. Теперь длина кодового слова не привязана к байтам, хотя всё ещё фиксирована.
    Результаты:

    • Мастер&Маргарита: с 1.4МБ до 772.2КБ (в 1.85 раз)
    • Текст программы: с 11.7КБ до 7.0КБ (в 1.67 раз)
    • Преступление&наказание: с 2.2МБ до 1.2МБ (в 1.83 раз)
    • Рецепт жареного супа: с 1.4КБ до 940 байт (в 1.52 раз)


    1. TrllServ
      11.04.2018 17:15
      #10750148

      Убрал носы.… Результаты:
      Для понимания, было бы очень интересно и полезно рядом видеть цифры насколько сжимает 7z в методами PPMd и ZLMA в однопоточном.
      При чём как с носами так и без. Результаты могут заметно меняться.