我們如何有效地將不帶空格的串聯單字的文字字串拆分為單字？

將文字分割為不含空格的單字清單

問題

給定一個由不含空格的串聯單字組成的文字字符字串：

Input: "tableapplechairtablecupboard..."

我們如何有效地將這段文字分割成單字的清單？

Output: ["table", "apple", "chair", "table", ["cupboard", ["cup", "board"]], ...]

演算法

一個簡單的方法是迭代地找出文本中最長的可能單字。然而，這可能會導致次優結果。

基於頻率的演算法

相反，我們可以利用語言中單字的相對頻率來提高準確性：

1. 對單字分佈建模： 假設單字獨立分佈並遵循齊普夫定律，其中單字機率與其排名成反比。
2. 定義單字成本：成本單字的機率被定義為其似然性的倒數的對數。

3. 動態規劃方法：

   • 初始化一個成本數組，其中第一個元素為 0。
   • 對於文本中的每個字符，找到使到該點的字符總成本最小的單字。
   • 從末尾回溯以重建最小成本單字序列.

程式碼實現

<code class="python">from math import log

wordcost = {}  # Dictionary of word costs using Zipf's law

maxword = max(len(word) for word in wordcost)

def infer_spaces(s):
    cost = [0]
    for i in range(1, len(s) + 1):
        candidates = enumerate(reversed(cost[max(0, i - maxword):i]))
        c, k = min((wordcost.get(s[i - k - 1:i], 9e999) + c, k + 1) for k, c in candidates)
        cost.append(c)

    out = []
    i = len(s)
    while i > 0:
        c, k = best_match(i)
        assert c == cost[i]
        out.append(s[i - k:i])
        i -= k

    return " ".join(reversed(out))</code>

結果

結果該

該結果

Input: "tableapplechairtablecupboard..."
Output: ["table", "apple", "chair", "table", ["cupboard", ["cup", "board"]], ...]

該算法能夠準確地將文本分割成單詞列表，即使在

示例：

優化：

後綴樹：從單字清單建立後綴樹，可以加速候選搜尋。 文字區塊分割：對於大文字輸入，可以將文字分割成區塊以在保持準確性的同時最大限度地減少記憶體使用。

以上是我們如何有效地將不帶空格的串聯單字的文字字串拆分為單字？的詳細內容。更多資訊請關注PHP中文網其他相關文章！