#java #dictionary
#java #словарь
Вопрос:
Я выполняю довольно классное домашнее задание, в котором, используя словарь D с текстом T, я должен сканировать текст T и для каждого слова в T, которого нет в D, генерировать список возможного правильного написания, выполняя по крайней мере одну из следующих распространенных орфографических ошибок: замена двух соседних символов, вставка дополнительного символа, удаление одного символа и замена символа на другой.
Я не уверен, как приступить к последней части, но вот что у меня есть на данный момент:
1.) используйте любой из методов Java для разделения каждого слова на запись в массиве строк I. 2.) используйте цикл for с индексом k для перехода к каждой записи в I и используйте get (k), чтобы посмотреть, существует ли это слово в нашем словаре. если этого не произойдет, добавьте это слово в другой строковый массив MisspelledWords[].
3.) как я мог бы эффективно выполнить одну из этих распространенных проверок орфографических ошибок? Прямо сейчас я могу думать только о вещах, которые были бы крайне неэффективны, например, произвольное изменение последней буквы или что-то в этом роде.
Спасибо!
Ответ №1:
Ну, пара советов для начала. Если вы хотите эффективно хранить и извлекать слова с распространенными префиксами, попробуйте дерево префиксов. Что касается проверки орфографии, прочитайте о расстоянии редактирования.
Кроме того, для простой, но практичной и очень хорошо объясненной (и короткой!) реализации смотрите эту статью Норвига.
Ответ №2:
По сути, вы хотите вычислить расстояние Левенштейна между вашим «неправильным» словом и каждым словом в словаре. Это не «дешевый» процесс в вычислительном отношении, но он позволит вам легко обнаружить простые транспозиции / различия в одном символе.
Короче говоря, L.D. — это количество «шагов», необходимых для преобразования одной строки в другую путем добавления / удаления / изменения только одного символа на каждом шаге.
color / colour = LD of 1
mad / min = LD of 2 ( mad -> man -> min
Комментарии:
1. Проблема здесь в том, что LD для mad / min равен 2 (и это не квалифицируется как потенциальная орфографическая ошибка в соответствии с решением о назначении), а LD для mad / mda также равен 2 (но это квалифицируется как потенциальная орфографическая ошибка). Таким образом, после всех хлопот по вычислению LD для каждого слова OP все равно потребуется применить дополнительную логику.
Ответ №3:
У меня был школьный проект, который был очень похож на этот.
Основная теория заключается в том, что вы хотите вычислить расстояние Левенштейна между словом T и всеми словами в словаре D. Затем вы представляете лучшие результаты X, где чем меньше расстояние, тем лучше.
Я согласен, что этот проект был одним из моих любимых. Одной из интересных особенностей, которые я обнаружил, было то, что в результирующей таблице была определенная симметрия, которая позволяет легко выполнять многопоточность алгоритма.
Удачи!
Ответ №4:
Ответ, который я мог придумать для эффективного выполнения этого, заключается в использовании сортировки. В основном это подход, используемый для обнаружения анаграмм.
-
Вы берете свой словарь, сортируете каждое слово и сохраняете его в виде хэша. например. Собака, Бог — > после сортировки — > DGO. Итак, в DGO у вас будут Dog и god (понравился chained hash).
-
Теперь вы сортируете свое слово с ошибкой и находите, где есть совпадение. И вы сравниваете символ за символом со всеми другими словами, которые попадают в ту же корзину.
Предостережение :
Если отсутствуют буквы, это не может быть обнаружено. Возможно, при сравнении слова с ошибкой мы можем просто рассмотреть любую ячейку, содержащую все буквы . (например) если вы ищете добро, и у вас есть бог (будем надеяться, что слова «бог» не существует). Вы выполните сортировку и получите dgo. Вы можете просмотреть любую корзину, содержащую более половины букв .В данном случае 2 буквы.
Как только вы создадите этот хэш (единовременная стоимость), ваша эффективность будет хорошей. Пожалуйста, дайте мне знать, могут ли быть внесены какие-либо улучшения в это.
Комментарии:
1. Это сработает только для случая, когда символы были заменены местами. Это не будет работать для удаленных символов, добавленных символов или замененных символов
2. Я упомянул этот случай в качестве предостережения, и мы можем справиться с ним так, как я упомянул там.
Ответ №5:
Напишите алгоритм, который сравнивает два слова и использует правила, которые дал вам ваш учитель, чтобы определить, может ли одно слово быть орфографической ошибкой для другого. Если вы застряли, посмотрите на расстояние Дамерау-Левенштейна, которое представляет собой модифицированное расстояние Левенштейна, учитывающее транспонированные символы.
Затем вам нужно будет использовать этот алгоритм для сравнения каждого слова с ошибкой с каждым словом в вашем словаре. Один совет, чтобы сделать алгоритм более эффективным: Вы можете исключить множество слов в качестве кандидатов без вычисления функции расстояния (подумайте о минимальном расстоянии слова из n символов от слова из n 2 символов).