¿hay alguna posibilidad de incluir distancia levenshtein en la consulta de expresión regular?distancia de Levenshtein en la expresión regular
Excepto haciendo la unión entre las permutaciones. Me gusta buscar "hola" con L.d. 1
.ello | h.llo | he.lo | hel.o | hell.
esto es muy estúpido e inutilizable para números más grandes de L.d.
¿Existe la posibilidad de incluir distancia levenshtein en la consulta de expresión regular?
No, no de una manera sensata. Implementar - o usar un algoritmo de distancia Levenshtein existente - es el camino a seguir.
Puede generar la expresión regular por programación. Eso se lo dejo como ejercicio para el lector, pero para la salida de esta función hipotética (dada una entrada de "palabra") que desee algo así como esta cadena:
"^(?>word|wodr|wrod|owrd|word.|wor.d|wo.rd|w.ord|.word|wor.?|wo.?d|w.?rd|.?ord)$"
En Inglés, primero intenta emparejar en la palabra misma, luego en cada transposición única posible, luego en cada inserción individual posible, luego en cada omisión o sustitución simple posible (se puede hacer 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.
Usted pasa esto a su generador de expresiones regulares (como en Ruby sería Regexp.new (str)) y bam, tiene una coincidencia para CUALQUIER palabra con una distancia Damerau-Levenshtein de 1 a partir de una palabra determinada.
(distancias Damerau-levenshtein de 2 son mucho más complicadas.)
Nota uso del (> constructo no backtracing que significa el fin del individuo |?. 'Expresiones d en el caso de salida
yo no podía pensar en una manera de "compacto" que la expresión
EDIT:. yo tengo que trabajar, por lo menos en Elixir https://github.com/pmarreck/elixir-snippets/blob/master/damerau_levenshtein_distance_1.exs
no necesariamente recomendar esto, sin embargo (a excepción de la educación! pu rposes) ya que solo te llevará a distancias de 1; una legítima biblioteca de DL te permitirá calcular distancias> 1. Aunque como esto es regex, probablemente funcione bastante rápido una vez construido (ten en cuenta que debes guardar la expresión regular "compilada" en algún lugar dado que este código la reconstruye en CADA comparación)
bien, esperaré si alguien más contestará, de lo contrario marcaré tu respuesta como correcta :-) – d1x