从文本中检测最可能的单词而不使用空格/组合单词

Question

是否有一个好的库可以从组合字符串中检测和拆分单词？

例:

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

Answer 1

这是一个动态编程解决方案(作为memoized函数实现).给定具有其频率的单词字典,它将输入文本分割为给出总体最可能短语的位置.你必须找到一个真正的单词列表,但我为一个简单的测试包含了一些组合频率.

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'])

Answer 2

我不知道它的任何库,但实现基本功能应该不难.

1. 获取单词列表,如UNIX words.
2. 将单词列表的内容填入trie.
3. 取出要拆分的字符串,并在trie中跟踪其路径.每次到达有效单词时,创建一个新分支,从您到达的字符串的点开始搜索单词.完成当前分支后,回溯到您创建的分支,就像在深度优先搜索中一样.
4. 使用试探法或通过自然语言解析器手动消除结果列表的歧义.

例:

1. 单词:"filesaveasstring"
2. 第一个有效的单词是"file".尝试匹配"saveas".第一个有效的词是"保存".尝试匹配"asstring".第一个有效单词是"as".尝试匹配"字符串".第一个有效字是"字符串".匹配到结束; 将[file save as string]放入结果列表中.
3. 回溯到匹配"字符串" - 没有其他可能性.回溯到"asstring".第一个未经访问的有效词是"屁股".尝试匹配"tring".没有可能的比赛.回溯到"asstring".没有可能的比赛.回溯到"filesaveasstring".
4. 第一个未访问的匹配是"文件".尝试匹配"aveasstring".第一场比赛是"大道".尝试匹配"asstring"(与步骤2/3相同的结果),将[file ave as string]添加到结果列表并回溯到开头.
5. 尝试匹配"filesaveasstring".没有未经访问的比赛.完成.
6. 使用启发式或自然语言解析器从[[file save as string] [files ave as string]]中选择最有可能的.