Форум пользователей MySQL

-- s1, s2 - сравниваемые строки, dist - максимальное расстояние между ними
CREATE OR REPLACE FUNCTION damerau_levenshtein(s1 character varying,
   s2 character varying, dist integer)
   RETURNS boolean AS
$BODY$
        DECLARE
        s1_len INTEGER := CHAR_LENGTH(s1);
        s2_len INTEGER := CHAR_LENGTH(s2);
        i INTEGER := 0;
        j INTEGER := 0;
        c INTEGER := 0;
        prev INTEGER[]; -- первая строка
        curr INTEGER[]; -- вторая строка
        next INTEGER[]; -- третья строка
        s1_char TEXT[];
        s2_char TEXT[];
        temp INTEGER;
        st CHARACTER VARYING;
     BEGIN  
        IF s1 = s2 THEN RETURN TRUE;
        ELSIF abs(s1_len - s2_len) > dist THEN RETURN FALSE;
        ELSE
           -- для оптимизации объема используемой памяти О(m*n) -> O(min(m,n))
           IF s1_len < s2_len THEN
              temp := s2_len;
              s2_len := s1_len;
              s1_len := temp;
              st := s2;
              s2 := s1;
              s1 := st;
           END IF;
 
           -- увеличиваем высоту и ширину матрицы на 2
           s1_len := s1_len + 2;
           s2_len := s2_len + 2;
 
           curr[1] := s1_len + s2_len;
 
           FOR i IN 2..s2_len LOOP
              curr[i] := i-2;
              s2_char[i] := substr(lower(s1), i-1, 1);
           END LOOP;
 
           FOR i IN 1..s1_len-1 LOOP
              s1_char[i+1] := substr(lower(s2), i, 1);
           END LOOP;  
 
           FOR i IN 3..s1_len LOOP
              next[1] := s1_len + s2_len;
              next[2] := i - 2;
              FOR j IN 3..s2_len LOOP
                 -- находим цену замены символа
                 IF s1_char[i-1] = s2_char[j-1] THEN c := 0; ELSE c := 1; END IF;
                 -- считаем D(i,j) = next[j]
                 IF curr[j] <= next[j-1] THEN
                    next[j] := curr[j] + 1;
                 ELSE next[j] := next[j-1] + 1; END IF;
                 IF curr[j-1] + c < next[j] THEN
                    next[j] := curr[j-1] + c; END IF;
                 IF s1_char[i-1] = s2_char[j-2] AND s1_char[i-2] = s2_char[j-1]
                    AND next[j] > prev[j-2] + 1 THEN
                    next[j] := prev[j-2] + 1;
                 END IF;  
                 -- если значение диагонального или последующих краевых элементов
                 -- больше заданного расстояния, выходим с false
                 IF (i = j OR (i > s2_len AND j = s2_len)) AND next[i] > dist THEN
                    RETURN FALSE; END IF;
              END LOOP;
 
              for j IN 1..s2_len LOOP
              -- сдвигаем строки
                  prev[j] := curr[j];
                  curr[j] := next[j];
              END LOOP;
           END LOOP;
 
            -- расстояние Дамерау-Левенштейна после работы функции оказывается
            -- в ячейке next[s2_len]
            IF next[s2_len] <= dist THEN RETURN TRUE; ELSE RETURN FALSE; END IF;
        END IF;      
     END;
     $BODY$
  LANGUAGE plpgsql IMMUTABLE