在Python中查找部分指定单词的最佳匹配

Question

我有一个文件叫做 dict.txt，里面包含了所有的英语单词。

用户会输入他们想要的单词：

x = raw_input("请输入部分单词: ")

比如输入可以是：r-n、--n、-u-、he--o、h-llo等等，未知的字符用下划线（_）表示，最好不要用减号（-）。

我想让程序列出所有在字典中找到的最佳匹配单词。

举个例子：如果输入的部分单词是 r--，那么列表中应该包含 run、ran、rat、rob 等等。

有没有办法用 for 循环来实现这个功能呢？

Answer 1

如果你想要反复执行这个操作，你应该创建一个索引：

wordlist = [word.strip() for word in "run, ran, rat, rob, fish, tree".split(',')]

from collections import defaultdict

class Index(object):

    def __init__(self, wordlist=()):
        self.trie = defaultdict(set)
        for word in wordlist:
            self.add_word(word)

    def add_word(self, word):
        """ adds word to the index """
        # save the length of the word
        self.trie[len(word)].add(word)    
        for marker in enumerate(word):
            # add word to the set of words with (pos,char)
            self.trie[marker].add(word)


    def find(self, pattern, wildcard='-' ):
        # get all word with matching length as candidates
        candidates = self.trie[len(pattern)]

        # get all words with all the markers
        for marker in enumerate(pattern):            
            if marker[1] != wildcard:
                candidates &= self.trie[marker]

            # exit early if there are no candicates
            if not candidates:                
                return None

        return candidates


with open('dict.txt', 'rt') as lines:
    wordlist = [word.strip() for word in lines]

s = Index(wordlist)
print s.find("r--")

字典树（Tries）是用来搜索字符串的。这是一个简单的前缀字典树，使用了一个单一的字典。

Answer 2

与其用 _ 来表示通配符，不如用 \w。把 \b 加到模式的开头和结尾，然后把字典用正则表达式匹配器来处理。这样 -un--- 就变成了：

>>> import re
>>> re.findall(r'\b\wun\w\w\w\b', "run runner bunt bunter bunted bummer")
['runner', 'bunter', 'bunted']

\w 可以匹配任何“字母数字字符”。而 \b 则匹配任何单词的边界。

Answer 3

一个简单的方法是使用正则表达式。因为不确定这个问题是不是作业，所以具体的细节就留给你自己去练习了。