Python - 查找一个单词中所有子词

Question

最后，我想找出英语词典中哪个单词包含的子单词最多，而且这些子单词至少要有三个字母。我写了一个算法，但运行起来太慢，没法用。想知道有没有什么方法可以让它更快一些。

def subWords(word):
    return set((word[0:i] for i in range(2, len(word)+1))) #returns all subWords of length 2 or greater

def checkDict(wordList, dictList):
    return set((word for word in wordList if word in dictList))

def main():
    dictList = [i.strip() for i in open('wordlist.txt').readlines()]
    allwords = list()
    maximum = (0, list())

    for dictWords in dictList:
        for i in range (len(dictWords)):
            for a in checkDict(subWords(dictWords[i: len(dictWords) + 1]), dictList):
                allwords.append(a)

        if len(allwords) > maximum[0]:
            maximum = (len(allwords), allwords)

        print maximum
        allwords = list()

    print maximum 
main()

Answer 1

想要了解基础的Python，可以看看这个函数（基本上是JBernardo和Karl Knechtel建议的一个更快、更精致的版本，符合PEP8标准）：

def check_dict(word, dictionary): 
  """Return all subwords of `word` that are in `dictionary`."""
  fragments = set(word[i:j] 
                  for i in xrange(len(word) - 2) 
                  for j in xrange(i + 3, len(word) + 1))
  return fragments & dictionary

dictionary = frozenset(word for word in word_list if len(word) >= 3)
print max(((word, check_dict(word, dictionary)) for word in dictionary), 
          key=lambda (word, subwords): len(subwords)) # max = the most subwords

输出的结果大概是这样的：

('greatgrandmothers',
set(['and', 'rand', 'great', 'her', 'mothers', 'moth', 'mother', 'others', 'grandmothers', 'grandmother', 'ran', 'other', 'greatgrandmothers', 'greatgrandmother', 'grand', 'hers', 'the', 'eat']))

这是从http://www.mieliestronk.com/wordlist.html获取的单词列表。

---

我知道你并不是追求性能（上面的代码对于标准的58,000个英语单词的词汇量来说，已经不到1秒）。

但是如果你需要在某个内部循环中运行得超级快呢？

• 你会想要避免在堆内存中创建所有子字符串的副本，这样会严重影响性能。
• 你可以通过指针运算来做到这一点，只用指针的边界来表示子字符串（而不是创建完整的对象）。
• 使用这个子字符串快速判断它是否是有效词汇的一部分：
  • 可以使用字典树数据结构，或者它的内存友好版本PATRICIA树
  • 从你的字典中构建一个静态的字典树，然后快速查找子字符串
  • 逐步调整指针，探索所有可能的子字符串，同时为有效单词增加计数
  • 这样你就避免了任何动态内存分配（没有字符串，没有集合），速度飞快！！
• 不过这些在Python中并不是特别相关，因为这种内存管理太底层了，实际上你最好还是不要在性能要求高的代码中使用Python。

Answer 2

你这个算法的一个大问题是，对于每个子词，你都需要把它和字典里的每个单词进行比较。其实你不需要这样做——如果你的单词是以'a'开头的，那就没必要去看以'b'开头的单词。如果下一个字母是'c'，那也不需要去比较以'd'开头的单词。那么问题就变成了：“我该怎么高效地实现这个想法呢？”

为了做到这一点，我们可以创建一个树来表示字典中的所有单词。我们通过将字典中的每个单词添加到这棵树中来构建它，并把最后一个节点标记为已填充。

当我们想要检查一个子词是否在这棵树中时，我们只需逐个字母地遍历这个单词，用这些字母来决定在树中接下来该去哪里（从顶部开始）。如果我们发现没有地方可以去，或者在遍历完整个子词后停在一个未填充的树节点上，那么这个词就不是一个有效的单词。否则，如果我们停在一个已填充的节点上，那它就是一个有效的单词。这样一来，我们就可以一次性搜索整个字典，而不是一个一个单词地查找。当然，这样做的代价是一开始需要花一些时间来设置，但如果字典里的单词很多，这个代价其实并不算高。

这听起来真不错！让我们试着实现一下：

class Node:
    def __init__( self, parent, valid_subword ):
        self.parent = parent
        self.valid_subword = valid_subword
        self.children = {}

    #Extend the tree with a new node
    def extend( self, transition, makes_valid_word ):
        next_node = None
        if transition in self.children:
            if makes_valid_word:
                self.children[transition].makes_valid_word = True
        else:
            self.children[transition] = Node( self, makes_valid_word )
        return self.children[transition]

def generateTree( allwords ):
  tree = Node( None, False )
    for word in allwords:
      makes_valid_word = False
      current_node = tree
      for i in range(len(word)):
        current_node = current_node.extend( word[i], True if i == len(word) - 1 else False )
  return tree

def checkDict( word, tree ):
    current_node = tree
    for letter in word:
        try:
            current_node = current_node.children[letter]
        except KeyError:
            return False

    return current_node.valid_subword

然后，稍后：

for word in allWords:
  for subword in subWords(word):
    checkDict(subword)
    #Code to keep track of the number of words found, like you already have

这个算法让你可以在O(m)的时间内检查一个单词是否在字典中，其中m是字典中最长单词的长度。注意，对于包含任意数量单词的字典，这个时间复杂度大致是常数。而你原来的算法每次检查的时间复杂度是O(n)，其中n是字典中单词的数量。

Answer 3

1) 风格和组织：用一个函数来生成一个单词的所有子词，这样更合理。

2) 风格：使用 set 时不需要双括号。

3) 性能（希望如此）：也要把你要查找的单词放进一个 set 中；这样你就可以使用内置的集合交集检查。

4) 性能（几乎可以肯定）：不要手动循环去找最大元素；用内置的 max 就可以了。你可以直接比较（长度，元素）元组；Python 会从头到尾逐对比较元组中的元素，就像每个元素都是字符串中的一个字母一样。

5) 性能（也许）：确保字典里没有1个或2个字母的单词，因为它们会干扰你的操作。

6) 性能（可悲的事实）：不要把所有东西都拆分成函数。

7) 风格：文件输入输出应该使用 with 语句块，这样可以确保资源得到正确清理，而且文件迭代器默认是按行迭代的，所以我们可以隐式地得到一行列表，而不需要调用 .readlines()。

最后我得到的结果是（除了 'fragments' 表达式外，没有经过严格测试）：

def countedSubWords(word, dictionary): 
  fragments = set(
    word[i:j]
    for i in range(len(word)) for j in range(i+3, len(word)+1)
  )
  subWords = fragments.intersection(dictionary)
  return (len(subWords), subWords)


def main():
  with open('wordlist.txt') as words:
    dictionary = set(word.strip() for word in words if len(word.strip()) > 2)
    print max(countedSubWords(word, dictionary) for word in dictionary)