Смотря какие тексты. Если большие, больше нескольких абзацев, то однозначно (почти) алгоритм шинглов (чешуек). Если короткие — то приходиться плясать вокруг ключевых слов. Если одно слово — soundex/DM. Если сравнить два слова — Левенштейн.
Это я про задачу поиска похожих текстов из БД. А что нужно собственно вам?
Что за анализ и что за сравнение? Они разные бывают. Переводчик тоже тексты анализирует и сравнивает для подписывания у нотариуса утверждения об их идентичности.
> А, и ещё - насколько это затратно в плане вычислительных мощностей?
Сначала опишите что у вас есть. Какие по размеру тексты, сколько их. Чешуйки пакуются в crc, но их получается много, миллионы записей на тысячи текстов. Соотвественно памяти нужно сотни мегабайт под индексы (говорю с позиций web-dev). Вообщем, затраты средние я бы сказал.
Ну да, скорее с позиции веба и нужно. Ну берём стандартный размер реферата в 20-30 страниц. В базе по данной теме рефератов несколько тысяч, возможно даже десятков тысяч. Ну и вот. И при этом, единовременно этим не один человек ведь должен иметь возможность пользоваться.
> Ну, к примеру, есть база рефератов и при добавлении нужно проверять, насколько данная конкретная работа уникальна.
Чешуйки однозначно. Только не забывайте предварительно обрабатывать: убрать все пробельные символы, полностью в транслит (хитрые студенты идут лесом) и т.п. С помощью чешуек можно найти тексты по убыванию похожести. Можно и какой-либо индекс похожести вычислять.
Но это, конечно, не спасет от просто пересказа содержимого предыдущего реферата. Т.е. трудолюбивый, но тупой студент, систему обойдет. Чешуйки могут найти лишь насколько скопи-пастено. Есть какие-то заумные работы по построению связей на основе смысла текста, но я всего лишь говнопэхапэкодер.
Ну в принципе, по пересказу то да, понятно. Это, если что, питоновскую либу natural language toolkit надо будет потыкать. Вот только не уверен я, что она может работать с чем-то кроме английского:(
> Ну да, скорее с позиции веба и нужно. Ну берём стандартный размер реферата в 20-30 страниц. В базе по данной теме рефератов несколько тысяч, возможно даже десятков тысяч. Ну и вот. И при этом, единовременно этим не один человек ведь должен иметь возможность пользоваться.
Скучная до зевоты задача. Когда вам говорят решение, вы ленитесь даже слегка погуглить, да?
почему же?.. если элементами массивов считать не символы, а слова, то при при длине LCS > 80% длины входного текста можно почти с уверенностью сказать, что кто-то у кого-то содрал ;)
> почему же?.. если элементами массивов считать не символы, а слова, то при при длине LCS > 80% длины входного текста можно почти с уверенностью сказать, что кто-то у кого-то содрал ;)
Да, только нужен ведь мгновенный поиск. Не будете же каждый раз делать сравнение со всеми остальными тысячами? Шинглы как раз и будут это решать.
А на фига это надо? Все эти системы против плагиата бесполезны - студентишки очень изобретательны, когда надо обмануть (и вовсе не так умны, когда надо по честному что-то сделать). Так что уж лучше выборочные проверки.
> такие проверки рефератов легко взломать. достаточно хорошенько переставить местами слова в тексте.
если после такой (хорошенькой) перестановки реферат будет читаем, то можно и 5 поставить, фигня вопрос :) (ведь по сути реферат это и есть «перестановка слов» из первоисточников + немножко «клея».) а если его никто читать не будет, и нечто вроде cat /dev/random >~/referat.txt сойдёт, то смысл в самой проверке на плагиат?