如何将没有空格的文本分割为单词列表
输入： "tableapplechairtablecupboard..." 许多单词
我们需要一个高效的方法，把这些文字分割成单词列表，得到：
输出： ["table", "apple", "chair", "table", ["cupboard", ["cup", "board"]], ...]
首先想到的办法是，从第一个字母开始，检查所有可能的单词，找到最长的那个单词，然后继续从 position=word_position+len(word) 的位置开始。
附注：
我们有一个所有可能单词的列表。
单词 "cupboard" 可以分成 "cup" 和 "board"，我们选择最长的那个。
使用的语言是 Python，但关键是算法本身。
18 个回答
这里是一个使用递归搜索的解决方案：
def find_words(instring, prefix = '', words = None):
if not instring:
return []
if words is None:
words = set()
with open('/usr/share/dict/words') as f:
for line in f:
words.add(line.strip())
if (not prefix) and (instring in words):
return [instring]
prefix, suffix = prefix + instring[0], instring[1:]
solutions = []
# Case 1: prefix in solution
if prefix in words:
try:
solutions.append([prefix] + find_words(suffix, '', words))
except ValueError:
pass
# Case 2: prefix not in solution
try:
solutions.append(find_words(suffix, prefix, words))
except ValueError:
pass
if solutions:
return sorted(solutions,
key = lambda solution: [len(word) for word in solution],
reverse = True)[0]
else:
raise ValueError('no solution')
print(find_words('tableapplechairtablecupboard'))
print(find_words('tableprechaun', words = set(['tab', 'table', 'leprechaun'])))
结果是
['table', 'apple', 'chair', 'table', 'cupboard']
['tab', 'leprechaun']
根据在最佳答案中的出色工作，我创建了一个方便使用的pip包。
>>> import wordninja
>>> wordninja.split('derekanderson')
['derek', 'anderson']
要安装这个包，可以运行pip install wordninja。
这个包和之前的版本相比，只有一些小的不同。它返回的是一个list（列表），而不是str（字符串），并且可以在python3中使用。它还包含了单词列表，并且即使有一些非字母字符（比如下划线、破折号等），也能正确地进行分割。
再次感谢Generic Human的贡献！
一个简单的算法在处理真实世界的数据时效果不好。这里有一个20行的算法，它利用单词的相对频率来为真实文本提供准确的结果。
（如果你想要一个不使用单词频率的答案，你需要明确“最长单词”到底是什么意思：是一个20个字母的单词加上十个3个字母的单词更好，还是五个10个字母的单词更好？一旦你确定了具体的定义，你只需要修改定义wordcost的那一行，以反映你的意思。）
思路
最好的方法是建模输出的分布。一个好的初步假设是所有单词都是独立分布的。这样你只需要知道所有单词的相对频率。可以合理地假设它们遵循齐夫定律，也就是说，在单词列表中排名为n的单词，其出现的概率大约是1/(n log N)，其中N是字典中的单词总数。
一旦你确定了模型，就可以使用动态规划来推断空格的位置。最可能的句子是最大化每个单词概率乘积的句子，使用动态规划计算这个是很简单的。我们不是直接使用概率，而是使用定义为概率倒数的对数的成本，以避免溢出。
代码
from math import log
# Build a cost dictionary, assuming Zipf's law and cost = -math.log(probability).
words = open("words-by-frequency.txt").read().split()
wordcost = dict((k, log((i+1)*log(len(words)))) for i,k in enumerate(words))
maxword = max(len(x) for x in words)
def infer_spaces(s):
"""Uses dynamic programming to infer the location of spaces in a string
without spaces."""
# Find the best match for the i first characters, assuming cost has
# been built for the i-1 first characters.
# Returns a pair (match_cost, match_length).
def best_match(i):
candidates = enumerate(reversed(cost[max(0, i-maxword):i]))
return min((c + wordcost.get(s[i-k-1:i], 9e999), k+1) for k,c in candidates)
# Build the cost array.
cost = [0]
for i in range(1,len(s)+1):
c,k = best_match(i)
cost.append(c)
# Backtrack to recover the minimal-cost string.
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))
你可以用它来配合
s = 'thumbgreenappleactiveassignmentweeklymetaphor'
print(infer_spaces(s))
结果
我使用了这个我从维基百科的小部分整理出来的快速字典，包含125,000个单词。
之前： thumbgreenappleactiveassignmentweeklymetaphor.
之后： thumb green apple active assignment weekly metaphor.
之前： thereismassesoftextinformationofpeoplescommentswhichisparsedfromhtmlbuttherearen odelimitedcharactersinthemforexamplethumbgreenappleactiveassignmentweeklymetapho rapparentlytherearethumbgreenappleetcinthestringialsohavealargedictionarytoquery whetherthewordisreasonablesowhatsthefastestwayofextractionthxalot.
之后： there is masses of text information of peoples comments which is parsed from html but there are no delimited characters in them for example thumb green apple active assignment weekly metaphor apparently there are thumb green apple etc in the string i also have a large dictionary to query whether the word is reasonable so what s the fastest way of extraction thx a lot.
之前： itwasadarkandstormynighttherainfellintorrentsexceptatoccasionalintervalswhenitwascheckedbyaviolentgustofwindwhichsweptupthestreetsforitisinlondonthatoursceneliesrattlingalongthehousetopsandfiercelyagitatingthescantyflameofthelampsthatstruggledagainstthedarkness.
之后： it was a dark and stormy night the rain fell in torrents except at occasional intervals when it was checked by a violent gust of wind which swept up the streets for it is in london that our scene lies rattling along the housetops and fiercely agitating the scanty flame of the lamps that struggled against the darkness.
如你所见，效果几乎完美。最重要的是确保你的单词列表是根据你实际会遇到的语料库训练的，否则结果会很糟糕。
优化
这个实现消耗的时间和内存是线性的，所以效率还算不错。如果你需要更快的速度，可以从单词列表构建一个后缀树，以减少候选集的大小。
如果你需要处理一个非常大的连续字符串，合理的做法是将字符串拆分，以避免过多的内存使用。例如，你可以将文本分成10000个字符的块，并在每边加上1000个字符的边距，以避免边界效应。这将使内存使用保持在最低限度，并几乎不会影响质量。