Главная страница
    Top.Mail.Ru    Яндекс.Метрика
Форум: "Основная";
Текущий архив: 2003.11.13;
Скачать: [xml.tar.bz2];

Вниз

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

 
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;
Скачать: [xml.tar.bz2];

Наверх




Память: 0.45 MB
Время: 0.036 c
14-42099
Yttrium
2003-10-23 01:00
2003.11.13
FreePascal, борьба с компилятором под Linux


3-40897
shihovtseva
2003-10-20 09:25
2003.11.13
Ошибка в базе IB


1-41672
Islander
2003-10-24 09:52
2003.11.13
Как узнать текущую кодовую страницу винды и текущую локаль?


14-42043
Marser
2003-10-14 00:22
2003.11.13
Панове!


1-41194
KSergey
2003-11-02 10:48
2003.11.13
String-поле в Record и Dispose.





Afrikaans Albanian Arabic Armenian Azerbaijani Basque Belarusian Bulgarian Catalan Chinese (Simplified) Chinese (Traditional) Croatian Czech Danish Dutch English Estonian Filipino Finnish French
Galician Georgian German Greek Haitian Creole Hebrew Hindi Hungarian Icelandic Indonesian Irish Italian Japanese Korean Latvian Lithuanian Macedonian Malay Maltese Norwegian
Persian Polish Portuguese Romanian Russian Serbian Slovak Slovenian Spanish Swahili Swedish Thai Turkish Ukrainian Urdu Vietnamese Welsh Yiddish Bengali Bosnian
Cebuano Esperanto Gujarati Hausa Hmong Igbo Javanese Kannada Khmer Lao Latin Maori Marathi Mongolian Nepali Punjabi Somali Tamil Telugu Yoruba
Zulu
Английский Французский Немецкий Итальянский Португальский Русский Испанский