En informática , el algoritmo de coincidencia de comodines de Krauss es un algoritmo de coincidencia de patrones . Basado en la sintaxis de comodines de uso común, por ejemplo, en la interfaz de línea de comandos de Microsoft Windows , el algoritmo proporciona un mecanismo no recursivo para hacer coincidir patrones en aplicaciones de software, basado en una sintaxis más simple que la que ofrecen las expresiones regulares .
Historia
El algoritmo se basa en un historial de desarrollo, pruebas de corrección y rendimiento, y comentarios del programador que comenzaron con una búsqueda infructuosa de un algoritmo no recursivo confiable para la coincidencia de comodines. Un algoritmo inicial, implementado en un solo ciclo while, rápidamente provocó comentarios de los desarrolladores de software, lo que condujo a mejoras. [1] Comentarios y sugerencias en curso [2] [3] culminaron en un algoritmo revisado aún implementado en un solo ciclo while pero refinado en base a una colección de casos de prueba y un perfilador de desempeño . [4] La experiencia de ajustar el bucle while simple utilizando el generador de perfiles impulsó el desarrollo de una estrategia de dos bucles que logró mayores ganancias de rendimiento, particularmente en situaciones que involucran cadenas de entrada vacías o entradas que no contienen caracteres comodín. [5] El algoritmo de dos bucles está disponible para su uso por parte de la comunidad de desarrollo de software de código abierto , según los términos de la licencia Apache v. 2.0, y se acompaña de un código de caso de prueba.
Uso
El algoritmo disponible bajo la licencia de Apache se implementa tanto en C ++ basado en punteros como en C ++ portátil (implementado sin punteros). El código del caso de prueba, también disponible bajo la licencia de Apache, se puede aplicar a cualquier algoritmo que proporcione las siguientes operaciones de coincidencia de patrones. La implementación codificada no puede manejar juegos de caracteres multibyte y plantea problemas cuando el texto que se busca puede contener múltiples juegos de caracteres incompatibles.
Operaciones de coincidencia de patrones
El algoritmo admite tres operaciones de coincidencia de patrones:
- Se realiza una coincidencia uno a uno entre el patrón y la fuente para comprobar si existe una coincidencia, con la excepción de los caracteres de asterisco ( * ) o signo de interrogación ( ? ) En el patrón.
- Un carácter de asterisco ( * ) coincide con cualquier secuencia de cero o más caracteres.
- Un carácter de signo de interrogación ( ? ) Coincide con cualquier carácter.
Ejemplos de
- * foo * coincide con cualquier cadena que contenga "foo".
- mini * coincide con cualquier cadena que comience con "mini" (incluida la cadena "mini").
- ??? * coincide con cualquier cadena de tres o más letras.
Aplicaciones
El algoritmo original ha sido adaptado al lenguaje de programación DataFlex por Larry Heiges [6] para su uso con la biblioteca de códigos Data Access Worldwide . Se ha publicado en GitHub en forma modificada como parte de un lector de archivos de registro. [7] El algoritmo de 2014 es parte del Unreal Model Viewer integrado en el motor de juego Unreal Engine de Epic Games . [8] [9]
Ver también
Referencias
- ^ Krauss, Kirk (2008). "Coincidencia de comodines: un algoritmo" . Diario del Dr. Dobb .
- ^ "búsqueda con comodines" . alt.os.development. 2008.
- ^ TJ (2014). "coincidencia de comodines en la cadena de texto" . Desbordamiento de pila.
- ^ Krauss, Kirk (2014). "Coincidencia de comodines: una forma empírica de domar un algoritmo" . Diario del Dr. Dobb .
- ^ Krauss, Kirk (2018). "Coincidencia de comodines: un algoritmo mejorado para Big Data" . Desarrollar para el rendimiento.
- ^ Heiges, Larry (2008). "Función de comparación de texto - generalTextCompare.txt" . Biblioteca de códigos de acceso a datos en todo el mundo .
- ^ Deniskore (2013). "Deniskore / comodín / CLogReader.cpp" . Repositorios populares . GitHub. Líneas 173-279.
- ^ gildor2 (2016). "UModel / Core / Core.cpp" . Visor de modelos de Unreal Engine (visor de UE) . GitHub. Líneas 334-435.
- ^ gildor2 (2016). "Historial de UModel / Core / Core.cpp" . Visor de modelos de Unreal Engine (visor de UE) .