How to search for Model Numbers that contain wildcards?

Question

I have a database full of ModelNumbers that I want a user to be able to search for. The tricky part is that some of the model numbers have lots of funny characters including:

* - Alphanumeric wildcard
# - Numeric wildcard
(AB,CD) - List of options

So for example model number 1234#*(AB,CD)

The following searches should return this model number:

1. 12341ACD - full part number with options
2. 12341A - "starts with" with some wildcards filled in.
3. 2341 - "contains" with some wildcards filled in.

I have attempted to use regular expressions. I have written some code to convert these wild card characters into regular expressions; that code was relatively easy and I have good unit tests for it. A regular expression of 1234[0-9]?[A-Z0-9]?(AB|CD)? will work for the first search string; the regex will not for #2 and #3 since it only matches a part of the pattern.

I tried using PCRE with partial matching, but the intent for that is for evaluating the regex as a user types (from left to right), so the partial match only works for #1 and #2.

I do not want to use fuzzy matching. I am trying to return only specific matching model numbers. The results of the search will represent "qualified" model numbers, so I cannot return model numbers that are only "close" to the search text.

How can I do this? I'm not looking for help with the code, but maybe instead for a strategy. Is there some way to use a regex with only a "contains" type of match? Should I use regex at all for this?

Answer 1

I created an iterator which would generate literal model numbers from the wildcard pattern. This worked but the technique ended up generating way too many model numbers. A numeric wildcard is not so bad, but the number of permutations for an alpha-numeric wildcard adds up VERY fast; just 4 wildcards would yield more than a million permutations.

    /// <summary>
    /// Get a distinct list of permutations of a model number by filling in wildcards with actual values.
    /// </summary>
    /// <remarks>
    /// This algorithm does not have the best performance as we parse and calculate the options in each iteration.
    /// I suppose the options and literals could be a list so that we only need to process once and then use the sequence
    /// to fill in values.
    /// </remarks>
    /// <param name="input"></param>
    /// <returns></returns>
    public static IEnumerable<string> GetPermutations(string input)
    {
        var countPermutations = CountPermutations(input);

        if (countPermutations <= 1)
        {
            yield return input;
        }
        
        input = WildcardConverter.Normalize(input);

        for (int sequence = 0; sequence < countPermutations; sequence++)
        {
            yield return GetPermutation(input, sequence);
        }
    }

    private static string GetPermutation(string input, int sequence)
    {
        var permutation = new StringBuilder(string.Empty);
        var inParens = false;
        var optionFillers = new List<string>();
        var currentOption = "";
        foreach (var chr in input)
        {
            if (chr.IsFillerWildcard())
            {
                var fillCount = chr.GetFillCount();
                var fillerIndex = sequence % fillCount;
                sequence = sequence / fillCount;
                permutation.Append(WildcardData.FillCharacters[fillerIndex]);
            }
            else if (chr == '(')
            {
                inParens = true;
                optionFillers = new List<string>();
                optionFillers.Add(""); // blank option
                currentOption = "";
            }
            else if (chr == ',')
            {
                optionFillers.Add(currentOption);
                currentOption = "";
            }
            else if (chr == ')')
            {
                inParens = false;
                optionFillers.Add(currentOption);
                var fillerIndex = sequence % optionFillers.Count;
                permutation.Append(optionFillers[fillerIndex]);
            }
            else
            {
                if (inParens)
                {
                    // Parse multi-character option
                    currentOption += chr;
                }
                else
                {
                    // Tack on a literal value
                    permutation.Append(chr);
                }
            }
        }

        return permutation.ToString();
    }