如何将没有空格的文本拆分为单词列表
- 2025-01-06 08:32:00
- admin 原创
- 151
问题描述：
输入： "tableapplechairtablecupboard..."许多单词
将这样的文本拆分为单词列表并获得以下结果的有效算法是什么：
输出： ["table", "apple", "chair", "table", ["cupboard", ["cup", "board"]], ...]
首先想到的是遍历所有可能的单词（从第一个字母开始），并找到最长的单词，然后从position=word_position+len(word)
PS
我们有一个所有可能单词的列表。
单词“cupboard”可以是“cup”和“board”，选择最长的。
语言：python，但最重要的是算法本身。
解决方案 1：
简单的算法在应用于真实数据时不会产生良好的结果。这是一个 20 行的算法，它利用相对词频为真实文本提供准确的结果。
（如果您想要一个不使用词频的原始问题的答案，您需要细化“最长单词”的确切含义：有一个 20 个字母的单词和十个 3 个字母的单词更好，还是有五个 10 个字母的单词更好？一旦您确定了精确的定义，您只需更改定义的行wordcost以反映预期的含义。）
想法
最好的方法是模拟输出的分布。一个好的第一个近似方法是假设所有单词都是独立分布的。然后你只需要知道所有单词的相对频率。合理的假设是它们遵循 Zipf 定律，即单词列表中排名为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))
结果
我正在使用这本根据维基百科的一小部分汇编而成的 125k 词的快速词典。
之前： thumbgreenappleactiveassignmentweeklymetaphor。
之后： thumb green apple active assignment weekly metaphor。
之前： thereismassesofttextinformationofpeoplescommentswhichisparsedfromhtmlbuttherearen odelimitedcharactersintheexamplethumbgreenappleactiveassignmentweeklymetapho rap显然therearethumbgreenappleetcinthestringialsohavealargedictionarytoquerywotherisreasonablesowhatsthefastestwayofextractionthxalot。
之后：从html解析出来大量的人们评论的文本信息但是其中没有分隔字符例如thumb green apple active assignment weekly metaphor显然字符串中有thumb green apple等我也有大词典可以查询这个词是否合理所以最快的提取方法是什么非常感谢。
之前：那是一个黑暗而暴风雨的夜晚，大雨倾盆而下，除了偶尔被猛烈的阵风阻挡之外，狂风席卷伦敦的街道，我们的场景在屋顶上嘎嘎作响，猛烈地搅动着与黑暗抗争的灯光的微弱火焰。
之后：那是一个漆黑而暴风雨的夜晚，大雨倾盆而下，只是偶尔被一阵席卷街道的狂风所阻挡，因为我们所拍摄的场景是在伦敦，雨水在屋顶上嘎嘎作响，猛烈地搅动着与黑暗抗争的路灯的微弱火光。
如你所见，它基本上是完美的。最重要的是确保你的单词表是针对与你实际遇到的相似的语料库进行训练的，否则结果会非常糟糕。
优化
该实现消耗的时间和内存量是线性的，因此效率相当高。如果您需要进一步加速，可以从单词列表中构建后缀树以减少候选集的大小。
如果您需要处理非常大的连续字符串，则拆分字符串以避免过多的内存使用是合理的。例如，您可以将文本分成 10000 个字符的块，并在两边留出 1000 个字符的空白，以避免边界效应。这将使内存使用量保持在最低水平，并且几乎肯定不会影响质量。
解决方案 2：
基于最佳答案中的出色工作，我创建了一个pip易于使用的包。
>>> import wordninja
>>> wordninja.split('derekanderson')
['derek', 'anderson']
要安装，请运行pip install wordninja。
唯一的区别很小。这将返回一个list而不是str，它在 中工作python3，它包括单词列表并且即使有非字母字符（如下划线、破折号等）也能正确拆分。
再次感谢 Generic Human！
https://github.com/keredson/wordninja
解决方案 3：
以下是使用递归搜索的解决方案：
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']
解决方案 4：
使用保存可能单词列表的trie 数据结构，执行以下操作并不太复杂：
前进指针（在连接字符串中）
在字典树中查找并存储相应节点
如果 trie 节点有子节点（例如有更长的单词），则转到 1。
如果到达的节点没有子节点，则发生最长单词匹配；将单词（存储在节点中或在 trie 遍历期间连接）添加到结果列表中，重置 trie 中的指针（或重置引用），然后重新开始
解决方案 5：
Generic Human的答案很棒。但我见过的对此最好的实现是 Peter Norvig 在他的书《Beautiful Data》中写的。
在我粘贴他的代码之前，让我先解释一下为什么 Norvig 的方法更准确（尽管代码稍微慢一些、更长一些）。
数据稍微好一些 - 无论是在大小方面还是在精度方面（他使用字数统计而不是简单的排名）
更重要的是，n-gram 背后的逻辑才使得这种方法如此准确。
他在书中提供的示例是拆分字符串“sitdown”的问题。现在，一种非二元字符串拆分方法将考虑 p('sit') * p ('down')，如果这个小于 p('sitdown') - 这种情况经常发生 - 它不会拆分它，但我们希望它这样做（大多数时候）。
但是，当您使用二元模型时，您可以将 p('sit down') 视为二元模型，而将 p('sitdown') 视为二元模型，前者获胜。基本上，如果您不使用二元模型，它会将您要拆分的单词的概率视为独立的，而事实并非如此，有些单词更有可能一个接一个地出现。不幸的是，这些单词在很多情况下也经常粘在一起，使拆分器感到困惑。
这是数据链接（这是 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=' '):
"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
解决方案 6：
Unutbu 的解决方案非常接近，但我发现代码难以阅读，并且没有产生预期的结果。Generic Human 的解决方案的缺点是它需要词频。不适合所有用例。
这是一个使用分治算法的简单解决方案。
它试图最小化Eg将返回的单词数量而不是（假设、和在词典中）
find_words('cupboard')`['cupboard']['cup', 'board']cupboardcupboard`最优解不是唯一的，下面的实现返回一个解。
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
在我的 3GHz 机器上这将花费大约 5 秒：
result = find_words("thereismassesoftextinformationofpeoplescommentswhichisparsedfromhtmlbuttherearenodelimitedcharactersinthemforexamplethumbgreenappleactiveassignmentweeklymetaphorapparentlytherearethumbgreenappleetcinthestringialsohavealargedictionarytoquerywhetherthewordisreasonablesowhatsthefastestwayofextractionthxalot")
assert(result is not None)
print ' '.join(result)
从 html 解析出来的人们评论的大量文本信息，但没有分隔符，例如拇指绿苹果活动作业周隐喻显然字符串中有拇指绿苹果等我还有一个大词典来查询这个词是否合理所以提取的最快方法是什么非常感谢
解决方案 7：
以下是翻译成 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('
');
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();
}
解决方案 8：
这将有助于
from wordsegment import load, segment
load()
segment('providesfortheresponsibilitiesofperson')运行代码片段Hide results展开片段
解决方案 9：
如果将单词列表预编译为DFA（这会非常慢），那么匹配输入所需的时间将与字符串的长度成正比（实际上，仅比迭代字符串慢一点）。
这实际上是前面提到的 trie 算法的更通用版本。我提到它只是为了不完全实现——到目前为止，还没有您可以使用的 DFA 实现。RE2可以工作，但我不知道 Python 绑定是否允许您调整允许 DFA 的大小，否则它会丢弃编译的 DFA 数据并进行 NFA 搜索。
解决方案 10：
非常感谢https://github.com/keredson/wordninja/的帮助
这是我在 Java 方面做出的一点小贡献。
公共方法splitContiguousWords可以嵌入到同一目录中具有 ninja_words.txt 的类中的其他 2 个方法中（或根据编码器的选择进行修改）。并且该方法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;
}
解决方案 11：
看起来相当普通的回溯就可以了。从字符串的开头开始。向右扫描直到找到一个单词。然后，对字符串的其余部分调用该函数。如果函数一直向右扫描而没有识别出一个单词，则返回“false”。否则，返回找到的单词和递归调用返回的单词列表。
例如：“tableapple”。找到“tab”，然后是“leap”，但“ple”中没有单词。“leapple”中没有其他单词。找到“table”，然后是“app”。“le”不是单词，因此尝试 apple，识别并返回。
为了获得最长的可能，继续下去，只发出（而不是返回）正确的解决方案；然后，根据您选择的任何标准（maxmax，minmax，average等）选择最佳的一个。
解决方案 12：
如果您有字符串中包含的单词的详尽列表：
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()
该函数string按列表顺序返回单词的输出table table apple chair cupboard
解决方案 13：
以下是使用原始（纯）JavaScript 的示例代码（基于一些示例）。请确保添加要使用的单词库（sample.txt）：
async function getSampleText(data) {
await fetch('sample.txt').then(response => response.text())
.then(text => {
const wordList = text;
// Create a regular expression for splitting the input string.
const splitRegex = new RegExp("[^a-zA-Z0-9']+", "g");
// Initialize the variables for storing the maximum word length and the word costs.
let maxWordLen = 0;
let wordCost = {};
// Split the word list into an array of words.
const words = wordList.split('
');
// Calculate the word costs based on the word list.
words.forEach((word, index) => {
wordCost[word] = Math.log((index + 1) * Math.log(words.length));
});
// Find the maximum word length.
words.forEach((word) => {
if (word.length > maxWordLen) {
maxWordLen = word.length;
}
});
console.log(maxWordLen);
//console.log(split(process.argv[2]));
/**
* Split the input string into an array of words.
* @param {string} s The input string.
* @return {Array} The array of words.
*/
function split(s) {
const list = [];
s.split(splitRegex).forEach((sub) => {
_split(sub).forEach((word) => {
list.push(word);
});
});
return list;
}
/**
* Split the input string into an array of words.
* @private
* @param {string} s The input string.
* @return {Array} The array of words.
*/
function _split(s) {
const cost = [0];
/**
* Find the best match for the i first characters, assuming cost has been built for the i-1 first characters.
* @param {number} i The index of the character to find the best match for.
* @return {Array} A pair containing the match cost and match length.
*/
function best_match(i) {
const candidates = cost.slice(Math.max(0, i - maxWordLen), i).reverse();
let minPair = [Number.MAX_SAFE_INTEGER, 0];
candidates.forEach((c, k) => {
let ccost;
if (wordCost[s.substring(i - k - 1, i).toLowerCase()]) {
ccost = c + wordCost[s.substring(i - k - 1, i).toLowerCase()];
} else {
ccost = Number.MAX_SAFE_INTEGER;
}
if (ccost < minPair[0]) {
minPair = [ccost, k + 1];
}
});
return minPair;
}
// Build the cost array.
for (let i = 1; i < s.length + 1; i++) {
cost.push(best_match(i)[0]);
}
// Backtrack to recover the minimal-cost string.
const out = [];
let i = s.length;
while (i > 0) {
const c = best_match(i)[0];
const k = best_match(i)[1];
if (c === cost[i]) {
console.log("Done: " + c);
}
let 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();
}
console.log(split('Thiswasaveryniceday'));
})
}
getSampleText();
解决方案 14：
使用附魔库。最佳选择。查看：https ://www.youtube.com/watch?v=Q3UR-uBWGfY&t=206s
# Import the enchant library for spell-checking
import enchant
def split_merged_words(word_to_split):
splitted_words = []
# "en_US" is the language code for English
dictionary = enchant.Dict("en_US")
word = word_to_split
length_of_word = len(word)
i = 0
while i < length_of_word:
for j in range(length_of_word, i, -1):
word_to_check = word[i:j]
if dictionary.check(word_to_check):
splitted_words.append(word_to_check)
i = j
break
return splitted_words
merged_words = input("Enter the merged words: ")
words = split_merged_words(merged_words)
print("The splitted words:", words)
输入合并的单词：tableapplechairtablecupboard
拆分后的单词：['table', 'apple', 'chair', 'table', 'cupboard']
解决方案 15：
您需要确定您的词汇量 - 也许任何免费的单词列表都可以。
完成后，使用该词汇表构建后缀树，并将您的输入流与其进行匹配： http: //en.wikipedia.org/wiki/Suffix_tree
解决方案 16：
基于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]
解决方案 17：
对于德语，有 CharSplit，它使用机器学习，并且对于几个单词的字符串非常有效。
https://github.com/dtuggener/CharSplit
解决方案 18：
扩展@miku使用的建议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 -> 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最多遍历一次每个可能的解决方案（而不是: ,2的次数）。最后的短路使我们免于在最坏情况下逐个字符地遍历字符串。peanut`pea`peanut
最终结果只需进行少量的检查：
'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
