Pregunta sobre levenshtein-distance, regex – Levenshtein distancia en expresión regular

9

¿Existe la posibilidad de incluir la distancia de levenshtein en la consulta de expresiones regulares?

Excepto hacer unión entre permutaciones. Como buscar "hola" con L.d. 1

<code>.ello | h.llo | he.lo | hel.o | hell.
</code>

esto es muy estúpido e inutilizable para un mayor número de L.d.

Tu respuesta

2   la respuesta
5

nsulta de expresiones regulares?

No, no de una manera sana. La implementación, o el uso de un algoritmo de distancia Levenshtein existente, es el camino a seguir.

ok, esperaré si alguien más responde, de lo contrario marcaré su respuesta como correcta :-) zdenda.online
7

Puede generar la expresión regular mediante programación. Dejaré eso como un ejercicio para el lector, pero para la salida de esta función hipotética (dada una entrada de "palabra") quieres algo como esta cadena:

<code>"^(?>word|wodr|wrod|owrd|word.|wor.d|wo.rd|w.ord|.word|wor.?|wo.?d|w.?rd|.?ord)$"
</code>

En inglés, primero intenta hacer coincidir la palabra en sí, luego en cada posible transposición, luego en cada posible inserción, luego en cada posible omisión o sustitución (puede hacerse simultáneamente).

La longitud de esa cadena, dada una palabra de longitud n, es lineal (y notablemente no exponencial) con n.

Lo cual es razonable, creo.

Pasas esto a tu generador de expresiones regulares (como en Ruby sería Regexp.new (str)) y bam, obtuviste un matcher para CUALQUIER palabra con una distancia Damerau-Levenshtein de 1 de una palabra dada.

(Las distancias de Damerau-Levenshtein de 2 son mucho más complicadas.)

Tenga en cuenta el uso de la estructura (?> Non-backtring) que significa que el orden de las expresiones individuales en esa salida es importante.

No pude pensar en una forma de "compactar" esa expresión.

EDIT: ¡Tengo que trabajar, al menos en Elixir!https://github.com/pmarreck/elixir-snippets/blob/master/damerau_levenshtein_distance_1.exs

Sin embargo, no lo recomendaría necesariamente (excepto con fines educativos) ya que solo te llevará a distancias de 1; una biblioteca legítima de D-L le permitirá calcular distancias> 1. Aunque como es una expresión regular, es probable que funcione bastante rápido una vez que se haya construido (tenga en cuenta que debe guardar la expresión regular "compilada" en algún lugar, ya que este código la reconstruye en CADA comparación.)

Preguntas relacionadas