Алгоритм сравнения строк

← →
Dimedrol © (2005-12-12 15:09) [0]

Коллеги, у меня есть задача: найти среди нескольких тысяч текстовых записей (<=200 знаков) похожие.

Я испробовал мой, где-то скачанный давным давно алгоритм сравнения строк, который выдает "похожесть" строк в процентах (очень полезная вещь!), но на 3000 тысячах записей,
он ооооооочень медленно работает.
Фактически, он работает почти 1 час.
Это медленно.
(могу кинуть исходник)

Пробовал SoundEX, причем написал DLL-ку на FreePas.
Все классно. Работает очень быстро, но очень не точно!
Т.к. если строках (<=200 знаков) 2-е слово разное,
то это уже - разное значение на выходе.
Это - не подходит.

И вот - хотел посоветоваться, - какие есть алгоритмы
для выполнения подобных задач ?
Я готов проверить все. :-)
По скорости.
Т.к. сейчас - в тупике.

PS
В моем алгоритме и в SoundEx я русский текст, да и вообще - весь текст, перевожу в заглавную латиницу, чтобы
не иметь проблем с языками.

← →
Tor © (2005-12-12 16:13) [1]

Простые вопросы перекручивают в заумные.
Что значит "похожие"? Что бы в них одинаковые буквы были или что? :)

← →
TUser © (2005-12-12 16:14) [2]

Ищи по ключевым словам "выравнивание" и "неточное сравнение строк".

← →
Jeer © (2005-12-12 16:31) [3]

Вероятно, среди 200 символов надо отыскать смысловое содержание, похожее на еще какие-то 200 символов и так - все тома "Война - им мир":))

← →
Dimedrol © (2005-12-12 16:52) [4]

2 Tor © & Jeer ©
"похожие", это значит, - даешь на вход 2 строки -
1. Мама мыла раму
2. Мама мыла Рому

И мой алгоритм "говорит", что - "мне переданы строки, похожие на 92%"!
Этот алгоритм у меня есть!
Только - медленный.

← →
Tor © (2005-12-12 17:04) [5]

Че один символ это уже целых 8% ? :)
Ищи подстроку в строке, полубому тебе сравнивать все тома "Война и мир" сами с собой. А как ты там будеш процентное отношение получать это уже ... . Хоят зачем тебе процентное отношение? Мне кажеться это ни кому и ни где не нужно.
Если есть готовый алгоритм, проверь где он медлит и упрости ток участок, возможно это будет быстрее чем снова все придумавать. Всеравно тоже самое получится.

← →
Jeer © (2005-12-12 17:07) [6]

А так - это тоже похожие ?

раму мама рыла

← →
Tor © (2005-12-12 17:18) [7]

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

← →
Leonid Troyanovsky © (2005-12-12 18:19) [8]

> Dimedrol © (12.12.05 16:52) [4]

> Этот алгоритм у меня есть!

Если это не А.Л. Грибов. "Простой алгоритм для решения задачи
идентификации символьных выражений" ,то, возможно, стоит
посмотреть и его:

http://rsdn.ru:80/File/13030/Probably2.doc

Во всяком случае, этот подход основан на некоторой
интуитивно-понятной модели.

Ну, а, вообще, чем более тщательно сформулированы условия
подобной задачи, тем больше шансов, IMHO, найти
правдоподобный ответ.

Т.е., например, можно попробывать искать:
алгоритмы нечеткого сравнения (поиска) строк.

--
Regards, LVT.

← →
Verg © (2005-12-12 19:39) [9]

{
>> Расстояние (разность) между двумя строками. Функция Левенштейна
***************************************************** }

const cuthalf = 100; // константа, ограничивающая макс. длину
// обрабатываемых строк

var buf: array [0..((cuthalf * 2) - 1)] of integer; // рабочий буффер, заменяет
// матрицу, представленную
// в описании

function min3(a, b, c: integer): integer; // вспомогательная функция
begin
Result := a;
if b < Result then Result := b;
if c < Result then Result := c;
end;

// реализация функции в принципе соответствует описанию с одной оговоркой:
// матрица из описания заменена статическим буффером, длина которого
// равна удвоенной максимальной длине строк
// это сделано для 1) экономии памяти и во избежание её перераспределений
// 2) повышения быстродействия (у меня функция работает
// в обработчике onfilterRecord)
// таким образом, в реализации половинами буффера представлены только
// две последние строки матрицы, которые меняются местами каждую
// итерацию внешнего цикла (по i)... для определения того, какая из половин
// буффера является "нижней строкой", служит переменная flip
// т. е. при flip = false первая половина буффера является предпоследней
// строкой, а вторая - последней; при flip = true наоборот,
// первая половина - последняя строка, вторая половина - предпоследняя

function LeveDist(s, t: string): integer;
var i, j, m, n: integer;
cost: integer;
flip: boolean;
begin
s := copy(s, 1, cuthalf - 1);
t := copy(t, 1, cuthalf - 1);
m := length(s);
n := length(t);
if m = 0 then Result := n
else if n = 0 then Result := m
else begin
flip := false;
for i := 0 to n do buf[i] := i;
for i := 1 to m do begin
if flip then buf[0] := i
else buf[cuthalf] := i;
for j := 1 to n do begin
if s[i] = t[j] then cost := 0
else cost := 1;
if flip then
buf[j] := min3((buf[cuthalf + j] + 1),
(buf[j - 1] + 1),
(buf[cuthalf + j - 1] + cost))
else
buf[cuthalf + j] := min3((buf[j] + 1),
(buf[cuthalf + j - 1] + 1),
(buf[j - 1] + cost));
end;
flip := not flip;
end;
if flip then Result := buf[cuthalf + n]
else Result := buf[n];
end;
end;

← →
Dimedrol © (2005-12-13 15:22) [10]

Verg !
Большое спасибо за код!
Я тут поискал по сети на "fuzzy search", и думаю что именно FUZZY -
это то что мне больше поможет.

Т.к. при вычислении Функции Левенштейна, иногда в очень похожих
строчках нужно сделать довольно большое кол-во изменений,
чтобы преобразовать одно в другое.
Думаю, что "Левенштейн" больше подходит для устранения ошибок
набора.

В моем случае - это немного другое.
Дело в том, что мне нужно выявить (и показать администратору)
дубликаты объявлений, поданных на сайт.
Ну или очень похожие объявления, т.к. хитро-попых ребят везде хватает. :-)

Для большей ясности - привожу свой код (FreePas, Delphi...)-

program sym; {$MODE OBJFPC} uses SysUtils; Type TRetCount = record lngSubRows : integer; lngCountLike : integer; end; var r:integer; function ReplaceChars(CString: PChar;scr: PChar;dest: PChar):PChar; var i,j:integer; begin i:=0; while (CString[i]<>#0) do begin j:=0; while (scr[j]<>#0) do begin if CString[i]=scr[j] then begin CString[i]:=dest[j]; Break; end; inc(j); end; inc(i); end; result:=CString; end; function MyUpper(src:PChar): PChar; const small_chars:PChar="abcdefghijklmnopqrstuvwxyzабвгдеёжзийклмнопрстуфхцчшщъыьэюяў¤¦є°іµљЅї"; big_chars:PChar= "ABCDEFGHIJKLMNOPQRSTUVWXYZАБВГДЕЁЖЗИЙКЛМНОПРСТУФХЦЧШЩЪЫЬЭЮЯЎЈҐЄ¬ЇІґЉјѕ"; begin Result:=ReplaceChars(src,small_chars,big_chars); end; function Matching(StrInputA: String; StrInputB: String; lngLen: Integer) : TRetCount; Var TempRet : TRetCount; PosStrB : Integer; PosStrA : Integer; StrA : String; StrB : String; StrTempA : String; StrTempB : String; p1,p2:pchar; begin StrA := StrInputA; StrB := StrInputB; TempRet.lngCountLike:=0; TempRet.lngSubRows:=0; For PosStrA:= 1 To Length(strA) - lngLen + 1 do begin StrTempA:= Copy(strA, PosStrA, lngLen); PosStrB:= 1; For PosStrB:= 1 To Length(strB) - lngLen + 1 do begin StrTempB:= Copy(strB, PosStrB, lngLen); p1:=StrAlloc(length(StrTempA)+1); StrPCopy (P1, StrTempA); p2:= StrAlloc(length(StrTempB)+1); StrPCopy (P2, StrTempB); if string(MyUpper(p1))=string(MyUpper(p2)) then begin Inc(TempRet.lngCountLike); break; end end; Inc(TempRet.lngSubRows); end; // PosStrA Matching.lngCountLike:= TempRet.lngCountLike; Matching.lngSubRows := TempRet.lngSubRows; end; { function } //------------------------------------------------------------------------------ function IndistinctMatching(MaxMatching : Integer; strInputMatching: String; strInputStandart: String): Integer; Var gret : TRetCount; tret : TRetCount; lngCurLen: Integer ; //текущая длина подстроки begin //если не передан какой-либо параметр, то выход If (MaxMatching = 0) Or (Length(strInputMatching) = 0) Or (Length(strInputStandart) = 0) Then begin IndistinctMatching:= 0; exit; end; gret.lngCountLike:= 0; gret.lngSubRows := 0; // Цикл прохода по длине сравниваемой фразы For lngCurLen:= 1 To MaxMatching do begin //Сравниваем строку A со строкой B tret:= Matching(strInputMatching, strInputStandart, lngCurLen); gret.lngCountLike := gret.lngCountLike + tret.lngCountLike; gret.lngSubRows := gret.lngSubRows + tret.lngSubRows; //Сравниваем строку B со строкой A tret:= Matching(strInputStandart, strInputMatching, lngCurLen); gret.lngCountLike := gret.lngCountLike + tret.lngCountLike; gret.lngSubRows := gret.lngSubRows + tret.lngSubRows; end; If gret.lngSubRows = 0 Then begin IndistinctMatching:= 0; exit; end; IndistinctMatching:= Trunc((gret.lngCountLike / gret.lngSubRows) * 100); end; //------------------------------------------------------------------------------ begin r:=IndistinctMatching(4, "PLOTNIKI Regips-Steny,potolki,peregorodki.Poly.", "STROITELI Plotniki:-Regips-Steny,potolki,peregorodki.Poly." ); if r > 40 then writeln("Strings are seems to be match, with similarity=",r,"%") else writeln("Strings NOT match. Similarity=",r,"%"); end.

Пожалуйста не обращайте внимания на неоптимизированность некоторых функций (замены символов и т.п.). У меня есть и более оптимизированный вариант, но в принципе - производительность не повысилась "на порядок".

Так вот, берем для сравнения 2 строки (уже в translite для удобства)
"PLOTNIKI Regips-Steny,potolki,peregorodki.Poly.", и "STROITELI Plotniki:-Regips-Steny,potolki,peregorodki.Poly."

Это - 2 объявления от строителей. Похожи, не правда ли ?!

Так вот, мой алгоритм выдает следующий результат:
c:\FreePas\dima\Textmatch>sym Strings are seems to be match, with similarity=88%

По-моему - все логично.

Но! "Левенштейн" в данном случае выдает значение = 17 !
Много это или мало ?!
Трудно сказать.

Конечно же на примере:
Мама мыла раму и Мама мыла рому
"Левенштейн" "скажет" = 1.
Но как раз дело в том, что у меня могут быть разные объявы и по словам
и по длине и т.п.

Мне показалось, что Функция Левенштейна здесь не совсем подходит.

Может у кого-то есть пример FUZZY search ?

> Т.к. при вычислении Функции Левенштейна, иногда в очень
> похожих
> строчках нужно сделать довольно большое кол-во изменений,
>
> чтобы преобразовать одно в другое.

Эээ, откуда такое мнение?

Dimedrol © (13.12.05 15:22) [10]

Копай в сторону семантического распознавания текста, т.е. смыслового.
Но это на нобелевскую потянет.

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

В общем, сначала - теория.
Ищи - "компоненты языковой системы".

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

И в контексте "объявления" могут быть использованы любые их сочетания, тем не менее, правильно понимаемые читающим это объявление.

1. "Продается славянский шкаф, недорого".
2. "Имеем возможность предложить старинный платяной шкаф, гарантированно не мусульманского дизайна. Цена - ниже возможной в любом ином месте.

Не не не !!!
Ребята !!!
Все не так страшно!
Никакой нобелевской премии!

У меня уже есть(!!!) работающий алгоритм!
Проверьте его сами.
И делает он то что надо!
Только не быстро.

Мне советовали FUZZY search!
Говорят - то что надо - "нечеткий поиск".

Алгоритм сравнения строк Найти похожие ветки