26 сентября 2003 - Shelwien

From: Eugene D. Shelwien
  To: Dmitry Khmelev
Subj: О сжатии словаря
Date: Fri, 26 Sep 2003 23:41:23


> У меня тут появилась мысль о сжатии словаря, но я что-то не могу
> сообразить, является ли это сжатие обратимым. ;) 

Как меня недавно убедил Вадим Юкин, для настоящих фанатов компрессии это несущественно ;)

> Чтобы запрограммировать и проверить у меня нету необходимых 
> подпрограмм, так что может быть, Вам это будет легче.

Да ладно, лень - тоже хорошее оправдание ;)

> Итак, пусть нам надо сжать N слов w[1], ..., w[N], причём они все
> попарно не равны w[i]!=w[j] при i!=j. Предлагается сжимать это с
> помощью преобразования Барроуза-Уилера, но с некоторой оговоркой.

У BWT есть одна маленькая проблема. По сравнению с современными реализациями PPM/CM, основанные на нем компрессоры дают существенно меньшее сжатие.

 
> Если мы просто вставим разделитель S между словами (т.е. будем
> преобразовывать текст T = w[1] S w[2] S ... S w[N] S), то группировка
> близких контекстов (концов слов) будет нарушаться символами из следующего
> лексикографически слова. Поэтому надо каким-то образом избавиться от этой
> зависимости. 

Н-да. Эту-то проблему я в своей заметке решил. В случае с BWT достаточно будет просто заменить его на ST(32) и дополнить слова до этой длины нулями. Или вообще сделать специализированный вариант ST, где сортировка отключается при достижении разделителя. Вопрос был, собственно, о другом - какие корреляции между какими частями слов надо учитывать.

> Избавление предлагается такое. Введём N различных
> символов-разделителей S[1], ..., S[N], которые будем вставлять между
> словами, причём все S[i] лексикографически предшествуют буквам основного
> алфавита (в котором записаны слова w[i]). Остаётся задать
> лексикографический порядок на S[i]. Самый примитивный способ:
> S[i]<S[j] тогда и только тогда, когда i<j. 

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

> Более интересный способ:
> S[i]<S[j] тогда и только тогда, когда reverse(w[i])<reverse(w[j]), 
> (здесь reverse() означает инверсию слова, т.е. перестановку букв слова 
> в обратном порядке). В силу неравенства слов этот порядок 
> однозначно определён.

А здесь я перевернул файл (переставил символы в обратном порядке), заново отсортировал (как раз по твоему reverse()), добавил номера (записав "цифры" в обратном порядке), затем перевернул весь файл обратно.

Потом подумал, и изменил направление сравнения в сортировке - эффект тот же.

 
> А теперь --- трюк, в правильности которого я не уверен. Давайте рассмотрим
> преобразование Барроуза-Уилера текста
> 
>   T = w[1] S[1] w[2] S[2] ... S[N-1] w[N] S[N]
> 
> которое обозначим через BW(T). А теперь заменим в BW(T)
> все символы разделители S[1], ..., S[N] на один (например, на код 0).
> 
> Вопрос: верно ли, что при обращении преобразования Уилера из полученной
> строки получатся все исходные слова, может и в перепутанном порядке?

Обычным iBWT здесь не обойдешься (хотя я даже отломал на пробу проверки контрольных сумм из DC - но добился только Out of memory).

Но вообще такое вполне реально.

Хотя в данном случае это не имеет значения по другой причине.

 
> Если да - то вот оно решение. 

Это - решение задачи блокирования ложных контекстов для BWT.

К моей задаче, к сожалению, это имеет весьма отдаленное отношение ;)

 
> Правда, надо ещё проверить, насколько сильно получится сжать. 

См. ниже.

> Интуиция подсказывает, что поскольку информации о
> порядке слов мы не передаём 
> (что происходит в подходах, описанных на
> странице http://compression.graphicon.ru/download/text.html), 

Если речь о моей заметке, то проблем это не вызывает по причине умения ppmonstr'а работать с локальными изменениями статистики.

 
> то всё должно ужаться очень хорошо.

Смотрим:    

Transform                     Postcoder
                            O1BFA    Ash02-o4  Binder's DC

Plain BWT                 1172644    1231928   1191292
Direct delimiters + BWT    801452     717420    971242
Reverse delimiters + BWT   491444     496021    519844
Modified BWT               491444     496021    519844

Dictpack1 data + BWT       437193     463704    442987

                         ppmonstr ash02  slim16 epm8

Dictpack1 to compare       426005 426945 432240 429631

Так что предложенный подход, конечно, позволяет-таки получить с помощью BWT менее 1M на бергмансовском english.dic, что тоже полезно. Только вот мой фильтр работает лучше. Да и вообще некоторые полезные корреляции после BWT становится трудновато разглядеть.

"Modified BWT" выше - это полный аналог второго варианта с разделителями, только никакие символы в исходный файл не добавляются. Вместо этого, функция сравнения строк изменена так, чтобы имитировать тот же эффект.

Имхо интересно, что многосимвольные разделители оказалось возможным полностью и корректно удалить из BWT - первоначально они просто заменялись на код 0A и результат был на несколько килобайт больше.

> Прекрасно. Остаётся строго доказать этот факт и можно писать статью ;) Мне
> всё ещё не ясно, почему же восстановление (с точностью до
> перестановки слов) однозначно.

А ты видел вадимово объяснение (в BWT FAQ) принципа действия iBWT?

У нас есть последняя колонка таблицы. Мы ее сортируем, получаем первую - а также все диграммы, т.к. колонки соседние. Затем сортируем диграммы и т.п.

Далее, допустим, нам известно, что все разделители лексикографически предшествуют обычным символам. Что произойдет с вышеописанным процессом, если мы их все заменим в BWT единственным разделителем? А то, что поменяется только соответствие разделитель(в первой колонке) - символ (в последней), а не символ-символ. Т.о. от любого символа мы всегда сможем корректно перейти к следующему, нельзя лишь гарантировать, что с разделителя мы попадем именно на тот символ, который за ним следовал в оригинале, т.к. порядок разделителей в BWT утерян. Поэтому нельзя и применять к таким данным обычное BWT - возможны циклы etc. Однако с соответствием разделитель(в последней колонке)-символ также остается все в порядке, так что мы можем получить все слова (в произвольном порядке), перебрав все разделители.

Все программы/исходники, необходимые для проверки всего вышенаписанного, находятся здесь.