Rookie question about data types (hashtables)

Eric Brunel eric.brunel at N0SP4M.com
Thu Jan 29 15:43:09 CET 2004


Steve D. Perkins wrote:
[snip]
>     	What I would LIKE to have is a hashtable-like structure that lets me 
> retrieve multiple values based on a partial key.

AFAIK, if you can do queries on a "hashtable-like structure" with a partial key, 
it cannot be a real hashtable...

 > I want to have a text
> field for the user to type in a Spanish word, and a box below containing 
> a list of English words.  With each character that the user types, I 
> would like to narrow down the words listed in the box below.  That is, 
> when you type the letter "a" the box will contain all English words 
> starting with the letter "a".  When you then type "n", the box will 
> narrow further and contain all words starting with "an", etc... until 
> you've narrowed it down to appropriate word.

I'd use a Python dictionary indexed not on words, but on letters in the word. 
So, for a dictionary translating english words into french, you'd have for example:

dictionary['m']['o']['n']['d']['a']['y']['translation'] = 'lundi'

(NB: having 'translation' as the last key is to solve the problem of words 
included in another; see 'sun' and 'sunday'. BTW, any key that is not a single 
character can be used...)

Here is an example implementation:

--------------------------------------------------------
def addWord(myDict, originalWord, translatedWord):
   d = myDict
   for c in originalWord:
     if not d.has_key(c): d[c] = {}
     d = d[c]
   d['translation'] = translatedWord

def _allTranslations(rootWord, d):
   res = []
   for c in d.keys():
     if c == 'translation':
       res.append((rootWord, d[c]))
     else:
       res += _allTranslations(rootWord + c, d[c])
   return res

def getTranslations(myDict, word):
   d = myDict
   for c in word:
     if not d.has_key(c): return []
     d = d[c]
   return _allTranslations(word, d)
--------------------------------------------------------

And then you'd do:

frenchDict = {}
## Week days
addWord(frenchDict, 'monday', 'lundi')
addWord(frenchDict, 'tuesday', 'mardi')
# ...
addWord(frenchDict, 'sunday', 'dimanche')
## Months
addWord(frenchDict, 'january', 'janvier')
addWord(frenchDict, 'february', 'fevrier')
# ...
addWord(frenchDict, 'december', 'decembre')

print getTranslations(frenchDict, 'wednesday')
print getTranslations(frenchDict, 'ju')
print getTranslations(frenchDict, 's')

I don't know how it scales up for big dictionaries, not to mention huge ones...

HTH
-- 
- Eric Brunel <eric dot brunel at pragmadev dot com> -
PragmaDev : Real Time Software Development Tools - http://www.pragmadev.com




More information about the Python-list mailing list