Анализ и сравнение текстов.

Думается, используют библиотеки регулярных выражений.

Смотря какие тексты. Если большие, больше нескольких абзацев, то однозначно (почти) алгоритм шинглов (чешуек). Если короткие — то приходиться плясать вокруг ключевых слов. Если одно слово — soundex/DM. Если сравнить два слова — Левенштейн.

Это я про задачу поиска похожих текстов из БД. А что нужно собственно вам?

А, и ещё - насколько это затратно в плане вычислительных мощностей?

Что за анализ и что за сравнение? Они разные бывают. Переводчик тоже тексты анализирует и сравнивает для подписывания у нотариуса утверждения об их идентичности.

Ну, к примеру, есть база рефератов и при добавлении нужно проверять, насколько данная конкретная работа уникальна.

> А, и ещё - насколько это затратно в плане вычислительных мощностей?

Сначала опишите что у вас есть. Какие по размеру тексты, сколько их. Чешуйки пакуются в crc, но их получается много, миллионы записей на тысячи текстов. Соотвественно памяти нужно сотни мегабайт под индексы (говорю с позиций web-dev). Вообщем, затраты средние я бы сказал.

Ну да, скорее с позиции веба и нужно. Ну берём стандартный размер реферата в 20-30 страниц. В базе по данной теме рефератов несколько тысяч, возможно даже десятков тысяч. Ну и вот. И при этом, единовременно этим не один человек ведь должен иметь возможность пользоваться.

> Ну, к примеру, есть база рефератов и при добавлении нужно проверять, насколько данная конкретная работа уникальна.

Чешуйки однозначно. Только не забывайте предварительно обрабатывать: убрать все пробельные символы, полностью в транслит (хитрые студенты идут лесом) и т.п. С помощью чешуек можно найти тексты по убыванию похожести. Можно и какой-либо индекс похожести вычислять.

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

Ну в принципе, по пересказу то да, понятно. Это, если что, питоновскую либу natural language toolkit надо будет потыкать. Вот только не уверен я, что она может работать с чем-то кроме английского:(

> Ну, к примеру, есть база рефератов и при добавлении нужно проверять, насколько данная конкретная работа уникальна.

http://en.wikipedia.org/wiki/Longest_common_subsequence_problem ?

я так понял, что нужно в первую очередь семантическое сравнение - поиск общих подпоследовательностей здесь не катит

> Ну да, скорее с позиции веба и нужно. Ну берём стандартный размер реферата в 20-30 страниц. В базе по данной теме рефератов несколько тысяч, возможно даже десятков тысяч. Ну и вот. И при этом, единовременно этим не один человек ведь должен иметь возможность пользоваться.

Скучная до зевоты задача. Когда вам говорят решение, вы ленитесь даже слегка погуглить, да?

http://habrahabr.ru/blogs/algorithm/65944/

http://habrahabr.ru/blogs/development/52120/

http://www.codeisart.ru/python-shingles-algorithm/

Десятки тысяч — смешно, конечно. Метров сто на индексы хватит.

> я так понял, что нужно в первую очередь семантическое сравнение - поиск общих подпоследовательностей здесь не катит

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

почему же?.. если элементами массивов считать не символы, а слова, то при при длине LCS > 80% длины входного текста можно почти с уверенностью сказать, что кто-то у кого-то содрал ;)

> почему же?.. если элементами массивов считать не символы, а слова, то при при длине LCS > 80% длины входного текста можно почти с уверенностью сказать, что кто-то у кого-то содрал ;)

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

такие проверки рефератов легко взломать. достаточно хорошенько переставить местами слова в тексте.

А на фига это надо? Все эти системы против плагиата бесполезны - студентишки очень изобретательны, когда надо обмануть (и вовсе не так умны, когда надо по честному что-то сделать). Так что уж лучше выборочные проверки.

> такие проверки рефератов легко взломать. достаточно хорошенько переставить местами слова в тексте.

если после такой (хорошенькой) перестановки реферат будет читаем, то можно и 5 поставить, фигня вопрос :) (ведь по сути реферат это и есть «перестановка слов» из первоисточников + немножко «клея».) а если его никто читать не будет, и нечто вроде cat /dev/random >~/referat.txt сойдёт, то смысл в самой проверке на плагиат?

>из первоисточников + немножко «клея».

а как же выводы?

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

каким именно анализом и как именно задействованы нейронные сети для этого анализа?

О, за последний линк вообще огромное спасибо - всё очень доходчиво:)