Текущий архив: 2003.11.13;
Скачать: CL | DM;

Вниз

Совпадение строк   Найти похожие ветки 

← →
SG ©   (2003-11-01 15:09) [0]

Как найти процентное совпадение одной строки с другой?

---

← →
Verg ©   (2003-11-01 15:27) [1]

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

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;

---

Страницы: 1 вся ветка

Текущий архив: 2003.11.13;
Скачать: CL | DM;

Наверх

Память: 0.47 MB
Время: 0.022 c