Алгоритм нахождения процента того, насколько два текста идентичны

Question

Какой алгоритм вы бы предложили определить, насколько от 0 до 1 (с плавающей запятой) два текста идентичны?

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

Хороший пример алгоритма, который мне нужен, - это один из Google.использует для идентификации дублированного контента на веб-сайтах (результаты поиска X, очень похожие на показанные, были опущены, нажмите здесь, чтобы увидеть их).

Причина, по которой мне это нужно, заключается в том, что мой веб-сайт имеет возможность для пользователей публиковать сообщенияКомментарии;похожие, но разные страницы в настоящее время имеют свои собственные комментарии, поэтому многие пользователи в конечном итоге копируют и вставляют свои комментарии на все похожие страницы.Теперь я хочу объединить их (все похожие страницы будут «делиться» комментариями, и если вы разместите их на странице A, они появятся на аналогичной странице B), и я хотел бы программно удалить все эти копии и вставленные комментарии от одного и того же пользователя.

У меня довольно много миллионов комментариев, но скорость не должна быть проблемой, так как это единовременная вещь, которая будет работать в фоновом режиме.

Язык программирования на самом деле не имеет значения (до тех пор, пока он может взаимодействовать с базой данных MySQL), но я думал об этом на C ++.

Answer 1

Надежные сравнения подобия, например Расстояние Левенштейна обычно дорого. Имея множество различных текстов для сравнения, вы также сталкиваетесь с проблемой огромного числа потенциальных парных сравнений.

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

Answer 2

Заполнит ли счет алгоритм Longest Common Subsequence ? Это в основном то, что diff использует. Существует алгоритм динамического программирования, который позволяет эффективно решать такие проблемы. На странице Википедии, на которую я ссылаюсь, есть вся необходимая информация.

Чтобы поэкспериментировать с ним в удобной и дружественной форме, вы можете использовать модуль Python difflib, который его реализует. Он содержит класс difflib.SequenceMatcher, который имеет метод ratio, который:

Возвращает меру последовательностей Сходство как поплавок в диапазоне [0, 1].

где T - общее количество элементы в обеих последовательностях, и М является количество матчей, это 2,0 * М / Обратите внимание, что это 1,0, если последовательности идентичны, и 0,0, если у них нет ничего общего.

Answer 3

Сходство косинусов - хорошая мера. См. Главы 6-7 «Введение в поиск информации» по адресу http://nlp.stanford.edu/IR-book/information-retrieval-book.html

Answer 4

Сходство косинусов

В случае поиска информации, косинусное сходство двух документов будет варьироваться от 0 до 1, так как срок Частоты (веса tf-idf) не могут быть отрицательный. Угол между двумя членами частотные векторы не могут быть больше чем 90 °. - Википедия

EDIT:

ПОХОЖИЕ, но разные страницы в настоящее время имеют свои собственные комментарии, поэтому многие пользователи в конечном итоге копируют и вставляют свои комментарии на все страницы ПОХОЖИЕ.

Это сходство можно использовать.

1. Найти похожие сообщения.
2. Найти пользователей, ОБЩИХ в сообщениях, просто игнорировать других.

Эта группировка должна сократить вашу задачу :)