Levenshtein Distance Algorithm: Oracle PL/SQL Implementation using a two-dimensional array of numbers

In a previous post, I mentioned a concept called Levenstein Distance (or Edit Distance). I also mentioned that Steve Feuerstein posted some code to the Oracle Magazine site that shows us how to work with a two-dimensional array of numbers.

While thinking about Steve's article, I decided to create a new PL/SQL Function to determine the Levenstein Distance between two objects based on Barbara Boehmer's Levenshtein Distance Algorithm: Oracle PL/SQL Implementation and Steve's article.

Here's the code for all of you to enjoy:

--fx_ld.sql
--Levenshtein distance
CREATE OR REPLACE FUNCTION fx_ld(
    p_string_orig VARCHAR2,--s
    p_string_new  VARCHAR2)--t
RETURN NUMBER DETERMINISTIC IS
    TYPE data_t IS TABLE OF NUMBER INDEX BY PLS_INTEGER;
    TYPE array_t IS TABLE OF data_t INDEX BY PLS_INTEGER;
    l_2d_grid    array_t;
    TYPE char_table_type 
                 IS TABLE OF char(1) INDEX BY binary_integer;
    s            char_table_type;
    t            char_table_type;
    n            PLS_INTEGER := LENGTH(p_string_orig);
    m            PLS_INTEGER := LENGTH(p_string_new);
    lv_cost      PLS_INTEGER;

BEGIN

    IF    n = 0 
    THEN  RETURN m;
    END IF;

    IF      m = 0 
    THEN    RETURN n;
    END IF;

    --Let's load up the arrays
    l_2d_grid (0) (0) := 0;
    FOR i IN 1..n
    LOOP
        s(i) := SUBSTR(p_string_orig, i, 1);
        l_2d_grid (i) (0) := i;

        FOR j IN 1..m
        LOOP
            t(j) := SUBSTR(p_string_new, j, 1);
            l_2d_grid (0) (j) := j;
            IF      s(i) = t(j)
            THEN    lv_cost := 0;
            ELSE    lv_cost := 1;
            END IF;

            l_2d_grid (i) (j) := LEAST (
                                    l_2d_grid (i-1)(j) + 1, 
                                    l_2d_grid (i)(j-1) + 1,
                                    l_2d_grid (i-1)(j-1) + lv_cost);
            --dbms_output.put_line(i||':'||j||' := '||
                        --l_2d_grid (i) (j)||', cost:='||lv_cost||
                        --', s(i):='||s(i)||', t(j):='||t(j));
        END LOOP;

    END LOOP;

    --The Levenshtein(Edit) distance is found in cell d[n,m]
    RETURN l_2d_grid (n) (m);

END fx_ld;

SQL>select fx_ld('XRICH', 'RICHARD') LD from dual;

     LD
-------
      4