Как сравнить фразы для сходства?

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

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

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

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

Ответ 1

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

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

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

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

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

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

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

Ответ 2

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

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

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

Ответ 3

Чтобы увеличить идею слова "сумка слов":

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

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

Ответ 4

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

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