Regular expression as dictionary key?

[Luke]

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:

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

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

Luke