Distancia entre la expresión regular

Question

¿Podemos calcular un tipo de distancia entre las expresiones regulares?

La idea es medir de qué manera dos expresiones regulares son similares.

Answer 1

hay algunas de las métricas que puede usar:

1. La longitud de un partido válido. Algunas expresiones regulares tienen un tamaño fijo, algunas un límite superior y otras un límite inferior. Compare cuán similares son sus longitudes o longitudes posibles.

2. Los caracteres que coinciden. Cualquier expresión regular tendrá un conjunto de caracteres que una coincidencia puede contener (tal vez todos los caracteres). Compara el conjunto de caracteres incluidos.

3. Utilice un documento grande y vea cuántas coincidencias hace cada expresión regular y cuántas de ellas son idénticas.

¿Está buscando la equivalencia estricta?

Answer 2

Creo que primero debes entender por ti mismo cómo ves una "diferencia" entre dos expresiones. Básicamente, define una métrica de distancia.

En general, sería bastante diferente de hacer. Dependiendo de lo que necesite hacer, es posible que ver a un personaje diferente en algún lugar sea una gran diferencia. En el otro caso, permitir cualquier cantidad de caracteres consecuentes pero iguales puede no producir mucha diferencia.

Me gustaría enfatizar también que normalmente cuando hablan de funciones de distancia, las aplican a ..., bueno, llamémoslas, tokens. En nuestro caso, secuencias de personajes. Lo que estás dispuesto a hacer es aplicar este método no a esos tokens, sino a las reglas que una gran cantidad de tokens igualará. No estoy seguro de que tenga sentido.

Aún así, creo que podríamos pensar en algo, pero no en general, sino en un caso particular y bastante restringido. ¿Tienes algún tipo de ejemplo para mostrarnos?

Answer 3

Puede compilar deterministic finite-state machines para ambas expresiones regulares y comparar las transiciones. La diferencia de ambas transiciones se puede usar para medir la distancia de estas expresiones regulares.

Answer 4

Si tiene dos expresiones regulares y tiene un conjunto de entradas de ejemplo, puede intentar hacer coincidir cada entrada con cada expresión regular. Para cada entrada:

• Si ambos partido o ambas no coinciden, la puntuación de 0.
• Si uno partidos y el otro no, la puntuación de 1.

Suma esta puntuación de más de todas las entradas, y esto le dará una 'distancia' entre las expresiones regulares. Esto le dará una idea de la frecuencia con la que dos expresiones regulares serán diferentes para una entrada típica. Será muy lento calcular si su conjunto de entrada de muestra es grande. No funcionará en absoluto si ambas expresiones regulares no coinciden para casi todas las cadenas aleatorias y su entrada esperada es completamente aleatoria. Por ejemplo, la expresión regular 'sgjlkwren' y la expresión regular 'ueuenwbkaalf' probablemente nunca coincidirían con nada si se probaran con una entrada aleatoria, por lo que esta métrica diría que la distancia entre ellas es cero. Eso podría o no ser lo que quieres (probablemente no).

Usted puede ser capaz de analizar la estructura de la expresión regular y el uso de un muestreo aleatorio sesgado para golpear deliberadamente cadenas que coinciden con más frecuencia que en la entrada completamente al azar. Por ejemplo, si ambas expresiones regulares requieren que la cadena comience con 'foo', puede asegurarse de que sus entradas de prueba también comiencen siempre con foo, para evitar perder tiempo probando cadenas que sabe que fallarán para ambas.

Así que en conclusión: a menos que tenga una situación muy específica con una entrada restringida establecer y/o restringido el lenguaje de expresiones regulares, yo diría que no es posible. Si tiene algunas restricciones sobre su entrada y sobre la expresión regular, podría ser posible. Por favor, especifique cuáles son estas restricciones y tal vez pueda encontrar algo mejor.

Answer 5

supongo que se podría calcular una Levenshtein Distance entre las cadenas reales experssion regulares. Esa es ciertamente una manera de medir una "distancia" entre dos cadenas de expresiones regulares diferentes.

Por supuesto, creo que es posible que aquí no se necesiten expresiones regulares, y calcular la Distancia de Levenshtein de las cadenas de "valores" reales a las que se aplicarían las Expresiones regulares puede dar mejores resultados.

Answer 6

Hay una respuesta oculta en una pregunta anterior aquí en SO: Generating strings from regexes. Puede calcular una medida de distancia (asimétrica) generando cadenas usando una expresión regular y verificando cuántas de ellas coinciden con la otra expresión regular.

esto puede ser optimizado por despojar a los prefijos/sufijos comunes. P.ej. a[0-9]* y a[0-7]* comparten el prefijo a, por lo que se puede calcular la distancia entre [0-9]* y [0-7]* lugar.