在 python 中实现 T9 字典时输出错误

Question

我正在尝试在 python 中实现 T9 字典。我正在使用 Trie 来实现它。我有这段代码，它根据字典中的单词创建 Trie，然后查找模式

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()

现在当我运行时，我应该得到 [hello,hess] 作为输出，对吗？但是我得到一个空列表。我在这里犯了什么错误？

Answer 1

当您 map 您的 append 函数时，您真的想将其映射到整个 wlist 字符串吗？

如果您在 wlist 字符串而不是每个单独的字母上调用 translate，您将获得：

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

您只需删除 map 调用：

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()

在 python 中实现 T9 字典时输出错误

Wrong output in implementing T9 dictionary in python

python

dictionary

trie

t9