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

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

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

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

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

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

вычислять.

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

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

11ный,

6ять,

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

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

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

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