Расширение алфавита: сколько можно выиграть, схлопывая частые диграфы

Задача: найти самый частый диграф, заменить его новой буквой и оценить, выгодна ли такая модификация. При замене текст становится короче, но алфавит растёт и энтропия увеличивается.

Результаты

English (UDHR, art. 1)

замены: 0=th, 1=the, 2=ou, 3=nd, 4=and, 5=ve, 6=ng, 7=ing, 8=was, 9=you

исходный (170 симв.):

all human beings are born free and equal in dignity and rights. they are endowed with reason and conscience and should act towards one another in a spirit of brotherhood.

закодированный (151 симв., -11.2%):

all human be7s are born free 4 equal in dignity 4 rights. 1y are e3owed wi0 reason 4 conscience 4 sh2ld act towards one ano1r in a spirit of bro1rhood.

Esperanto (UDHR, art. 1)

замены: 0=la, 1=de, 2=aj, 3=oj, 4=kaj, 5=st, 6=est, 7=li, 8=aŭ, 9=al

исходный (154 симв.):

ĉiuj homoj estas denaske liberaj kaj egalaj laŭ digno kaj rajtoj. ili posedas racion kaj konsciencon, kaj devus konduti unu al alia en spirito de frateco.

закодированный (131 симв., -14.9%):

ĉiuj hom3 6as 1naske 7ber2 4 ega0j 0ŭ digno 4 r2t3. i7 posedas racion 4 konsciencon, 4 1vus konduti unu 9 a7a en spirito 1 frateco.

Описание решения для английского

Исходные данные — 840 175 букв, алфавит 26, энтропия 4.1796 бит/букву.
Шаги 1–8 выбраны алгоритмом, шаги 9–10 — вручную из просчитанных кандидатов.

Итог: алфавит 26 → 36, текст 840 175 → 734 402 букв (−12.6%), энтропия 4.1796 → 4.5270, суммарная стоимость по MDL −5.314%.

Анализ. Три из восьми символов — двухуровневые: 1 = 0+e = the, 4 = a+3 = and, 7 = i+6 = ing. Именно они дают непропорционально большой выигрыш: шаг 5 (and, 10 237 вхождений) принёс 26 662 бита, вдвое больше шага 4 (nd, 13 168 вхождений, 13 846 бит) — несмотря на меньшую частоту.

Схлопывается два типа избыточности:
- орфографическая — th — один звук, записанный двумя буквами; ng — тоже;
- лексико-морфологическая — артикль the, союз and, суффикс герундия -ing.

Выбор по реальному выигрышу MDL, а не по частоте, принципиален: на шаге 1 he встречался чаще th (25 249 против 25 005), но дал бы 29k вместо 37k бит. На шаге 6 выбран ve с 5 537 вхождениями, опередив in с 13k — редкий, но «неожиданный» диграф ценнее частого предсказуемого.

Описание решения для Эсперанто

Исходные данные — 28 819 194 буквы, алфавит 28, энтропия 4.1384 бит/букву.

Шаги 1–8 выбраны алгоритмом, шаги 9–10 — вручную из просчитанных кандидатов.

Итог: алфавит 28 → 38, текст 28 819 194 → 25 286 470 букв (−12.3%), энтропия 4.1384 → 4.5405, суммарная стоимость по MDL −3.733%.

Анализ. Выигрыш идёт целиком от грамматической регулярности, а не от орфографии: артикль la, предлог de, окончания множественного числа -aj/-oj, союз kaj, глагольный корень est. В фонетической орфографии эсперанто нет аномалий вроде английского th, схлопывать нечего на уровне букв.

Два символа второго уровня: 4 = k+2 = kaj, 6 = e+5 = est. Они появляются только после того, как предыдущие шаги подготовили почву, — жадный выбор по частоте их бы не нашёл.

Ни одного убыточного шага: минимальный выигрыш +189k бит на восьмом. Но выигрыши быстро падают (836k → 189k), следующие кандидаты pr=152k, vi=115k уже слабее.

Сравнение языков

Английский сжимается заметно лучше при меньшем числе добавленных символов. Причина — двойной источник избыточности: неэффективная орфография (th, ng — по одному звуку на два знака) плюс частотные служебные слова. Эсперанто с фонетическим письмом такого запаса не имеет; единственное исключение — дифтонг aŭ, где ŭ жёстко привязан к предшествующей a., и весь выигрыш приходится на повторяющиеся служебные слова и флексии.

Методически важно: выбор кандидата по реальному выигрышу MDL, а не по частоте диграфа, даёт существенно лучший результат. Для эсперанто жадный выбор по частоте давал −1.683%, по выигрышу — −3.300%, то есть вдвое больше при том же числе шагов. Корреляция между частотой и пользой слабая: диграф on в эсперанто встречается 485 797 раз и даёт 0.12 бит на вхождение, а de при 429 406 вхождениях — 1.31 бита, в 11 раз больше.

Почему остановились на 10 символах. Проверка ещё 10 шагов (до алфавита 44–46) показала, что отдача падает: у английского с ~0.59 п.п. на символ в начале до ~0.14 п.п., у эсперанто с ~0.41 до ~0.16. Точка, где MDL начал бы расти, не достигается, но алфавит из 45+ знаков практически бесполезен при приросте сжатия в доли процента.

Энтропия

Энтропия Шеннона H — средняя «неожиданность» одного символа текста, измеряется в битах:

H = -\sum_{i=1}^{N} F_i \log_2 F_i

где F_i — частота i-й буквы (сумма частот = 1).

Смысл величины -\log_2 F_i — сколько бит нужно на кодирование одной буквы при оптимальном коде. Редкая буква несёт больше информации и стоит дороже: буква с частотой 1/2 стоит 1 бит, с частотой 1/1000 — почти 10 бит. Энтропия — средняя стоимость по всем буквам с учётом того, как часто каждая встречается.

Свойства, важные для нашей задачи:

- H \le \log_2 N, равенство только при равномерном распределении. Чем сильнее перекос частот, тем меньше энтропия и тем лучше сжимается текст.
- L \cdot H — нижняя граница размера текста в битах при посимвольном кодировании (теорема Шеннона о кодировании источника).
- Добавление новой буквы повышает H: распределение выравнивается, редкие события становятся менее предсказуемыми.

В наших расчётах энтропия растёт на каждом шаге (английский: 4.18 → 4.49), но длина текста падает быстрее, поэтому произведение L \cdot H уменьшается.

MDL — Minimum Description Length

Принцип минимальной длины описания: из нескольких моделей данных лучшая та, для которой суммарная длина «описание модели + данные, закодированные этой моделью» минимальна.

Зачем нужна вторая часть суммы? Без неё оптимизация вырождается: можно ввести по отдельному символу на каждое слово языка, текст станет очень коротким — но словарь-расшифровка окажется огромным. MDL автоматически штрафует такое переусложнение и сам находит точку остановки.

Наша формула:

\text{MDL} = \underbrace{L\cdot H}_{\text{данные}} + \underbrace{N\log_2 L}_{\text{таблица частот}} + \underbrace{k\cdot 2\log_2 N_0}_{\text{определения новых букв}}

Цена модели ничтожна на больших текстах, поэтому почти любое схлопывание частого диграфа окупается. Но она задаёт точку окупаемости: на коротком тексте замена невыгодна. Для английского th→þ порог составляет около 634 букв — на SMS расширять алфавит смысла нет, на книге есть.

MDL также объясняет, почему процесс не может продолжаться бесконечно: с каждым шагом энтропия растёт, выигрыш от укорочения падает, и в какой-то момент прирост H перевешивает экономию на L. В ранних прогонах это проявлялось как отрицательный выигрыш на 6-м шаге.