Функция схожести текста для строгого сходства документов

Question

Я пишу часть программного обеспечения Java, которое должно принять окончательное решение о сходстве двух документов, закодированных в UTF-8.

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

Я ожидаю, что текст этих двух документов будет либо очень похожим, либо совсем не похожим, поэтому я могу быть довольно строгим в отношении порогового значения, установленного для сходства. Например, я мог бы сказать, что эти два документа похожи, только если у них есть 90% общих слов, но я хотел бы иметь что-то более надежное, которое бы работало для коротких и длинных текстов.

Подводя итог, я имею:

• два документа, либо очень похожих, либо совсем не похожих, но:
• более вероятно, что два документа похожи, чем нет
• документы могут быть как длинными (некоторые абзацы), так и короткими (несколько предложений)

Я экспериментировал с simmetrics , который имеет большой массив функций сопоставления строк, но меня больше всего интересует предложение о возможных алгоритмах для использования.

Возможные кандидаты:

• Левенштейн: его вывод более важен для коротких текстов
• коэффициент перекрытия: возможно, но хорошо ли он будет различать документы различной длины?

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

Answer 1

Левенштейн подходит для редактирования расстояния между двумя словами; если вы сравниваете документы, что-то вроде diff, вероятно, будет больше соответствовать тому, что вам нужно.

Я бы начал здесь: http://c2.com/cgi/wiki?DiffAlgorithm. Они предоставляют ссылки на ряд алгоритмов в стиле diff, с которыми вы можете ознакомиться.

Answer 2

Расстояние Левенштейна используется для сравнения двух слов. Когда это документы, популярными способами являются косинусное сходство или скрытый семантический анализ.

Answer 3

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

Answer 4

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