Процентная похожесть строк.

← →
Гость из солнечной Алматы (2003-01-27 12:51) [0]

Требуеться function(procedure) которая могла бы сопоставить
две строки и выдать результат в процентном соотношение.

Типа

стр1 Корова
стр2 Карова

результат строки совпадают на 80%

Заранее благодарен.

← →
REA (2003-01-27 12:59) [1]

А корова и орки насколько? Что считать похожестью? Звучание?
Можно наверно посчитать спектры букв и сравнить как то.

← →
Гость из солнечной Алматы (2003-01-28 07:35) [2]

Ну если по большому счету, то я видел такую функцию в PHP.
И я думаю похожесть строк там основана не только на частоте
встречаемости одних и тех же букв в двух строках.
Но также зависит от порядка их следования.То есть

abc и abc 100%
abc и bca 66%

Большинство алгоритмов по-буквенного сравнения
не являються оптимальными.
На мой взгляд некий универсальный алгоритм будет включать
в себя частоту встречаемости,порядок следования и сравнение
длины двух строк.

Далее могу добавить лишь только, что алгоритм разработан
Оливером в 1993г.

← →
Separator (2003-01-28 07:58) [3]

Кстати в Алматы сейчас не так уж много солнца

← →
Гость из солнечной Алматы (2003-01-30 14:52) [4]

Да, в Алмате идет... вот прямо сейчас ... снег... Много снега...
Давайте не будем кидать Офтопики.Просто уважаемый Separator
я был жутко разочарован когда увидел, что моя надежда на
дельный совет с очередным сообщение не оправдалась.

Delphi код который делает анализ строки исходя из длины двух
слов,конечно, кривовато но если использовать SoundEx в Дельфях
то может быть будет более менее.

function LCS_Length(s1,s2:string):integer;
var m,n : integer;
LCS_Len_Tab : array[0..128,0..128] of integer;
i,j : integer;
begin
m:=length(s1);
n:=length(s2);
for i:=1 to m-1 do LCS_Len_Tab[i,0]:=0;
for j:=1 to n-1 do LCS_Len_Tab[0,j]:=0;

for i:=1 to m do
begin
for j:=1 to n do
begin
if (s1[i-1]=s2[j-1]) then LCS_Len_Tab[i,j]:=LCS_Len_Tab[i-1,j-1]+1
else if (LCS_Len_Tab[i-1,j]>=LCS_Len_Tab[i,j-1]) then LCS_Len_Tab[i,j]:=LCS_Len_Tab[i-1,j]
else LCS_Len_Tab[i,j]:=LCS_Len_Tab[i,j-1]+1;
end;
end;
LCS_Length:=LCS_Len_Tab[m,n];
end;

function get_lcs(s1,s2:string):real;
var lcs:integer;
ms:real;
begin
s1:=lowercase(s1);
s2:=lowercase(s2);
lcs:=LCS_Length(s1,s2);
ms:=(length(s1)+length(s2))/2;
get_lcs:=((lcs*100)/ms);
end;

Процентная похожесть строк. Найти похожие ветки