string - 如何拆分多个连接的单词？

Question

我有一个包含 1000 个左右条目的数组，示例如下:

wickedweather
liquidweather
driveourtrucks
gocompact
slimprojector

我希望能够将它们分成各自的单词，例如:

wicked weather
liquid weather
drive our trucks
go compact
slim projector

我希望正则表达式能够解决这个问题。但是，由于没有边界可以停止，也没有任何类型的大写字母可供我选择，我在想，可能有必要对字典进行某种引用吗？

我想这可以手动完成，但为什么 - 当它可以用代码完成时! =)但这让我很困惑。有任何想法吗？

Answer 1

Viterbi algorithm速度要快得多。它计算的分数与上面 Dmitry 的答案中的递归搜索相同，但时间复杂度为 O(n)。 (德米特里的搜索需要指数时间；维特比通过动态规划来完成。)

import re
from collections import Counter

def viterbi_segment(text):
    probs, lasts = [1.0], [0]
    for i in range(1, len(text) + 1):
        prob_k, k = max((probs[j] * word_prob(text[j:i]), j)
                        for j in range(max(0, i - max_word_length), i))
        probs.append(prob_k)
        lasts.append(k)
    words = []
    i = len(text)
    while 0 < i:
        words.append(text[lasts[i]:i])
        i = lasts[i]
    words.reverse()
    return words, probs[-1]

def word_prob(word): return dictionary[word] / total
def words(text): return re.findall('[a-z]+', text.lower()) 
dictionary = Counter(words(open('big.txt').read()))
max_word_length = max(map(len, dictionary))
total = float(sum(dictionary.values()))

测试它:

>>> viterbi_segment('wickedweather')
(['wicked', 'weather'], 5.1518198982768158e-10)
>>> ' '.join(viterbi_segment('itseasyformetosplitlongruntogetherblocks')[0])
'its easy for me to split long run together blocks'

为了实用，您可能需要一些改进:

• 添加概率的对数，而不是乘以概率。这可以避免浮点下溢。
• 您的输入通常会使用您的语料库中没有的单词。这些子字符串必须被指定为单词的非零概率，否则您最终将得不到解决方案或得到糟糕的解决方案。 (对于上述指数搜索算法来说也是如此。)这个概率必须从语料库单词的概率中抽取出来，并合理地分布在所有其他候选单词中:一般主题在统计语言模型中称为平滑。 (不过，你可以通过一些相当粗暴的黑客手段逃脱惩罚。)这就是 O(n) 维特比算法击败搜索算法的地方，因为考虑非语料库单词会放大分支因子。