Поиск и сравнение оригинальных текстов

[jeka!]

Поиск и сравнение оригинальных текстов

Информация к размышлению!!!
Анекдоты :: пользовательский ввод.

В общем, имеется БД анектотов, колличество 6000 штук.
Посетитель может записывать свои, но, как правильно проверить, имеется ли этот анекдот уже в БД???

Я сделал примитивно, просто создал в таблице дополнительное поле с ограничением 200 символов, уникальное, и туда дописывается часть анекдота.
И при добавлении, если этот текст уже был, то он ессно не добавляется.
Но если изменить хоть одну букву, то всё пролезет.

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

 

[Silent]

Насколько я помню, один человек это делал (именно для анекдотов) и где-то в сети было описание алгоритма. Но оно меня тогда не интересовало, поэтому я даже на диск не сохранил. Поищи в Яндексе.

 

[jeka!]

Ну я описал что это как бы информация к размышлению, анекдоты это пример.
А так может быть всё что угодно.
Не помнишь название того что изобрел тот человек, или по каким ключевым словам хоть поискать?

 

[jeka!]

Нашел, но там чел писал на FoxPro, я его не понимаю...
По сути наверное он использует тот же метод, разбиение и сравнение слов в процентном варианте.
Хотя наверное по другому не сделаешь...

 

[Silent]

Задача конечно интересная, но так сразу ее не решишь. Тут думать надо, потом писать, потом долго тестировать, коэффициенты подбирать. Наверное можно придумать какие-нибудь сигнатуры, а потом их сравнивать на неполное сходство. Или что-то на основе "n"-грамм.

 

[Silent]

Да, вот еще что можно сделать (это если речь идет именно об анектодах): составить небольшой словарик из наиболее "употребимых" слов, вроде "любовник", "Чапаев", "программист", "Штирлиц" и т.п. И при занесении анекдота в базу присваивать ему категорию на основе того, какие из этих слов в нем есть (не исключено, что некоторые анектоды подойдут сразу к нескольким категориям). А при сравнении можно сразу выбросить те категории, которые явно нам не подходят.

 

[Silent]

Или такой вариант: похожие анекдоты наверняка имеют несколько совпадающих слов (сколько "должно" совпасть нужно эмпирически подбирать). Делаем классический инвертированный индекс (как в поисковой системе) и для нового анекдота ищем в индексе те анекдоты, где есть слова из нового. Получаем список ID, выбрасываем из этого списка те ID, которые встречаются в нем меньше 10 (или сколько-нибудь) раз. Теперь есть список анекдотов, которые как минимум на 10 слов совпадают с новым. Их уже проверяем более изощренными методами.

 

[Nime]

А как насчёт FULLTEXT Search?
http://www.mysql.com/doc/en/Fulltext_Search.html

 

[Tronyх]

А как насчёт FULLTEXT Search?

Но если изменить хоть одну букву, то всё пролезет.

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

А что если хранить md5 хеш этих слов? И сделать индекс по этому полю.
Ещё нужно хорошо продумать обработку текста:
Переводить в нижний регист
Заменять "особые" синонимы (програмёр -> программист)
Удалять кавычки, смайлики и т.п.

 

[young]

Не помню где, может у кнута, был алгоритм вычисления "похожести" строк. Может его использовать? Скажем, если коэффициент похожести > 0.9, Считать их одинаковыми.

 

[tony2001]

[m]soundex[/m] и иже с ним ?

 

[slach]

http://php.net/manual/en/function.levenshtein.php

 

[jeka!]

Да, ссылок конечно вы надавали немало, надо бы всё это дело переварить...
Я тут вот пока как продвинулся в этом направлении:
Решил сначала разделить текст на слова, выбросить все приставки и прочее ненужное, и оставить только значимые слова, существительные, глаголы, прилагательные и перевести все эти словоформы в базовую форму, пример:
машин машине машину машины машинам машинами машинах - машина
В общем поискал словари, и наткнулся только на 1 заинтересовавший меня, тем более уже готов на PHP & Perl
http://risearch.org/rus/rumor/index.html
Правда это демка, урезана и медленная, но всё же для тестов пока потянет.
А уже полученные результативные слова, можно сравнивать с текстами в БД.
И соответственно выводить процент похожести.
На счёт бинарных БД, у меня пока гемор с этим, небыло соответствующего опыта, поэтому рад любому "научению".
В общем скорость по любому очень мала.

 

[Silent]

> Правда это демка, урезана и медленная, но всё же для тестов пока потянет.

Гм... 5000 слов в секунду тебе мало? А быстрее я нигде не видел. Тогда ищи бинарник на Си, он будет быстрее.

> В общем скорость по любому очень мала.

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