группировка строк по сходству

Question

У меня есть массив строк, не много (может быть, несколько сотен), но часто длинные (несколько сотен символов).

Эти строки, как правило, бессмысленны и отличаются друг от друга ... но в группе из этих строк, может быть, 5 из 300, есть большое сходство. На самом деле это одна и та же строка, которая отличается форматированием, пунктуацией и несколькими словами.

Как я могу определить эту группу строк?

Кстати, я пишу в ruby, но если бы ничего другого, алгоритм в псевдокоде был бы в порядке.

спасибо

Answer 1

Есть много способов сравнить строки по сходству.

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

Вот статья в Википедии с различными метриками сходства , которую вы можете использовать.

Answer 2

Для этого вы можете использовать алгоритм Левенштейна . Вот реализация в Ruby.

Answer 3

Если вы не беспокоитесь об опечатках или других ошибках в каждом слове, вы можете сделать следующее:

Создайте инвертированный индекс, который в основном представляет собой хеш-код по слову, указывающий на список указателей на строки, содержащие это слово (как вы обрабатываете повторяющиеся вхождения, зависит от вас) Чтобы определить строки, похожие на заданную строку запроса, найдите каждое слово запроса в индексе, и для каждой исходной строки в результирующих списках подсчитайте, сколько раз исходная строка появляется в каждом списке. Строки с самыми высокими значениями - ваши лучшие кандидаты на сходство, потому что они содержат наибольшее количество общих слов.

Затем вы можете вычислить расстояние редактирования между двумя строками или любую другую метрику, которую вы хотите. Таким образом, вы избегаете сложности O (n ^ 2), сравнивая каждую строку с любой другой строкой.

Answer 4

Это может быть излишним и, возможно, не совсем соответствовать тому, чего вы хотите достичь, но вы можете использовать 'Ferret', чтобы помочь (Ruby-версия Lucene - полнотекстовый индекс / API поиска) для сортировки вне знаков препинания и форматирования - также, если предложения отличаются общими «стоп-словами» (the, and, is ...), они могут быть отфильтрованы.

Тогда вашим запросам будут присвоены веса: это дает представление о подобии.

http://www.davebalmain.com/ http://www.amazon.co.uk/Ferret-David-Balmain/dp/0596519400/ref=sr_1_2?ie=UTF8&s=books&qid=1264751909&sr=8-2