Имеется большая база текстов (чуть больше 11000 текстов, средний размер текста 50Кб).
Часть текстов идентичны и отличаются только переносами строк, регистром символов, отступами от начала строки (может быть, а может не быть отступ в виде символа табуляции или пробела или нескольких табуляций/пробелов).
Часть текстов совпадают за исключением некоторой части (один текст идет полностью, а второй может быть без нескольких абзацев).


Вопрос: есть ли способ максимально автоматически найти совпадения? 
Есть ли алгоритм неточного сравнения строк, при котором на результат сравнения (скорее всего выраженный в %) не будут влиять знаки препинания, пробелы, табуляция?

Результаты такого поиска будут перепроверяться вручную. дубликаты будут удаляться тоже ручками, но искать совпадения вручную по всей базе - жестоко :(

Спасибо.

Это сообщение отредактировал(а) knyshow - 30.7.2010, 17:54

http://dev.mysql.com/doc/refman/5.0/en/replace.html 

прочитал. причем тут замена?

Вот к примеру, как будет работать поиск без учета пробелов и запятых:


Ну это общая схема, можно и регулярками.

Это сообщение отредактировал(а) CruorVult - 30.7.2010, 20:17

По частотному словарю, например.
Ну и 11000 текстов желательно будет дополнительно кластеризовать каким-нибудь алгоритмом автоматической классификации - чтобы искать тексты, ближайшие к обрабатываемому тексту, не среди всей большой кучи, а только среди кластера, к которому принадлежит этот искомый текст (ну и еще среди второго по близости к этому тексту кластера - вдруг текст окажется на "границе" и реально ближайший к нему другой текст будет в соседнем кластере)

Да - в тему не вернусь, я её случайно увидел среди новых тем, и отметился чисто ради саморекламы. 

CruorVult, тут есть еще и такая проблема.

1 текст(фильтрованый): одинтекстидетполностьюавторойможетбытьбезнесколькихабзацев
2 текст(фильтрованый): полностьюавторойможетбытьбезнесколькихабзацев

совпадение: одинтекстидетполностьюавторойможетбытьбезнесколькихабзацев

В общем нужно разбить текст, по которому будут искатся совпадения,  на куски по абзацам или предложениям(в зависимости от нужной точности), отфильтровать и по каждому куску искать совпадения(использовав фильтрацию). 

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

Не то все :(
Пасип, буду искать дальше, о результатах доложу.

ЗЫ: время на самом деле роли не играет.

Что именно не то?



1) вытягиваешь все тексты.
2) разбиваешь текст по предложениям( по "\r\n", ".", если надо то "\t" ) и сравниваешь каждое предложение данного теста с каждым предложением всех остальных.(предварительно отфильтровав ненужные знаки)
3) подситываешь количество совпавших предложений( вот тебе и процент от общего количества предложений в тексте).
4) формируешь массив данных, что-то типа:  



Главное немного включить мозги и не надо никуда бегать за какими-то алгоритмами   

сам с аппаратом сравнения не знаком. просто поискал в google за тебя:
алгоритм шинглов: раз и два
алгоритм Рабина-Карпа

Сорри что пропал.
Задачу решил следующим образом:

- из базы в массив выгребаются все тексты;
- из текстов удаляются все символы, не отвечающие шаблону [A-Za-zА-Яа-я0-9];
- ну, а дальше самое смешное:



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

CruorVult, спасибо за идею!



skyboy, поверь, я там был)
данные алгоритмы конфузятся при сравнении текстов, идентичных изначально, но в случае, когда один текст представляет собой мАлую часть второго.

Это сообщение отредактировал(а) knyshow - 12.8.2010, 20:00