Сравнение текста на идентичность

[Skif]

Собственно сабж. Стоит задача сравнить два документа в текстовом формате на идентичность. В случае совпадения хотя бы на 50 процентов - документы признаются идентичными.

Простой пример. Берем любой текстовый документ. Удаляем из него несколько предложений. Несмотря на их отсутствие, этот и исходный документ все таки одно и тоже.

Как произвести сравнение? Может есть подходящие модули? Буду благодарен за любую помощь.
:beer:

P.S.: Да. Самый тривиальный способ, что напрашивается - создать массив/хеш слов, что встречаются в документе и их количество. И на разнице сыграть. Вот только умозаключения все же подсказывают ненадежность такого решения Да и не такое уж оно тривиальное в плане написания.

[commander]

Skif
может стоит разделить текст на предложения и работать с ними?

P.S. точнее определи задачу... это мне допустим мало что говорит:

В случае совпадения хотя бы на 50 процентов - документы признаются идентичными.

[cr4ck3r]

perldoc File::Compare

[Green Kakadu]

http://forum.searchengines.ru/showthread.php?postid=778982#post778982
http://company.yandex.ru/articles/article7.html

.

Skif:
P.S.: Да. Самый тривиальный способ, что напрашивается - создать массив/хеш слов, что встречаются в документе и их количество. И на разнице сыграть. Вот только умозаключения все же подсказывают ненадежность такого решения Да и не такое уж оно тривиальное в плане написания.

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

[Skif]

Скажем так основная задача - сравнения ряда веб-страничек на идентичность. Пояснюсь. Например, я имею скачанные странички с нескольких серверов, условимся, что серверов пока 10, на каждом не менее 50 страниц. И того 500 страниц текста. Мне необходимо проверить совпадает в них текст или нет (то есть сначала отпарсивается текст со страниц и сохраняется либо в базу либо в текстовый файл, потом, полученные документы проверяются на идентичность) тривиальный пример:
Первая страница
http://www.opennet.ru/base/net/postfix_per_user_acl.txt.html
Вторая страница.
http://skif.in.ua/cgi-bin/article.pl?lang=rus&text=postfix_permission_

Основной текст полностью идентичен. За исключением пары предложений. Но имеется определенный муссор, который не совпадает. Например в OpenNet-овском варианте присутствуют заголовки письма, а на основном сервере их, по понятным причинам нет. Ну и так далее по мелочам. Вот мне и нужно доказать, что странички вообще-то копии друг дружки за рядом исключений, и копию убрать.

[Skif]

Green Kakadu
http://company.yandex.ru/articles/article7.html

И почему я нечеткую математику с нейронными сетями завалил? Эх... Похоже оно

Да, если я не сильно наглею, можно что нить в этом духе еще подкинуть. Буду премного благодарен.
Насчет того, что это не перловая задача... Не знаю, поставили и надо решить.

[Green Kakadu]

обзор методов кластеризации документов:
http://www.dialog-21.ru/Archive/2001/volume2/2_26.htm

И глянь тут:
http://forum.searchengines.ru/showthread.php?postid=30367#post30367

 Существует два подхода определения близости двух документов - на основе статистической модели (мера косинуса - LSA/LSI/PLSA и т.д.) и технологии, основанные на знаниях.
Стандартный алгоритм определения близости - можно рассчитать меру косинуса угла между двумя документами

Для кластеризации документов есть модуль: AI::Categorizer - Automatic Text Categorization в котором реализованы различные алгоритмы классификации документов, но они основаны на знаниях (т.е. вначале скармливается надор уже готовых документов) и предназначены для классификации документа, т.е. насколько документы близки друг другу по тематике, а не определения близости.

[Green Kakadu]

Skif:
Насчет того, что это не перловая задача... Не знаю, поставили и надо решить.

сама задача довольно ресурсоемка и если объемы для сравнения большие, то будет это делаться довольно долго

[Skif]

Ну в принципе исходя из этого я вижу такую систему так(пока оставим в стороне математику), получается: Либо распаралеливание на потоки и обработку в них и соответственно не менее 2-х процессоров. Либо почти тоже, но вот выкачка документов и локальное зеркало - при помощи перла, а все остальное на старом добром Си++
Хотя это все лирика
Насчет модуля. интересный. Но у меня создается впечатление, да и вы своим тезисом его подтвердили, что там задействован все же принцип нейронных сетей.
А это не самый удачный вариант При сравниваемых значениях близких к 0 на этапе "скармливания" это может дать большую вероятностную ошибку на выходе для реального документа. Что есть не очень Гуд.
То есть нужно будет заранее скормить похожие, но очень контрастные документы. Например, мой пример сразу же не подойдет - они слишком похожи и в итоге на реальном документе ошибка будет огромной.

А вообще огромное спасибо. Все же полистав линки я все больше убеждаюсь - в лоб не решить - очень много математики. Придеться почитать  

[Skif]

Green Kakadu
И отдельное спасибо за http://forum.searchengines.ru
Оч познавательно

[Green Kakadu]

Если еще нужно, то на днях прочитал статейку в которой описан довольно интересный алгоритм на эту тему. Прочитать можно здесь:
  И. В. Сегалович Как работают поисковые системы
Статья интересная, а в конце статьи, в параграфе Качество индекса описан алгоритм «шинглов»

Для каждого десятисловия текста рассчитывается контрольная сумма (шингл). Десятисловия идут внахлест, с перекрытием, так, чтобы ни одно не пропало. А затем из всего множества контрольных сумм (очевидно, что их столько же, сколько слов в документе минус 9) отбираются только те, которые делятся на, скажем, 25. Поскольку значения контрольных сумм распределены равномерно, критерий выборки никак не привязан к особенностям текста. Ясно, что повтор даже одного десятисловия – весомый признак дублирования, если же их много, скажем, больше половины, то с определенной (несложно оценить вероятность) уверенностью можно утверждать: копия найдена! Ведь один совпавший шингл в выборке соответствует примерно 25 совпавшим десятисловиям в полном тексте!

[Skif]

Спасибо, нужно. Даже очень.