LINUX.ORG.RU

Подскажите алгоритм «приблизительного» сравнения двух строк

 


2

3

В IRC чатике флудят, надо прикрутить антифлуд на повторяющиеся строки, при этом, чтобы нельзя было так просто добавить какой-нибудь символ в конец фразы и обойти антифлуд, чтобы боты посчитал, что это новая строка, хотя она на 92.8% похожа на предыдущую.

Первое, что приходит на ум — отсортировать все буквы в строках по их ASCII номеру, а потом сравнивать, правда, каким макаром, опять не знаю. :(

Подскажите пожалуйста, каким образом можно сравнить две строки и вывести процент их приблизительной похожести. Спасибо.

★★★★★

Расстояние Левенштейна обычно советуют.

arturpub ★★
()

Разве флуд не решается ограничением на количество сообщений в единицу времени? Будешь детектить изменение одного символа, станут флудить разными строками (их можно сразу из буфера обмена вставить), делов-то.

А так если именно про символы в конце строки - достаточно найти наибольший общий префикс. Если то что осталось < N (1,2) символов, значит это повторение.

slovazap ★★★★★
()

Смотри триграммы и нормализаторы типа metaphone и soundex. Нормализаторы вроде замены латинских букв в кирилических текстах тоже придётся использовать.

mashina ★★★★★
()

Можно попробовать байесовский классификатор на н-граммах.

E ★★★
()
Ответ на: комментарий от anonymous

Эта проблема элементарно решается банхаммером.

На самом деле именно так. Человек всё равно рано или поздно найдёт способ написать «ЖОПА» так, чтобы алгоритм посчитал это непохожим, а любой человек не мог не заметить сходства.

sholom
()

Да тут уже все сказали выше.

  • Во-первых — с флудом борются элементарным лимитированием. Просто почитай для начала что такое флуд.
  • Во-вторых, если ты хочешь чтобы люди не смогли вставлять йух вместо [censored] как описал cdshines, то можно применить элементарные расстояния. Я помню твои старые темы. Ты же быдлокодишь на PHP, ЕМНИП? В PHP даже есть спец. функция levenshtein, внезапно :)
    Можно набыдлокодить за пару минут годную проверку. Только словарь из нежелательных тебе слов все равно придется слить с инета. Ну или самому составить.
  • В-третьих, есть качественные решения, вроде n-gramm, но если ты делаешь это для своего знаменитого форума, то думаю они тебе не понадобятся.

В любом случае, через расстояния это можно сделать за несколько минут. Вот, я тебе даже пример реализации принес.
http://php.net/manual/en/function.levenshtein.php

znenyegvkby
()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.