输入: "tableapplechairtablecupboard..." 许多单词
有什么有效的算法可以将这样的文本拆分成单词列表并获得：
输出： ["table", "apple", "chair", "table", ["cupboard", ["cup", "board"]], ...]
首先想到的是遍历所有可能的单词（从第一个字母开始）并找到最长的单词，然后从position = word_position + len(word)继续。
P.S.
我们有所有可能单词的列表。
"cupboard"单词可以是"cup"和"board"，选择最长的那个单词。
语言：Python，但主要是算法本身。
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))
我使用了这个我从维基百科的一个小子集中组合起来的快速且简短的125k词典。
Before: thumbgreenappleactiveassignmentweeklymetaphor.
After: thumb green apple active assignment weekly metaphor.
Before: 有大量从HTML中解析出来的人们评论的文本信息，但是它们并没有分隔符，例如thumb green apple active assignment weekly metaphor。显然字符串中也有thumb green apple等单词，在我的字典中也有查询是否合理的大量单词，所以最快的提取方式是什么？多谢。
After: 有大量从HTML中解析出来的人们评论的文本信息，但是它们并没有分隔符，例如thumb green apple active assignment weekly metaphor。显然字符串中也有thumb green apple等单词，在我的字典中也有查询是否合理的大量单词，所以最快的提取方式是什么？多谢。
Before: 这是一个又黑暗又有风暴的夜晚，雨水倾盆而下，除了偶尔的间歇时刮起的狂风，街道上一片漆黑。我们的场景在伦敦，屋顶上格格作响，灯光微弱，几乎被黑暗吞噬。
After: 这是一个又黑暗又有风暴的夜晚，雨水倾盆而下，除了偶尔的间歇时刮起的狂风，街道上一片漆黑。我们的场景在伦敦，屋顶上格格作响，灯光微弱，几乎被黑暗吞噬。
您可以看到这个方法基本上是完美无瑕的，最重要的部分是确保您的词汇表训练于与实际遇到相似的语料库中，否则结果将很糟糕。
该实现消耗时间和内存量呈线性增长，因此效率还算不错。如果您需要更快的速度，可以从单词列表构建后缀树以缩小候选集的大小。
如果您需要处理非常大的连续字符串，则将字符串拆分为减少内存使用量是合理的。例如，您可以将文本按10000个字符的块处理，再加上每侧1000个字符的边距以避免边界效应。这将使内存使用量最小，并且几乎不会影响质量。
pip install wordninja - keredsonwords.txt 文件中包含 "comp"：$ grep "^comp$" words.txt
comp并且它是按字母顺序排序的。这段代码假设它按出现频率降序排序（这在像 n-gram 列表这样的列表中很常见）。
如果你使用一个正确排序的列表，你的字符串就会正常输出：>>> wordninja.split('namethecompanywherebonniewasemployedwhenwestarteddating')
['name', 'the', 'company', 'where', 'bonnie', 'was', 'employed', 'when', 'we', 'started', 'dating'] - keredson基于顶级答案的优秀工作，我已经创建了一个pip软件包以便于使用。
>>> import wordninja
>>> wordninja.split('derekanderson')
['derek', 'anderson']
安装方法：运行pip install wordninja。
唯一的区别是微小的。它返回一个list而不是str，在python3中工作，包括单词列表，并正确地分割非字母字符（如下划线、破折号等）。
再次感谢Generic Human！
这是一种使用递归搜索的解决方案：
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']
Generic Human的答案很好。但我见过的最好的实现是Peter Norvig自己在他的书“美丽的数据”中写的。
在我贴出他的代码之前，让我解释一下为什么Norvig的方法更准确（虽然稍微慢一些，代码也长一些）。
他在书中提供的例子是将字符串'sitdown'拆分成两个单词。现在，一个非bigram方法的字符串拆分会考虑p('sit') * p ('down')，如果这个结果小于p('sitdown') - 这通常是情况 - 它就不会拆分，但我们希望它能够拆分（大多数情况下）。
然而，当你使用bigram模型时，你可以将p('sit down')视为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
翻译如下：
find_words('cupboard')将返回['cupboard']而不是['cup', 'board']（假设字典中有cupboard、cup和board）。find_words('charactersin')可以返回['characters', 'in']或者可能会返回['character', 'sin']（如下所示）。您可以很容易地修改算法以返回所有最优解。代码如下：
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
result = find_words("thereismassesoftextinformationofpeoplescommentswhichisparsedfromhtmlbuttherearenodelimitedcharactersinthemforexamplethumbgreenappleactiveassignmentweeklymetaphorapparentlytherearethumbgreenappleetcinthestringialsohavealargedictionarytoquerywhetherthewordisreasonablesowhatsthefastestwayofextractionthxalot")
assert(result is not None)
print ' '.join(result)
这里是被接受的答案，已翻译为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();
}
这将有所帮助
from wordsegment import load, segment
load()
segment('providesfortheresponsibilitiesofperson')非常感谢在https://github.com/keredson/wordninja/中的帮助。
我也提供一个关于Java的小贡献。
可以将公共方法splitContiguousWords与该类中包含忍者单词文本文件的其他两个方法一起嵌入同一目录中（或根据编码人员的选择进行修改）。并且可以使用方法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;
}
['able', 'air', 'apple', 'boa', 'boar', 'board', 'chair', 'cup', 'cupboard', 'ha', 'hair', 'lea', 'leap', 'oar', 'tab', 'table', 'up']- reclosedev