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

Question

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

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

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

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

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

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

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

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

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

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

Answer 1

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

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

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

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

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

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

Answer 2

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

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 + "'s paper compares to " + second.name + "'s paper with a similarity score of " + dist);
    }
}

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

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

Answer 3

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

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