String matching for wildcard-based records

Question

Let's say that we have a string "1.2.3" and want to find a match for it in the following records:

1.2.9
1.4.5
1.*.3

For each record:

• The . is a separator that divides the string into segments.
• Each segment can have a static value or * that matches any segment value.
• There are no duplicated records. If there are multiple matches for a given string, only one is returned, following an exact match and left to right rule. So, for the following hypothetical matches for 1.2.3, the previous has priority over the latter: 1.2.3 > 1.2.* > 1.*.3 > *.2.3.

In the initial example, the matching record will be "1.*.3".

Note: here, the numbers used to represent a record are a simplification of a more complex, unpredictable, variable-sized value, such as abc.wxyz.fghijklm. So it is not possible to build tables for possible wildcard values.

I'm looking for the (theoretically) fastest lookup algorithm to find a matching record in memory given these non-requirements:

• Longest prefix matches are not a requirement;
• Only lookup speed matters: record insertion or deletion are not required to be fast;
• Memory space efficiency is not a requirement.

I experimented a range of trie variants and I am guessing (sorry if this sounds naive) that tries, or any datastructure, can't find a match for the proposed problem without backtracking. I'd appreciate some comments on this.

So, which datastructure would best fit my (non-)criteria?

Answer 1

One candidate approach would be build a BDD or a deterministic finite-state automaton that accepts all strings that match at least one of the records in your set of records. These data structures can handle wildcards. To use a BDD, treat each segment as a bit string, so the alphabet is $\{0,1,.\}$ (perhaps it's now a trinary decision diagram rather than a binary decision diagram, but the ideas remain the same).

---

An alternative approach (if the number of segments per string will always be relatively small): You can solve your problem by building a set of indices, one index for each subset of possible segments.

Suppose we're guaranteed that every string will have exactly 3 segments, call them segments ABC. We're now going to build seven indices:

• The ABC index contains the set of all records with no wildcard. e.g., 1.2.3
• The AB index contains the set of all records with a single wildcard, in the 3rd (C) segment. e.g., 1.2.*
• The AC index contains the set of all records with a single wildcard, in the 2nd (B) segment. e.g., 1.*.3
• The BC index contains the set of all records with a single wildcard, in the 1st (A) segment. e.g., *.2.3
• The A index contains the set of all records with two wildcards, in the 2nd and 3rd (B and C) segments. e.g., 1.*.*
• The B index contains the set of all records with two wildcards, in the 1st and 3rd (A and C) segments. e.g., *.2.*
• The C index contains the set of all records with two wildcards, in the 1st and 2nd (A and B) segments. e.g., *.*.3
• I assume you won't have any records with three wildcards (*.*.*), but if that was possible, you'd have an 8th index that records whether you have such a record or not.

Each index is stored as a hash table, so given a string you can quickly (in $O(1)$ time) check whether that string is present in that index.

Now, when you receive a string 4.5.6, you look it up in each index. For instance, you look up 4.5.6 in the ABC index, 4.5.* in the AB index, 4.*.6 in the AC index, and so on. If any of these lookups succeeds, then you know that 4.5.6 matches one of the records. Otherwise, 4.5.6 does not match any of the records. The running time for a lookup is $O(1)$.

If you know that every string will have exactly 5 segments, you'll need 31 indices and the time for a lookup is $O(1)$ (31 lookups into 31 hashtables). If every string has exactly 5 segments and you know that no record will have more than 2 wildcards, then it's enough to have $1+5+10=16$ indices.

This will probably be OK for your particular parameters, where every string has at most 5 segments. Obviously, though, if the number of segments is too large, this will be extremely slow and inefficient.

Answer 2

Edit: I was short on time earlier, but I'll expand my reasoning a bit:

Assumptions:

1. No bound on insertion time or memory size.

2. Lookup speed should be minimal, ie O(query length) which is the time to read the input.

3. Backtracking during search or any extra search time beyond O(length) would violate #2.

Given that there are no constraints on memory or insertion time, one solution is to enumerate each wildcard during insertion, with backtracking, and insert each key generated in a trie or hash table.

So for 1.*.3 above you generate 1.0.3, 1.1.3, ... and insert them into the index. For multiple wildcards this obviously becomes large, but it guarantees that any match will be found as-is in the index.

This idea simply moves any backtracking to the insertion phase, and guarantees optimal search times.

Rivest also gives some ways to bound this process if #1 is not actually true; his approach in this case would be to reduce the number of keys in the index by allowing some wildcards, but only up to a fixed number k, so that the amount of backtracking during search is O(1).

A quick example:

Say k=1 but we're inserting a key $2.*.3.*$; we generate all keys

2.[0-9].3.* = 2.0.3.*, 2.1.3.*, etc.
2.*.3.[0-9]

And insert them in the index. Then at search time, if we have a key

2.1.3.1

We generate and search for all 1-wildcard variants:

*.1.3.1
2.*.3.1  (match)
2.1.*.1
2.1.3.*  (match)

and probe for those exact strings; the number of variants is bounded by our choice of k (and the key length).

=== original:

Your situation is a bit reversed from the usual partial match problem, where the wildcards appear in the queries, but the data is fixed.

If the number of wildcards is bounded, you can expand the wildcards on insertion to get o(length) lookup time.