Представим ситуацию:
Студент сдал реферат и надо проверить, не скопипастил ли из других источников.
Так же есть куча других рефератов(в дальнейшем будем называть база рефератов), среди которых и буду искать.
Алгоритм простой:
Достаю каждое предложение из исходного реферата и проверяю по базе рефератов, есть ли похожее предложение там.
Что значит похожее. Это значит что последовательность слов из моего предложения встречается в искомом предложение.
Например:
Дано предложение «Здоровый образ жизни — это образ жизни, основанный на принципах нравственности.»
1. Если я найду такое же предложение, то значит копипаст.
2. Пропущено слово(или несколько слов) в начале или в конце предложения:
это образ жизни, основанный на принципах нравственности — копипаст, т.к пропущены слова в начале предложения.
3. Добавлено слово(или слова) в начале или в конце предложения:
Пупкин говорит: Здоровый образ жизни — это образ жизни, основанный на принципах нравственности. — копипаст, т.к. добавлены слова «Пупкин говорит:».
Теперь надо как то оптимально реализовать данный алгоритм. Естественно будет ограничение типа «куски предложения меньше 3 слов не рассматриваем»
Подскажите, в какую сторону копать? А то если тупо перебирать, то скорость пострадает.
Обновление от 27.09.2011
В итоге получился следующий алгоритм:
1. Разбиваю исходный текст на предложения(с помощью split по символам '.','!','?')
2. Пробегаюсь по каждому тексту из БД(в моем случае это не реляционная база, а отдельные текстовые файлы) и каждый текст разбиваю на предложения
3. Сравниваю исходное предложение с предложением из БД следующим образом:
а)сколько слов из исходного предложения содержится в предложение из БД
б)если это число больше N процентов, то считаю расстояние Левенштейна для этих предложений
Результат меня устраивает вполне. В принципе пункт «3а» можно было опустить, но в моем случае я вывожу отдельно информацию «Сколько слов совпало»
Может не пройти по быстродействию.
Тысяча рефератов по тысяче предложений, вот и миллион слов, с которыми надо сравнить. Слова очень длинные, да и допустимое расстояние по Левенштейну для копипаста в примере большое.
Левенштайном сравнивают ДНА, пару тысяч слво = ерунда. Сравнивайте так: расстояние / количество слов или букв. Это должно дать какой-то там коофициент.
Минус не ставил, сейчас плюсанул :)
>>Сравнивайте так: расстояние / количество слов или букв
хорошо, завтра как раз и попробую, а то этот момент больше всего и смущает.
Давайте прикинем.
Для упомянутой мной базы и реферата нужно 10^9 поисков каждый примерно в 80*40=3200 операций (50% отличие).
Итого 3*10^12 операций, т.е. где-то 6000 сек.
Вроде, приемлемо, но не ерунда.
И зависит от объема базы.
В моем примере это 70Мб, а для 700Мб получится уже 17 часов.
Может помочь метод шинглов.
Каждое предложение разбиваем на ряд n-грамм, например, триграмм. Строим хэши для триграмм. Таким образом каждому предложению соответствует несколько хэшей, для триграмм их будет k-2, т.е. в Вашем примере 8. При совпадении хэшей проверяемого предложения с хэшами какого-либо предложения из базы больше некой границы, скажем, 50%, будем считать предложение «копипастным».
У Яндекса, естественно, сложнее.
Для больших баз нужно, как минимум, убрать наиболее энтропийные слова, а также повысить вес уникальных n-грамм. Плюс учитывать и отдельные редкие слова (например, ошибки).
Я бы начал разбивать по предложению, которое переводил бы в регулярку и пробивал бы по базе куда вносил текст. Так же в одну бы регулярку все не вставлял разбил бы по порядку с эффектом точности. Базу можно использовать например MySQL (SELECT MYSQL regexp и т.д.)
habrahabr.ru/qa/11270/ вот тут пример поиска. Единственное, просмотр вперёд и назад в mysql не канает, для того, чтоб его добиться, как вариант можно использовать LIKE.
P.S. Данная задача аналогична поисковой системе, поэтому решение сильно простое искать не стоит.
В какой то степени сейчас к тому и идет, только не через полнотекстовый поиск, а просто проверкой «Содержит ли?».
Т.е. берем искомое предложение, берем текст реферата, из текста реферата удаляем все знаки препинания и приводим к нижнему регистру, далее в этом тексте ищем наше предложение, если не нашли убираем слова от начала предложения до тех пор пока не найдем или не останется меньше 3 слов. Если не нашли, то ту же операцию повторяем, только удаляем уже с конца предложения.
В принципе этот алгоритм работает, но может есть другие более простые и по скорости быстрее способы.
Можно построить хеш-таблицу (или другую структуру, например, сложить в БД), содержащую все предложения из базы рефератов, а также все их достаточно длинные префиксы и суффиксы. То есть для предложения «мама мыла раму вчера вечером» в хеш-таблицу можно сложить предложения
«мама мыла раму вчера вечером»
«мыла раму вчера вечером»
«раму вчера вечером»
«мама мыла раму вчера»
«мама мыла раму».
Когда надо проверить предложение на баянистость, так же размножаем его на набор предложений, полученных из него удалением слов в начале или конце. Для каждого проверяем, есть ли оно в хеш-таблице. Если какое-то есть, наше предложение, возможно, баян. Более того, чем больше совпало, тем более вероятно, что предложение похоже на существующие в базе. Это должно работать достаточно быстро: предложения будут размножаться в среднем на 10-15, то есть индекс (хеш-таблицы) будет занимать примерно в 10-15 раз больше чем исходные тексты, а проверка предложения на баянистость будет сводиться к 10-15 поискам предложения в хеш-таблице. Можно вместо слов хранить их айдишники, уменьшив занимаемое место и время в несколько раз.
Простой
Простой
Простой
