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排序算法工作得很快，但它仍然處理一個大列表，並且可能會有相當大的成本。一個理想的算法可能不得不考慮這個成本，並決定它是否值得（或許不）。如果沒有對列表進行排序，您可能希望第一遍只考慮具有某個最小長度的單詞 - 甚至可能是更大循環的一部分。在計算與解決方案無關的詞時，確實沒有意義。