Algoritmo de coincidencia de comodines de Krauss

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 la coincidencia de patrones en aplicaciones de software, basado en una sintaxis más simple que la que suelen ofrecer las expresiones regulares .

El algoritmo se basa en un historial de desarrollo, pruebas de corrección y rendimiento, y comentarios de programadores 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 bucle while, rápidamente generó comentarios de desarrolladores de software, lo que llevó a mejoras. ^{[ 1 ]} Los comentarios y sugerencias continuos ^{[ 2 ] [ 3 ]} culminaron en un algoritmo revisado que aún se implementa en un solo bucle while, pero refinado en base a una colección de casos de prueba y un perfilador de rendimiento . ^{[ 4 ]} La experiencia de ajustar el bucle while simple usando el perfilador 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 entrada que no contiene caracteres comodín. ^{[ 5 ]} El algoritmo de dos bucles está disponible para su uso por la comunidad de desarrollo de software de código abierto , bajo los términos de la Licencia Apache v. 2.0, y viene acompañado de código de casos de prueba.

El algoritmo, disponible bajo la licencia Apache, está implementado tanto en C++ con punteros como en C++ portable (sin punteros). El código de prueba, también disponible bajo la licencia Apache, puede aplicarse a cualquier algoritmo que proporcione las operaciones de coincidencia de patrones descritas a continuación. La implementación actual no admite conjuntos de caracteres multibyte y presenta problemas cuando el texto buscado contiene varios conjuntos de caracteres incompatibles.

• *foo* coincide con cualquier cadena que contenga "foo".
• mini* coincide con cualquier cadena que comience con "mini" (incluida la propia cadena "mini").
• ???* coincide con cualquier cadena de tres o más letras.

El algoritmo original fue adaptado al lenguaje de programación DataFlex por Larry Heiges ^{[ 6 ]} para su uso con la biblioteca de código Data Access Worldwide . Se publicó en GitHub en forma modificada como parte de un lector de archivos de registro. ^{[ 7 ]} El algoritmo de 2014 forma parte del Unreal Model Viewer integrado en el motor de juego Unreal Engine de Epic Games . ^{[ 8 ] [ 9 ]}

• coincidencia de patrones
• glob (programación)
• Wildmat