Qué es la búsqueda de cadenas difusas

La coincidencia aproximada de cadenas, o búsqueda de cadenas difusas (fuzzy string match, en inglés), consiste en encontrar una cadena de texto (por ejemplo, la búsqueda de una película) parecida pero no exactamente igual a una cadena de texto determinada.

El algoritmo que mide la coincidencia o no de dos cadenas de texto cuantifica la distancia entre estas dos cadenas. La métrica que mide dicha distancia se denomina “distancia de edición”. Hay diferentes tipos de distancias de edición: la distancia de Levenshtein, distancia Damerau-Levenshtein, la distancia de Hamming, la distancia de Jaro, etc.

El concepto de distancia es muy importante en el área de las búsquedas de texto, y por tanto es muy importante para Lucene y de ahí que también sea importante para Solr Lucene.

Un ejemplo básico podría ser la siguiente situación: buscamos la información relativa a un director de cine, por ejemplo, Hitchcock. Sin embargo, fácilmente podemos equivocarnos en la escritura de las letras correctas, y podríamos escribir tal como para nosotros suena, algo tipo “Hichcock”. El programa de búsqueda debería ser capaz de interpretar que buscamos realmente Hitchcock porque es el nombre de un director de cine más cercano a la palabra que nosotros tecleamos.

Lucene y clase Class FuzzyQuerys

En Lucene la distancia está implementada a través de la clase Class FuzzyQuery.

La medida de similaridad entre cadenas se basa en la distancia Damerau-Levenshtein.

Sin embargo, el usuario de Lucene puede elegir la distancia Levenshtein eligiendo Falso al parámetro de trasposición. Esto es así porque la diferencia entre la distancia Damerau-Levenshtein y la distancia Levenshtein es la trasposición entre letras de una cadena de texto, condición que más adelante veremos en detalle. Lucene permitirá en la coincidencia de búsquedas una distancia máxima de 2. Si deseamos distancias superiores nos recomienda otras técnicas de indexado tipo SpellChecker.

Qué es la distancia Damerau-Levenshtein

La Distancia Damerau-Levenshtein mide el número mínimo de operaciones necesarias para transformar una cadena de caracteres en otra.

Las operaciones empleadas son las inserción, eliminación, sustitución o transposición de dos caracteres.

Es una evolución de la Distancia de Levensthein donde no se empleaba la operación de transposición.

Veamos un ejemplo cada una de estas operaciones:

Cadena original Cadena final Operación
eno heno Inserción carácter h
malo mao Eliminación carácter l
cabe cave Sustitución de la b por la v
cable calbe Trasposición de bl por lb

A modo de ejemplo, veamos cuantas son las operaciones y por tanto la distancia Damerau-Levenshtein de una palabra a otra, por ejemplo, de la palabra “casa” a la palabra “pasado”.

casa -> casad -> casado -> pasado

Se han realizado 3 operaciones y por tanto la distancia de casa a pasado es de 3.

Matriz de la distancia Damerau-Levenshtein

Desde el punto de vista de matemático la distancia Damerau-Levenshtein se representa como una matriz donde en cada celda se indica la distancia entre la letra correspondiente a la fila y la correspondiente a la columna.

En dicha matriz, se irían rellenando cada uno de las celdas de forma recursiva de acuerdo a las siguientes condiciones lógicas:

condiciones de distancia Damerau-Levensthein

Para entender dichas condiciones, hemos de tener en cuenta que:

  • - A las cadenas de texto cuya distancia queremos calcular las llamaremos a y b
  • - A las coordenadas de la matriz les llamaremos i (fila) y j (columna)
  • - Al valor de cada una de las coordenadas de la matriz lo representaremos como: dab (i,j)
  • - La condición 4, 1si  ai bj significa que si la letra de la fila i es igual a la letra de la columna j, entonces el valor es 0, y, si no son iguales, el valor es 1.

Podemos ver que las diversas operaciones de la distancia distancia Damerau-Levenshtein corresponden a las condiciones lógicas que acabamos de ver:

  • - La eliminación de un carácter corresponde a la condición dab (i-1, j)+1
  • - La inserción de un carácter corresponde a la condición dab (i, j-1)+1
  • - Si un carácter fila es igual a un carácter columna corresponde a la condición

    dab (i-1, j-1) + 1si  ai bj

  • - La trasposición corresponde a la condición dab (i-2, j-2) +1 si se cumplen las condiciones:

    ai = bj-1

    ai-1 = bj

Ejemplo sencillo de construcción de Matriz de la distancia Damerau-Levenshtein

Vamos a construir una matriz para calcular la distancia de Damerau-Levenshtein para un caso sencillo.

Imaginemos que queremos medir la distancia de la palabra DA a la palabra DO.

Es fácil comprobar que la distancia será de 1, ya que se pasa de una palabra a otra sustituyendo la A por una O

DA > DO

Empecemos con la matriz inicial. En la matriz inicial, el valor de la fila = 0, columna = 0, es 0 por la condición 1 según la cual, el valor de la casilla si i=0 y j=0 es igual a 0. Por tanto:

dab (0, 0)=0

A continuación, los sucesivos valores de la fila = 0 aumentan cada vez en 1 unidad por la condición 2, de manera que:

dab (0, 1)=1

dab (0, 2)=2

Y los sucesivos valores de la columna = 0 aumentan cada vez en 1 unidad por la condición 3. De manera que:

dab (1, 0)=1

dab (2, 0)=2

Cuando veamos cómo encontrar el valor de las otras casillas, veremos el efecto de las diversas condiciones más claramente.

En definitiva, partimos de esta matriz:

DA 012 D1 O2

Ahora calcularemos el valor de la fila 1, columna 1.

Valor de dab (1, 1) = Mínimo de los valores siguientes:

  • • condición 1 no procede porque i y j son diferentes de 0. A partir de ahora nos la saltaremos dado que sólo tiene sentido cuando fila y columna son iguales a 0
  • • condición 2: dab (0, 1)+1=2
  • • condición 3: dab (1, 0)+1=2
  • • condición 4: dab (0, 0)+ 1si  a1 b1 =0
  • • condición 5 no procede porque i y j no son mayores de 1

Por tanto, el valor de dab (1, 1) =0

Y la matriz ahora queda así:

DA 012 D10 O2

Valor de dab (1, 2) = Mínimo de los valores siguientes:

  • • condición 2: dab (0, 2)+1=3
  • • condición 3: dab (1, 1)+1=1
  • • condición 4: dab (0, 1)+ 1si  a1 b2 =1
  • • condición 5 no procede porque i no es mayor de 1

Por tanto, el valor de dab (1, 2) =1

Y la matriz ahora queda así:

DA 012 D101 O2

Valor de dab (2, 1) = Mínimo de los valores siguientes:

  • • condición 2: dab (1, 1)+1=1
  • • condición 3: dab (2, 0)+1=3
  • • condición 4: dab (1, 0)+ 1si  a2 b1 =2
  • • condición 5 no procede porque j no es mayor de 1

Por tanto, el valor de dab (2, 1) =1

Y la matriz ahora queda así:

DA 012 D101 O21

Valor de dab (2, 2) = Mínimo de los valores siguientes:

  • • condición 2: dab (1, 2)+1=2
  • • condición 3: dab (2, 1)+1=2
  • • condición 4: dab (1, 1)+ 1si  a2 b2 =1
  • • condición 5 no procede porque no se cumplen las dos condiciones:

    a2 = bj-1

    ai-2 = b1

Por tanto, el valor de dab (2, 2) =1

Y la matriz finalmente queda así:

DA 012 D101 O211

En definitiva, la distancia Damerau-Levenshtein entre las cadenas DA y DO es 1.