从没有空格/组合词的文本中检测最可能出现的词

Question

如何从组合字符串中检测和拆分单词？

例：

"cdimage" -> ["cd", "image"]
"filesaveas" -> ["file", "save", "as"]

Answer 1

这是一个动态编程解决方案（实现为记忆功能）。给定具有频率的单词词典，它会将输入文本拆分为给出整体最可能短语的位置。您必须找到一个真实的单词表，但是为了简单的测试，我列出了一些虚构的频率。

WORD_FREQUENCIES = {
    'file': 0.00123,
    'files': 0.00124,
    'save': 0.002,
    'ave': 0.00001,
    'as': 0.00555
}

def split_text(text, word_frequencies, cache):
    if text in cache:
        return cache[text]
    if not text:
        return 1, []
    best_freq, best_split = 0, []
    for i in xrange(1, len(text) + 1):
        word, remainder = text[:i], text[i:]
        freq = word_frequencies.get(word, None)
        if freq:
            remainder_freq, remainder = split_text(
                    remainder, word_frequencies, cache)
            freq *= remainder_freq
            if freq > best_freq:
                best_freq = freq
                best_split = [word] + remainder
    cache[text] = (best_freq, best_split)
    return cache[text]

print split_text('filesaveas', WORD_FREQUENCIES, {})

--> (1.3653e-08, ['file', 'save', 'as'])