Словари очень часто применяются в современных прикладных программных продуктах, например, при проверке орфографии в текстовом процессоре WinWord. Для их рационального хранения применяются рассмотренные ниже методы.
Обычно в словарях слова упорядочены по алфавиту, поэтому для эффективного кодирования словарей можно применить метод, аналогичный разностному кодированию для числовых последовательностей: у каждого n-го слова отбрасываются начальные буквы, совпадающие с начальными буквами предыдущего (n-1)-го слова, и заменяются на количество отброшенных букв.
Пусть есть фрагмент словаря со словами:
вычислитель,
вычислительный,
вычислять.
Очевидно, у двух подряд расположенных слов есть общие буквы в начале. Тогда можно выполнить следующую замену:
вычислитель,
11ный,
6ять,
где числа означают, сколько букв из предыдущего слова надо взять, чтобы восстановить данное слово. Здесь слово «вычислитель» можно рассматривать как некоторое базовое слово, которое не подвергается кодированию.
|
|
Недостаток данного подхода заключается в необходимости декодировать все (n-1) слов, начиная с базового слова, для декодирования n-го слова словаря.
Второй подход состоит в том, что формируется вспомогательный словарь, в который включаются наиболее часто повторяющиеся части слов (в нашем случае, например, это фрагменты слов «вычисл» и «ител»). Каждому такому фрагменту назначается код, например, его порядковый номер во вспомогательном словаре. Затем в основном словаре фрагменты слов заменяются их кодами из вспомогательного словаря.
Для нашего примера будут сформированы два словаря:
Основной вспомогательный
12ь 1 - вычисл
12ьный 2 - ител
1ять.