Алгоритм сжатия для кодирования списков слов
Я ищу конкретные предложения или ссылки на алгоритм и / или структуры данных для кодирования списка слов в то, что фактически оказалось бы словарем проверки орфографии. Цели этой схемы привели бы к очень высокой степени сжатия необработанного списка слов в закодированную форму. Единственное требование к выходным данным, которое я предъявляю к закодированному словарю, - это то, что любое предлагаемое целевое слово может быть сравнительно эффективно проверено на наличие относительно исходного списка слов. Например, приложение может захотеть проверить 10 000 слов в словаре на 100 000 слов. нет является требованием для того, чтобы закодированная словарная форма могла быть [легко] преобразована обратно в исходную форму списка слов - двоичный результат да / нет - это все, что требуется для каждого слова, проверенного по результирующему словарю.
Я предполагаю, что схема кодирования для улучшения степени сжатия будет использовать известные структуры в данном языке, такие как формы единственного и множественного числа, притяжательные формы, сокращения и т. д. Меня особенно интересует кодирование в основном английских слов, но для ясности , схема должна быть способна кодировать любые и все "слова" текста ASCII.
Вы можете предположить, что конкретное приложение, которое я имею в виду, предназначено для встраиваемых устройств, где энергонезависимое хранилище имеет большой недостаток, а словарь будет случайно доступной областью памяти только для чтения.
РЕДАКТИРОВАТЬ: Подводя итог требованиям словаря:
- ноль ложных срабатываний
- ноль ложноотрицательных результатов
- очень высокая степень сжатия
- нет необходимости в декомпрессии
Ответы 9
См. «Разработка орфографического листа» Макилроя на его страница пабов. Классическая старая статья о проверке орфографии на мини-компьютере, которая на удивление хорошо сочетается с перечисленными вами. Подробный анализ удаления аффиксов и двух различных методов сжатия: фильтры Блума и родственная схема кодирования Хаффмана разреженного битового набора; Я бы предпочел фильтры Блума выбранному им методу, который выжимает еще несколько килобайт при значительных затратах в скорости. (У Жемчуг программирования есть короткая глава об этой статье.)
См. Также методы, используемые для хранения словаря в системах полнотекстового поиска, например Введение в поиск информации. В отличие от вышеупомянутых методов, здесь нет ложных срабатываний.
Фильтр Блума (http://en.wikipedia.org/wiki/Bloom_filter и http://www.coolsnap.net/kevin/?p=13) представляет собой структуру данных, используемую для очень компактного хранения словарных слов в некоторых средствах проверки орфографии. Однако существует риск ложных срабатываний.
Подводить итоги:
- ноль ложных срабатываний
- ноль ложноотрицательных результатов
- высокая степень сжатия
- нет необходимости в инверсии (т.е. нет необходимости в несжатии)
Я собирался предложить фильтры Блума, но у них ненулевые ложные срабатывания.
Вместо этого Programming Pearls говорит об аналогичном наборе требований (/usr/share/dict/words в 41 КБ).
Здесь использовался подход сокращения стеблей: Например: отправлено было корнем, поэтому могли быть добавлены предварительные и пост-исправления:
- настоящее время
- представлять
- представление
- искажение фактов
Удаление аффиксов приводит к ложным срабатываниям. Я не видел здесь требования «ноль ложных срабатываний» - проверка орфографии по своей сути неточна.
проверка орфографии, как определено, совершенно точна. определение просто не охватывает контекст.
Это неточно, потому что человеческий язык неограничен. Возможно, у Джеффа действительно есть точная проблема поиска в словаре, а не неточная проверка орфографии (я не уверен в его формулировке проблемы), но если это проверка орфографии, это просто вопрос, сколько ошибок и какого рода.
Кнут упоминает "Патрисия Три" в Искусство программирования, т. 3. Я никогда не использовал его для реальной работы, но, возможно, это было бы полезно.
изменить: какое у вас ограничение ОЗУ? Если у вас намного больше ОЗУ, чем доступно ПЗУ, возможно, сжатие данных в ПЗУ (требующее декомпрессии в ОЗУ) - правильный путь. Я полагаю, что если у вас средний, но не большой объем ОЗУ, технически вы также можете хранить части структуры данных в виде сжатых BLOB-объектов в памяти и кеша, который использовался не так давно, чтобы хранить несколько из них, а затем динамически распаковывать соответствующие blob, когда его нет в кеше.
Я предполагаю, что объем ОЗУ ограничен по сравнению с размером закодированного словаря, и, вероятно, с вычислительной точки зрения нецелесообразно требовать декомпрессии фрагментов в ОЗУ для проверки словаря. Хотя сохранение состояния на основе ОЗУ возможно, поиск слова должен выполняться «на месте» и только для чтения. Спасибо
Вы можете получить степень сжатия 30% +, сохраняя слова в виде последовательных суффиксов в 7-битном формате. Я не уверен, как это называется, но это довольно эффективно переводится в древовидную структуру.
бывший.: a + n + d + s | an + d + y | и + es + roid
составляет 26 символов, по сравнению с:
а ан объявление в виде а также любой Анды андроид
что 33.
С учетом степени сжатия 12,5% для хранения в виде 7-битного содержимого получается примерно 31% общего сжатия. Степень сжатия зависит, конечно, от размера и содержания вашего списка слов.
Превращение этого в древовидную структуру с 26 корнями, вероятно, приведет к более быстрому поиску, чем сравнение подстроки открытого текста с плоским файлом.
Подумайте об этом, если вы используете только 26 символов плюс два для разделителей, вы можете сделать все в 5 битах, что само по себе составляет 37,5% сжатия, доведя приведенный выше пример до степени сжатия более 50%.
Вы даже можете использовать специальный символ, чтобы выбрать следующий суффикс: a + n! + D + s | d! + Y | es + roid - чтобы сделать его 21 символом. Или вы всегда сначала пишете следующий суффикс (19 символов). Затем вы можете использовать новую строку для совершенно нового суффикса.
Я не эксперт в этом, но разве префиксное дерево не стандартное решение для этого? Это сохраняет общие префиксы слов только один раз.
Я бы посоветовал добавить суффиксное дерево. Хорошее сжатие списков слов и отличное время поиска.
Для чистого сжатия сайт Максимальное сжатие предлагает некоторые результаты для английского словаря объемом 4 МБ, лучшая программа сжимает его примерно до 400 КБ. Некоторые другие ресурсы сжатия для сжатия текста / слова - это Страница приза Хаттера и Тест сжатия большого текста.
Я думаю, ваш лучший выбор - Сжатое суффиксное дерево / Сжатый массив суффиксов. Вы можете найти много информации по указанным выше ссылкам. Это область постоянных исследований, действительно очень интересная.
В частности, спасибо за ссылку Макилроя, это действительно хорошая отправная точка.