Алгоритм сжатия для кодирования списков слов

Question

Я ищу конкретные предложения или ссылки на алгоритм и / или структуры данных для кодирования списка слов в то, что фактически оказалось бы словарем проверки орфографии. Цели этой схемы привели бы к очень высокой степени сжатия необработанного списка слов в закодированную форму. Единственное выходное требование, которое я предъявляю к закодированному словарю, заключается в том, что любое предлагаемое целевое слово может быть сравнительно эффективно проверено на наличие в сравнении с исходным списком слов. Например, приложение может захотеть проверить 10000 слов по словарю в 100 000 слов. Это не требование, чтобы закодированная словарная форма была [легко] преобразована обратно в исходную форму списка слов - двоичный результат да / нет - это все, что нужно для каждого слова, проверяемого по полученному словарю.

Я предполагаю, что схема кодирования, чтобы улучшить степень сжатия, использовала бы преимущества известных структур на данном языке, таких как формы единственного и множественного числа, притяжательные формы, сокращения и т. Д. Меня особенно интересует кодирование в основном английских слов, но чтобы быть понятным, схема должна иметь возможность кодировать любые текстовые слова ASCII.

Можно предположить, что конкретное приложение предназначено для встраиваемых устройств, где объем энергонезависимой памяти выше, а словарь представляет собой произвольно доступную область только для чтения.

РЕДАКТИРОВАТЬ : Суммировать требования словаря:

• ноль ложных срабатываний
• ноль ложных негативов
• очень высокая степень сжатия
• декомпрессия не требуется

Answer 1

См. "Разработка списка правописания" Макилроя на странице его пабов . Классическая старая статья о проверке правописания на миникомпьютере, которая на удивление хорошо отображает те, что вы перечислили. Детальный анализ разложения аффиксов и двух разных методов сжатия: фильтры Блума и связанная с ними схема Хаффмана - кодирование разреженного набора битов; Я предпочел бы использовать фильтры Блума, вероятно, предпочтительнее метода, который он выбрал, который выдавливает еще несколько килобайт при значительной скорости. ( Programming Pearls имеет небольшую главу об этой статье.)

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

Answer 2

Фильтр Блума (http://en.wikipedia.org/wiki/Bloom_filter и http://www.coolsnap.net/kevin/?p=13)) - это структура данных, используемая для очень компактного хранения словарных слов в некоторых средствах проверки орфографии. Однако существует риск ложных срабатываний.

Answer 3

Я бы предложил дерево с суффиксами. Хорошее сжатие в списках слов и отличное время поиска.

http://en.wikipedia.org/wiki/Suffix_tree

Answer 4

Я думаю, что ваша лучшая ставка - это Сжатое суффиксное дерево / Сжатый суффиксный массив . Вы можете найти множество информации по ссылкам выше. Это область постоянных исследований, действительно очень интересная.

Answer 5

Вы можете получить 30% + степень сжатия за счет сохранения слов в виде последовательных суффиксов в 7-битном формате. Я не уверен, как это называется, но довольно эффективно переводится в древовидную структуру.

напр .: а + п + д + з | ап + д + у | + и ES + Roid

- это 26 символов, по сравнению с:

а объявление как а также любой Анды андроид

, что составляет 33.

С учетом степени сжатия 12,5% для хранения в виде 7-битного контента, это составляет около 31% общего сжатия. Коэффициент сжатия зависит, конечно, от размера и содержания вашего списка слов.

Превращение этого в структуру с 26 корневыми деревьями, вероятно, приведет к поискам, которые будут быстрее, чем сравнение подстрок с открытым текстом с плоским файлом.

Если подумать, если вы используете только 26 символов плюс два для разделителей, вы можете делать все в 5 битах, что само по себе является 37,5% -ным сжатием, в результате чего приведенный выше пример более чем на 50%. ставка.

Answer 6

Подводя итог:

• ноль ложных срабатываний
• ноль ложных негативов
• высокая степень сжатия
• нет необходимости для обратного (т.е. нет необходимости в сжатии)

Я собирался предложить фильтры Блума, но они имеют ненулевые ложные срабатывания.

Вместо этого, Programming Pearls говорит о схожем наборе требований (/usr/share/dict/words в 41K).

Это приняло подход сокращения стеблей: Например: sent был корневым, поэтому можно добавить до и после исправления:

• присутствует * * тысячу двадцать-одна
• представляет
• представление
• искажение

Answer 7

Для чистого сжатия сайт Maximum Compression предлагает некоторые результаты для английского словаря на 4 МБ, лучшая программа сжимает его до 400 КБ. Некоторыми другими ресурсами сжатия для сжатия текста / слов являются страница премии Хаттера и тест сжатия большого текста .

Answer 8

Я не эксперт в этом, но разве дерево префиксов не является достаточно стандартным решением для этого? Это хранит общие префиксы слов только один раз.

Answer 9

Кнут упоминает "Patricia trie" в Искусство компьютерного программирования vol. 3 . Я никогда не использовал его для какой-либо реальной работы, но, возможно, это было бы полезно.

редактировать: какое у вас ограничение ОЗУ? Если у вас гораздо больше ОЗУ, чем доступно в ПЗУ, возможно, правильное решение - сжатие данных в ПЗУ (требующее распаковки в ОЗУ). Я полагаю, если у вас средний, но не большой объем оперативной памяти, технически вы также можете хранить части структуры данных в виде сжатых больших двоичных объектов в памяти и кэш, который использовался не так давно, чтобы хранить несколько из них, а затем динамически распаковывать соответствующие blob, когда его нет в кеше.