Автоматическая проверка орфографии слов в тексте

Question

[EDIT] Короче: как бы вы написали автоматическую проверку орфографии? Идея состоит в том, что контролер строит список слов из известного хорошего источника (словаря) и автоматически добавляет новые слова, когда они используются достаточно часто. Слова, которые не использовались в то время, должны быть постепенно прекращены. Поэтому, если я удаляю часть сцены, содержащую «Mungrohyperiofier», контролер должен помнить об этом некоторое время, и когда я набираю «Mung < Ctrl + Space >» в другой сцене, он должен предложить его снова. Если я не буду использовать это слово, скажем, через несколько дней, он должен забыть об этом.

В то же время, я хотел бы, чтобы избежать добавления опечаток в словарь. [/ EDIT]

Я хочу написать текстовый редактор для SciFi историй. Редактор должен предлагать слово для любого слова, используемого где угодно в текущей истории. Он будет предлагать только одну сцену истории для редактирования (так что вы можете легко перемещать сцены вокруг).

Это означает, что у меня есть три набора:

1. Множество всех слов во всех остальных сценах
2. Множество слов в текущей сцене перед тем я начал редактировать его
3. Множество слова в текущем редакторе

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

Когда пользователь редактирует сцену, у нас есть такие ситуации:

1. Она удаляет слово. Это слово не используется нигде в текущей сцене.
2. типы Она слово, которое является новым
3. типов Она слово, которое уже существует
4. типа She слово, которое уже существует, но делает опечатку
5. Она исправляет опечатку в слове, которое находится в наборе # 2 ,
6. Она исправляет опечатку словом, которое находится в наборе №1 (т. Е. Опечатка находится в другом месте).
7. Она удаляет слово, которое она планирует использовать снова. Однако после удаления слово больше не находится в наборах # 1 и # 3.

Очевидной стратегией было бы перестроить наборы слов при сохранении сцены и построить набор # 1 из файла списка слов на сцену.

Итак, мой вопрос: есть ли умная стратегия держать слова, которые больше нигде не используются, но все же быть в состоянии поэтапно отказаться от опечаток? Если это возможно, эта стратегия должна работать в фоновом режиме, даже если пользователь не замечает, что происходит (т. Е. Я хочу избегать захвата мыши, чтобы выбрать «добавить слово в словарь» в меню).

[EDIT] На основе комментарий от grieve

Answer 1

Структура вы должны использовать это Trie. Хранение/сжатие суффиксов поможет с памятью. Вы можете использовать GC подсчета псевдоданных для отслеживания использования.

Для реальных узлов вам, вероятно, потребуется не более 32-битного целого числа, 21 бит для юникода, а остальное для различных других тегов и информации.

Answer 2

Напоминает мне о том, что я сказал о мусорном сборе в современных реализациях LISP:

данных при создании помещаются в «пуле 1»,

, когда есть необходимость сборки мусор сборщик мусора посмотрите в пуле 1 для неиспользуемых записей и удалите их.

Затем оставшаяся запись перемещается в бассейн 2.

Pool 2 рассматривается только тогда, когда существует необходимость в дополнительной памяти, чем бассейн 1 может выпустить.

Данные из бассейна 2, которые выдержали сбор мусора, помещаются в бассейн 3 и ... так далее.

Идея заключается в том, чтобы поместить динамически данные в пуле, соответствующем его жизни ...

Answer 3

Так что вы хотите написать проверку орфографии. Вот Peter Norvig's paper about writing a spelling corrector. Он описывает простой и надежный корректор орфографии. Вы можете использовать уже написанную часть книги, а также список ссылок (скажем, из бесплатного словаря) для языковой модели. Я бы также пошел на существующие проверки правописания с открытым исходным кодом, такие как aspell и hunspell, чтобы получить некоторые идеи.