user2916886 user2916886 - 4 months ago 18
Python Question

Wrong output in implementing T9 dictionary in python

I am trying to implement

T9
dictionary in
python
. I am using
Trie
to implement it. I have this code which creates a
Trie
from the words in the dictionary and then do a lookup for the pattern

import string

PHONE_LETTERS = 'abcdefghijklmnopqrstuvwxyz'
PHONE_NUMBERS = '22233344455566677778889999'
PHONE_TRANS = string.maketrans(PHONE_LETTERS, PHONE_NUMBERS)

class Node:

def __init__(self, key):
self.children = {}
self.key = key
self.values = []


def append_word(node, sequence, completeword):
if not sequence:
return
key = sequence[0]
try:
child = node.children[key]
except KeyError:
child = Node(key)
node.children[key] = child
if len(sequence) == 1:
child.values.append(completeword)
else:
append_word(child, sequence[1:], completeword)


def lookup(node, sequence=None):
if sequence:
# there are still numbers in the sequence: follow them in the trie
try:
child = node.children[sequence[0]]
return lookup(child, sequence[1:])
except KeyError:
return []
else:
# the sequence is empty: explore the trie using a DFS
result = node.values[:]
for child in node.children.values():
result.extend(lookup(child))
return result


def main():
root = Node(None)

words = ['hello','hess','home','abhi','busy','disturb']
for wlist in words:
print wlist
map(lambda l: append_word(root, l.strip().translate(PHONE_TRANS), l.strip()), wlist)

words = sorted(lookup(root, '43'))
print "Words: %s" % words


if __name__ == '__main__':
main()


Now when I run this I should get
[hello,hess]
as output right? But I get an empty list. What mistake am I making here?

Answer

When you map your append function are you really meaning to map it over the entire wlist string?

If you call translate on the wlist string instead of each individual letter you get:

hello
hess
home
abhi
busy
disturb
Words: ['hello', 'hess']

All you have to do is remove the map call:

import string

PHONE_LETTERS = 'abcdefghijklmnopqrstuvwxyz'
PHONE_NUMBERS = '22233344455566677778889999'
PHONE_TRANS = string.maketrans(PHONE_LETTERS, PHONE_NUMBERS)

class Node:

    def __init__(self, key):
        self.children = {}
        self.key = key
        self.values = []


def append_word(node, sequence, completeword):
    if not sequence:
        return
    key = sequence[0]
    try:
        child = node.children[key]
    except KeyError:
        child = Node(key)
        node.children[key] = child
    if len(sequence) == 1:
        child.values.append(completeword)
    else:
        append_word(child, sequence[1:], completeword)


def lookup(node, sequence=None):
    if sequence:
        # there are still numbers in the sequence: follow them in the trie
        try:
            child = node.children[sequence[0]]
            return lookup(child, sequence[1:])
        except KeyError:
            return []
    else:
        # the sequence is empty: explore the trie using a DFS
        result = node.values[:]
        for child in node.children.values():
            result.extend(lookup(child))
        return result


def main():
    root = Node(None)

    words = ['hello','hess','home','abhi','busy','disturb']
    for wlist in words:
        print wlist
        # XXX here, you shouldn't be mapping the `translate` call onto the entire string
        append_word(root, wlist.strip().translate(PHONE_TRANS), wlist)

    words = sorted(lookup(root, '43'))
    print "Words: %s" % words


if __name__ == '__main__':
    main()
Comments