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

Question

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

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

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

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

Answer 1

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

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

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

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

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

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

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

Answer 2

@ Ханно, тебе стоит попробовать алгоритм расстояния Левенштейна.Учитывая входную строку с и список строк т перебирать для каждой строки ты в т и верните тот, у которого минимальное расстояние Левенштейна.

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

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

Answer 3

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

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

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

Answer 4

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

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