ignorēt mazās izmaiņas
Ir reizes, kad lielos VARCHAR2 laukos tiek veiktas minimālas izmaiņas. Tādas izmaiņas varētu nelogot.
Uzrakstīju Lēvenšteina attāluma noteikšanu iekš PL/SQL.
Varbūt kāds var pārrakstīt, lai atmiņas izmantošana būtu O(n), nevis O(n^2)? Wikipedia raksta, ka tas esot izdarāms.



FUNCTION LEVENSHTEIN_DISTANCE(p_str1 in varchar2, p_str2 in varchar2)
return number
is
-- funkcija aprēķina Lēvenšteina attālumu diviem stringiem
-- http://en.wikipedia.org/wiki/Levenshtein_distance

type t_number_table is table of number index by pls_integer;
-- v_line_j t_number_table; -- j rinda
-- v_line_j_previous t_number_table; -- j-1 rinda
-- v_line_temp t_number_table; -- izmanto priekš piešķiršanas
type t_matrix is table of t_number_table index by pls_integer;
type t_char_array is table of varchar2(1) index by pls_integer;
v_matrix t_matrix;
v_length1 number := length(p_str1);
v_length2 number := length(p_str2);
v_cost number;

v_char_array1 t_char_array;
v_char_array2 t_char_array;
begin
-- identiskām vērtībām Lēvenšteina attālums ir 0
if p_str1 = p_str2 then
return 0;
end if;

if p_str1 is null or p_str2 is null then
return null;
end if;

-- inicializācija
for i in 0..v_length1 loop
v_matrix(i)(0) := i;
end loop;

for j in 0..v_length2 loop
v_matrix(0)(j) := j;
end loop;

for i in 1..v_length1 loop
v_char_array1(i) := substr(p_str1,i,1);
end loop;

for j in 1..v_length2 loop
v_char_array2(j) := substr(p_str2,j,1);
end loop;

for i in 1..v_length1 loop
for j in 1..v_length2 loop
if v_char_array1(i) = v_char_array2(j) then
v_cost := 0;
else
v_cost := 1;
end if;

v_matrix(i)(j) := least(v_matrix(i-1)(j)+1
,v_matrix(i)(j-1)+1
,v_matrix(i-1)(j-1) + v_cost);

end loop;
end loop;

-- atgriež sarēķināto vērtību
return v_matrix(v_length1)(v_length2);

end;