TRE es una biblioteca de código abierto para la coincidencia de patrones en texto, [2] que funciona como un motor de expresión regular con la capacidad de hacer una coincidencia aproximada de cadenas . [3] Fue desarrollado por Ville Laurikari [1] y se distribuye bajo una licencia tipo BSD de 2 cláusulas .
Autor (es) original (es) | Ville Laurikari [1] |
---|---|
Repositorio | |
Escrito en | C |
Tipo | Coincidencia aproximada de cadenas |
Licencia | Licencia tipo BSD de 2 cláusulas |
Sitio web | laurikari |
La biblioteca [4] está escrita en C y proporciona funciones que permiten usar expresiones regulares para buscar en líneas de texto de entrada. La principal diferencia con otros motores de expresión regular es que TRE puede hacer coincidir fragmentos de texto de forma aproximada, es decir, suponiendo que el texto pueda tener algún número de errores tipográficos .
Características
TRE usa una sintaxis extendida de expresión regular con la adición de "direcciones" para hacer coincidir el fragmento anterior de forma aproximada. Cada una de estas direcciones especifica cuántos errores tipográficos se permiten para este fragmento.
La coincidencia aproximada [5] se realiza de forma similar a la distancia de Levenshtein , lo que significa que hay tres tipos de errores tipográficos "reconocidos": [6]
Error de tipografía | Ejemplo | Datos |
---|---|---|
inserción de un carácter extra | experesión regular | extra l , extra e |
falta un personaje del patrón | Expesión regular | falta de u , que falta r |
reemplazo de algún personaje | exprezsion regolar | u → o , s → z |
TRE permite especificar el costo de cada uno de los tres tipos de errores tipográficos de forma independiente.
El proyecto viene con una utilidad de línea de comandos, una reimplementación de agrep .
Aunque la coincidencia aproximada requiere alguna extensión de sintaxis, cuando no se utiliza esta función, TRE funciona como la mayoría de los otros motores de coincidencia de expresiones regulares. Esto significa que
- implementa expresiones regulares ordinarias escritas para una coincidencia estricta; [3] [7]
- Los programadores familiarizados con las expresiones regulares de estilo POSIX [4] no necesitan hacer mucho estudio para poder usar TRE. [3]
Consumo de memoria y tiempo predecible
El autor de la biblioteca afirma [8] que el tiempo dedicado a la comparación crece linealmente con el aumento de la longitud del texto de entrada, mientras que el requisito de memoria es constante durante la comparación y no depende de la entrada, solo del patrón.
Otro
Otras características, comunes para la mayoría de los motores de expresión regular, se pueden verificar en las tablas de comparación de motores de expresiones regulares o en la lista de características de TRE en su página web.
Ejemplo de uso
Las direcciones de coincidencia aproximadas se especifican entre corchetes y deben distinguirse de los cuantificadores repetitivos (posiblemente insertando un espacio después de abrir el corchete):
(regular){~1}\s+(expression){~2}
coincidiría con variantes de la frase "expresión regular" en la que "regular" no tiene más de un error tipográfico y "expresión" no más de dos; como en las expresiones regulares ordinarias, "\s+
" significa uno o más caracteres de espacio, es decirpasaría la prueba;expresión regular
(expression){ 5i + 3d + 2s < 11}
coincidiría con la palabra "expresión" si el costo total de los errores tipográficos es inferior a 11, mientras que el costo de inserción se establece en 5, la eliminación en 3 y la sustitución del carácter en 2, es decir,ekspresson
da un costo de 10.
Enlaces de idioma
Aparte de C, TRE se puede utilizar a través de enlaces para Perl , Python y Haskell . [9] Es el motor de expresión regular predeterminada en R . [10] Sin embargo, si el proyecto fuera multiplataforma , sería necesaria una interfaz separada para cada una de las plataformas de destino.
Desventajas
Dado que otros motores de expresión regular no suelen ofrecer una capacidad de coincidencia aproximada, casi no existe una implementación simultánea con la que pueda compararse TRE. Sin embargo, hay algunas cosas que los programadores pueden desear ver implementadas en versiones futuras: [11]
- un mecanismo de reemplazo para sustituir fragmentos de texto coincidentes (como en el procesador de cadenas sed y muchas implementaciones modernas de expresiones regulares, incluidas las integradas en Perl o Java );
- oportunidad de utilizar otro algoritmo de coincidencia aproximado (que el de Levenshtein ) para una mejor evaluación del valor de error tipográfico (por ejemplo, Soundex ), o al menos este algoritmo se mejorará para permitir errores tipográficos del tipo "intercambio" (consulte la distancia Damerau-Levenshtein ).
Ver también
- Autómata de Levenshtein
- Comparación de motores de expresión regular
- Agrep
Referencias
- ^ "Tre para Windows" .
- ^ a b c "Uso de búsquedas difusas con tre-agrep" . Revista Linux .
- ^ a b "tre 0.8.0-6 (x86_64)" . 7 de julio de 2020.
- ^ Andoni, Alexandr; Krauthgamer, Robert; Onak, Krzysztof (2010). Aproximación polilogarítmica para la distancia de edición y la complejidad de la consulta asimétrica . IEEE Symp. Fundamentos de la informática (FOCS). arXiv : 1005.4033 . Código bibliográfico : 2010arXiv1005.4033A . CiteSeerX 10.1.1.208.2079 .
- ^ "Página web de TRE - Sintaxis de expresiones regulares" .
- ^ "Tre-agrep tiene todas las funciones de grep, pero también puede ser ambiguo o difuso"
- ^ "Página web de TRE - Acerca de" .
- ^ "Página web de TRE - Preguntas frecuentes" .
- ^ "Expresiones regulares como se usa en R" .
- ^ "Autómatas finitos deterministas etiquetados con Lookahead" .
mejoras prácticas .. Algoritmo de Lurikari, en particular ..
enlaces externos
- TRE: la biblioteca de coincidencia de expresiones regulares aproximadas, gratuita y portátil
Otras lecturas
- Navarro, Gonzalo (marzo de 2001), "Una visita guiada para aproximar la coincidencia de cadenas", Encuestas de computación de ACM , 33 (1): 31–88, CiteSeerX 10.1.1.452.6317 , doi : 10.1145 / 375360.375365 , S2CID 207551224