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

Question

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

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

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

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

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

Answer 1

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

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

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

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

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

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

Вместо этого в Programming Pearls говорится об аналогичном наборе требований (/usr/share/dict/words в 41К).

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

• подарок
• представлять
• представление
• искажение фактов

Answer 5

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

бывший.:a+n+d+s|an+d+y|и+es+roid

составляет 26 символов по сравнению с:

объявление как и любые Анды Android

что равно 33.

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

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

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

Answer 6

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

Answer 7

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

Answer 8

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

Answer 9

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

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