Distancia de Levenshtein

 

05/03/2020

En Teoría de la información y Ciencias de la Computación se llama Distancia de Levenshtein, distancia de edición, o distancia entre palabras, al número mínimo de operaciones requeridas para transformar una cadena de caracteres en otra. Se entiende por operación, bien una inserción, eliminación o la sustitución de un carácter. Esta distancia recibe ese nombre en honor al científico ruso Vladimir Levenshtein, quien se ocupara de esta distancia en 1965. Es útil en programas que determinan cuán similares son dos cadenas de caracteres, como es el caso de los correctores de ortografía.

Por ejemplo, la distancia de Levenshtein entre “casa” y “calle” es de 3 porque se necesitan al menos tres ediciones elementales para cambiar uno en el otro.

1. casa → cala (sustitución de ‘s’ por ‘l’)
2. cala → calla (inserción de ‘l’ entre ‘l’ y ‘a’)
3. calla → calle (sustitución de ‘a’ por ‘e’)

Se le considera una generalización de la distancia de Hamming, que se usa para cadenas de la misma longitud y que solo considera como operación la sustitución. Hay otras generalizaciones de la distancia de Levenshtein, como la distancia de Damerau-Levenshtein, que consideran el intercambio de dos caracteres como una operación

Wikipedia: Distancia de Levenshtein

Algoritmo de Levenshtein para Vfp por Miguel A. Martínez [1]

nLevenst = SortedLevenshteinD(sStr1, sStr2)

RETURN

* Función mejorada, ordena las subcadenas separadas por espacios y después compara
**********************************
FUNCTION SortedLevenshteinD(sStr1, sStr2)
**********************************
LOCAL asStr1[1], asStr1[2], sStr
ALINES(asStr1, sStr1, " ")
ASORT(asStr1)
sStr1 = ""
FOR EACH sStr IN asStr1
sStr1 = sStr1 + IIF(! EMPTY(sStr1), " ", "") + sStr
NEXT

ALINES(asStr2, sStr2, " ")
ASORT(asStr2)
sStr2 = ""
FOR EACH sStr IN asStr2
sStr2 = sStr2 + IIF(! EMPTY(sStr2), " ", "") + sStr
NEXT
RETURN LevenshteinD(sStr1, sStr2)
ENDFUNC

**********************************
FUNCTION LevenshteinD(tcTarget, tcSource)
**********************************
LOCAL lnLenTarget, lnLenSource, lnRow, lnCol, lnTempRow, lnTempCol, lnCost
lnLenTarget = LEN(tcTarget) + 1
lnLenSource = LEN(tcSource) + 1
DIMENSION aryTable(lnLenTarget, lnLenSource)
STORE 0 TO aryTable

* Quita las 2 líneas siguientes si quieres distinguir mayúsculas de minúsculas
tcTarget = UPPER(tcTarget)
tcSource = UPPER(tcSource)

FOR lnCol = 1 TO lnLenSource
aryTable[1, lnCol] = lnCol - 1
ENDFOR

FOR lnRow = 2 TO lnLenTarget
lnTempRow = lnRow - 1
aryTable[lnRow, 1] = lnTempRow
FOR lnCol = 2 TO lnLenSource
lnTempCol = lnCol - 1
IF SUBSTR(tcTarget, lnTempRow, 1) == SUBSTR(tcSource, lnTempCol, 1)
lnCost = 0
ELSE
lnCost = 1
ENDIF
aryTable[lnRow, lnCol] = MIN(aryTable[lnTempRow, lnCol] + 1, ;
aryTable[lnRow, lnTempCol] + 1, ;
aryTable[lnTempRow, lnTempCol] + lnCost)
ENDFOR
ENDFOR
RETURN aryTable[lnLenTarget, lnLenSource]
ENDFUNC

 

---

Distancia de Levenshtein Función en Oracle/PL por Hugo Méndez [2]

 

CREATE OR REPLACE FUNCTION LEVENSTHEIN (CAD1 IN VARCHAR2 , CAD2 IN VARCHAR2) RETURN NUMBER IS

TYPE T_LIST IS TABLE OF INTEGER;
TYPE T_TABLA IS TABLE OF T_LIST;

TABLA T_TABLA := T_TABLA();
LISTA T_LIST;

I INTEGER;
J INTEGER;

UNO INTEGER;
DOS INTEGER;
TRES INTEGER;
RES NUMBER(5);

BEGIN
IF NOT CAD1 IS NULL AND NOT CAD2 IS NULL THEN

–RESERVAMOS MEMORIA E INICIALIZAMOS ESPACIO DE LA TABLA A USAR.
TABLA:=T_TABLA();

FOR I IN 1.. LENGTH(CAD1)+1 LOOP
TABLA.EXTEND;
TABLA(I):=T_LIST();

FOR J IN 1.. LENGTH(CAD2)+1 LOOP
TABLA(I).EXTEND;
TABLA(I)(J):=0 ;
END LOOP;
END LOOP;

FOR I IN 1.. LENGTH(CAD1)+1 LOOP
TABLA(I)(1):=I -1;
END LOOP;

FOR J IN 1.. LENGTH(CAD2)+1 LOOP
TABLA(1)(J):=J -1;
END LOOP;

FOR I IN 2.. LENGTH(CAD1)+1 LOOP
FOR J IN 2.. LENGTH(CAD2)+1 LOOP
UNO:=TABLA(I-1 )(J-1);

IF SUBSTR(CAD1,I -1,1) <> SUBSTR(CAD2,J- 1,1) THEN
UNO:=UNO+1;
END IF;

DOS:=TABLA(I)(J -1)+1;
TRES:=TABLA(I-1 )(J)+1;
TABLA(I)(J):=UNO ;

IF DOS<TABLA(I )(J) THEN
TABLA(I)(J):=DOS ;
END IF;

IF TRES<TABLA(I )(J) THEN
TABLA(I)(J):=TRES ;
END IF;
END LOOP;
END LOOP;

RES:=TABLA(LENGTH(CAD1 )+1)(LENGTH(CAD2)+ 1);

ELSIF NOT CAD1 IS NULL THEN
RES:=LENGTH(CAD1);
ELSE
RES:=LENGTH(CAD2);
END IF;

RETURN (RES);
END;

---

 

Referencias

1. Artículo original enviado por: Miguel A. Martínez

Correo: miguel@prymer.es

Algoritmo de Levenshtein Vfp

 

2. Artículo original: Hugo Méndez

Web: User