Regular expression as dictionary key?

Michael Hudson mwh at
Mon Dec 3 12:06:00 CET 2001

Luke <LLoeffler at> writes:

> Let's say you have a dict of words like
> words = {"dogs":1,"cats":2}
> Let's say I'm given a singular form of a word and want to match it
> with plurals still, but words["dog"] will obviously raise a KeyError.
> Without doing a linear substring search on every element in
> words.key(), is there a way to take advantage of the dict's binary
> tree layout properties (e.g. speed) like:

Which "binary tree layout properties" are those?

> words["dog*"]   # where dog* is a Regex

You could do 

/>> def process(d):
|..     r = {}
|..     for k,v in d.items():
|..         for i in range(len(k)):
|..             r[k[:i]] = v
|..     return r
->> words = {"dogs":1,"cats":2}
->> stems = process(words)
->> stems["dog"]

So you only do the linear stuff once.

You could also do some stuff with regexps, I suspect.

> Nonexistant syntax, I know, but you get the idea...  I smell a PEP

Perhaps I'll save you some bother: the chance of extending the native
dict implementation to support this is zero.


  C++ is a siren song.  It *looks* like a HLL in which you ought to
  be able to write an application, but it really isn't.
                                       -- Alain Picard, comp.lang.lisp

More information about the Python-list mailing list