26 сентября 2003 - Д.Хмелёв

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

Привет!

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

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

Если мы просто вставим разделитель S между словами (т.е. будем преобразовывать текст T = w[1] S w[2] S ... S w[N] S), то группировка близких контекстов (концов слов) будет нарушаться символами из следующего лексикографически слова. Поэтому надо каким-то образом избавиться от этой зависимости. Избавление предлагается такое. Введём N различных символов-разделителей S[1], ..., S[N], которые будем вставлять между словами, причём все S[i] лексикографически предшествуют буквам основного алфавита (в котором записаны слова w[i]). Остаётся задать лексикографический порядок на S[i]. Самый примитивный способ: S[i]<S[j] тогда и только тогда, когда i<j. Более интересный способ: S[i]<S[j] тогда и только тогда, когда reverse(w[i])<reverse(w[j]), (здесь 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).

Вопрос: верно ли, что при обращении преобразования Уилера из полученной строки получатся все исходные слова, может и в перепутанном порядке?

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

Пока,

Дима Хмелёв