Python-什么单词可以删除最连续的字母，仍然是字典有效的单词？

Question

我用这个可怕而低效的实现来找到可以删除最后连续的最后一个字母并且仍然是单词的单词。例如，Rodeo是一个众所周知的：Rodeo，Rode，Rod，Ro。 该程序发现'作曲家'：作曲家，作曲家，撰写，作曲，对比

我想知道如何创建一个程序，找到最长的单词， ）移除，它仍然被认为是一个字：

例如：野兽，最好的赌注，是 - 将是一个有效的可能性

这里是我的我的程序，以找到一个去除连续的字母（” m也有兴趣听听如何改进和优化）：

#Recursive function that finds how many letters can be removed from a word and 
#it still be valid. 
def wordCheck(word, wordList, counter): 

    if len(word)>=1: 
     if word in wordList: 
      return (wordCheck(word[0:counter-1], wordList, counter-1)) 
     else: 
      return counter 
    return counter 


def main(): 
    a = open('C:\\Python32\\megalist2.txt', 'r+') 
    wordList = set([line.strip() for line in a]) 
    #megaList contains a sorted list of tuple of 
    #(the word, how many letters can be removed consecutively) 
    megaList = sorted([(i, len(i)-1- wordCheck(i, wordList, len(i))) for i in wordList], key= lambda megaList: megaList[1]) 


    for i in megaList: 
     if i[1] > 3: 
      print (i) 

if __name__ == '__main__': 
    main() 

Answer 1

这是我刚刚写的一个实现。它用约235k字的单词列表运行约五秒钟。输出不显示整个链，但您可以轻松地从输出重新组合它。

# Load the words into a dictionary 
words = dict((x.strip(), set()) for x in open("/usr/share/dict/words")) 

# For each word, remove each letter and see if the remaining word is still 
# in the dictionary. If so, add it to the set of shorter words associated with 
# that word in the dictionary. 
# For example, bear -> {ear, bar, ber} 
for w in words: 
    for i in range(len(w)): 
     shorter = w[:i] + w[i+1:] 
     if shorter in words: 
      words[w].add(shorter) 

# Sort the words by length so we process the shortest ones first 
sortedwords = sorted(words, key=len) 

# For each word, the maximum chain length is: 
# - the maximum of the chain lengths of each shorter word, if any 
# - or 0 if there are no shorter words for this word 
# Note that because sortedwords is sorted by length, we will always 
# have maxlength[x] already available for each shorter word x 
maxlength = {} 
for w in sortedwords: 
    if words[w]: 
     maxlength[w] = 1 + max(maxlength[x] for x in words[w]) 
    else: 
     maxlength[w] = 0 

# Print the words in all chains for each of the top 10 words 
toshow = sorted(words, key=lambda x: maxlength[x], reverse=True)[:10] 
while toshow: 
    w = toshow[0] 
    print(w, [(x, maxlength[x]) for x in words[w]]) 
    toshow = toshow[1:] + list(x for x in words[w] if x not in toshow) 

在我的字典上最长的单词链：

• abranchiate
• branchiate
• 鳃
• 鳃
• branchi
• 分支
• 牧场
• RACH
• ACH
• 啊
• 一个

Answer 2

for each english word W: 
    for each letter you can remove: 
     remove the letter 
     if the result W' is also word: 
      draw a line W->W' 
for each english word W: 
    connect ROOT-> each english word W 
use a graph search algorithm to find the longest path starting at ROOT 
    (specifically, the words are now in a directed acyclic graph; traverse 
    the graph left-right-top-down, i.e. in a "topological sort", keeping 
    track of the longest candidate path to reach each node; this achieves 
    the result in linear time) 

这个算法只需要线性O（＃wordsInEnglish * averageWordLength）时间！基本上只要它需要来读取输入

它可以很容易被修改，以找到连续字母移除：而不是保持每个节点单个候选像（节点（“杆”）的候选= rodeo->rode->rod），保持每个节点的候选人家族以及您为获取每个候选人而删除的字母索引（节点（'棒'）。candidates = {rodeo->rod|e->rod|,road->ro|d}）。这有相同的运行时间。

Answer 3

也许我只是缺少运动的点，但应该不是一个简单的启发式规则能够砍掉很多搜索？特别是如果你试图找到一个单词可以删减的字母最多，你可能只想看最大的单词并检查它们是否包含最小的单词。

例如，大量的单词包括字母“a”和“i”，它们都是有效的英文单词。而且，更长的单词将越来越可能具有一个或两个字母。你可以跳过任何没有“a”或“i”的单词。

你也许可以将它变成Greg的解决方案，其实，如果你先得到你的排序的单词列表的副本，即：

# Similar to Greg's. Reads into a dict 
words = dict((x.strip(), None) for x in open("/usr/share/dict/words")) 
# Generates a reverse sorted list from the dict (largest words first) 
sortedwords = sorted(words, key=len, reverse=True) 

# Largest possible reduction is making a longest word into 1 letter 
longestPossible = len(sortedWords[0])-1 

# Function that recursively finds shorter words and keeps count of reductions 
def getMaxLettersRemoved(w, words, alreadyRemovedCount=0): 
    # If you've already calculated the value, return it 
    if words[w] is not None: 
     return words[w] 
    # Recursively calculate how many letters you can remove 
    shorterPossibilities = [w[:i] + w[i+1:] for i in xrange(len(w))] 
    # Calculate how max # of letters you can remove from shortened words 
    totalRemoved = max([getMaxLettersRemoved(w, words, alreadyRemovedCount+1) for shorter in shorterPossibilities if shorter in words]) 
    # Total removed will be the same or will increase due to removals from shorter words 
    totalRemoved = max(totalRemoved, alreadyRemovedCount) 
    # Cache the result and return it 
    words[w] = totalRemoved 
    return totalRemoved 

# Go through words from largest to smallest, so long as they have 'a' or 'i' 
bestNumRemoved = 0 
for w in sortedwords: 
    if 'a' in w or 'i' in w: 
     # Get the number of letters you can remove 
     numRemoved = getMaxLettersRemoved(w, words) 
     # Save the best one found 
     if numRemoved > bestNumRemoved: 
      bestWord = w 
      bestNumRemoved = numRemoved 
     # Stop if you can't do better 
     if bestNumRemoved >= len(w)-1: 
      break 

# Need to make sure the best one found is better than any left 
if bestNumRemoved < longestPossible: 
    for w in sortedwords: 
     # Get the number of letters you can remove 
     numRemoved = getMaxLettersRemoved(w, words) 
     # Save the best one found 
     if numRemoved > bestNumRemoved: 
      bestWord = w 
      bestNumRemoved = numRemoved 
     # Stop if you can't do better 
     if bestNumRemoved >= len(w)-2: 
      break 

因此，这一个在几个方面有所不同。首先，它首先排序，这样你可以得到最大的单词。其次，它完全忽略了第一遍中不包含'a'或'i'的任何单词。第三，它不需要计算每个词或整个树来产生结果。相反，它只是在需要时通过单词进行递归查看。

每当它切出一个字母并找到一个新单词时，它将运行相同的函数来查找它可以从该较小单词切出的字母数加上已从任何根单词中删除的数字。这在理论上应该相当快，因为​​它不需要运行大多数单词，因为它有一个典型的优化技巧：检查它是否处于最佳范围。首先，它在具有'我'或'一个'的人中找到最好的可能性。然后，它会检查比找到的最好的单词更长的单词，以确保没有更好的选项不包含任何一个字母，但长度至少增加2个字母（因此理论上可以更好）。

这可能会有一些改进，可以做一个更好的工作，利用英语的规律性使用概率算法，但我怀疑这将是一个确定性的行为。另外，我手边没有字典，所以我实际上不能呃...运行这个，但概念是健全的。

此外，我不完全相信排序键的列表是值得的。虽然python排序算法工作得很快，但它仍然处理一个大列表，并且可能会有相当大的成本。一个理想的算法可能不得不考虑这个成本，并决定它是否值得（或许不）。如果没有对列表进行排序，您可能希望第一遍只考虑具有某个最小长度的单词 - 甚至可能是更大循环的一部分。在计算与解决方案无关的词时，确实没有意义。