¿Cómo dividir texto sin espacios en una lista de palabras?

Entrada: "tableapplechairtablecupboard..." muchas palabras

¿Cuál sería un algoritmo eficiente para dividir dicho texto en la lista de palabras y obtener:

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

Lo primero que me viene a la mente es revisar todas las palabras posibles (comenzando con la primera letra) y encontrar la palabra más larga posible, continúe desde position=word_position+len(word)

PD:
Tenemos una lista de todas las palabras posibles.
La palabra "armario" puede ser "taza" y "tabla", seleccione la más larga.
Idioma: python, pero lo principal es el algoritmo en sí.

Un algoritmo ingenuo no dará buenos resultados cuando se aplique a datos del mundo real. Aquí hay un algoritmo de 20 líneas que explota la frecuencia relativa de palabras para brindar resultados precisos para texto de palabras reales.

(Si desea una respuesta a su pregunta original que no usa la frecuencia de palabras, debe refinar qué se entiende exactamente por "palabra más larga": ¿es mejor tener una palabra de 20 letras y diez palabras de 3 letras, o es ¿Es mejor tener cinco palabras de 10 letras? Una vez que establezca una definición precisa, solo tiene que cambiar la línea que define wordcostpara reflejar el significado deseado).

La idea

La mejor forma de proceder es modelar la distribución de la salida. Una buena primera aproximación es asumir que todas las palabras se distribuyen de forma independiente. Entonces solo necesita saber la frecuencia relativa de todas las palabras. Es razonable suponer que siguen la ley de Zipf, que es la palabra con rango n en la lista de palabras que tiene una probabilidad de aproximadamente 1 / ( n log N ) donde N es el número de palabras en el diccionario.

Una vez que haya arreglado el modelo, puede usar la programación dinámica para inferir la posición de los espacios. La oración más probable es la que maximiza el producto de la probabilidad de cada palabra individual y es fácil de calcular con programación dinámica. En lugar de usar directamente la probabilidad, usamos un costo definido como el logaritmo de la inversa de la probabilidad para evitar desbordamientos.

El 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 puedes usar con

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

Los resultados

Estoy usando este diccionario rápido y sucio de 125k palabras que reuní a partir de un pequeño subconjunto de Wikipedia.

Antes: pulgarverdemanzanaactivaasignaciónsemanalmetafora.
Después: pulgar manzana verde asignación activa metáfora semanal.

Antes: hay una gran cantidad de información de texto de los comentarios de la gente que se separa de html, pero hay o personajes delimitados en ellos, por ejemplo, pulgar verde manzana, asignación activa semanal, metafórica, aparentemente, el pulgar verde manzana se muestra en la cadena de caracteres, por lo que tiene un diccionario rápido más grande para consultar si la expresión es la siguiente.

Después: hay una gran cantidad de información de texto de los comentarios de las personas que se analiza de html pero no hay caracteres delimitados en ellos, por ejemplo, manzana verde pulgar asignación activa semanal metáfora aparentemente hay pulgar manzana verde, etc.en la cadena también tengo un diccionario grande para pregunte si la palabra es razonable entonces cuál es la forma más rápida de extracción gracias mucho.

Antes: era una noche oscura y tormentosala lluvia caía en el sexo actual en intervalos ocasionales cuando se controlaba por una violenta ráfaga de viento que barría las calles para estar en el interior de nuestros cenelos alborotando a lo largo de las azoteas y agitando ferozmente las llamas de las lámparas que luchaban contra la lucha.

Después: era una noche oscura y tormentosa, la lluvia caía a torrentes, excepto a intervalos ocasionales, cuando fue frenada por una violenta ráfaga de viento que barrió las calles, porque es en Londres donde nuestra escena yace traqueteando a lo largo de los tejados y agitando ferozmente la llama escasa de las lámparas que luchaban contra la oscuridad.

Como puede ver, es esencialmente impecable. La parte más importante es asegurarse de que su lista de palabras haya sido entrenada en un corpus similar al que realmente encontrará, de lo contrario, los resultados serán muy malos.

Mejoramiento

La implementación consume una cantidad lineal de tiempo y memoria, por lo que es razonablemente eficiente. Si necesita más aceleraciones, puede crear un árbol de sufijos a partir de la lista de palabras para reducir el tamaño del conjunto de candidatos.

Si necesita procesar una cadena consecutiva muy grande, sería razonable dividir la cadena para evitar el uso excesivo de memoria. Por ejemplo, puede procesar el texto en bloques de 10000 caracteres más un margen de 1000 caracteres a cada lado para evitar efectos de límites. Esto mantendrá el uso de la memoria al mínimo y es casi seguro que no tendrá ningún efecto en la calidad.

Basado en el excelente trabajo en la respuesta principal , he creado un pippaquete para un uso fácil.

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

Para instalar, ejecute pip install wordninja.

Las únicas diferencias son menores. Esto devuelve un en listlugar de a str, funciona python3, incluye la lista de palabras y se divide correctamente incluso si hay caracteres no alfa (como guiones bajos, guiones, etc.).

¡Gracias de nuevo a Generic Human!

https://github.com/keredson/wordninja

Aquí hay una solución mediante la búsqueda 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'])))

rendimientos

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

Usando una estructura de datos trie , que contiene la lista de palabras posibles, no sería demasiado complicado hacer lo siguiente:

1. Puntero avanzado (en la cadena concatenada)
2. Busque y almacene el nodo correspondiente en el trie
3. Si el nodo trie tiene hijos (por ejemplo, hay palabras más largas), vaya al 1.
4. Si el nodo alcanzado no tiene hijos, se produjo una coincidencia de palabra más larga; agregue la palabra (almacenada en el nodo o simplemente concatenada durante el recorrido del ensayo) a la lista de resultados, restablezca el puntero en el ensayo (o restablezca la referencia) y comience de nuevo

La solución de Unutbu estuvo bastante cerca, pero encuentro el código difícil de leer y no produjo el resultado esperado. La solución de Generic Human tiene el inconveniente de que necesita frecuencias de palabras. No es apropiado para todos los casos de uso.

Aquí hay una solución simple usando un algoritmo Divide and Conquer .

1. Intenta minimizar el número de palabras que Eg find_words('cupboard')devolverá en ['cupboard']lugar de ['cup', 'board'](asumiendo que cupboard, cupy boardestán en el diccionario)
2. La solución óptima no es única , la implementación a continuación devuelve una solución. find_words('charactersin')podría volver ['characters', 'in']o tal vez volverá ['character', 'sin'](como se ve a continuación). Puede modificar fácilmente el algoritmo para devolver todas las soluciones óptimas.
3. En esta implementación se memorizan las soluciones para que se ejecute en un tiempo razonable.

El 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

Esto tomará alrededor de 5 segundos en mi máquina de 3GHz:

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

las reis masas de información de texto de los comentarios de las personas que se analizan desde html pero no hay un carácter delimitado en ellos, por ejemplo, pulgar manzana verde asignación activa metáfora semanal aparentemente hay pulgar manzana verde, etc.en la cadena también tengo un diccionario grande para consultar si la palabra es razonable, ¿cuál es la forma más rápida de extracción?

La respuesta de https://stackoverflow.com/users/1515832/generic-human es excelente. Pero la mejor implementación de esto que he visto nunca fue escrita por el propio Peter Norvig en su libro 'Beautiful Data'.

Antes de pegar su código, permítanme explicarme por qué el método de Norvig es más preciso (aunque un poco más lento y más largo en términos de código).

1) Los datos son un poco mejores, tanto en términos de tamaño como en términos de precisión (usa un recuento de palabras en lugar de una clasificación simple) 2) Más importante aún, es la lógica detrás de los n-gramas lo que realmente hace que el enfoque sea tan preciso .

El ejemplo que proporciona en su libro es el problema de dividir una cuerda 'sentada'. Ahora, un método de división de cadenas que no es bigrama consideraría p ('sit') * p ('down'), y si es menor que p ('sitdown'), que será el caso con bastante frecuencia, NO se dividirá , pero nos gustaría que lo hiciera (la mayor parte del tiempo).

Sin embargo, cuando tiene el modelo de bigrama, puede valorar p ('sentarse') como un bigrama frente a p ('sentarse') y el primero gana. Básicamente, si no usa bigrams, trata la probabilidad de las palabras que está dividiendo como independientes, lo cual no es el caso, es más probable que algunas palabras aparezcan una tras otra. Desafortunadamente, esas son también las palabras que a menudo se juntan en muchos casos y confunden al divisor.

Aquí está el enlace a los datos (son datos para 3 problemas separados y la segmentación es solo uno. Lea el capítulo para obtener más detalles): http://norvig.com/ngrams/

y aquí está el enlace al código: http://norvig.com/ngrams/ngrams.py

Estos enlaces han estado activos por un tiempo, pero copiaré y pegaré la parte de segmentación del código aquí de todos modos.

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 

Aquí está la respuesta aceptada traducida a JavaScript (requiere node.js y el archivo "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();
}

Si precompila la lista de palabras en un DFA (que será muy lento), entonces el tiempo que lleva hacer coincidir una entrada será proporcional a la longitud de la cadena (de hecho, solo un poco más lento que simplemente iterar sobre la cadena).

Esta es efectivamente una versión más general del algoritmo trie que se mencionó anteriormente. Solo lo menciono en forma completa: hasta el momento, no existe una implementación de DFA que pueda usar. RE2 funcionaría, pero no sé si los enlaces de Python le permiten ajustar el tamaño que permite que sea un DFA antes de que simplemente elimine los datos compilados de DFA y realice la búsqueda NFA.

Parece que un retroceso bastante mundano servirá. Empiece por el principio de la cuerda. Escanee a la derecha hasta que tenga una palabra. Luego, llame a la función en el resto de la cadena. La función devuelve "falso" si escanea completamente hacia la derecha sin reconocer una palabra. De lo contrario, devuelve la palabra que encontró y la lista de palabras devuelta por la llamada recursiva.

Ejemplo: "tableapple". Busca "tabulación", luego "salto", pero ninguna palabra en "ple". Ninguna otra palabra en "salto". Busca "tabla", luego "aplicación". "le" ni una palabra, así que intenta Apple, reconoce, vuelve.

Para obtener el mayor tiempo posible, continúe, solo emitiendo (en lugar de devolver) las soluciones correctas; luego, elija el óptimo según cualquier criterio que elija (maxmax, minmax, average, etc.)

Basado en la solución de unutbu, he implementado una versión de 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"

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

Entrada: "tableprechaun"

Salida: [tab, leprechaun]

Para el idioma alemán, existe CharSplit, que utiliza el aprendizaje automático y funciona bastante bien para cadenas de unas pocas palabras.

https://github.com/dtuggener/CharSplit

Ampliando la sugerencia de @ miku de usar a Trie, un append-only Triees relativamente sencillo de implementar en 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

Luego podemos construir un Triediccionario basado en un conjunto de palabras:

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

Lo que producirá un árbol que se ve así ( *indica el comienzo o el final de una palabra):

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

Podemos incorporar esto en una solución combinándolo con una heurística sobre cómo elegir palabras. Por ejemplo, podemos preferir palabras más largas a palabras más cortas:

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 esta función así:

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

Porque mantenemos nuestra posición en la Triemedida que la búsqueda por más tiempo y las palabras más largas, se recorre el triemáximo una vez por cada posible solución (en lugar de 2veces para peanut: pea, peanut). El cortocircuito final nos salva de caminar como carbón a través de la cuerda en el peor de los casos.

El resultado final es solo un puñado de inspecciones:

'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

Una ventaja de esta solución es el hecho de que sabe muy rápidamente si existen palabras más largas con un prefijo determinado, lo que evita la necesidad de probar exhaustivamente las combinaciones de secuencias en un diccionario. También hace que llegar a una unsolvablerespuesta sea comparativamente más económico que otras implementaciones.

Las desventajas de esta solución son una gran huella de memoria para el triey el costo de construcción trieinicial.

Si tiene una lista exhaustiva de las palabras contenidas en la cadena:

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

Usar la comprensión de listas para iterar sobre la lista para localizar la palabra y cuántas veces 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()

La función devuelve una stringsalida de palabras en el orden de la lista.table table apple chair cupboard

Muchas gracias por la ayuda en https://github.com/keredson/wordninja/

Una pequeña contribución de lo mismo en Java de mi parte.

El método público splitContiguousWordspodría integrarse con los otros 2 métodos de la clase que tiene ninja_words.txt en el mismo directorio (o modificarse según la elección del codificador). Y el método splitContiguousWordspodría usarse para ese 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;
}

Esto ayudará

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

Necesita identificar su vocabulario, tal vez cualquier lista de palabras gratuita sea suficiente.

Una vez hecho esto, use ese vocabulario para construir un árbol de sufijos y haga coincidir su flujo de entrada con eso: http://en.wikipedia.org/wiki/Suffix_tree