使用高效演算法將無空格文字標記為單字

在自然語言處理領域，分割連續字元流的能力轉化為有意義的詞語至關重要。這個過程稱為標記化，在處理缺少空格或分隔符號的文字時特別具有挑戰性。

挑戰語句

當前的任務涉及分割輸入字符串，例如將“tableapplechairtablecupboard...”放入單詞列表中，考慮到存在不明確子字符串的可能性，其中一個序列可以形成多個單字（例如，「cupboard」可以是「cup」或「board」）。

演算法：利用詞頻

迭代識別每個位置的最長可能單字的幼稚方法會產生不令人滿意的結果現實世界的場景。為了克服這個限制，我們利用了一個結合詞頻分佈的演算法。

詞頻建模

我們假設詞頻遵循齊普夫定律，該定律規定機率遇到第n 個頻繁單字的機率約為1/(n * log(N))，其中N 是語言中的單字總數。使用對這種關係進行編碼的預先計算的成本字典，我們可以為每個潛在的候選詞分配一個成本。

動態規劃方法

為了確定最佳分詞，我們採用動態規劃。我們迭代輸入字串，為每個潛在的分割點維護一個運行成本值。在每個位置，我們從字串末尾開始評估候選詞，並選擇成本最低的分割。

演算法實作

提供的Python程式碼提供此演算法的簡潔實作：

from math import log

# Precomputed word cost dictionary using Zipf's law
wordcost = ...

# Helper function to find the best word match based on cost
def best_match(i):
    ...

# Function to infer spaces in the input string using dynamic programming
def infer_spaces(s):
    ...

用法範例

要使用此程式碼，只需輸入連續文字字串，如下所示：

s = 'thumbgreenappleactiveassignmentweeklymetaphor'
print(infer_spaces(s))

結果和評估

即使在字典有限的情況下，該演算法也能表現出卓越的性能。它成功地以高精度標記複雜文字。