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:
.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:
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?