給定一個由不帶空格的單字組成的字串，本文提出了一個高效率的分割演算法
輸入：「tableapplechairtablecupboard...」
輸出：["table", "apple", " chair" , "table", ["cupboard", ["cup", "board"]], ...]
演算法不是使用簡單的方法，而是使用簡單的方法利用詞頻來提高準確性。假設單字獨立分佈並遵循齊普夫定律，演算法使用動態規劃來識別最可能的單字序列。
<code class="python">from math import log
words = open("words-by-frequency.txt").read().split()
wordcost = dict((k, log((i+1)*log(len(words)))) for i,k in enumerate(words))
maxword = max(len(x) for x in words)
def infer_spaces(s):
cost = [0]
for i in range(1,len(s)+1):
c,k = best_match(i)
cost.append(c)
out = []
i = len(s)
while i>0:
c,k = best_match(i)
out.append(s[i-k:i])
i -= k
return " ".join(reversed(out))
def best_match(i):
candidates = enumerate(reversed(cost[max(0, i-maxword):i]))
return min((c + wordcost.get(s[i-k-1:i], 9e999), k+1) for k,c in candidates)
s = 'thumbgreenappleactiveassignmentweeklymetaphor'
print(infer_spaces(s))</code>演算法依賴字典，該字典將單字映射到它們的相對頻率，假設齊普夫定律。為了考慮到未見過的單詞，為它們分配了很高的成本。
演算法計算每個可能的單字片段的成本，考慮潛在的下一個單字。它使用動態規劃來選擇成本最低的路徑，確保最有可能的單字序列。
對於大量輸入，可以透過將文字分割為區塊並處理來最佳化演算法他們獨立。這可以減少記憶體使用，而不會顯著影響準確性。
以上是我們如何利用詞頻和動態規劃有效地將沒有空格的文字分離到單字清單中？的詳細內容。更多資訊請關注PHP中文網其他相關文章！
