如何将没有空格的文本拆分为单词列表

Unutbu 的解决方案非常接近，但是我发现代码很难阅读，而且它没有产生预期的结果。通用人类的解决方案有一个缺点，那就是它需要单词频率。不适用于所有用例。

下面是一个使用 分治法的简单解决方案。

1. 它尝试 尽量减少单词的数量，例如 find_words('cupboard')将返回 ['cupboard']而不是 ['cup', 'board'](假设 cupboard、 cup和 board在字典中)
2. 最佳解决方案是 不是独一无二的，下面的实现返回 一解决方案。find_words('charactersin')可能返回 ['characters', 'in']，也可能返回 ['character', 'sin'](如下所示)。您可以很容易地修改算法以返回所有最优解。
3. 在这个实现解决方案是 记下来了，以便它运行在一个合理的时间。

密码:

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)

人们评论的大量文本信息都是从 ht l 中解析出来的，但是没有限定的字符，例如拇指绿苹果主动分配周隐喻显然字符串中有拇指绿苹果等等我还有一个大字典来查询这个词是否合理，那么最快的提取 th x 的方法是什么呢

基于 unutbu 的解决方案，我实现了一个 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;
}

输入: "tableapplechairtablecupboard"

输出: [table, apple, chair, table, cupboard]

输入: "tableprechaun"

输出: [tab, leprechaun]

普通人类的 回答是伟大的。但是我所见过的最好的实现是 Peter Norvig 自己在他的书《美丽的数据》中写的。

在我粘贴他的代码之前，让我解释一下为什么 Norvig 的方法更精确(尽管在代码方面稍微慢一些，也更长一些)。

1. 数据要好一些——无论是从大小还是从精确度来说(他使用的是单词计数而不是简单的排名)
2. 更重要的是，n-gram 背后的逻辑使得这种方法非常精确。

他在书中提供的例子是拆分字符串“ sitdown”的问题。现在一个非二元组的字符串拆分方法会考虑 p (‘ sit’) * p (‘ down’) ，如果这个小于 p (‘ sitdown’)——这种情况经常发生——它不会拆分它，但是我们希望它(大多数时候)这样做。

然而，当你有二元模型时，你可以将 p (“ sit down”)作为二元模型对 p (“ sit down”)进行估值，前者胜出。基本上，如果你不使用双字母，它会把你分割的单词的概率看作是独立的，但事实并非如此，有些单词更可能一个接一个地出现。不幸的是，在很多情况下，这些词也常常粘在一起，使分离者感到困惑。

下面是到数据的链接(它的数据针对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

基于在 最佳答案的出色工作，我已经创建了一个易于使用的 pip包。

>>> import wordninja
>>> wordninja.split('derekanderson')
['derek', 'anderson']

要安装，请运行 pip install wordninja。

唯一的区别是微小的。这将返回一个 list而不是 str，它在 python3中工作，它包含单词列表，并且即使有非 alpha 字符(如下划线、破折号等)也能正确分割。

再次感谢普通人类！

Https://github.com/keredson/wordninja

对于德语来说，有 CharSplit，它使用机器学习，对于几个单词组成的字符串非常有效。

Https://github.com/dtuggener/charsplit

在 @ miku’s建议使用 Trie的基础上，只附加 Trie在 python中的实现相对简单:

class Node:
def __init__(self, is_word=False):
self.children = {}
self.is_word = is_word


class TrieDictionary:
def __init__(self, words=tuple()):
self.root = Node()
for word in words:
self.add(word)


def add(self, word):
node = self.root
for c in word:
node = node.children.setdefault(c, Node())
node.is_word = True


def lookup(self, word, from_node=None):
node = self.root if from_node is None else from_node
for c in word:
try:
node = node.children[c]
except KeyError:
return None


return node

然后，我们可以从一组单词中构建一个基于 Trie的字典:

dictionary = {"a", "pea", "nut", "peanut", "but", "butt", "butte", "butter"}
trie_dictionary = TrieDictionary(words=dictionary)

它将生成一个类似下面这样的树(*表示单词的开头或结尾) :

* -> a*
\\\
\\\-> p -> e -> a*
\\              \-> n -> u -> t*
\\
\\-> b -> u -> t*
\\             \-> t*
\\                 \-> e*
\\                     \-> r*
\
\-> n -> u -> t*

我们可以通过将其与关于如何选择单词的启发式方法相结合，将其纳入解决方案中。例如，我们可以选择较长的单词而不是较短的单词:

def using_trie_longest_word_heuristic(s):
node = None
possible_indexes = []


# O(1) short-circuit if whole string is a word, doesn't go against longest-word wins
if s in dictionary:
return [ s ]


for i in range(len(s)):
# traverse the trie, char-wise to determine intermediate words
node = trie_dictionary.lookup(s[i], from_node=node)


# no more words start this way
if node is None:
# iterate words we have encountered from biggest to smallest
for possible in possible_indexes[::-1]:
# recurse to attempt to solve the remaining sub-string
end_of_phrase = using_trie_longest_word_heuristic(s[possible+1:])


# if we have a solution, return this word + our solution
if end_of_phrase:
return [ s[:possible+1] ] + end_of_phrase


# unsolvable
break


# if this is a leaf, append the index to the possible words list
elif node.is_word:
possible_indexes.append(i)


# empty string OR unsolvable case
return []

我们可以这样使用这个函数:

>>> using_trie_longest_word_heuristic("peanutbutter")
[ "peanut", "butter" ]

因为当我们搜索越来越长的单词时，我们保持在 Trie中的位置，所以我们在每个可能的解决方案中最多遍历 trie一次(而不是在 peanut: pea，peanut中遍历 2次)。最后的短路使我们避免了在最坏的情况下沿着字符串走。

最终结果只是少数几次检查:

'peanutbutter' - not a word, go charwise
'p' - in trie, use this node
'e' - in trie, use this node
'a' - in trie and edge, store potential word and use this node
'n' - in trie, use this node
'u' - in trie, use this node
't' - in trie and edge, store potential word and use this node
'b' - not in trie from `peanut` vector
'butter' - remainder of longest is a word

这种解决方案的一个好处是，您可以非常快速地知道是否存在具有给定前缀的较长单词，这样就不需要根据字典详尽地测试序列组合。与其他实现相比，它还使得得到 unsolvable的答案变得相对便宜。

这种解决方案的缺点是 trie的内存占用量很大，而且预先构建 trie的成本很高。

以下是转换成 JavaScript 的公认答案(需要 node.js，以及来自 https://github.com/keredson/wordninja的文件“ wordninja _ words.txt”) :

var fs = require("fs");


var splitRegex = new RegExp("[^a-zA-Z0-9']+", "g");
var maxWordLen = 0;
var wordCost = {};


fs.readFile("./wordninja_words.txt", 'utf8', function(err, data) {
if (err) {
throw err;
}
var words = data.split('\n');
words.forEach(function(word, index) {
wordCost[word] = Math.log((index + 1) * Math.log(words.length));
})
words.forEach(function(word) {
if (word.length > maxWordLen)
maxWordLen = word.length;
});
console.log(maxWordLen)
splitRegex = new RegExp("[^a-zA-Z0-9']+", "g");
console.log(split(process.argv[2]));
});




function split(s) {
var list = [];
s.split(splitRegex).forEach(function(sub) {
_split(sub).forEach(function(word) {
list.push(word);
})
})
return list;
}
module.exports = split;




function _split(s) {
var cost = [0];


function best_match(i) {
var candidates = cost.slice(Math.max(0, i - maxWordLen), i).reverse();
var minPair = [Number.MAX_SAFE_INTEGER, 0];
candidates.forEach(function(c, k) {
if (wordCost[s.substring(i - k - 1, i).toLowerCase()]) {
var ccost = c + wordCost[s.substring(i - k - 1, i).toLowerCase()];
} else {
var ccost = Number.MAX_SAFE_INTEGER;
}
if (ccost < minPair[0]) {
minPair = [ccost, k + 1];
}
})
return minPair;
}


for (var i = 1; i < s.length + 1; i++) {
cost.push(best_match(i)[0]);
}


var out = [];
i = s.length;
while (i > 0) {
var c = best_match(i)[0];
var k = best_match(i)[1];
if (c == cost[i])
console.log("Alert: " + c);


var newToken = true;
if (s.slice(i - k, i) != "'") {
if (out.length > 0) {
if (out[-1] == "'s" || (Number.isInteger(s[i - 1]) && Number.isInteger(out[-1][0]))) {
out[-1] = s.slice(i - k, i) + out[-1];
newToken = false;
}
}
}


if (newToken) {
out.push(s.slice(i - k, i))
}


i -= k


}
return out.reverse();
}

如果您有字符串中包含的单词的详尽列表:

word_list = ["table", "apple", "chair", "cupboard"]

使用列表内涵对列表进行迭代，以确定单词的出现次数。

string = "tableapplechairtablecupboard"


def split_string(string, word_list):


return ("".join([(item + " ")*string.count(item.lower()) for item in word_list if item.lower() in string])).strip()

该函数按照列表 table table apple chair cupboard的顺序返回单词的 string输出

非常感谢 https://github.com/keredson/wordninja/的帮助

一个小小的贡献相同的爪哇从我的身边。

公共方法 splitContiguousWords可以与类中的其他两个方法一起嵌入，这两个方法的 ninja _ words.txt 位于相同的目录中(或者根据编码器的选择进行修改)。方法 splitContiguousWords可以用于此目的。

public List<String> splitContiguousWords(String sentence) {


String splitRegex = "[^a-zA-Z0-9']+";
Map<String, Number> wordCost = new HashMap<>();
List<String> dictionaryWords = IOUtils.linesFromFile("ninja_words.txt", StandardCharsets.UTF_8.name());
double naturalLogDictionaryWordsCount = Math.log(dictionaryWords.size());
long wordIdx = 0;
for (String word : dictionaryWords) {
wordCost.put(word, Math.log(++wordIdx * naturalLogDictionaryWordsCount));
}
int maxWordLength = Collections.max(dictionaryWords, Comparator.comparing(String::length)).length();
List<String> splitWords = new ArrayList<>();
for (String partSentence : sentence.split(splitRegex)) {
splitWords.add(split(partSentence, wordCost, maxWordLength));
}
log.info("Split word for the sentence: {}", splitWords);
return splitWords;
}


private String split(String partSentence, Map<String, Number> wordCost, int maxWordLength) {
List<Pair<Number, Number>> cost = new ArrayList<>();
cost.add(new Pair<>(Integer.valueOf(0), Integer.valueOf(0)));
for (int index = 1; index < partSentence.length() + 1; index++) {
cost.add(bestMatch(partSentence, cost, index, wordCost, maxWordLength));
}
int idx = partSentence.length();
List<String> output = new ArrayList<>();
while (idx > 0) {
Pair<Number, Number> candidate = bestMatch(partSentence, cost, idx, wordCost, maxWordLength);
Number candidateCost = candidate.getKey();
Number candidateIndexValue = candidate.getValue();
if (candidateCost.doubleValue() != cost.get(idx).getKey().doubleValue()) {
throw new RuntimeException("Candidate cost unmatched; This should not be the case!");
}
boolean newToken = true;
String token = partSentence.substring(idx - candidateIndexValue.intValue(), idx);
if (token != "\'" && output.size() > 0) {
String lastWord = output.get(output.size() - 1);
if (lastWord.equalsIgnoreCase("\'s") ||
(Character.isDigit(partSentence.charAt(idx - 1)) && Character.isDigit(lastWord.charAt(0)))) {
output.set(output.size() - 1, token + lastWord);
newToken = false;
}
}
if (newToken) {
output.add(token);
}
idx -= candidateIndexValue.intValue();
}
return String.join(" ", Lists.reverse(output));
}




private Pair<Number, Number> bestMatch(String partSentence, List<Pair<Number, Number>> cost, int index,
Map<String, Number> wordCost, int maxWordLength) {
List<Pair<Number, Number>> candidates = Lists.reverse(cost.subList(Math.max(0, index - maxWordLength), index));
int enumerateIdx = 0;
Pair<Number, Number> minPair = new Pair<>(Integer.MAX_VALUE, Integer.valueOf(enumerateIdx));
for (Pair<Number, Number> pair : candidates) {
++enumerateIdx;
String subsequence = partSentence.substring(index - enumerateIdx, index).toLowerCase();
Number minCost = Integer.MAX_VALUE;
if (wordCost.containsKey(subsequence)) {
minCost = pair.getKey().doubleValue() + wordCost.get(subsequence).doubleValue();
}
if (minCost.doubleValue() < minPair.getKey().doubleValue()) {
minPair = new Pair<>(minCost.doubleValue(), enumerateIdx);
}
}
return minPair;
}

这会有帮助的

from wordsegment import load, segment
load()
segment('providesfortheresponsibilitiesofperson')