-= нечеткое сравнение строк =-

← →
WST (2005-09-14 21:29) [0]

Представте, что у вас 2 строчки с текстом. Вам нужно сравнить насколько они совпадают. Они могут иметь разную длинну, символы, буквы, цифры. А мне необходимо узнать насколько процентов одна строка "похожа на вторую". Нужно мне это чтобы если человек введет вместо слова Мастера ДЕЛФИ, например, Мастра Делви или чтото в этом роде. Я уже долго пытаюсь что-то такое написать. Не получаеться. Подскажите, МАСТЕРА, плз.

← →
kami © (2005-09-14 21:40) [1]

Из ветки
http://delphimaster.net/view/1-1115465140/&web=1
//------------------------------
Функция вычисляющая в процентах схожесть двух строк..
infom © (07.05.05 15:25)

Я как-то очень давно видел здесь упоминание об этой функции, но к сожалению найти её не смог... помогите плиз найти или где искать !
//-----------------------------------------------
[1] Slym © (07.05.05 15:32)
/*
Нечеткое сравнение строк
Авторство:
(c) N!ghtmare [nightmare2000@pisem.net]
*/
macro ПоискСовпаденийВСтроке(Стр1, Стр2, МаксПодстрока,ЧК,ЧС)
НомерСимволаСтр2 = 1;
while (strlen(substr(Стр2,НомерСимволаСтр2,МаксПодстрока))==МаксПодстрока)
НомерСимволаСтр1 = 1;
Выход = 0;
while ((Выход ==0) and (strlen(substr(Стр1,НомерСимволаСтр1,МаксПодстрока))==МаксПодстрока))
if (substr(Стр1,НомерСимволаСтр1,МаксПодстрока)!=substr(Стр2,НомерСимволаСтр2,МаксПодстрока))
НомерСимволаСтр1 = НомерСимволаСтр1 + 1;
else
ЧС = ЧС + 1;
Выход = 1;
end;
end; // строка а
ЧК = ЧК + 1;
НомерСимволаСтр2 = НомерСимволаСтр2 + 1;
end; // строка б
SetParm(3, ЧК);
SetParm(4, ЧС);
end;

macro НечеткоеСравнениеСтрок(МаксДлинаПодстроки,Стр1,Стр2);
if ((МаксДлинаПодстроки<=0) or (trim(Стр1)=="") or (trim(Стр2)==""))
return 0;
end;
ЧК = 0; // Число комбинаций
ЧС = 0; // Число совпадений
ДлинаПодстроки = 1;
while (ДлинаПодстроки<=МаксДлинаПодстроки)
ПоискСовпаденийВСтроке(Стр1,Стр2,ДлинаПодстроки,ЧК,ЧС);
ПоискСовпаденийВСтроке(Стр2,Стр1,ДлинаПодстроки,ЧК,ЧС);
ДлинаПодстроки = ДлинаПодстроки + 1;
end;
if (ЧК == 0)
return 0;
end;
return double(ЧС)/double(ЧК);
end;

macro FuzzyCompareString(S1,S2)
rez=НечеткоеСравнениеСтрок(3, trim(S1), trim(S2));
println("Процент совпадения: "+(rez*100));
end;

//FuzzyCompareString("ABDUL RAHMAN YASIN","ABDUL RAHMAN");
//----------------------------------------------------------------------
[2] infom © (07.05.05 15:35)

Спасибки !
//-------------------------------------------------------------------

← →
kami © (2005-09-14 21:46) [2]

[3] Nik_vr (07.05.05 18:41)

Где нашел - не помню...

//-----------------------------------------------------------
//MaxMatching - максимальная длина подстроки (достаточно 3-4)
//strInputMatching - сравниваемая строка
//strInputStandart - строка-образец

// Сравнивание без учета регистра
// if IndistinctMatching(4, "поисковая строка", "оригинальная строка - эталон") > 40 then ...
type
TRetCount = packed record
lngSubRows: Word;
lngCountLike: Word;
end;

//--------------------------------------------------------------

function Matching(StrInputA: WideString;
StrInputB: WideString;
lngLen: Integer): TRetCount;
var
TempRet: TRetCount;
PosStrB: Integer;
PosStrA: Integer;
StrA: WideString;
StrB: WideString;
StrTempA: WideString;
StrTempB: WideString;
begin
StrA := string(StrInputA);
StrB := string(StrInputB);

for PosStrA := 1 to Length(strA) - lngLen + 1 do
begin
StrTempA := System.Copy(strA, PosStrA, lngLen);

PosStrB := 1;
for PosStrB := 1 to Length(strB) - lngLen + 1 do
begin
StrTempB := System.Copy(strB, PosStrB, lngLen);
if SysUtils.AnsiCompareText(StrTempA, StrTempB) = 0 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: WideString;
strInputStandart: WideString): 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;

← →
default © (2005-09-14 22:42) [3]

для этого нужно определиться с критерием схожести
естественна такая линия поведения: Вам нужно распознать ситуацию когда человек ошибся в наборе текста по которому хочет что-то найти для помощи ему в его поиске; для этого целесообразно найти какую-нибудь статистику таких ошибок и подумать в связи с ней о том каков должен быть искомый критерий;
пример;
пишет человек слово "Масерта", а хотел "Мастера" то есть возникла перестановка букв, состав прежний; значит стоит перебрать все комбинации букв какие есть в слове "Масерта" и проверить получающиеся комбинации букв на "словарность" - то есть что получаются реальные слова, а не ненаделённые смыслом последовательности букв и тд
это лишь одна возможная ситуация ошибки; поэтому думаю стоит посмотреть на статистику ошибок и подумать как сказано выше над тем какой должен быть критерий

← →
Джо © (2005-09-14 22:45) [4]

Алгоритм SoundEx, реализован в StrUtils.pas. Впрочем, кажется, только для английского.

← →
wicked © (2005-09-14 22:55) [5]

еще вот такое можно предложить:
http://delphibase.spb.ru/?action=viewfunc&topic=strmath&id=10289

в общем - вариантов море...

← →
farapiplug (2005-09-14 23:05) [6]

http://itman.narod.ru/index.htm - здесь на эту тему куча информации, хотя по мне, слишком долго разбираться

← →
Германн © (2005-09-15 01:07) [7]

Самое сложное тут
> узнать насколько процентов одна строка "похожа на вторую".
!

Имхо, очень трудно перевести "количество галош" в проценты. При том, что и алгоритмов сравнения текста - неперечесть.

← →
default © (2005-09-15 01:15) [8]

я и говорю - статистика + логика
двое судей которые могут вынести справедливый вердикт:)
предмет определён - ошибки человеские! могут быть связаны со скоростью печати, неграмотностью, ... всё нужно учесть, причём статистика сказала бы какие ошибки более вероятны

Ищи по ключевым словам "функция Левенталя, выравнивание, алгоритм Нидлмана-Вунча, алгоритм Смита-Ватермана".

Если в слове "хлеб" сделать четыре ошибки, получится "пиво"

← →
WST (2005-09-18 16:18) [11]

Огромное СПАСИБО

-= нечеткое сравнение строк =- Найти похожие ветки