Algorithme de correspondance des caractères génériques de Krauss - Krauss wildcard-matching algorithm
En informatique , l' algorithme de correspondance générique de Krauss est un algorithme de correspondance de motifs . Basé sur la syntaxe générique couramment utilisée, par exemple dans l' interface de ligne de commande de Microsoft Windows , l'algorithme fournit un mécanisme non récursif pour faire correspondre les modèles dans les applications logicielles, basé sur une syntaxe plus simple que celle généralement offerte par les expressions régulières .
Histoire
L'algorithme est basé sur un historique du développement, des tests d'exactitude et de performances, et des commentaires du programmeur qui ont commencé par une recherche infructueuse d'un algorithme non récursif fiable pour faire correspondre les caractères génériques. Un premier algorithme, implémenté en une seule boucle while, a rapidement suscité des commentaires de la part des développeurs de logiciels, conduisant à des améliorations. Les commentaires et suggestions en cours ont abouti à un algorithme révisé toujours implémenté dans une seule boucle while mais affiné sur la base d'une collection de cas de test et d'un profileur de performances . L'expérience du réglage de la boucle while unique à l'aide du profileur a incité le développement d'une stratégie à deux boucles qui a permis d'obtenir des gains de performances supplémentaires, en particulier dans des situations impliquant des chaînes d'entrée vides ou une entrée ne contenant aucun caractère générique. L'algorithme à deux boucles est disponible pour une utilisation par la communauté de développement de logiciels open source , sous les termes de la licence Apache v. 2.0, et est accompagné d'un code de cas de test.
Usage
L'algorithme mis à disposition sous la licence Apache est implémenté à la fois en C ++ basé sur des pointeurs et en C ++ portable (implémenté sans pointeurs). Le code du cas de test, également disponible sous la licence Apache, peut être appliqué à tout algorithme qui fournit les opérations de correspondance de modèle ci-dessous. L'implémentation telle que codée ne peut pas gérer les jeux de caractères multi-octets et pose des problèmes lorsque le texte recherché peut contenir plusieurs jeux de caractères incompatibles.
Opérations de correspondance de modèle
L'algorithme prend en charge trois opérations de correspondance de modèles:
- Une correspondance biunivoque est effectuée entre le modèle et la source à vérifier pour une correspondance, à l'exception des caractères astérisque ( * ) ou point d'interrogation ( ? ) Dans le modèle.
- Un caractère astérisque ( * ) correspond à toute séquence de zéro caractère ou plus.
- Un caractère point d'interrogation ( ? ) Correspond à n'importe quel caractère unique.
Exemples
- * foo * correspond à toute chaîne contenant "foo".
- mini * correspond à toute chaîne commençant par "mini" (y compris la chaîne "mini" elle-même).
- ??? * correspond à n'importe quelle chaîne de trois lettres ou plus.
Applications
L'algorithme original a été porté au langage de programmation DataFlex par Larry Heiges pour une utilisation avec la bibliothèque de codes Data Access Worldwide . Il a été publié sur GitHub sous une forme modifiée dans le cadre d'un lecteur de fichier journal. L'algorithme 2014 fait partie de l'Unreal Model Viewer intégré au moteur de jeu Epic Games Unreal Engine .