“Krauss matching wildcards algorithm”的意思、由来-开放百科全书

In computer science, the Krauss matching wildcards algorithm is a pattern matching algorithm. Based on the wildcard syntax in common use, e.g. in the Microsoft Windows command-line interface, the algorithm provides a non-recursive mechanism for matching patterns in software applications, based on syntax simpler than that typically offered by regular expressions.

History

The algorithm is based on a history of development, correctness and performance testing, and programmer feedback that began with an unsuccessful search for a reliable non-recursive algorithm for matching wildcards. An initial algorithm, implemented in a single while loop, quickly prompted comments from software developers, leading to improvements.^[1] Ongoing comments and suggestions^[2]^[3] culminated in a revised algorithm still implemented in a single while loop but refined based on a collection of test cases and a performance profiler.^[4] The experience tuning the single while loop using the profiler prompted development of a two-loop strategy that achieved further performance gains, particularly in situations involving empty input strings or input containing no wildcard characters.^[5] The two-loop algorithm is available for use by the open-source software development community, under the terms of the Apache License v. 2.0, and is accompanied by test case code.

Usage

The algorithm made available under the Apache license is implemented in both pointer-based C++ and portable C++ (implemented without pointers). The test case code, also available under the Apache license, can be applied to any algorithm that provides the pattern matching operations below. The implementation as coded is unable to handle multibyte character sets and poses problems when the text being searched may contain multiple incompatible character sets.

Pattern matching operations

Examples

Applications

The original algorithm has been ported to the DataFlex programming language by Larry Heiges^[6] for use with Data Access Worldwide code library. It has been posted on GitHub in modified form as part of a log file reader.^[7] The 2014 algorithm is part of the Unreal Model Viewer built into the Epic Games Unreal Engine game engine.^[8]^[9]

See also

References

1. ^{{cite journal| last=Krauss| first=Kirk| title=Matching Wildcards: An Algorithm| publisher=Dr. Dobb's Journal| year=2008| url=http://www.drdobbs.com/architecture-and-design/matching-wildcards-an-algorithm/210200888}}
2. ^{{cite web| title=wild card searching| publisher=alt.os.development| year=2008| url=https://groups.google.com/forum/#!topic/alt.os.development/8-rIaarASu8}}
3. ^{{cite web| last=T.J.| title=wild card matching in text string| year=2014| publisher=Stack Overflow| url=https://stackoverflow.com/questions/21409588/wild-card-matching-in-text-string}}
4. ^{{cite journal| last=Krauss| first=Kirk| title=Matching Wildcards: An Empirical Way to Tame an Algorithm| publisher=Dr. Dobb's Journal| year=2014| url=http://www.drdobbs.com/architecture-and-design/matching-wildcards-an-empirical-way-to-t/240169123}}
5. ^{{cite web| last=Krauss| first=Kirk| title=Matching Wildcards: An Improved Algorithm for Big Data| publisher=Develop for Performance| year=2018| url=http://www.developforperformance.com/MatchingWildcards_AnImprovedAlgorithmForBigData.html}}
6. ^{{cite web| work=Data Access Worldwide Code Library| last=Heiges| first=Larry| title=Text compare function - generalTextCompare.txt| year=2008| url=https://support.dataaccess.com/Forums/showthread.php?1064-Text-compare-function-generalTextCompare-txt-(0-1)}}
7. ^{{cite web| last=Deniskore| work=Popular repositories| title=Deniskore/wildcard/CLogReader.cpp| publisher=GitHub| year=2013| url=https://github.com/Deniskore/wildcard/blob/master/CLogReader.cpp}} Lines 173-279.
8. ^{{cite web| last=gildor2| work=Unreal Engine Model Viewer (UE Viewer)| title=UModel/Core/Core.cpp| publisher=GitHub| year=2016| url=https://github.com/gildor2/UModel/blob/master/Core/Core.cpp}} Lines 334-435.
9. ^{{cite web| last=gildor2| work=Unreal Engine Model Viewer (UE Viewer)| title=History for UModel/Core/Core.cpp| year=2016| url=https://github.com/gildor2/UModel/commits/master/Core/Core.cpp}}