Методы эффективного кодирования словарей

Словари очень часто применяются в современных прикладных программных продуктах, например, при проверке орфографии в текстовом процессоре WinWord. Для их рационального хранения применяются рассмотренные ниже методы.

Обычно в словарях слова упорядочены по алфавиту, поэтому для эффективного кодирования словарей можно применить метод, аналогичный разностному кодированию для числовых последовательностей: у каждого n-го слова отбрасываются начальные буквы, совпадающие с начальными буквами предыдущего (n-1)-го слова, и заменяются на количество отброшенных букв.

Пусть есть фрагмент словаря со словами:

вычислитель        ,

вычислительный        ,

вычислять.

Очевидно, у двух подряд расположенных слов есть общие буквы в начале. Тогда можно выполнить следующую замену:

вычислитель        ,

11ный        ,

6ять        ,

где числа означают, сколько букв из предыдущего слова надо взять, чтобы восстановить данное слово. Здесь слово «вычислитель» можно рассматривать как некоторое базовое слово, которое не подвергается кодированию.

Недостаток данного подхода заключается в необходимости декодировать все (n-1) слов, начиная с базового слова, для декодирования n-го слова словаря.

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

Для нашего примера будут сформированы два словаря:

основной                        вспомогательный

12ь                                1 - вычисл

12ьный                        2 - ител

1ять                .

Методы эффективного кодирования естественно-языковых текстов

Наиболее распространенным и эффективным является адаптивный алгоритм, который в литературе называется также алгоритмом Зива (по имени его разработчика) или алгоритмом с указателями назад (или вперед).

В соответствии с этим алгоритмом в исходном тексте ищутся повторяющиеся фрагменты, каждый последующий из которых заменяется указателем на такой же фрагмент, который встречался ранее в начале (указатель назад) или  в конце (указатель вперед) текста. В первом случае текст просматривается от начала к концу, во втором – от конца к началу.

Например, пусть задан исходный текст:

«информатика изучает способы обработки информации».

В этом тексте дважды повторяются фрагменты «информа» длиной 7 символов (они выделены жирным стилем). Построим эффективно закодированный текст:

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

«информатика изучает способы обработки 38/7ции»,

где знак / играет роль разделителя.

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

Таким образом, для нашего примера имеем текст длиной 31 символ:

«31/7тика изучает способы обработки  информации».

Очевидно, в обоих случаях полученный результат короче исходного текста.

Помехозащитное кодирование

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

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

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

Искажение кодовых комбинаций

При передаче по каналу связи на передаваемый код, возможно, накладывается ошибка, которая формально представляется кодовой комбинацией с числом разрядов, равным числу разрядов передаваемого кода, содержащей 1 в искажаемых разрядах. Так, если a₁a₂…a_k – передаваемая кодовая комбинация, то b₁b₂…b_k – ошибка (a_i = {0,1},_, b_i = {0,1}, i=1,k).

С ошибкой связано понятие ее кратности q – это число искажаемых ошибкой разрядов, т.е. число единиц в ее коде.

Искажение рассматривается как сложение по модулю 2 исходной кодовой комбинации и ошибки:

a₁a₂…a_k ⊕ b₁b₂…b_k = c₁c₂…c_k ,

где c₁c₂…c_k – искаженная кодовая комбинация.

Пусть имеется таблица кодов:

Исходные символы	Двоичные коды
a	00
b	01
c	10
d	11

и кратность ошибки равна 1, т.е. соответствующие ошибке кодовые комбинации – элементы множества {01, 10}. Пусть передается кодовая  комбинация 10 (код символа c). Тогда возможное искажение представлено в таблице:

Передаваемая кодовая комбинация	Ошибка	Принимаемая кодовая комбинация	Результат декодирования
10	01	11	d
10	10	00	a

Таким образом, в результате ошибки принимающая сторона вместо символа c примет символ d или a и ошибка даже не будет обнаружена.