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

Ответ 1

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

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

Ответ 2

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

Ответ 3

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

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

Ответ 4

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

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

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

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

Это привело к сокращению стеблей: Например: send был root, поэтому могут быть добавлены до и после исправления:

• присутствует
• представляют
• представление
• искажение

Ответ 5

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

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

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

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

который равен 33.

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

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

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

Ответ 6

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

Ответ 7

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

Ответ 8

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

Ответ 9

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

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