Efficient String Lookup?

Chris S. chrisks at NOSPAM.udel.edu
Sun Oct 17 09:18:07 CEST 2004


Bengt Richter wrote:

> On Sun, 17 Oct 2004 05:50:49 GMT, "Chris S." <chrisks at NOSPAM.udel.edu> wrote:
>>Sorry for the ambiguity. My case is actually pretty simple. '#' 
>>represents any single character, so it's essentially the same as re's 
>>'.'. The match must be exact, so the string and pattern must be of equal 
>>lengths. Each wildcard is independent of other wildcards. For example, 
>>suppose we restricted the possible characters to 1 and 0, then the 
>>pattern '##' would only match '00', '01', '10', and '11'. This pattern 
>>would not match '0', '111', etc. I feel that a trie would work well, but 
>>I'm concerned that for large patterns, the overhead in the Python 
>>implementation would be too inefficient.
> 
> 
> So is the set of patterns static and you want to find which pattern(s!)
> match dynamic input? How many patterns vs inputs strings? What max
> length patterns, input strings? Total volume?

Patterns and inputs are dynamic, input more so than patterns. The 
number, length, and volume of patterns and strings should be arbitrary.



More information about the Python-list mailing list