Возникла необходимость написать на MySQL функцию, возвращающую расстояние Дамерау-Левенштейна - степень "непохожести" двух строк в количестве операций замены, удаления или перестановки символов. Сам в математике не силен, поэтому написать с нуля трудно - нужно разбираться в сложных для меня формулах и алгоритмах.
Нашел текст функции для PostgreSQL (ниже по тексту сообщения). Мог бы и сам переписать ее для MySQL, но столкнулся с тем, что в PostgreSQL используются массивы. Есть ли альтернатива для массивов в MySQL? В любом случае есть ли возможность переписать данную функцию для 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
Можете написать на
