공백 없이 텍스트를 단어 목록으로 분할하는 방법
력입: "tableapplechairtablecupboard..." 단어들
이러한 텍스트를 단어 목록으로 분할하고 다음을 얻는 효율적인 알고리즘은 무엇입니까?
출력: ["table", "apple", "chair", "table", ["cupboard", ["cup", "board"]], ...]
은 모든 글자부터 을 가능한 긴 입니다.position=word_position+len(word)
추신.
우리는 가능한 모든 단어의 목록을 가지고 있습니다.
단어 "컵보드"는 "컵"일 수 있고 "보드"는 가장 길게 선택할 수 있습니다.
언어: 파이썬, 하지만 주요한 것은 알고리즘 그 자체입니다.
순진한 알고리즘은 실제 데이터에 적용될 때 좋은 결과를 제공하지 않습니다.여기에는 실제 단어 텍스트에 대한 정확한 결과를 제공하기 위해 상대 단어 빈도를 활용하는 20줄 알고리즘이 있습니다.
(단어 빈도를 사용하지 않는 원래 질문에 대한 답변을 원한다면 "가장 긴 단어"가 정확히 무엇을 의미하는지 구체화해야 합니다. 20자 단어와 10자 단어가 10개인 것이 더 좋습니까? 아니면 10자 단어가 5개인 것이 더 좋습니까? 정확한, ▁line됩▁the다▁once니▁have▁youition,면▁change▁to를 정의하는 선을 바꾸기만 하면 됩니다.wordcost의도된 의미를 반영합니다.)
그 생각
가장 좋은 방법은 출력 분포를 모형화하는 것입니다.좋은 첫 번째 근사치는 모든 단어가 독립적으로 분포되어 있다고 가정하는 것입니다.그러면 모든 단어의 상대 빈도만 알면 됩니다.Zipf의 법칙을 따른다고 가정하는 것이 합리적입니다. 즉, 단어 목록에서 순위가 n인 단어는 사전에 있는 단어의 수를 나타내는 확률이 약 1/(n log 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))
그 결과들
저는 위키백과의 작은 부분 집합에서 가져온 빠르고 더러운 12만 5천 단어 사전을 사용하고 있습니다.
이전: 엄지 녹색 사과 활성 할당 주간 메타포.
이후: 엄지 초록 사과 활동 과제 주간 은유.
이전: html에서 구문 분석된 사람들 댓글의 텍스트 정보는 많지만, 예를 들어 주별 썸그린 사과 활성 할당 메타파에는 제한된 문자가 없거나 문자열에 분명히 썸그린 사과 등이 있습니다. 또한 해당 단어가 가장 빨리 추출할 수 있는 방법인지 쿼리하기 위해 큰 사전을 가지고 있습니다.
이후: html에서 구문 분석된 사람들 댓글의 텍스트 정보가 많지만, 예를 들어 섬 그린 애플 활성 과제 주간 메타포와 같이 구분된 문자가 없습니다. 분명히 문자열에 섬 그린 애플 등이 있습니다. 저는 또한 단어가 합리적인지 문의할 수 있는 큰 사전을 가지고 있습니다. 가장 빠른 것은 무엇입니까?추출 방법 thx 많이.
이전: 런던의 거리를 휩쓸고 있는 거센 바람의 돌풍에 의해 확인되었을 때, 어둠과 폭풍이 몰아치는 밤이었습니다. 우리의 풍경은 집 꼭대기를 따라 달그락거리고 어둠에 맞서 싸우는 램프의 빈약한 불꽃을 격렬하게 자극했습니다.
그 후: 거리를 휩쓴 거센 돌풍에 의해 확인될 때를 제외하고는 이따금씩 비가 억수같이 내리는 어둡고 폭풍이 몰아치는 밤이었습니다. 왜냐하면 우리의 장면은 집 꼭대기를 따라 덜컹거리고 어둠과 싸우는 램프의 미미한 불꽃을 맹렬히 선동하고 있기 때문입니다.
보시다시피 근본적으로 흠잡을 데가 없습니다.가장 중요한 부분은 단어 목록이 실제로 마주칠 것과 유사한 말뭉치로 훈련되었는지 확인하는 것입니다. 그렇지 않으면 결과가 매우 나쁠 것입니다.
최적화
구현은 선형적인 시간과 메모리를 소비하므로 상당히 효율적입니다.추가 속도 향상이 필요한 경우 단어 목록에서 접미사 트리를 작성하여 후보 집합의 크기를 줄일 수 있습니다.
매우 큰 연속 문자열을 처리해야 하는 경우 과도한 메모리 사용을 방지하기 위해 문자열을 분할하는 것이 합리적입니다.예를 들어, 경계 효과를 피하기 위해 텍스트를 10000자의 블록과 1000자의 여백으로 처리할 수 있습니다.이렇게 하면 메모리 사용량이 최소화되고 품질에 거의 영향을 미치지 않습니다.
1위 답변의 우수한 작업을 바탕으로 다음과 같은 내용을 작성했습니다.pip사용하기 쉬운 포장
>>> import wordninja
>>> wordninja.split('derekanderson')
['derek', 'anderson']
를 하십시오.pip install wordninja.
유일한 차이점은 사소한 것입니다.이는 다음을 반환합니다.list보다는 니▁rather▁a.str에서 작동합니다.python3단어 목록이 포함되어 있고 밑줄, 대시 등과 같이 영문자가 아닌 문자가 있더라도 적절하게 분할됩니다.
제네릭 휴먼에게 다시 한번 감사드립니다!
https://github.com/keredson/wordninja
다음은 재귀 검색을 사용하는 솔루션입니다.
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']
가능한 단어 목록을 포함하는 트라이 데이터 구조를 사용하면 다음을 수행하는 것이 그리 복잡하지 않을 것입니다.
- 고급 포인터(연결된 문자열)
- 해당 노드를 조회하고 트라이에 저장합니다.
- 트리 노드에 자식 노드가 있는 경우(예: 더 긴 단어가 있는 경우) 1로 이동합니다.
- 도달한 노드에 자식이 없는 경우 가장 긴 단어 일치가 발생했습니다. 결과 목록에 단어(노드에 저장되거나 트라이 트래버설 중에 연결됨)를 추가하고 트라이에서 포인터를 재설정(또는 참조 재설정)하고 다시 시작합니다.
Generic Human의 답변은 훌륭합니다.하지만 제가 본 것 중 가장 잘 구현된 것은 피터 노비그 자신이 그의 책 '아름다운 데이터'에 쓴 것입니다.
그의 코드를 붙이기 전에, 왜 Norvig의 방법이 더 정확한지에 대해 자세히 설명하겠습니다(코드 측면에서는 조금 느리고 길지만)
- 데이터는 크기와 정확도 측면에서 모두 약간 더 좋습니다(그는 단순한 순위가 아닌 단어 수를 사용합니다).
- 더 중요한 것은, 접근법을 매우 정확하게 만드는 것은 n-grams 이면의 논리입니다.
그가 그의 책에서 제시한 예는 '앉아' 줄을 나누는 문제입니다.이제 문자열 분할의 비빅그램 방법은 p('sit') * p('down')를 고려할 것이며, 만약 이것이 p('sitdown')보다 적다면 - 이것은 꽤 자주 있을 것입니다 - 그것은 분할하지 않을 것이지만, 우리는 그것을 원할 것입니다.
그러나 빅램 모델이 있을 때는 p('sitdown')를 빅램 대 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='\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
이 작업은 3GHz 기기에서 약 5초 정도 걸립니다.
result = find_words("thereismassesoftextinformationofpeoplescommentswhichisparsedfromhtmlbuttherearenodelimitedcharactersinthemforexamplethumbgreenappleactiveassignmentweeklymetaphorapparentlytherearethumbgreenappleetcinthestringialsohavealargedictionarytoquerywhetherthewordisreasonablesowhatsthefastestwayofextractionthxalot")
assert(result is not None)
print ' '.join(result)
html에서 구문 분석된 사람들의 의견에 대한 텍스트 정보가 대량으로 있지만, 예를 들어 섬 그린 애플 활성 과제 주간 메타포와 같이 그 안에 구분된 문자가 없습니다. 분명히 문자열에 섬 그린 애플 etc가 있습니다. 저는 또한 단어가 합리적인지 문의할 수 있는 큰 사전을 가지고 있습니다. 가장 빠른 것은 무엇입니까?추출 방법 x 많이
다음은 JavaScript(java 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')단어 목록을 DFA로 사전 컴파일하면(매우 느림) 입력을 일치시키는 데 걸리는 시간은 문자열의 길이에 비례합니다(실제로 문자열을 반복하는 것보다 약간 느립니다).
이것은 앞에서 언급한 트라이 알고리즘의 보다 일반적인 버전입니다.완전하지 않은 경우에만 언급합니다. 아직까지는 DFA 구현을 사용할 수 없습니다.RE2가 작동하겠지만, Python 바인딩을 사용하면 컴파일된 DFA 데이터를 버리고 NFA 검색을 수행하기 전에 DFA 크기를 조정할 수 있는지 모르겠습니다.
https://github.com/keredson/wordninja/ 에서 도움을 주셔서 감사합니다.
제가 보기에는 자바에서도 같은 작은 기여를 했습니다.
인 방법은splitContiguousWords의 두에 닌자_wordsninja_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;
}
꽤 평범한 역추적이 가능할 것 같습니다.문자열의 시작 부분에서 시작합니다.말이 나올 때까지 오른쪽으로 스캔합니다.그런 다음 문자열의 나머지 부분에 있는 함수를 호출합니다.함수가 단어를 인식하지 않고 오른쪽 끝까지 스캔하면 "false"를 반환합니다.그렇지 않으면 찾은 단어와 재귀 호출에 의해 반환된 단어 목록을 반환합니다.
예: "tableapple""탭"을 찾은 다음 "점프"를 찾지만 "플"에는 단어가 없습니다."leapple"에는 다른 단어가 없습니다."table"을 찾은 다음 "app"을 찾습니다."le"은 단어가 아닙니다. 그래서 사과를 시도하고, 인식하고, 반환합니다.
가능한 한 길게 하려면 올바른 솔루션만 내보내고(반환하지 않고) 계속한 다음 선택한 기준(최대, 최소, 평균 등)에 따라 최적의 솔루션을 선택합니다.
문자열에 포함된 단어의 전체 목록이 있는 경우:
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()
는 함는다반환니다합음을수▁a를 반환합니다.string의 table table apple chair cupboard
다음은 바닐라(순수) 자바스크립트가 포함된 샘플 코드(몇 가지 예를 기반으로 함)입니다.다음을 사용할 단어 베이스(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('\n');
// 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();
매혹적인 라이브러리를 사용하십시오.최선의 선택.체크아웃: 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)
병합된 단어 입력: 테이블 애플 의자 테이블 찬장
분할된 단어: ['table', 'apple', 'chair', 'table', 'cupboard']
당신은 당신의 어휘를 식별할 필요가 있습니다 - 아마도 어떤 자유 단어 목록이라도 좋습니다.
완료되면 해당 어휘를 사용하여 접미사 트리를 만들고 입력 스트림을 일치시킵니다. http://en.wikipedia.org/wiki/Suffix_tree
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]
독일어에는 기계 학습을 사용하고 몇 단어의 문자열에 꽤 잘 작동하는 CharSplit이 있습니다.
https://github.com/dtuggener/CharSplit
@miku의 사용 제안에 대한 확장.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 한 번 (단, (한신가능))2▁for의 시간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 리고건설비용그▁the용비설▁the▁of▁cost▁building를 짓는 비용.trie선취의
언급URL : https://stackoverflow.com/questions/8870261/how-to-split-text-without-spaces-into-list-of-words
'programing' 카테고리의 다른 글
| Django 템플릿 내 인덱스별 참조 목록 항목? (0) | 2023.07.17 |
|---|---|
| 참 조건(x = x ?: 1)에 대한 값을 할당하지 않고 3진수 연산자를 사용하는 이유는 무엇입니까? (0) | 2023.07.17 |
| 파이썬에서 __init__의 값을 반환하는 방법은 무엇입니까? (0) | 2023.07.17 |
| Chrome에서 Selenium WebDriver Python 바인딩 실행 (0) | 2023.07.17 |
| Oracle을 사용하여 Oracle에 연결합니다.관리되는 데이터 액세스 (0) | 2023.07.17 |