Some programs need to compare a lot of text strings quickly. Text output filters, search engines, and natural-language processors are examples of applications where rapid text string comparison is important. Besides simple character-by-character comparisons, many text comparison routines need to support matching on wildcard characters. One of the strings might treat the "*" character as a special wildcard character; for example, *sip* should match mississippi.
When I searched for a textbook wildcard string-matching algorithm that would fit this need, I discovered that a good algorithm is harder to find than I had expected. The algorithms that I found posted on the Web were buggy, slow, and/or needlessly complex -- typically all three. So I developed my own. Some colleagues then told me that I could have found similar algorithms among open-source regular expression matching routines. I looked at some of those routines, but the ones that I found use recursion. I find recursive algorithms difficult to understand and debug. They’re also exposed to stack overflows; for example, if the input strings are lacking proper termination. It’s difficult, if not impossible, to prevent stack overflows in a recursive algorithm and still keep it performing fast -- and stack overflows are often fatal even in the face of exception-handling logic. When no stack space is available, it’s tricky to do so much as output a diagnostic message. There’s no such difficulty with my nonrecursive approach.
Listing One is a coded-up version of my algorithm, which does all of its processing in a single while loop. It not only handles wildcard ("*") characters, but also alternate string-termination characters. And it does all of this in a minimal number of clock cycles. It’s relatively compact and understandable, compared to the wildcard comparison routines I found by searching.
Listing One
// This function compares text strings, one of which can
// have wildcards ("*").
BOOL GeneralTextCompare(
char * pTameText,
// A string without wildcards
char * pWildText,
// A (potentially) corresponding string with wildcards
BOOL bCaseSensitive = FALSE,
// By default, match on "X" vs "x"
char cAltTerminator = '\0'
// For function names, for example, you can stop at the first "("
)
{
BOOL bMatch = TRUE;
char * pAfterLastWild = NULL;
// Location after last "*", if we've encountered one
char t, w;
// Walk the text strings one character at a time.
while (1)
{
t = *pTameText;
w = *pWildText;
// How do you match a unique text string?
if (!t || t == cAltTerminator)
{
// Easy: unique up on it!
if (!w || w == cAltTerminator)
{
break; // "x" matches "x"
}
else if (w == '*')
{
pWildText++;
continue; // "x*" matches "x" or "xy"
}
bMatch = FALSE;
break; // "x" doesn't match "xy"
}
else
{
if (!bCaseSensitive)
{
// Lowercase the characters to be compared.
if (t >= 'A' && t <= 'Z')
{
t += ('a' - 'A');
}
if (w >= 'A' && w <= 'Z')
{
w += ('a' - 'A');
}
}
// How do you match a tame text string?
if (t != w)
{
// The tame way: unique up on it!
if (w == '*')
{
pAfterLastWild = ++pWildText;
continue; // "*y" matches "xy"
}
else if (pAfterLastWild)
{
pWildText = pAfterLastWild;
w = *pWildText;
if (!w || w == cAltTerminator)
{
break; // "*" matches "x"
}
else if (t == w)
{
pWildText++;
}
pTameText++;
continue; // "*sip*" matches "mississippi"
}
else
{
bMatch = FALSE;
break; // "x" doesn't match "y"
}
}
}
pTameText++;
pWildText++;
}
return bMatch;
}
The two text strings passed as input into the algorithm include a tame string, which contains no wildcard characters, and a wild string that may contain one or more wildcard characters. The two strings are traversed in parallel during processing. In Listing One, the first if clause in the loop checks for termination of the tame string. If the wild string has additional characters by the time processing reaches the end of the tame string, and if at least one of those additional characters in the wild string is not a wildcard character, then the strings don’t match. Most of the remaining code is in the big else clause corresponding to this first if clause.
In the big else clause, the first thing that happens is that an instant character from each string (both tame and wild) is lowercased, if the caller has specified case insensitivity. The core wildcard matching code is found in the several lines of code following the lowercasing operation. This core code executes only when the instant characters from the tame and wild strings don’t match. One of those nonmatching characters will be either a wildcard character, or it won’t. If it is, then a pointer to the next character after the wildcard is saved. Otherwise, the strings don’t match, unless such a pointer has already been saved during earlier processing, meaning the algorithm has encountered a wildcard character already. When that is the case, processing continues from the character after that previous wildcard character, which is compared with the instant character from the tame string. Then the following occurs:
- The string termination condition is checked, this time for the
wildstring, to ensure that it actually has additional valid characters to compare at this point. - If there are no valid characters, then there is nothing more to do.
- Otherwise, one of two things can happen: 1. If the instant characters from the tame and wild strings now match, the algorithm continues by comparing the next characters from each string; or 2. if those characters don’t match, the algorithm continues by comparing the same instant character from the
wildstring with the next character from the tame string.
After the big else clause, if the core code has not already continued from the top of the loop, the algorithm moves on to select the next pair of characters from each string, then it returns to the top of the loop to compare them.
If you use the debugger to check the algorithm's ability to compare the text string Mississippi against *sip*, this is what you’ll see looking at the Watch window view associated with the tame and wild string pointers. The algorithm compares the left-most characters of each string, moving through each string one character at a time, such that the debugger shows this representation of the two string pointers as you’re stepping through:
mississippi *sip*
mississippi sip*
ississippi sip*
ssissippi sip*
sissippi ip*
sissippi sip*
issippi ip*
ssippi p*
ssippi sip*
sippi ip*
sippi sip*
ippi ip*
ppi p*
pi *
i *
Clearly, the number of character comparisons performed by this algorithm is near to the minimum that can possibly be achieved, because that number is not much greater than the number of characters in the tame string Mississippi. Alternate approaches, such as the use of strchr(), typically lack equivalent computational performance, particularly when multiple wildcard characters are specified, as in this *sip* example.
The algorithm can be enhanced to support Unicode without much trouble. There are several ways to go about that, depending on which platform and toolset you’re using. If you’re a Windows programmer, for example, you could do what MFC does to arrange Unicode support. The CString class from the MFC library provided with Visual Studio .NET 2005 provides UTF-8 support by invoking multibyte string-handling routines from the C runtime library. The CString class includes a ::CompareNoCase() method that invokes _mbsicmp(). If you build a sample program that passes a Unicode string to CString::CompareNoCase() and debug it, you can follow the call into _mbsicmp() to observe how the UTF-8 conversions are arranged. You could then code the same underlying calls to do similar conversions to endow this algorithm with CString-like locale enablement.
Kirk is a software developer working on IBM Rational PurifyPlus. He can be contacted at [email protected].
