如何将没有空格的文本分割成单词列表？
input： "tableapplechairtablecupboard..."很多单词
将这样的文本分割成单词列表的有效algorithm是什么？
输出： ["table", "apple", "chair", "table", ["cupboard", ["cup", "board"]], ...]
首先想到的是通过所有可能的单词（从第一个字母开始），并find最长的单词，从position=word_position+len(word)
PS
我们有所有可能的单词列表。
单词“橱柜”可以是“杯子”和“板子”，select时间最长。
语言：python，但主要的是algorithm本身。
天真的algorithm应用于真实世界的数据时不会给出好的结果。 这是一个20行的algorithm，利用相对字词频率为真实的文字提供准确的结果。
（如果你想回答你的原始问题，不使用词频，你需要改进“最长的单词”究竟是什么意思：有20个字母的单词和10个3个字母的单词，还是更好最好有五个10个字母的单词吗？一旦你确定了一个精确的定义，你只需要改变定义wordcost的行来反映意图的含义。
这个想法
最好的方法是模拟输出的分布。 一个好的第一个近似是假设所有的单词是独立分布的。 那么你只需要知道所有单词的相对频率。 假设他们遵循Zipf定律是合理的，也就是说，单词列表中的秩为n的词的概率大约为1 /（ n log N ），其中N是词典中单词的数量。
一旦你修好了模型，你可以使用dynamic编程来推断空间的位置。 最可能的句子是使每个单词的概率乘积最大化的句子，并且用dynamic编程很容易计算。 而不是直接使用概率，我们使用成本定义为概率倒数的对数来避免溢出。
代码
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[ik-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[ik:i]) i -= k return " ".join(reversed(out))
你可以使用它
s = 'thumbgreenappleactiveassignmentweeklymetaphor' print(infer_spaces(s))
结果
我正在使用这个从维基百科的一小部分放在一起的快速和肮脏的125k字典 。
之前： thumbgreenappleactiveassignmentweeklymetaphor。
之后：大拇指青苹果每周比喻活跃分配。
在此之前：各种各样的文字信息都被分类，但是在这些词汇中却有一些有限的人物，例如绿色的应用程序，每周一次的标注，都有一些绿色的应用程序，以及一些词汇的含义，以便查询这些词语是否合理，以便提取这些文件的最快速度。
之后：有很多人的评论文字信息是从htmlparsing出来的，但是里面没有分隔字符，例如大拇指青苹果活动分配每周比喻显然有拇指青苹果等string我也有一个大字典查询这个词是否合理，提取thx的最快方法是多less。
之前，它正在冒险和风暴的时候，除了受到巨大的风吹雨打之外，没有其他的风险，而且在风暴之前，风暴已经被撕毁了， 在它们的屋顶之间进行了一系列的剧烈的冲击，并激烈地刺激着那些引人注目的灯光。
之后：这是一个黑暗而暴风雨的夜晚，除了偶尔的时间间隔，暴风雨袭来的时候，暴风雨席卷了大街小巷，因为在伦敦，我们的景象在屋顶嘎嘎作响，激烈地搅动着在黑暗中挣扎的灯火的稀薄的火焰。
正如你所看到的，它本质上是完美的。 最重要的部分是确保你的单词列表被训练成类似于你实际遇到的语料库，否则结果将是非常糟糕的。
优化
这个实现消耗了线性的时间和内存，所以它是合理的。 如果你需要进一步的加速，你可以从单词列表中build立一个后缀树来减less候选集的大小。
如果你需要处理一个非常大的连续string，分割string以避免过多的内存使用是合理的。 例如，您可以在10000个字符的块中处理文本，并在两边加上1000个字符的边距以避免边界效应。 这会将内存使用量降到最低，几乎肯定不会影响质量。
这里是使用recursionsearch的解决scheme：
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']
使用包含可能的单词列表的trie 数据结构 ，执行以下操作不会太复杂：
- 高级指针（在连接的string中）
- 在树中查找并存储相应的节点
- 如果trie节点有孩子（例如有更长的单词），请转到1。
- 如果到达的节点没有孩子，则发生最长的词匹配; 在结果列表中添加单词（存储在节点中或者在遍历期间只是连接），重置trie中的指针（或重置引用），并重新开始
基于顶级答案的出色工作，我创build了一个易于使用的pip包。
>>> import wordninja >>> wordninja.split('derekanderson') ['derek', 'anderson']
要安装，运行pip install wordninja 。
唯一的区别是次要的。 这返回一个list而不是一个str ，它在python3 ，它包括单词列表，并正确分裂，即使有非alpha字符（如下划线，破折号等）。
再次感谢Generic Human！
Unutbu的解决scheme非常接近，但是我发现代码难以阅读，并且没有产生预期的结果。 通用人的解决scheme有缺点，它需要词频。 不适合所有使用情况。
这是一个简单的解决scheme，使用分而治之的algorithm 。
- 它试图尽量减less单词的数量，例如
find_words('cupboard')将返回['cupboard']而不是['cup', 'board']（假设cupboard，cup和board在词典中） - 最佳解决scheme不是唯一的 ，下面的实现返回一个解决scheme。
find_words('charactersin')可以返回['characters', 'in']或者返回['character', 'sin']（如下所示）。 你可以很容易地修改algorithm返回所有的最佳解决scheme。 - 在这个实现中，解决scheme被logging下来，以便在合理的时间内运行。
代码：
words = set() with open('/usr/share/dict/words') as f: for line in f: words.add(line.strip()) solutions = {} def find_words(instring): # First check if instring is in the dictionnary if instring in words: return [instring] # No... But maybe it's a result we already computed if instring in solutions: return solutions[instring] # Nope. Try to split the string at all position to recursively search for results best_solution = None for i in range(1, len(instring) - 1): part1 = find_words(instring[:i]) part2 = find_words(instring[i:]) # Both parts MUST have a solution if part1 is None or part2 is None: continue solution = part1 + part2 # Is the solution found "better" than the previous one? if best_solution is None or len(solution) < len(best_solution): best_solution = solution # Remember (memoize) this solution to avoid having to recompute it solutions[instring] = best_solution return best_solution
我的3GHz机器大约需要5秒左右的时间：
result = find_words("thereismassesoftextinformationofpeoplescommentswhichisparsedfromhtmlbuttherearenodelimitedcharactersinthemforexamplethumbgreenappleactiveassignmentweeklymetaphorapparentlytherearethumbgreenappleetcinthestringialsohavealargedictionarytoquerywhetherthewordisreasonablesowhatsthefastestwayofextractionthxalot") assert(result is not None) print ' '.join(result)
reis群众的文字信息是从htmlparsing的人民的意见，但没有分隔的字符罪他们例如拇指青苹果活跃分配每周隐喻显然有拇指青苹果等在string我也有一个大字典查询是否这个词是合理的，所以提取thxa最快的方法是什么
通过https://stackoverflow.com/users/1515832/generic-human的答案是伟大的。; 但是，我见过的最好的实现是彼得·诺维格（Peter Norvig）在他的“美丽的数据”一书中写的。
在我粘贴他的代码之前，让我扩展一下为什么Norvig的方法更精确（尽pipe在代码方面稍慢一点）。
1）数据更好一些 – 无论是在大小还是在精度方面（他使用的是一个字数而不是简单的排名）2）更重要的是，这是n-gram背后的逻辑确实使得方法如此准确。
他在书中提供的例子是分割string“静坐”的问题。 现在一个非bigram的string拆分方法会考虑p（'sit'）* p（'down'），如果这小于p（'sitdown'） – 这将是很常见的情况 – 它不会分裂它，但我们希望（大部分时间）。
然而，当你拥有bigram模型时，你可以将p（'坐下'）看作是一个bigram对p（'sitdown'），而前者是胜利。 基本上，如果你不使用bigrams，它把你分裂的单词的概率看作是独立的，事实并非如此，有些单词更可能一个接一个地出现。 不幸的是，这些也是经常在许多情况下粘在一起的话，并且混淆了分离器。
这里是数据的链接（这是3个不同的问题的数据，分割只有一个，详情请阅读本章）： http : //norvig.com/ngrams/
这里是代码的链接： http : //norvig.com/ngrams/ngrams.py
这些链接已经过去了一段时间，但是我仍然要复制代码的分段部分
import re, string, random, glob, operator, heapq from collections import defaultdict from math import log10 def memo(f): "Memoize function f." table = {} def fmemo(*args): if args not in table: table[args] = f(*args) return table[args] fmemo.memo = table return fmemo def test(verbose=None): """Run some tests, taken from the chapter. Since the hillclimbing algorithm is randomized, some tests may fail.""" import doctest print 'Running tests...' doctest.testfile('ngrams-test.txt', verbose=verbose) ################ Word Segmentation (p. 223) @memo def segment(text): "Return a list of words that is the best segmentation of text." if not text: return [] candidates = ([first]+segment(rem) for first,rem in splits(text)) return max(candidates, key=Pwords) def splits(text, L=20): "Return a list of all possible (first, rem) pairs, len(first)<=L." return [(text[:i+1], text[i+1:]) for i in range(min(len(text), L))] def Pwords(words): "The Naive Bayes probability of a sequence of words." return product(Pw(w) for w in words) #### Support functions (p. 224) def product(nums): "Return the product of a sequence of numbers." return reduce(operator.mul, nums, 1) class Pdist(dict): "A probability distribution estimated from counts in datafile." def __init__(self, data=[], N=None, missingfn=None): for key,count in data: self[key] = self.get(key, 0) + int(count) self.N = float(N or sum(self.itervalues())) self.missingfn = missingfn or (lambda k, N: 1./N) def __call__(self, key): if key in self: return self[key]/self.N else: return self.missingfn(key, self.N) def datafile(name, sep='\t'): "Read key,value pairs from file." for line in file(name): yield line.split(sep) def avoid_long_words(key, N): "Estimate the probability of an unknown word." return 10./(N * 10**len(key)) N = 1024908267229 ## Number of tokens Pw = Pdist(datafile('count_1w.txt'), N, avoid_long_words) #### segment2: second version, with bigram counts, (p. 226-227) def cPw(word, prev): "Conditional probability of word, given previous word." try: return P2w[prev + ' ' + word]/float(Pw[prev]) except KeyError: return Pw(word) P2w = Pdist(datafile('count_2w.txt'), N) @memo def segment2(text, prev='<S>'): "Return (log P(words), words), where words is the best segmentation." if not text: return 0.0, [] candidates = [combine(log10(cPw(first, prev)), first, segment2(rem, first)) for first,rem in splits(text)] return max(candidates) def combine(Pfirst, first, (Prem, rem)): "Combine first and rem results into one (probability, words) pair." return Pfirst+Prem, [first]+rem
如果预编译单词表到DFA中 （这将非常慢），那么匹配input所需的时间将与string的长度成比例（事实上，只比迭代string慢一点点）。
这实际上是前面提到的triealgorithm的更一般的版本。 我只提到它是完全没有的，因为目前还没有DFA实现可以使用。 RE2可以工作，但我不知道Python绑定是否允许您调整DFA的大小，然后才丢弃已编译的DFA数据并执行NFAsearch。
这似乎是相当普通的回溯会做。 从string的开始处开始。 直接扫描，直到有一个字。 然后，在string的其余部分调用该函数。 如果在不识别单词的情况下一直扫描到右侧，函数将返回“false”。 否则，返回find的单词和recursion调用返回的单词列表。
例如：“tableapple”。 find“标签”，然后“跳跃”，但在“ple”中没有词。 没有其他字在“leapple”。 find“表”，然后“应用程序”。 “le”不是一个字，所以尝试苹果，承认，返回。
为了尽可能长时间地继续下去，只发出（而不是返回）正确的解决scheme; 然后，根据您select的任何标准（最大最大值，最小最大值，平均值等）select最佳值。
基于unutbu的解决scheme，我已经实现了一个Java版本：
private static List<String> splitWordWithoutSpaces(String instring, String suffix) { if(isAWord(instring)) { if(suffix.length() > 0) { List<String> rest = splitWordWithoutSpaces(suffix, ""); if(rest.size() > 0) { List<String> solutions = new LinkedList<>(); solutions.add(instring); solutions.addAll(rest); return solutions; } } else { List<String> solutions = new LinkedList<>(); solutions.add(instring); return solutions; } } if(instring.length() > 1) { String newString = instring.substring(0, instring.length()-1); suffix = instring.charAt(instring.length()-1) + suffix; List<String> rest = splitWordWithoutSpaces(newString, suffix); return rest; } return Collections.EMPTY_LIST; }
input： "tableapplechairtablecupboard"
输出： [table, apple, chair, table, cupboard]
input： "tableprechaun"
输出： [tab, leprechaun]
你需要识别你的词汇 – 也许任何免费的单词列表都可以。
一旦完成，使用该词汇来build立一个后缀树，并匹配你的inputstream： http : //en.wikipedia.org/wiki/Suffix_tree
