MySQL - ReducedLevenshtein

levenshtein.sql

-- store this as a procedure lv_leq_2. To be able to call this "revursivly" 
-- you have to add this function a second time named lv_leq_1. lv_leq_0 stopps
-- the recursion and just compares if two strings are equal.

BEGIN
  DECLARE s1_len, s2_len, i INT;
  SET s1_len = CHAR_LENGTH(s1), s2_len = CHAR_LENGTH(s2), i = 1;
  IF s1 = s2 THEN
    RETURN TRUE;
  ELSEIF ABS(s1_len - s2_len) > 3 THEN
    RETURN FALSE;
  ELSE
    WHILE SUBSTRING(s1,s1_len - i,1) = SUBSTRING(s2,s2_len - i,1) DO
     SET i = i + 1;
    END WHILE;
    RETURN lv_leq_1(SUBSTRING(s1,1,s1_len-i),SUBSTRING(s2,1,s2_len-i)) 
      OR lv_leq_1(SUBSTRING(s1,1,s1_len-i),SUBSTRING(s2,1,s2_len-i+1)) 
      OR lv_leq_1(SUBSTRING(s1,1,s1_len-i+1),SUBSTRING(s2,1,s2_len-i));
  END IF;
END