Krauss wildcard-matching algorithm: Difference between revisions

Revision as of 06:52, 9 May 2018

Latest revision as of 11:39, 16 August 2025

(15 intermediate revisions by 9 users not shown)

Line 1:

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

{{AFC submission|t||ts=20180509065111|u=JuliusClimacus|ns=118|demo=}}<!-- Important, do not remove this line before article has been created. -->

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

== 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.<ref>{{cite journal|magazine |last=Krauss| |first=Kirk |date=August 26, 2008 |year= |title=Matching Wildcards: An Algorithm| publisher|url=[[Drhttp://www.drdobbs.com/architecture-and-design/matching-wildcards-an-algorithm/210200888 Dobb's Journal]]| yearurl-status=2008|dead |archive-url=httphttps://web.archive.org/web/20241204085600/https://www.drdobbs.com/architecture-and-design/matching-wildcards-an-algorithm/210200888 |archive-date=4 December 2024 |magazine=[[Dr. Dobb's Journal]]}}</ref> Ongoing comments and suggestions<ref>{{cite web| title=wild card searching| publisher=alt.os.development| year=2008| url=https://groups.google.com/forum/#!topic/alt.os.development/8-rIaarASu8}}</ref><ref>{{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}}</ref> culminated in a revised algorithm still implemented in a single while loop but refined based on a collection of [[test case (software)|test case]]s and a [[profiling (computer programming)|performance profiler]].<ref>{{cite journalmagazine| last=Krauss| first=Kirk| title=Matching Wildcards: An Empirical Way to Tame an Algorithm| publishermagazine=[[Dr. Dobb's Journal]]| year=2014| url=http://www.drdobbs.com/architecture-and-design/matching-wildcards-an-empirical-way-to-t/240169123}}</ref> 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.<ref>{{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}}</ref> 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 (computer programming)|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 [[Variable-width encoding|multibyte character sets]] and poses problems when the text being searched may contain multiple incompatible character sets.

=== Pattern matching operations ===

The algorithm supports three pattern matching operations:

* A one-to-one match is performed between the pattern and the source to be checked for a match, with the exception of asterisk ([[*]]) or question mark ([[?]]) characters in the pattern.

Line 18 ⟶ 17:

* ''mini*'' matches any string that begins with "mini" (including the string "mini" itself).

* ''???*'' matches any string of three or more letters.

== Applications ==

The original algorithm has been ported to the [[DataFlex]] programming language by Larry Heiges<ref>{{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)}}</ref> for use with [[Visual DataFlex|Data Access Worldwide]] code library. It has been posted on GitHub in modified form as part of a log file reader.<ref>{{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.</ref> The 2014 algorithm is part of the Unreal Model Viewer built into the Epic Games [[Unreal Engine]] [[game engine]].<ref>{{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.</ref><ref>{{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}}</ref>

== See also ==

Line 26 ⟶ 28:

== References ==

{{reflist}}

[[Category:Pattern matching]]