Jak podzielić tekst bez spacji na listę słów?

Wejście: "tableapplechairtablecupboard..." wiele słów

Jaki byłby skuteczny algorytm do podzielenia takiego tekstu na listę słów i uzyskania:

Wynik: ["table", "apple", "chair", "table", ["cupboard", ["cup", "board"]], ...]

Pierwszą rzeczą, która przychodzi na myśl, jest przejście przez wszystkie możliwe słowa (zaczynając od pierwszej litery) i znalezienie najdłuższego możliwego słowa, kontynuuj od position=word_position+len(word)

PS
Mamy listę wszystkich możliwych słów.
Wyrazem „szafka” może być „filiżanka” i „deska”, wybierz najdłuższe.
Język: python, ale najważniejszy jest sam algorytm.

Naiwny algorytm nie da dobrych wyników, gdy zostanie zastosowany do rzeczywistych danych. Oto 20-liniowy algorytm, który wykorzystuje względną częstotliwość słów w celu uzyskania dokładnych wyników dla tekstu rzeczywistego.

(Jeśli chcesz odpowiedzieć na swoje pierwotne pytanie, które nie używa częstotliwości słów, musisz sprecyzować, co dokładnie oznacza „najdłuższe słowo”: czy lepiej mieć 20-literowe słowo i dziesięć 3-literowych, czy też lepiej mieć pięć 10-literowych słów? Gdy już zdecydujesz się na precyzyjną definicję, wystarczy zmienić definicję linii, wordcostaby odzwierciedlić zamierzone znaczenie.)

Pomysł

Najlepszym sposobem postępowania jest modelowanie rozkładu wyników. Dobrym pierwszym przybliżeniem jest założenie, że wszystkie słowa są rozmieszczone niezależnie. Wtedy wystarczy znać względną częstotliwość wszystkich słów. Można założyć, że są zgodne z prawem Zipfa, to znaczy słowo o randze n na liście słów ma prawdopodobieństwo około 1 / ( n log N ), gdzie N to liczba słów w słowniku.

Po ustaleniu modelu można użyć programowania dynamicznego, aby wywnioskować położenie przestrzeni. Najbardziej prawdopodobne zdanie to takie, które maksymalizuje iloczyn prawdopodobieństwa każdego pojedynczego słowa i można je łatwo obliczyć za pomocą programowania dynamicznego. Zamiast bezpośrednio korzystać z prawdopodobieństwa, używamy kosztu zdefiniowanego jako logarytm odwrotności prawdopodobieństwa, aby uniknąć przepełnienia.

Kod

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))

z którym możesz korzystać

s = 'thumbgreenappleactiveassignmentweeklymetaphor'
print(infer_spaces(s))

Wyniki

Używam tego szybkiego i nieczytelnego słownika na 125 000 słów, który stworzyłem na podstawie niewielkiego podzbioru Wikipedii.

Przed: kciukzielonyappleaktywne zadanieweeklymetafora.
Po: kciuk zielone jabłko aktywne zadanie cotygodniowa metafora.

Przed: istnieje wiele informacji tekstowych narodów, które zostały wyodrębnione z htmlbuttherearen od ograniczonych znaków w nich przed badaniem grubozielonych jabłek, aktywnych zadań tygodniowo, metaforę, wydaje się, że istnieje wiele zielonych jabłek, które można znaleźć w jednym z nich, tak więc trzeba było wyskoczyć na pytanie, niezależnie od tego, czy jest to rozsądny przedmiot w słowniczku.

Po: jest mnóstwo informacji tekstowych komentarzy ludzi, które są analizowane z html, ale nie ma w nich znaków rozdzielonych, na przykład kciuk zielone jabłko aktywne przypisanie cotygodniowa metafora najwyraźniej jest kciuk zielone jabłko itp. W ciągu mam również duży słownik do zapytaj, czy słowo jest rozsądne, więc jaki jest najszybszy sposób wyodrębnienia thx dużo.

Przedtem: w nocy, w nocy, w pociągu spotykał się i burzy, akceptowano sporadyczne odstępy czasu, gdy był on kontrolowany przez gwałtowny podmuch wiatru, który trzepotał ulicami wywołującymi zapalenie, gdy ten cudowny widok wywoływał brzęczenie w pobliżu domków i gwałtowniej potrząsając potwornym ogniem.

Potem: była ciemna i burzowa noc, deszcz padał ulewami, z wyjątkiem sporadycznych okresów, kiedy był zatrzymywany przez gwałtowny podmuch wiatru, który przetoczył się ulicami, ponieważ to w Londynie nasza scena grzechota wzdłuż dachów i gwałtownie wstrząsa skąpe płomienie lamp, które walczyły z ciemnością.

Jak widać, jest w zasadzie bezbłędny. Najważniejszą częścią jest upewnienie się, że twoja lista słów została przeszkolona w korpusie podobnym do tego, z czym faktycznie się spotkasz, w przeciwnym razie wyniki będą bardzo złe.

Optymalizacja

Implementacja zużywa liniowo ilość czasu i pamięci, więc jest dość wydajna. Jeśli potrzebujesz dalszego przyspieszenia, możesz zbudować drzewo sufiksów z listy słów, aby zmniejszyć rozmiar zestawu kandydatów.

Jeśli chcesz przetworzyć bardzo duży ciąg ciągów kolejnych, rozsądne byłoby podzielenie ciągu, aby uniknąć nadmiernego wykorzystania pamięci. Na przykład, możesz przetworzyć tekst w blokach po 10000 znaków plus margines 1000 znaków po obu stronach, aby uniknąć efektów brzegowych. Pozwoli to zminimalizować użycie pamięci i prawie na pewno nie będzie miało wpływu na jakość.

Opierając się na doskonałej pracy w górnej odpowiedzi , stworzyłem pippakiet do łatwego użycia.

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

Aby zainstalować, uruchom pip install wordninja.

Jedyne różnice są niewielkie. Zwraca a listzamiast a str, działa w programie python3, zawiera listę słów i poprawnie dzieli, nawet jeśli istnieją znaki inne niż alfa (takie jak podkreślenia, myślniki itp.).

Jeszcze raz dziękuję Generic Human!

https://github.com/keredson/wordninja

Oto rozwiązanie wykorzystujące wyszukiwanie rekurencyjne:

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'])))

plony

['table', 'apple', 'chair', 'table', 'cupboard']
['tab', 'leprechaun']

Używając trie struktury danych , która zawiera listę możliwych słów, nie byłoby zbyt skomplikowane wykonanie następujących czynności:

1. Wskaźnik zaawansowany (w połączonym ciągu)
2. Wyszukaj i zapisz odpowiedni węzeł w trie
3. Jeśli węzeł trie ma dzieci (np. Są dłuższe słowa), przejdź do 1.
4. Jeśli osiągnięty węzeł nie ma dzieci, następuje dopasowanie najdłuższego słowa; dodaj słowo (zapisane w węźle lub po prostu połączone podczas przechodzenia przez próbę) do listy wyników, zresetuj wskaźnik w trie (lub zresetuj odniesienie) i zacznij od nowa

Rozwiązanie Unutbu było dość bliskie, ale uważam, że kod jest trudny do odczytania i nie przyniósł oczekiwanych rezultatów. Rozwiązanie Generic Human ma tę wadę, że wymaga częstotliwości słów. Nie nadaje się do wszystkich przypadków użycia.

Oto proste rozwiązanie wykorzystujące algorytm Divide and Conquer .

1. Stara się zminimalizować liczbę słów Np find_words('cupboard')powróci ['cupboard']zamiast ['cup', 'board'](zakładając, że cupboard, cupi boardsą w dictionnary)
2. Rozwiązaniem optymalnym jest nie wyjątkowy , realizacja poniżej zwrotów rozwiązanie. może powrócić, a może wróci (jak widać poniżej). Możesz dość łatwo zmodyfikować algorytm, aby zwrócić wszystkie optymalne rozwiązania.find_words('charactersin')['characters', 'in']['character', 'sin']
3. W tej implementacji rozwiązania są zapamiętywane, aby działały w rozsądnym czasie.

Kod:

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

Zajmie to około 5 sekund na moim komputerze 3GHz:

result = find_words("thereismassesoftextinformationofpeoplescommentswhichisparsedfromhtmlbuttherearenodelimitedcharactersinthemforexamplethumbgreenappleactiveassignmentweeklymetaphorapparentlytherearethumbgreenappleetcinthestringialsohavealargedictionarytoquerywhetherthewordisreasonablesowhatsthefastestwayofextractionthxalot")
assert(result is not None)
print ' '.join(result)

mnóstwo informacji tekstowych komentarzy ludzi, które są analizowane z html, ale nie ma w nich rozgraniczonych znaków, na przykład kciuk zielone jabłko aktywne przypisanie cotygodniowa metafora najwyraźniej jest kciuk zielone jabłko itp. w ciągu mam również duży słownik do sprawdzania, czy słowo jest rozsądne, więc jaki jest najszybszy sposób ekstrakcji thxa dużo

Odpowiedź https://stackoverflow.com/users/1515832/generic-human jest świetna. Ale najlepszą implementacją tego, jaką kiedykolwiek widziałem, był sam Peter Norvig w swojej książce „Beautiful Data”.

Zanim wkleię jego kod, pozwolę sobie wyjaśnić, dlaczego metoda Norviga jest dokładniejsza (choć trochę wolniejsza i dłuższa pod względem kodu).

1) Dane są nieco lepsze - zarówno pod względem wielkości, jak i precyzji (używa liczby słów zamiast prostego rankingu) 2) Co ważniejsze, to logika stojąca za n-gramami naprawdę sprawia, że ​​podejście jest tak dokładne .

Przykładem, który podaje w swojej książce, jest problem rozszczepienia struny „sitdown”. Teraz nie-bigramowa metoda podziału ciągów uwzględniłaby p ('sit') * p ('down'), a jeśli to mniej niż p ('sitdown') - co będzie miało miejsce dość często - NIE zostanie podzielone to, ale chcielibyśmy, żeby tak było (przez większość czasu).

Jednak gdy masz model bigramu, możesz wycenić p ('siadaj') jako bigram vs p ('siad') i ten pierwszy wygrywa. Zasadniczo, jeśli nie używasz bigramów, traktuje prawdopodobieństwo podzielenia słów jako niezależne, co nie jest prawdą, niektóre słowa częściej pojawiają się jedno po drugim. Niestety są to również słowa, które często są sklejane ze sobą w wielu przypadkach i mylą rozdzielacz.

Oto link do danych (są to dane dla 3 oddzielnych problemów, a segmentacja to tylko jeden. Przeczytaj rozdział po szczegóły): http://norvig.com/ngrams/

a oto link do kodu: http://norvig.com/ngrams/ngrams.py

Te linki są już od jakiegoś czasu, ale i tak skopiuję tutaj część kodu z segmentacją

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 

Oto akceptowana odpowiedź przetłumaczona na JavaScript (wymaga node.js i pliku „wordninja_words.txt” z https://github.com/keredson/wordninja ):

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();
}

Jeśli prekompilujesz listę słów do DFA (co będzie bardzo powolne), to czas potrzebny na dopasowanie danych wejściowych będzie proporcjonalny do długości ciągu (w rzeczywistości tylko trochę wolniej niż tylko iterowanie po ciągu).

W rzeczywistości jest to bardziej ogólna wersja algorytmu trie, o którym wspomniano wcześniej. Wspominam o tym tylko jako kompletnie - na razie nie ma implementacji DFA, której możesz po prostu użyć. RE2 zadziałałoby, ale nie wiem, czy powiązania Pythona pozwolą ci dostroić, jak duży może być DFA, zanim po prostu wyrzuci skompilowane dane DFA i przeszuka NFA.

Wygląda na to, że wystarczy dość przyziemne cofanie się. Zacznij od początku sznurka. Skanuj w prawo, aż znajdziesz słowo. Następnie wywołaj funkcję na pozostałej części ciągu. Funkcja zwraca wartość „false”, jeśli skanuje całą drogę w prawo bez rozpoznawania słowa. W przeciwnym razie zwraca znalezione słowo i listę słów zwróconych przez wywołanie rekurencyjne.

Przykład: „tableapple”. Znajduje „tab”, a następnie „skok”, ale nie zawiera słowa „ple”. Żadnego innego słowa w „skoku”. Znajduje „tabelę”, a następnie „aplikację”. „le” nie jest słowem, więc próbuje apple, rozpoznaje, zwraca.

Aby uzyskać jak najdłuższy czas, kontynuuj, emitując (zamiast zwracać) tylko poprawne rozwiązania; następnie wybierz optymalny według dowolnego kryterium (maxmax, minmax, Average, itp.)

W oparciu o rozwiązanie unutbu zaimplementowałem wersję 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;
}

Wejście: "tableapplechairtablecupboard"

Wynik: [table, apple, chair, table, cupboard]

Wejście: "tableprechaun"

Wynik: [tab, leprechaun]

W przypadku języka niemieckiego istnieje CharSplit, który wykorzystuje uczenie maszynowe i działa całkiem nieźle w przypadku ciągów kilku słów.

https://github.com/dtuggener/CharSplit

Rozwijając sugestię @ miku dotyczącą użycia a Trie, użycie tylko dopisywania Triejest stosunkowo proste do zaimplementowania w 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

Następnie możemy zbudować Triesłownik oparty na zestawie słów:

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

Który utworzy drzewo, które wygląda tak ( *wskazuje początek lub koniec słowa):

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

Możemy uwzględnić to w rozwiązaniu, łącząc je z heurystyką dotyczącą doboru słów. Na przykład możemy preferować dłuższe słowa od krótszych:

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 []

Możemy użyć tej funkcji w następujący sposób:

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

Ponieważ utrzymujemy naszą pozycję w Triejak szukamy dłuższe słowy, przejdziecie trieco najwyżej raz na możliwe rozwiązanie (zamiast 2czasach dla peanut: pea, peanut). Końcowe zwarcie ratuje nas przed chodzeniem zwęźle przez strunę w najgorszym przypadku.

Końcowy wynik to tylko kilka inspekcji:

'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

Zaletą tego rozwiązania jest fakt, że bardzo szybko wiesz, czy istnieją dłuższe słowa z danym przedrostkiem, co pozwala uniknąć wyczerpującego testowania kombinacji sekwencji w słowniku. Sprawia również, że dotarcie do plikuunsolvable odpowiedzi jest stosunkowo tanie w porównaniu z innymi wdrożeniami.

Wadami tego rozwiązania są duże zużycie pamięci triei koszt budowy z triegóry.

Jeśli masz wyczerpującą listę słów zawartych w ciągu:

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

Korzystanie z funkcji list złożonych do iteracji po liście w celu zlokalizowania słowa i tego, ile razy występuje.

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()

Funkcja zwraca stringwynik słów w kolejności na liścietable table apple chair cupboard

Wielkie dzięki za pomoc w https://github.com/keredson/wordninja/

Mały wkład tego samego w Javie z mojej strony.

Metoda publiczna splitContiguousWordsmoże być osadzona z pozostałymi 2 metodami w klasie mającej ninja_words.txt w tym samym katalogu (lub zmodyfikowane zgodnie z wyborem kodera). I metoda splitContiguousWordsmoże być wykorzystana do tego celu.

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;
}

To pomoże

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

Musisz zidentyfikować swoje słownictwo - być może wystarczy dowolna lista słów.

Po zakończeniu użyj tego słownictwa, aby zbudować drzewo sufiksów i dopasuj strumień danych wejściowych do tego: http://en.wikipedia.org/wiki/Suffix_tree