составление списка возможных правильных написаний из неправильно написанного слова

Question

Я делаю довольно классное домашнее задание, где, используя словарь D с текстом T, я должен сканировать текст T и для каждого слова в T, не принадлежащего D, составить список возможных правильных написаний, выполнив хотя бы одно из следующих действий: следующие распространенные ошибки: замена двух смежных символов, вставка дополнительного символа, удаление одного символа и замена символа другим.

Я не уверен, что делать с последней частью, но вот что у меня есть:

1.) Используйте любой из методов java для разделения каждого слова на запись в строковом массиве I. 2.) использовать цикл for с индексом k, чтобы перейти к каждой записи в I, и использовать get (k), чтобы проверить, существует ли это слово в нашем словаре. если это не так, добавьте это слово в другой строковый массив MisspelledWords [].

3.) Как я могу эффективно выполнить одну из этих общих проверок орфографии? Прямо сейчас я могу думать только о вещах, которые были бы крайне неэффективными, например о произвольном изменении последней буквы или о чем-то.

Спасибо!

Answer 1

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

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

color / colour = LD of 1
mad / min = LD of 2 ( mad -> man -> min

Answer 2

У меня был школьный проект, который был очень похож на этот .

Основная теория заключается в том, что вы хотите вычислить Левенштейновское расстояние между словом T и всеми словами в словаре D. Затем вы представляете лучшие результаты X, где чем меньше расстояние, тем лучше.

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

Удачи!

Answer 3

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

Также, для простой, но практичной и очень хорошо объясненной (и краткой!) Реализации, см. эту статью от Norvig.

Answer 4

Напишите алгоритм, который сравнивает два слова и использует правила, которые дал вам ваш учитель, чтобы определить, может ли одно слово быть опечаткой для другого. Если вы застряли, посмотрите на расстояние Дамерау-Левенштейна , которое является измененным расстоянием Левенштейна, которое учитывает транспонированные символы.

Затем вам нужно будет использовать этот алгоритм, чтобы сравнить каждое слово с ошибкой с каждым словом в вашем словаре. Один совет, чтобы сделать алгоритм более эффективным: Вы можете исключить много слов в качестве кандидатов, не вычисляя функцию расстояния (Подумайте о минимальном расстоянии слова из n символов от слова из n + 2 символов).

Answer 5

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

• Вы берете свой словарь, сортируете каждое слово и храните его в хэше.например.Собака, Бог -> после сортировки -> ДГО.Так что в DGO у вас будет собака и бог (понравился хэш).

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

Предупреждение:

Если пропущена буква, это не может быть обнаружено.Возможно, сравнивая слово с ошибкой, мы можем просто рассмотреть любое ведро, в котором есть все буквы.(например), если вы ищете добро, и у вас есть бог (будем надеяться, что нет слова бог).Вы будете сортировать и иметь DGO.Вы можете посмотреть на любое ведро, которое содержит более половины букв. В этом случае 2 буквы.

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