Efficient String Lookup?

Re: Efficient String Lookup?

Chris S. wrote:[color=blue]
> I have a number of strings, containing wildcards (e.g. 'abc#e#' where #
> is anything), which I want to match with a test string (e.g 'abcdef').
> What would be the best way for me to store my strings so lookup is as
> fast as possible?[/color]

If it were me, I would store them as compiled regular expressions.

See the re module documentation and use re.compile().

If you want a better solution, it might help if you supply a little more
information about your problem and why this solution is unsuitable
(maybe it is :]).
--
Michael Hoffman

Re: Efficient String Lookup?

Chris S. wrote:
[color=blue]
> I have a number of strings, containing wildcards (e.g. 'abc#e#' where #
> is anything), which I want to match with a test string (e.g 'abcdef').
> What would be the best way for me to store my strings so lookup is as
> fast as possible?[/color]

As a compiled regular expression, I guess - you don't give much info here,
so maybe there is a better way. But to me it looks like a classic regexp
thing. Maybe if your wildcards are equivalent to .*, then using subsequent
string searches lik this helps you:

pattern = 'abc#e#'.split( '#')
s = 'abcdef'
found = True
pos = 0
for p in pattern:
h = s.find(p)
if h != -1:
p = h + 1b
else:
found = False


That might be faster, if the string.find operation uses something else than
simple brute force linear searching - but I don't know enough about the
internals of python's string implementation to give an definite answer
here.

But to be honest: I don't think regexps are easy to beat, unless your
usecase is modeled in a way that makes it prone to other approaches.

--
Regards,

Diez B. Roggisch

Re: Efficient String Lookup?

[color=blue]
> I have a number of strings, containing wildcards (e.g. 'abc#e#' where #
> is anything), which I want to match with a test string (e.g 'abcdef').
> What would be the best way for me to store my strings so lookup is as
> fast as possible?[/color]

Start with a Trie, and virtually merge branches as necessary.

- Josiah

Re: Efficient String Lookup?

Josiah Carlson wrote:[color=blue][color=green]
>>I have a number of strings, containing wildcards (e.g. 'abc#e#' where #
>>is anything), which I want to match with a test string (e.g 'abcdef').
>>What would be the best way for me to store my strings so lookup is as
>>fast as possible?[/color]
>
>
> Start with a Trie, and virtually merge branches as necessary.
>
> - Josiah
>[/color]

Yup, you might also have a look at the Aho-Corasick algorithm, which can
match a test string against a big number of strings quite efficiently :



You'll have to adapt the algorithm so that it can handle your wilcard,
though. I found it easy to implement the '.' (one character wildcard),
but the '.*' (zero or more character wildcard) forces you to have
backtracking.

But if you can use the regexp engine, do not hesitate, it will save you
a lot of headaches. Unless of course you're a student and your teacher
asked you this question ;).

Regards,

Nicolas

Re: Efficient String Lookup?

Michael Hoffman wrote:[color=blue]
> Chris S. wrote:
>[color=green]
>> I have a number of strings, containing wildcards (e.g. 'abc#e#' where
>> # is anything), which I want to match with a test string (e.g
>> 'abcdef'). What would be the best way for me to store my strings so
>> lookup is as fast as possible?[/color]
>
>
> If it were me, I would store them as compiled regular expressions.
>
> See the re module documentation and use re.compile().
>
> If you want a better solution, it might help if you supply a little more
> information about your problem and why this solution is unsuitable
> (maybe it is :]).[/color]

The problem is I want to associate some data with my pattern, as in a
dictionary. Basically, my application consists of a number of
conditions, represented as strings with wildcards. Associated to each
condition is arbitrary data explaining "what I must do". My task is to
find this data by match a state string with these condition strings. Of
course, the brute force approach is to just add each pattern to a
dictionary, and linearly seach every key for a match. To improve this, I
considered a trie, implemented as a special dictionary:

class Trie(dict):
'''Implements a traditional Patricia-style Tria.
Keys must be sequence types. None key represents a value.'''

def __init__(self):
dict.__init__(s elf)

def __setitem__(sel f, key, value):
assert key, 'invalid key '+str(key)
d = self
last = None
for n in key:
if n not in d:
dict.__setitem_ _(d, n, {})
last = (d,n)
d = dict.__getitem_ _(d, n)
(d,n) = last
dict.__getitem_ _(d, n)[None] = value

def __getitem__(sel f, key):
d = self
for n in key:
assert n in d, 'invalid key '+str(key)
d = dict.__getitem_ _(d, n)
assert None in d, 'missing value for key '+str(key)
return dict.__getitem_ _(d, None)

def __delitem__(sel f, key):
previous = []
d = self
for n in key:
assert n in d, 'invalid key '+str(key)
previous.append ((d,n))
d = dict.__getitem_ _(d, n)
assert None in d, 'missing value for key '+str(key)
# remove value
dict.__delitem_ _(d, None)
# find and remove empty keys
while len(previous):
(d,n) = previous.pop()
if not len(dict.__geti tem__(d, n)):
dict.__delitem_ _(d, n)
else:
break

However, I'm uncertain about the efficiency of this approach. I'd like
to use regexps, but how would I associate data with each pattern?

Re: Efficient String Lookup?

Diez B. Roggisch wrote:
[color=blue]
> That might be faster, if the string.find operation uses something else than
> simple brute force linear searching - but I don't know enough about the
> internals of python's string implementation to give an definite answer
> here.
>
> But to be honest: I don't think regexps are easy to beat, unless your
> usecase is modeled in a way that makes it prone to other approaches.[/color]

The problem is, I want to find all patterns that match my test string,
so even with re I'd still have to search through every pattern, which is
what I'm trying to avoid. Something like a trie might be better, but
they don't seem very efficient when implemented in Python.

Re: Efficient String Lookup?

Chris S. wrote:[color=blue]
> The problem is I want to associate some data with my pattern, as in a
> dictionary. Basically, my application consists of a number of
> conditions, represented as strings with wildcards. Associated to each
> condition is arbitrary data explaining "what I must do".[/color]
...[color=blue]
> However, I'm uncertain about the efficiency of this approach. I'd like
> to use regexps, but how would I associate data with each pattern?[/color]

One way is with groups. Make each pattern into a regexp
pattern then concatenate them as
(pat1)|(pat2)|( pat3)| ... |(patN)

Do the match and find which group has the non-None value.

You may need to tack a "$" on the end of string (in which
case remember to enclose everything in a () so the $ doesn't
affect only the last pattern).

One things to worry about is you can only have 99 groups
in a pattern.

Here's example code.


import re

config_data = [
("abc#e#", "Reactor meltdown imminent"),
("ab##", "Antimatter containment field breach"),
("b####f", "Coffee too strong"),
]

as_regexps = ["(%s)" % pattern.replace ("#", ".")
for (pattern, text) in config_data]

full_regexp = "|".join(as_reg exps) + "$"
pat = re.compile(full _regexp)


input_data = [
"abadb",
"abcdef",
"zxc",
"abcq",
"b1234f",
]

for text in input_data:
m = pat.match(text)
if not m:
print "%s? That's okay." % (text,)
else:
for i, val in enumerate(m.gro ups()):
if val is not None:
print "%s? We've got a %r warning!" % (text,
config_data[i][1],)



Here's the output I got when I ran it


abadb? We've got a 'Antimatter containment field breach' warning!
abcdef? We've got a 'Reactor meltdown imminent' warning!
zxc? That's okay.
abcq? We've got a 'Antimatter containment field breach' warning!
b1234f? We've got a 'Coffee too strong' warning!


Andrew
dalke@dalkescie ntific.com

Re: Efficient String Lookup?

On Sat, 16 Oct 2004 09:11:37 GMT, "Chris S." <chrisks@NOSPAM .udel.edu> wrote:
[color=blue]
>I have a number of strings, containing wildcards (e.g. 'abc#e#' where #
>is anything), which I want to match with a test string (e.g 'abcdef').
>What would be the best way for me to store my strings so lookup is as
>fast as possible?[/color]

Insufficient info. But 'fast as possible' suggests putting your strings in
a flex grammar and generating a parser in c. See

Defining a grammar is a good exercise in precise definition of the problem anyway ;-)

If you want to do it in python, you still need to be more precise...

- is # a single character? any number of characters?
- if your test string were 'abcdefabcdef' would you want 'abc#e#' to match the whole thing?
or match abcdef twice?
- if one wild card string matches, does that "use up" the test string so other wild card strings
mustn't match? If so, what has priority? Longest? shortest? Other criterion?
- etc etc

Regards,
Bengt Richter

Re: Efficient String Lookup?

Bengt Richter wrote:
[color=blue]
> On Sat, 16 Oct 2004 09:11:37 GMT, "Chris S." <chrisks@NOSPAM .udel.edu> wrote:
>
>[color=green]
>>I have a number of strings, containing wildcards (e.g. 'abc#e#' where #
>>is anything), which I want to match with a test string (e.g 'abcdef').
>>What would be the best way for me to store my strings so lookup is as
>>fast as possible?[/color]
>
>
> Insufficient info. But 'fast as possible' suggests putting your strings in
> a flex grammar and generating a parser in c. See
> http://www.gnu.org/software/flex/
> Defining a grammar is a good exercise in precise definition of the problem anyway ;-)
>
> If you want to do it in python, you still need to be more precise...
>
> - is # a single character? any number of characters?
> - if your test string were 'abcdefabcdef' would you want 'abc#e#' to match the whole thing?
> or match abcdef twice?
> - if one wild card string matches, does that "use up" the test string so other wild card strings
> mustn't match? If so, what has priority? Longest? shortest? Other criterion?
> - etc etc[/color]

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.

Re: Efficient String Lookup?

Andrew Dalke wrote:
[color=blue]
> One way is with groups. Make each pattern into a regexp
> pattern then concatenate them as
> (pat1)|(pat2)|( pat3)| ... |(patN)
>
> Do the match and find which group has the non-None value.
>
> You may need to tack a "$" on the end of string (in which
> case remember to enclose everything in a () so the $ doesn't
> affect only the last pattern).
>
> One things to worry about is you can only have 99 groups
> in a pattern.
>
> Here's example code.
>
>
> import re
>
> config_data = [
> ("abc#e#", "Reactor meltdown imminent"),
> ("ab##", "Antimatter containment field breach"),
> ("b####f", "Coffee too strong"),
> ]
>
> as_regexps = ["(%s)" % pattern.replace ("#", ".")
> for (pattern, text) in config_data]
>
> full_regexp = "|".join(as_reg exps) + "$"
> pat = re.compile(full _regexp)
>
>
> input_data = [
> "abadb",
> "abcdef",
> "zxc",
> "abcq",
> "b1234f",
> ]
>
> for text in input_data:
> m = pat.match(text)
> if not m:
> print "%s? That's okay." % (text,)
> else:
> for i, val in enumerate(m.gro ups()):
> if val is not None:
> print "%s? We've got a %r warning!" % (text,
> config_data[i][1],)
>
>
>
> Here's the output I got when I ran it
>
>
> abadb? We've got a 'Antimatter containment field breach' warning!
> abcdef? We've got a 'Reactor meltdown imminent' warning!
> zxc? That's okay.
> abcq? We've got a 'Antimatter containment field breach' warning!
> b1234f? We've got a 'Coffee too strong' warning![/color]

Thanks, that's almost exactly what I'm looking for. The only downside I
see is that I still need to add and remove patterns, so continually
recompiling the expression might be expensive.

Re: Efficient String Lookup?

Andrew Dalke wrote:[color=blue]
> Here's the output I got when I ran it
>
>
> abadb? We've got a 'Antimatter containment field breach' warning!
> abcdef? We've got a 'Reactor meltdown imminent' warning!
> zxc? That's okay.
> abcq? We've got a 'Antimatter containment field breach' warning!
> b1234f? We've got a 'Coffee too strong' warning![/color]

Actually, I've noticed some strange behavior. It seems to match more
than one character per wild card. For instance, your code matches
'abaxile', 'abaze', and 'abbacomes' to the pattern 'ab##'. I'm not an
expert with rex, but your expression looks correct. What could be
causing this?

Re: Efficient String Lookup?

On Sun, 17 Oct 2004 05:50:49 GMT, "Chris S." <chrisks@NOSPAM .udel.edu> wrote:
[color=blue]
>Bengt Richter wrote:
>[color=green]
>> On Sat, 16 Oct 2004 09:11:37 GMT, "Chris S." <chrisks@NOSPAM .udel.edu> wrote:
>>
>>[color=darkred]
>>>I have a number of strings, containing wildcards (e.g. 'abc#e#' where #
>>>is anything), which I want to match with a test string (e.g 'abcdef').
>>>What would be the best way for me to store my strings so lookup is as
>>>fast as possible?[/color]
>>
>>
>> Insufficient info. But 'fast as possible' suggests putting your strings in
>> a flex grammar and generating a parser in c. See
>> http://www.gnu.org/software/flex/
>> Defining a grammar is a good exercise in precise definition of the problem anyway ;-)
>>
>> If you want to do it in python, you still need to be more precise...
>>
>> - is # a single character? any number of characters?
>> - if your test string were 'abcdefabcdef' would you want 'abc#e#' to match the whole thing?
>> or match abcdef twice?
>> - if one wild card string matches, does that "use up" the test string so other wild card strings
>> mustn't match? If so, what has priority? Longest? shortest? Other criterion?
>> - etc etc[/color]
>
>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
>implementati on would be too inefficient.[/color]

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?

Regards,
Bengt Richter

Re: Efficient String Lookup?

Chris S. wrote:
[color=blue]
> Andrew Dalke wrote:
>[color=green]
>> Here's the output I got when I ran it
>>
>>
>> abadb? We've got a 'Antimatter containment field breach' warning!
>> abcdef? We've got a 'Reactor meltdown imminent' warning!
>> zxc? That's okay.
>> abcq? We've got a 'Antimatter containment field breach' warning!
>> b1234f? We've got a 'Coffee too strong' warning![/color]
>
>
> Actually, I've noticed some strange behavior. It seems to match more
> than one character per wild card. For instance, your code matches
> 'abaxile', 'abaze', and 'abbacomes' to the pattern 'ab##'. I'm not an
> expert with rex, but your expression looks correct. What could be
> causing this?[/color]

Spoke too soon. I seems all you needed was to change:

full_regexp = "|".join(as_reg exps) + "$"

to:

full_regexp = "$|".join(as_re gexps) + "$"

However, I noticed rex still doesn't return multiple matches. For
instance, matching 'abc' to the given the patterns '#bc', 'a#c', and
'ab#', your code only returns a match to the first pattern '#bc'. Is
this standard behavior or is it possible to change this?

Re: Efficient String Lookup?

Chris S. wrote:
[color=blue]
> 'abaxile', 'abaze', and 'abbacomes' to the pattern 'ab##'. I'm not an
> expert with rex, but your expression looks correct. What could be
> causing this?[/color]

To avoid this, one would have to add to the patterns \b AFAIR, so that it
matches whole words only.

Regards,

--
* Piotr (pitkali) Kalinowski * mailto: pitkali (at) o2 (dot) pl *
* Registered Linux User No. 282090 * Powered by Gentoo Linux *
* Fingerprint: D5BB 27C7 9993 50BB A1D2 33F5 961E FE1E D049 4FCD *