Идентификация похожих строк

[[subway]design]

Привет!

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

Вот, что я придумал:
В каких случаях строки "похожи":

0) Если строки равны.
1) Если заголовки отличаются только пробелами.
2) Если какой-то кусок строки определенной длины повторяется.

Есть еще повод также проверять тело поста, но это долго работает.

Хочется узнать от вас добавку.

[Crazy]

У тебя пользователи действительно регулярно -- с интервалами не в несколько минут, а принципиально больше -- постят идентичные сообщения?

Это форум психиатрической лечебницы?

[[subway]design]

2 Crazy: я спрашиваю о технологии, а не о том какой у меня форум.

[Crazy]

Я не наезжаю. Я намекаю, что решения зависят от причин.

Например, если дубли создаются ввиду плохой связи -- это вполне реальная причина -- то для предотвращения их появления можно использовать механизм "мандатов на публикацию". Схема такова:

1. Когда пользователь запрашивает создание нового сообщения, мы генерим мандат -- некое случайное число большой длины (длина защищает от подбора) -- и передаем его hidden-полем в форме, сохраняя, разумеется, на стороне сервера.

2. Когда от клиента приходят данные нового сообщения -- мы проверяем, выдан ли такой мандат. Если нет -- запрос не обрабатывается. Если мандат подтвержден -- добавляем постинг и уничтожаем мандат.

Схема может быть дополнена таймаутом -- ограничением времени жизни мандатов периодом в 3-4 часа.

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

[[subway]design]

Млииин!

Допустим, у меня нет форума. Допустим у меня скрипт получает из ниоткуда две строки $a и $b... Мне хочется проверить "похожи" ли они или нет. Естественно, "похожесть" - это субъективное понятие, но хочется выяснить технологию. Вот.

зы: но спасибо за участие :)

[Crazy]

1. Удаляем все пробелы и переводим в единый регистр (верхний или нижний -- неважно).
2. Сравниваем сдева направо, сравнивая буквы по двум притериям: первое -- на равенство, второе: считая буквы одинаковыми, если они находятся на одной или соседних клавишах калвиатуры. Пример: буква "Л" эквивалента любой из: "ГШЩОЛДЬБЮUIOJKLM<>". Считаем, что можем N раз проигшнорировать первое несовпадение при успешном втором (обычно N -- 1-3).

Где-тол попадался алгоритм, которые чует пропуски букв и лишние буквы, но он сложный и я его не помню. Да и этот не особо устойчив.

[[subway]design]

Спасибо. Я еще вот что придумал: надо запихать в массивы слова из обеих строк (каждой строке - один массив) и посмотреть сколько слов совпадает.

[Crazy]

Если тебя не волнует возможность очепяток.

[[subway]design]

Тогда нужна функция "идентификации похожих слов":

1) Чтобы некое кол-во букв из одного слова присутствовало в другом слове
2) Чтобы некоторое количество первых букв совпадало. Это количество может быть относительным, например 25% слова.