Поиск похожего предложения

Представим ситуацию:
Студент сдал реферат и надо проверить, не скопипастил ли из других источников.
Так же есть куча других рефератов(в дальнейшем будем называть база рефератов), среди которых и буду искать.

Алгоритм простой:
Достаю каждое предложение из исходного реферата и проверяю по базе рефератов, есть ли похожее предложение там.
Что значит похожее. Это значит что последовательность слов из моего предложения встречается в искомом предложение.
Например:
Дано предложение «Здоровый образ жизни — это образ жизни, основан­ный на принципах нравственности.»
1. Если я найду такое же предложение, то значит копипаст.
2. Пропущено слово(или несколько слов) в начале или в конце предложения:
это образ жизни, основан­ный на принципах нравственности — копипаст, т.к пропущены слова в начале предложения.
3. Добавлено слово(или слова) в начале или в конце предложения:
Пупкин говорит: Здоровый образ жизни — это образ жизни, основан­ный на принципах нравственности. — копипаст, т.к. добавлены слова «Пупкин говорит:».

Теперь надо как то оптимально реализовать данный алгоритм. Естественно будет ограничение типа «куски предложения меньше 3 слов не рассматриваем»
Подскажите, в какую сторону копать? А то если тупо перебирать, то скорость пострадает.

Обновление от 27.09.2011
В итоге получился следующий алгоритм:
1. Разбиваю исходный текст на предложения(с помощью split по символам '.','!','?')
2. Пробегаюсь по каждому тексту из БД(в моем случае это не реляционная база, а отдельные текстовые файлы) и каждый текст разбиваю на предложения
3. Сравниваю исходное предложение с предложением из БД следующим образом:
а)сколько слов из исходного предложения содержится в предложение из БД
б)если это число больше N процентов, то считаю расстояние Левенштейна для этих предложений

Результат меня устраивает вполне. В принципе пункт «3а» можно было опустить, но в моем случае я вывожу отдельно информацию «Сколько слов совпало»
  • Вопрос задан
  • 3579 просмотров
Решения вопроса 1
Пригласить эксперта
Ответы на вопрос 7
@Trept
Может помочь метод шинглов.
Каждое предложение разбиваем на ряд n-грамм, например, триграмм. Строим хэши для триграмм. Таким образом каждому предложению соответствует несколько хэшей, для триграмм их будет k-2, т.е. в Вашем примере 8. При совпадении хэшей проверяемого предложения с хэшами какого-либо предложения из базы больше некой границы, скажем, 50%, будем считать предложение «копипастным».
Ответ написан
Riateche
@Riateche
Посмотрите в сторону расстояния Левенштейна. В вашем случае «символом» является слово.
Ответ написан
Я бы начал разбивать по предложению, которое переводил бы в регулярку и пробивал бы по базе куда вносил текст. Так же в одну бы регулярку все не вставлял разбил бы по порядку с эффектом точности. Базу можно использовать например MySQL (SELECT MYSQL regexp и т.д.)
Ответ написан
Troytft
@Troytft
Разбивал бы на предлодения, вырезал все знаки и выбирал через sphinx, хотя уверен должно быть более менее готовое решение для сравнения
Ответ написан
uscr
@uscr
Если база статична (постоянна), то можно провести некоторые преобразования для всех предложений в базе (например: сохраняем само предложение, часть предложения до и после знаков препинания, если эта часть больше 3 слов). Вычисляем для всех полученных паттернов хеши. С проверяемым предложением проделываем аналогичные операции по разбиению и проверяем наличие хешей в базе. Если хеши совпали, проверяем, совпали ли предложения (ну мало ли).

Правда, такой аглоритм даст сбой, если будет добавлена часть предложения, но не отделена знаками препинания. Однако, по общему количеству совпадений можно будет делать выводы.
Ответ написан
@al13n321
Можно построить хеш-таблицу (или другую структуру, например, сложить в БД), содержащую все предложения из базы рефератов, а также все их достаточно длинные префиксы и суффиксы. То есть для предложения «мама мыла раму вчера вечером» в хеш-таблицу можно сложить предложения
«мама мыла раму вчера вечером»
«мыла раму вчера вечером»
«раму вчера вечером»
«мама мыла раму вчера»
«мама мыла раму».
Когда надо проверить предложение на баянистость, так же размножаем его на набор предложений, полученных из него удалением слов в начале или конце. Для каждого проверяем, есть ли оно в хеш-таблице. Если какое-то есть, наше предложение, возможно, баян. Более того, чем больше совпало, тем более вероятно, что предложение похоже на существующие в базе. Это должно работать достаточно быстро: предложения будут размножаться в среднем на 10-15, то есть индекс (хеш-таблицы) будет занимать примерно в 10-15 раз больше чем исходные тексты, а проверка предложения на баянистость будет сводиться к 10-15 поискам предложения в хеш-таблице. Можно вместо слов хранить их айдишники, уменьшив занимаемое место и время в несколько раз.
Ответ написан
@AigizK Автор вопроса
Как написал выше, база не совсем статичная. Так что хеш таблицу не получится составить.
Ответ написан
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы