Литературный архиватор10.04.2018 12:33

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

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

Как было сказано, текст состоит из слов. В экспериментальных архиваторах символы всегда заменяются последовательностями битов, потому что их немного, и коды занимают в памяти меньший объём.
А = 00, Б = 01, В = 10, Г = 110
Когда нужно сжать огромную книгу, где каждая буква встречается миллионы раз, сохранённая память также огромна. Однако, такой метод работает не только с символами. Слова — тоже повторяющиеся единицы текста, и их не так много, как кажется. В словаре Даля около 200 000 слов, а среднестатистический аноним в повседневной речи использует не более 3–4 тысяч. Конечно, в русском языке слова могут склонятся, спрягаться и т.д., но, если верить tribayana.ru/? p=4143, в «Войне и мире» Л.Н. Толстого встречается только 38873 оригинальных лексемы. При одном регистре (см. метод 2) и фиксированной длине кода каждое слово будет кодироваться двумя байтами. Неплохо, если исходный файл записан в UTF-8, где два байта — это кириллическая графема. Средняя длина слова в русском языке — 7,2 букв. То есть получается выигрыш в 7,2 раз. В статье список встречаемых в файле слов обозван «словарём».
«батя» = 0, «суп» = 10, «травы» = 11
Если взялся делать архиватор, ограничивай кодировку. В обычных случаях нам не нужны все символы юникода, чтобы закодировать файл. Чаще всего пригодятся только страница ASCII и русский алфавит. 256 символов — не так много, но TrllServ не зря заглянул в песочницу. Буквы бывают заглавные и строчные. Забудем пока про иероглифы. Если строчные буквы — основа текста, то прописные чаще всего стоят по одной в каждом предложении. При этом, если строить кодовую таблицу по обычным правилам, им придётся выделить довольно длинные битовые последовательности (при префиксном кодировании), и, что ещё хуже, «словарь» наполнится одинаковыми словами, отличающимися лишь регистром. Много памяти потратится впустую. Для нас «Ё» и «ё» — одна и та же буква, а для машины — два совсем разных значения из кодовой таблицы. Чтобы не плодить лишние слова, все наши буквы уже хранятся в самом архиваторе попарно. Все заглавные он опускает до строчных. Вместе с этим помечаются слова текста, где стояли заглавные, и сохраняется их количество в каждом слове. Заглавные здесь всегда стоят в начале слова, «ВерблюжийСтиль» режется на отдельные лексемы: «Верблюжий» и «Стиль». Так что номер слова в тексте с числом заглавных в нём декодируются однозначно.
«Начало» — 1
«КАПС» — 4
«ЗАЕдает» — 3
«ОпТОвИк»: «Оп» — 1, «ТОв» — 2, «Ик» — 1
Каждый небуквенный знак (арифметический или пунктуационный) кодируется отдельной лексемой (из одного символа). Только пробел кодируется особо. Слова почти всегда разделены пробелами, вручную вставлять каждый — бессмысленно. Достаточно установить стандарт: при декодировании между двумя словами подразумевается один пробел, если не указано иное. А иное как раз указывается с помощью знака пробела в архиве. Есть несколько таких исключений:
- Череда пробелов (больше 1) в архиве означает такую же череду пробелов в тексте. Полезно при сжатии python-скриптов со строгими отступами.
  «слово1____слово2» → «cлово1» + »____» + «слово»
  * подчёркивание здесь — пробелы
- Пробел между двумя словами в архиве означает отсутствие пробела между ними в тексте. Да, вот так. Костыль к верблюжьему стилю.
  «ЗаББоЧеРГ» → «за» + » » + «ббо» + » » + «че» + » » + «рг»
  * все 4 слова помечаются, сохраняется число заглавных для каждого
- По умолчанию небуквенные знаки «крепятся» вплотную к слову, стоящему слева, и отделяются пробелом от слова (или знака) стоящего справа. Знак пробела в архиве меняет правила.
  «селитра-,_сахар» → «селитра» + »,» + «сахар»
  «запятая_,_сэр» → «запятая» + » » + »,» + «сэр»
  «эй-,-жлоб!» → «эй» + »,» + » » + «жлоб» + »!»
  «затролил_,-школник» → «затролил» + » » + »,» + » » + «школник»
  * здесь »_» — пробел, а »-» — его отсутствие. Из за особенностей Хабра автоисправлять.
- Одинокий пробел в самом начале архива (первым символом) означает одинокий пробел в начале текста.
  [начало текста] » первыйн» → [начало архива] » » + «первыйн»
Череда пробелов заменяет одиночные автоматические пробелы.
Цифры кодируются как буквы, числа — как слова. Буквы с цифрами сцепляются вместе. Менять регистр у цифр возможности нет.
»265» → »265»
»228статья» → »228статья»
«адын1111шмель» → «адын1111шмель»

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

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

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

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

Реализация

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

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

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

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

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

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

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

С любовью.