Разность между двумя строками - функция Левенштейна

Delphi , Синтаксис , Текст и Строки

Автор: Wicked
WEB-сайт: http://delphibase.endimus.com

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

Зависимости: System
Автор:       Андрей aka wicked, wilk@ua.fm, ICQ:92356239, Тернополь
Copyright:   описание алгоритма взято с http://www.merriampark.com/ld.htm, реализация моя
Дата:        10 августа 2002 г.
***************************************************** }

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;

Пример использования:

// на форме имеются поля Edit1 и Edit2, метка Label1
...
Label1.Caption := IntToStr(LeveDist(Edit1.Text, Edit2.Text));
...

Алгоритм функции Левенштейна - это известный алгоритм в области компьютерных наук, который рассчитывает минимальное количество операций (вставок, удалений и замены) для преобразования одного строки в другую.

Эта реализация на языке Delphi обеспечивает эффективный способ расчета расстояния Левенштейна между двумя строками. Код использует буферный массив (buf) для хранения промежуточных результатов, что уменьшает количество выделения памяти и улучшает производительность.

Вот разбивка кода:

1. Функция min3 - это вспомогательная функция, которая возвращает минимальное значение из трех целых чисел.
2. Функция LeveDist принимает два параметра-строки (s и t) и рассчитывает расстояние Левенштейна между ними.
3. Функция сначала обрезает обе строки до максимальной длины cuthalf - 1, которая является константой, определенной вверху кода.
4. Затем она инициализирует буферный массив индексными значениями от 0 до n (длиной строки t).
5. Внешний цикл проходит по каждому символу в строке s. Для каждого символа обновляет буферный массив, используя минимальное значение из трех возможностей:
   • Стоимость вставки символа (т.е., движение от предыдущей строки)
   • Стоимость удаления символа (т.е., движение от предыдущего столбца)
   • Стоимость замены символа (т.е., движение диагонально вверх и направо)
6. Переменная flip используется для переключения между двумя половинами буферного массива, которые представляют переход от "предыдущей строки" к "текущей строке".
7. Наконец, функция возвращает значение, хранящееся в последней ячейке буферного массива, которое представляет минимальное количество операций, необходимых для преобразования строки s в строку t.

Пример использования в конце кода показывает, как использовать эту функцию в приложении Delphi. Он рассчитывает расстояние Левенштейна между текстом в двух редактируемых контролах и отображает результат на метке.

В целом, эта реализация обеспечивает эффективный и точный способ расчета расстояния Левенштейна между двумя строками в Delphi.

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

Комментарии и вопросы

Получайте свежие новости и обновления по Object Pascal, Delphi и Lazarus прямо в свой смартфон. Подпишитесь на наш Telegram-канал delphi_kansoftware и будьте в курсе последних тенденций в разработке под Linux, Windows, Android и iOS

:: Главная :: Текст и Строки ::