Алгоритмы сходства текста

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

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

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

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

У меня есть некоторые вопросы, связанные с ними, так как я не получаю Википедию. Может кто-нибудь объяснить мне эти вещи?

Levenstein. Этот алгоритм изменен на sub, добавляет и устраняет слово и видит, насколько близко он относится к другому слову в текстовом документе. Но как это можно использовать для всего текстового файла? Я могу видеть, как это можно использовать по слову, но не по предложению или целому текстовому документу от одного к другому.

Косинус. Он измеряет сходство между двумя векторами, измеряя косинус угла между ними. Что я не понимаю здесь, как два текста могут стать 2 векторами, а как насчет слов/предложений?

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

Википедия должна иметь смысл, но это не так. Мне жаль, если вопросы звучат слишком глупо, но это меня подвешивает, и я думаю, что здесь есть люди, которые вполне способны объяснить это, так что даже новоиспеченные в эту область могут получить его.

Спасибо за ваше время.

Ответ 1

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

Косинус: вы начинаете с простого подсчета уникальных слов в каждом документе. Ответы на предыдущий вопрос охватывают вычисление, как только вы это сделали.

Я никогда не использовал расстояние Хэмминга для этой цели, поэтому я не могу много говорить об этом.

Я бы добавил в список TFIDF (Term Frequency * Inverted Document Frequency). Это довольно похоже на расстояние Косина, но 1) имеет тенденцию делать лучшую работу по более коротким документам и 2) делает лучше, чтобы учесть, какие слова чрезвычайно распространены во всем корпусе, а не только те, которые, как правило, являются общими к двум конкретным документам.

Последнее замечание: для любого из них для получения полезных результатов вам почти нужно вырезать стоп-слова, прежде чем пытаться вычислить степень сходства (хотя TFIDF кажется лучше других, если вы пропустите это). По крайней мере, по моему опыту, чрезвычайно полезно остановить слова (удалить суффиксы). Когда я это сделал, я использовал алгоритм стримера Porter.

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

Ответ 2

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

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

Ответ 3

Рассмотрим пример по википедии для расстояния Левенштейна:

For example, the Levenshtein distance between "kitten" and "sitting" is 3, since the following three edits change one into the other, and there is no way to do it with fewer than three edits:

   1. kitten → sitten (substitution of 's' for 'k')
   2. sitten → sittin (substitution of 'i' for 'e')
   3. sittin → sitting (insertion of 'g' at the end).

Теперь замените "котенок" на "текст из первой бумаги" и "сидите" с "текстом из второй бумаги".

Paper[] papers = getPapers();
for(int i = 0; i < papers.length - 1; i++) {
    for(int j = i + 1; j < papers.length; j++) {
        Paper first = papers[i];
        Paper second = papers[j];
        int dist = compareSimilarities(first.text,second.text);
        System.out.println(first.name + " paper compares to " + second.name + " paper with a similarity score of " + dist);
    }
}

Сравните эти результаты и привяжите детей к самым низким показателям расстояния.

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