Como dividir o texto sem espaços em uma lista de palavras?

Entrada: "tableapplechairtablecupboard..." muitas palavras

Qual seria um algoritmo eficiente para dividir esse texto na lista de palavras e obter:

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

A primeira coisa que vem à mente é percorrer todas as palavras possíveis (começando com a primeira letra) e encontrar a palavra mais longa possível, continuar de position=word_position+len(word)

PS
Temos uma lista de todas as palavras possíveis.
A palavra "armário" pode ser "xícara" e "tábua", selecione a mais longa.
Linguagem: python, mas o principal é o próprio algoritmo.

Um algoritmo ingênuo não dará bons resultados quando aplicado a dados do mundo real. Aqui está um algoritmo de 20 linhas que explora a frequência relativa de palavras para fornecer resultados precisos para texto de palavras reais.

(Se você quiser uma resposta à sua pergunta original que não use a frequência de palavras, você precisa refinar o que exatamente significa "palavra mais longa": é melhor ter uma palavra de 20 letras e dez palavras de 3 letras, ou é é melhor ter cinco palavras de 10 letras? Depois de estabelecer uma definição precisa, você só precisa alterar a definição de linha wordcost para refletir o significado pretendido.)

A ideia

A melhor maneira de proceder é modelar a distribuição da saída. Uma boa primeira aproximação é assumir que todas as palavras são distribuídas independentemente. Então você só precisa saber a frequência relativa de todas as palavras. É razoável supor que eles sigam a lei de Zipf, ou seja, a palavra com classificação n na lista de palavras tem probabilidade de aproximadamente 1 / ( n log N ), onde N é o número de palavras no dicionário.

Depois de corrigir o modelo, você pode usar a programação dinâmica para inferir a posição dos espaços. A frase mais provável é aquela que maximiza o produto da probabilidade de cada palavra individual, e é fácil computá-la com programação dinâmica. Em vez de usar diretamente a probabilidade, usamos um custo definido como o logaritmo do inverso da probabilidade para evitar overflows.

O código

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

que você pode usar com

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

Os resultados

Estou usando este dicionário rápido e sujo de 125 mil palavras que reuni de um pequeno subconjunto da Wikipedia.

Antes: thumbgreenappleactiveassignmentweeklymetaphor.
Depois: polegar maçã verde atribuição ativa metáfora semanal.

Antes: há massas de informações de texto dos comentários das pessoas que são separados de html, mas são exibidos os caracteres limitados neles para examinar se a palavra é uma ação razoável para testar se a palavra é razoável para expressar a ação.

Depois: há uma grande quantidade de informações de texto de comentários de pessoas que são analisados ​​em html, mas não há caracteres delimitados neles, por exemplo polegar maçã verde atribuição ativa semanal metáfora, aparentemente, há polegar maçã verde etc na string Eu também tenho um grande dicionário para questionar se a palavra é razoável, então qual é a maneira mais rápida de extração, muito obrigado.

Antes: era escuro e tempestuoso à noite para sentir sexo, exceto em intervalos ocasionais, quando foi verificado por uma rajada violenta de vento que varreu as ruas para a dor em menos de que nossos centésimos estão lutando ao longo das casas e agitando ferozmente a chama da bolsa contra a escuridão.

Depois: era uma noite escura e tempestuosa, a chuva caía torrencialmente, exceto em intervalos ocasionais quando era controlada por uma violenta rajada de vento que varreu as ruas, pois é em Londres que nossa cena está sacudindo ao longo dos telhados e agitando ferozmente o fraca chama das lâmpadas que lutavam contra a escuridão.

Como você pode ver, é essencialmente perfeito. A parte mais importante é certificar-se de que sua lista de palavras foi treinada para um corpus semelhante ao que você realmente encontrará, caso contrário, os resultados serão muito ruins.

Otimização

A implementação consome uma quantidade linear de tempo e memória, por isso é razoavelmente eficiente. Se precisar de mais acelerações, você pode construir uma árvore de sufixos a partir da lista de palavras para reduzir o tamanho do conjunto de candidatos.

Se você precisar processar uma string consecutiva muito grande, seria razoável dividir a string para evitar o uso excessivo de memória. Por exemplo, você pode processar o texto em blocos de 10.000 caracteres mais uma margem de 1.000 caracteres em cada lado para evitar efeitos de limite. Isso manterá o uso de memória no mínimo e quase certamente não terá efeito na qualidade.

Com base no excelente trabalho da primeira resposta , criei um pippacote para fácil uso.

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

Para instalar, execute pip install wordninja.

As únicas diferenças são pequenas. Isso retorna um em listvez de um str, ele funciona em python3, inclui a lista de palavras e se divide adequadamente, mesmo se houver caracteres não alfa (como sublinhados, travessões, etc.).

Obrigado mais uma vez a Generic Human!

https://github.com/keredson/wordninja

Aqui está a solução usando pesquisa recursiva:

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

rendimentos

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

Usando uma estrutura de dados trie , que contém a lista de palavras possíveis, não seria muito complicado fazer o seguinte:

1. Ponteiro de avanço (na string concatenada)
2. Procure e armazene o nó correspondente no trie
3. Se o nó trie tiver filhos (por exemplo, se houver palavras mais longas), vá para 1.
4. Se o nó atingido não tiver filhos, uma correspondência de palavra mais longa aconteceu; adicione a palavra (armazenada no nó ou apenas concatenada durante o trie traversal) à lista de resultados, redefina o ponteiro no trie (ou redefina a referência) e comece novamente

A solução de Unutbu foi bem próxima, mas acho o código difícil de ler e não produziu o resultado esperado. A solução da Generic Human tem a desvantagem de precisar de frequências de palavras. Não é apropriado para todos os casos de uso.

Aqui está uma solução simples usando um algoritmo Divide and Conquer .

1. Ele tenta minimizar o número de palavras que Eg find_words('cupboard')irá retornar ['cupboard']ao invés de ['cup', 'board'](assumindo que cupboard,cup e boardestão no dicionário)
2. A solução ótima não é única , a implementação abaixo retorna uma solução. find_words('charactersin')pode voltar ['characters', 'in']ou talvez volte['character', 'sin'] (como visto abaixo). Você pode facilmente modificar o algoritmo para retornar todas as soluções ideais.
3. Nesta implementação, as soluções são memorizadas para que sejam executadas em um tempo razoável.

O código:

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

Isso levará cerca de 5 segundos na minha máquina 3GHz:

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

os reis massas de informações de texto de comentários de pessoas que são analisados ​​em html, mas não há nenhum caractere delimitado por eles, por exemplo polegar maçã verde atribuição ativa semanal metáfora aparentemente há polegar maçã verde etc na string Eu também tenho um grande dicionário para verificar se a palavra é razoável, então qual é a maneira mais rápida de extração?

A resposta por https://stackoverflow.com/users/1515832/generic-human é ótima. Mas a melhor implementação disso que já vi foi escrita pelo próprio Peter Norvig em seu livro 'Beautiful Data'.

Antes de colar seu código, deixe-me explicar por que o método de Norvig é mais preciso (embora um pouco mais lento e longo em termos de código).

1) Os dados são um pouco melhores - tanto em termos de tamanho quanto em termos de precisão (ele usa uma contagem de palavras em vez de uma classificação simples) 2) Mais importante, é a lógica por trás de n-gramas que realmente torna a abordagem tão precisa .

O exemplo que ele fornece em seu livro é o problema de dividir uma string 'sitdown'. Agora, um método não bigrama de divisão de string consideraria p ('sentar') * p ('para baixo'), e se for menor que p ('sentar') - o que será o caso com bastante frequência - NÃO irá dividir , mas gostaríamos que fizesse (na maioria das vezes).

No entanto, quando você tem o modelo de bigrama, você pode avaliar p ('sentar') como um bigrama versus p ('sentar') e o anterior ganha. Basicamente, se você não usar bigramas, ele trata a probabilidade das palavras que você está dividindo como independentes, o que não é o caso, algumas palavras têm mais probabilidade de aparecer uma após a outra. Infelizmente, essas também são as palavras que costumam ficar juntas em muitos casos e confundem o divisor.

Aqui está o link para os dados (são dados para 3 problemas separados e segmentação é apenas um. Leia o capítulo para obter detalhes): http://norvig.com/ngrams/

e aqui está o link para o código: http://norvig.com/ngrams/ngrams.py

Esses links já estão no ar há algum tempo, mas vou copiar e colar a parte de segmentação do código aqui mesmo assim

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 

Aqui está a resposta aceita traduzida para JavaScript (requer node.js e o arquivo "wordninja_words.txt" de 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();
}

Se você pré-compilar a lista de palavras em um DFA (o que será muito lento), o tempo que leva para corresponder a uma entrada será proporcional ao comprimento da string (na verdade, apenas um pouco mais lento do que apenas iterar sobre a string).

Esta é efetivamente uma versão mais geral do algoritmo trie que foi mencionado anteriormente. Menciono apenas para completar - até o momento, não há nenhuma implementação do DFA que você possa usar. RE2 funcionaria, mas não sei se as ligações Python permitem que você ajuste o tamanho que permite que um DFA seja antes que ele simplesmente jogue fora os dados compilados do DFA e faça a pesquisa NFA.

Parece que um retrocesso bastante mundano bastará. Comece no início da corda. Leia direito até que você tenha uma palavra. Em seguida, chame a função no resto da string. A função retorna "falso" se varrer todo o caminho para a direita sem reconhecer uma palavra. Caso contrário, retorna a palavra encontrada e a lista de palavras retornadas pela chamada recursiva.

Exemplo: "tableapple". Encontra "tab", depois "leap", mas nenhuma palavra em "ple". Nenhuma outra palavra em "salto". Encontra "mesa", depois "app". "le" nem uma palavra, então tenta maçã, reconhece, retorna.

Para obter o maior tempo possível, continue, apenas emitindo (em vez de retornar) soluções corretas; em seguida, escolha o ideal por qualquer critério de sua escolha (maxmax, minmax, média, etc.)

Com base na solução da unutbu, implementei uma versão 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;
}

Entrada: "tableapplechairtablecupboard"

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

Entrada: "tableprechaun"

Resultado: [tab, leprechaun]

Para o idioma alemão, existe o CharSplit, que usa aprendizado de máquina e funciona muito bem com strings de poucas palavras.

https://github.com/dtuggener/CharSplit

Expandindo a sugestão de @miku para usar um Trie, um append-only Trieé relativamente simples de implementar em 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

Podemos então construir um Triedicionário baseado em um conjunto de palavras:

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

O que produzirá uma árvore semelhante a esta ( *indica o início ou o fim de uma palavra):

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

Podemos incorporar isso a uma solução combinando-o com uma heurística sobre como escolher as palavras. Por exemplo, podemos preferir palavras mais longas a palavras mais curtas:

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

Podemos usar essa função assim:

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

Porque mantemos a nossa posição no Triecomo nós procurar mais e palavras mais longas, nós percorremos a trieno máximo uma vez por solução possível (em vez de 2vezes para peanut: pea, peanut). O curto-circuito final nos salva de andar na corda bamba no pior caso.

O resultado final é apenas um punhado de inspeções:

'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

Um benefício dessa solução é o fato de que você sabe muito rapidamente se existem palavras mais longas com um determinado prefixo, o que evita a necessidade de testar exaustivamente as combinações de sequência em um dicionário. Também faz com que chegar a umunsolvable resposta comparativamente mais barata do que outras implementações.

As desvantagens desta solução são uma grande pegada de memória para o triee o custo de construção do trieinício.

Se você tiver uma lista exaustiva das palavras contidas na string:

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

Usando a compreensão de lista para iterar sobre a lista para localizar a palavra e quantas vezes ela aparece.

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 função retorna uma stringsaída de palavras na ordem da listatable table apple chair cupboard

Muito obrigado pela ajuda em https://github.com/keredson/wordninja/

Uma pequena contribuição do mesmo em Java da minha parte.

O método público splitContiguousWordspode ser incorporado com os outros 2 métodos na classe com ninja_words.txt no mesmo diretório (ou modificado de acordo com a escolha do codificador). E o método splitContiguousWordspode ser usado para esse propósito.

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

Isso vai ajudar

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

Você precisa identificar seu vocabulário - talvez qualquer lista de palavras livre sirva.

Uma vez feito isso, use esse vocabulário para construir uma árvore de sufixos e compare seu fluxo de entrada com aquele: http://en.wikipedia.org/wiki/Suffix_tree