Как мне сравнить фразы по сходству?

Question

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

Первый подход, который приходит мне в голову, - это разбить фразу на слова и искать фразы, содержащие эти слова. Прежде чем вы это сделаете, вы, вероятно, захотите выбросить незначительные слова (например, «the», «a», «делает» и т. Д.), И тогда вы захотите оценить результаты.

Эй, подождите - давайте сделаем это для веб-страниц, и тогда у нас может быть ... watchamacallit ... - "поисковая система", и тогда мы сможем продавать рекламу, а затем ...

Нет, серьезно, каковы общие способы решения этой проблемы?

Answer 1

Одним из подходов является так называемая модель «мешок слов».

Как вы уже догадались, сначала вы подсчитываете, сколько раз слова появляются в тексте (обычно называемый документ в NLP-lingo). Затем вы выбрасываете так называемые стоп-слова, такие как «the», «a», «or» и т. Д.

У вас остались слова и количество слов. Сделайте это на некоторое время, и вы получите полный набор слов, которые появляются в ваших документах. Затем вы можете создать индекс для этих слов: "aardvark" равен 1, "apple" равен 2, ..., "z-index" равен 70092.

Теперь вы можете взять ваши слова и превратить их в векторы. Например, если ваш документ содержит две ссылки на aardvarks и ничего больше, он будет выглядеть так:

[2 0 0 ... 70k zeroes ... 0].

После этого вы можете посчитать «угол» между двумя векторами с помощью точечного произведения . Чем меньше угол, тем ближе документы.

Это простая версия и другие более продвинутые методы. Да пребудет с вами Википедия .

Answer 2

Чтобы дополнить идею мешка слов:

Есть несколько способов, с помощью которых вы также можете обратить внимание на n-граммы, строки из двух или более слов, сохраняемые в порядке. Возможно, вы захотите сделать это, потому что поиск «космической сложности» - это гораздо больше, чем поиск вещей с «пространством» И «сложностью» в них, поскольку значение этой фразы больше, чем сумма ее частей; то есть, если вы получите результат, который говорит о сложности космического пространства и вселенной, это, вероятно, не то, что на самом деле имел в виду поиск «космической сложности».

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

Answer 3

@ Ханно, тебе стоит попробовать алгоритм расстояния Левенштейна. При заданной входной строке s и списке строк t итерация для каждой строки u в t и возврат минимальной строки Расстояние Левенштейна.

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

См. Пример реализации Java в http://www.javalobby.org/java/forums/t15908.html

Answer 4

Из моего (довольно небольшого) опыта разработки полнотекстовых поисковых систем: я бы искал вопросы, которые содержат несколько слов из запроса (в вашем случае запрос - это ваш вопрос). Конечно, шумовые слова следует игнорировать, и мы можем захотеть проверить запрос на наличие «сильных» слов, таких как «ASP.Net», чтобы сузить область поиска. http://en.wikipedia.org/wiki/Index_(search_engine)#Inverted_indices'>Inverted индексы обычно используются для поиска вопросов со словами, которые нас интересуют.

После поиска вопросов со словами из запроса нам может потребоваться вычислить расстояние между интересующими нас словами, поэтому вопрос с текстом «сходство фраз» занимает более высокое место, чем вопрос с «обсуждением сходства, вы слышите следующие фразы ... 'text.