Posts Tagged: Wildcard Matching

Fast Wildcard Matching in C Sharp

Recently I have been working on a .u3d (ECMA 363 4th Edition) compliant decoder in c#. In the specification for the External File Reference block is the requirement to support file name filters that may have the wildcard characters ‘?’ and ‘*’. Dot Net does not include a native method for matching wildcards characters in strings, so I went online to see what solutions others have come up with.

Turns out a really popular response to matching wildcards is to use RegEx. Unless the application is just doing this check once and never again, I cannot communicate just how poor this solution is. It is by far the simplest; a couple lines of code and you are done. RegEx is very powerful but that power comes at a cost; I had to remove it from the full test as it was just too time consuming. Recursive algorithms also seem to be a popular choice, but again they can be slow. I tried the Visual Basic “trick” and even though the performance was more suitable it failed on many of the test cases. The test consists of 100 different strings and wildcard strings that I gathered from the web. Some are “gotchas” intended to test if the method meets the requirements of wildcard rules others are possible uses like URLs. I did eventually find a method that only fails on one test case. I still felt this method was too slow for use in a file loader/decoder. So I decided to throw my hat into the ring and see if there was any way, ugly or elegant that would be faster and still pass every test. I am accustomed to writing real time code that must perform its duty fast enough that the application can go through a full update in 16-33 milliseconds (60 – 30 frames per second). I was determined even if it had to be some sort of dirty hack.