我们如何有效地将不带空格的串联单词的文本字符串拆分为单个单词？

将文本拆分为不带空格的单词列表

问题

给定一个由不带空格的串联单词组成的文本字符串：

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中文网其他相关文章！