Me pregunto cómo funciona expresiones regulares, mi expresión regular particular tiene un elemento que tiene este aspecto:¿Java Regex optimiza este caso específico?
(word1|word2|wordn......)
El número de palabras es grande varios cientos.
Me pregunto si el motor de expresiones regulares solo está probando las palabras una por una o si optimiza la búsqueda y de qué manera.
Cualquier puntero a una buena documentación será bueno.
Si tiene varios cientos de palabras, debe tener cuidado con el orden de las palabras en la expresión regular. El motor de expresiones regulares busca las palabras de izquierda a derecha.
Si prueba la palabra setValue en la alternancia set|setValue, coincidirá solo con las 3 letras que comprenden "conjunto" y no con toda la cadena.
Consulte esto link (de www.regular-expressions.info) para la explicación completa.
No creo que el motor de expresiones regulares verdaderamente optimice las alternancias (es decir, analizar prefijos comunes y construir nfa en consecuencia). Por lo tanto, con tantas palabras, no creo que sea una optimización.
Además de volver a ordenar las palabras, también puede intentar agregar un límite de palabra o línea después de la alternancia, p. Ej. (set|setValue)$, pero sospecho que el motor de expresiones regulares hará una gran cantidad de retrocesos por lo que puede no valer la pena el esfuerzo.
Supongo que el motor todavía prueba cada palabra letra por letra y retrocederá tan pronto como una letra sea diferente ¿verdad? – millebii
Quiero un punto de referencia de esto (handoptimized contra ingenua regex). –
Sí, retrocederá letra por letra, pero aún puede haber toneladas de retroceso con cientos de palabras – Yoni
consulte this link
En este artículo se explica JavaWorld mecanismo de la expresión regular de Java (llamada NFA para no determinista Autómata Finito, o NFA) subyacente. También hay libros enteros sobre el tema. También echa un vistazo al Resources Section.
Publicar * solo * un enlace como respuesta no es una buena idea. El artículo vinculado se puede quitar/mover/bitrot y la respuesta no tiene sentido. –
Normalmente tienes razón. Pero esto es un enlace a javaworld, así que tengo dudas de que se eliminará. Y lo explica todo muy bien. – AlexR
Thx, mala suerte para mí Los NFA no optimizan esas expresiones. – millebii
Si le parece que el motor de RE es el cuello de botella en dicha búsqueda, puede construir fácilmente un trie y verificar la contención.
Muy interesante, podría intentarlo. ¿Alguna implementación de Java que conozcas?O puedo usar la implementación del mapa hash que se describe en su enlace. – millebii
Para el registro, puede encontrar una implementación interesante de Java de TRIE [aquí] (https://github.com/rkapsi/simple-patricia-trie#readme) – millebii
[Allí] (http://www.javaworld.com/javaworld/jw-09-2007/jw-09-optimizingregex.html?page=2) dice: _Tened en cuenta la alternancia. Las expresiones regulares como "(X | Y | Z)" tienen la reputación de ser lentas, así que ten cuidado con ellas_ – millebii
** [...] en lugar de "(abcd | abef)" usar "ab (cd | ef)" [...] "* - Esta es la forma más trivial de optimización, y me sorprendería mucho si el motor de expresiones regulares de Java no lo hiciera. – aioobe
@aioobe no es muy útil, con varios cientos de palabras, ¿cómo lo haces? Creo que puedo usar eso – millebii