`

Levenshtein Distance Algorithm: Oracle PL/SQL Implementation

阅读更多

Levenshtein Distance Algorithm: Oracle PL/SQL Implementation

by Barbara Boehmer (baboehme@hotmail.com)

sql 代码
 
  1. CREATE OR REPLACE FUNCTION ld -- Levenshtein distance  
  2.   (p_source_string   IN VARCHAR2,  
  3.    p_target_string   IN VARCHAR2)  
  4.   RETURN                NUMBER  
  5.   DETERMINISTIC  
  6. AS  
  7.   v_length_of_source    NUMBER := NVL (LENGTH (p_source_string), 0);  
  8.   v_length_of_target    NUMBER := NVL (LENGTH (p_target_string), 0);  
  9.   TYPE mytabtype IS     TABLE OF NUMBER INDEX BY BINARY_INTEGER;  
  10.   column_to_left        mytabtype;  
  11.   current_column        mytabtype;  
  12.   v_cost                NUMBER := 0;  
  13. BEGIN  
  14.   IF v_length_of_source = 0 THEN  
  15.     RETURN v_length_of_target;  
  16.   ELSIF v_length_of_target = 0 THEN  
  17.     RETURN v_length_of_source;  
  18.   ELSE  
  19.     FOR j IN 0 .. v_length_of_target LOOP  
  20.       column_to_left(j) := j;  
  21.     END LOOP;  
  22.     FOR i IN 1.. v_length_of_source LOOP  
  23.       current_column(0) := i;  
  24.       FOR j IN 1 .. v_length_of_target LOOP  
  25.         IF SUBSTR (p_source_string, i, 1) =  
  26.            SUBSTR (p_target_string, j, 1)  
  27.         THEN v_cost := 0;  
  28.         ELSE v_cost := 1;  
  29.         END IF;  
  30.         current_column(j) := LEAST (current_column(j-1) + 1,  
  31.                                     column_to_left(j) + 1,  
  32.                                     column_to_left(j-1) + v_cost);  
  33.       END LOOP;  
  34.       FOR j IN 0 .. v_length_of_target  LOOP  
  35.         column_to_left(j) := current_column(j);  
  36.       END LOOP;  
  37.     END LOOP;  
  38.   END IF;  
  39.   RETURN current_column(v_length_of_target);  
  40. END ld;  
分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics