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

Entrada: "tableapplechairtablecupboard..." muchas palabras

¿Qué 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 repasar todas las palabras posibles (comenzando con la primera letra) y encontrar la palabra más larga posible, continuar desde position=word_position+len(word)

PD
Tenemos una lista de todas las palabras posibles.
La palabra “armario” puede ser “taza” y “tablero”, seleccione el más largo.
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 las palabras para obtener resultados precisos para el texto de palabras reales.

(Si desea una respuesta a su pregunta original que no usa la frecuencia de palabras, necesita refinar lo que significa exactamente “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 se establezca una definición precisa, solo tiene que cambiar la línea que define wordcost para reflejar el significado deseado.)

La idea

La mejor manera de proceder es modelar la distribución de la salida. Una buena primera aproximación es asumir que todas las palabras están distribuidas de manera independiente. Entonces solo necesitas saber la frecuencia relativa de todas las palabras. Es razonable suponer que siguen la ley de Zipf, es decir, la palabra con el rango n en la lista de palabras 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 progtwigció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 calcularla con progtwigción dinámica. En lugar de utilizar directamente la probabilidad, utilizamos un costo definido como el logaritmo del inverso 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[ik-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[ik:i]) i -= k return " ".join(reversed(out)) 

que puedes usar con

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

Los resultados

Estoy utilizando este diccionario de palabras rápidas y sucias de 125k que formé a partir de un pequeño subconjunto de Wikipedia.

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

Antes: hay una gran cantidad de información en el texto de los comentarios de la gente que muestra su contenido, pero otros grupos de caracteres son los que se encuentran en la caja de la foto.

Después: hay una gran cantidad de información de texto de los comentarios de los pueblos que se analiza desde html pero no hay caracteres delimitados en ellos, por ejemplo, la metáfora semanal de la asignación activa del pulgar de la manzana verde aparentemente hay una manzana del pulgar del pulgar, 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?

Antes: era una especie de antorcha y una tormenta, una noche, una imagen del infierno, un par de intercomunicadores ocasionales, cuando se verificaba por un acto violento del viento, que se mantenía en su lugar, por ejemplo, en un par de cosas, por ejemplo, por ejemplo.

Después: fue una noche oscura y tormentosa, la lluvia cayó en torrentes, excepto en intervalos ocasionales, cuando fue controlada por una violenta ráfaga de viento que barrió las calles, ya que es en Londres donde nuestra escena vibra a lo largo de las azoteas y agita ferozmente la Escasa llama de las lámparas que luchaban contra la oscuridad.

Como pueden ver, es esencialmente impecable. La parte más importante es asegurarse de que su lista de palabras haya sido entrenada para 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 la memoria. Por ejemplo, podría procesar el texto en bloques de 10000 caracteres más un margen de 1000 caracteres en cada lado para evitar efectos de contorno. Esto mantendrá el uso de memoria al mínimo y casi seguramente no tendrá ningún efecto en la calidad.

Basándome en el excelente trabajo en la respuesta principal , he creado un paquete pip 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 una list lugar de una str , funciona en 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 Genérico Humano!

https://github.com/keredson/wordninja

Aquí está la solución utilizando 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'] 

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

  1. Puntero de avance (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 a 1.
  4. Si el nodo alcanzado no tiene hijos, ocurrió una coincidencia de palabra más larga; agregue la palabra (almacenada en el nodo o solo concatenada durante el recorrido del trie) a la lista de resultados, reinicie el puntero en el trie (o reinicie la referencia) y comience de nuevo

La solución de Unutbu fue bastante cercana, pero me parece que el código es difícil de leer y no dio 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 de Dividir y Conquistar .

  1. Intenta minimizar el número de palabras, por ejemplo, find_words('cupboard') devolverá ['cupboard'] lugar de ['cup', 'board'] (asumiendo que la cupboard , la cup y el board está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 devolver ['characters', 'in'] o quizás devolverá ['character', 'sin'] (como se ve a continuación). Podría modificar fácilmente el algoritmo para devolver todas las soluciones óptimas.
  3. En esta implementación, las soluciones se memorizan para que se ejecuten 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 masas de información de texto de los comentarios de los pueblos se analizan a partir de html, pero no hay un carácter delimitado, por ejemplo, la metáfora semanal del pulgar de la manzana verde activa aparentemente hay una manzana verde del pulgar del pulgar, etc. También tengo un diccionario grande para consultar si la palabra es razonable, entonces, ¿cuál es la forma más rápida de extracción que muchas

La respuesta de https://stackoverflow.com/users/1515832/generic-human es genial. Pero la mejor implementación de esto que he visto en mi vida fue el mismo Peter Norvig en su libro ‘Beautiful Data’.

Antes de pegar su código, permítame explicar 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 de precisión (usa un recuento de palabras en lugar de una simple clasificación) 2) Lo más importante es que la lógica detrás de n-grams es lo que realmente hace que el enfoque sea tan preciso. .

El ejemplo que proporciona en su libro es el problema de dividir una cadena ‘sitdown’. Ahora, un método no de bigtwig de división de cadenas consideraría p (‘sentarse’) * p (‘abajo’), y si es menor que la p (‘sitdown’), que será el caso con bastante frecuencia, NO se dividirá eso, pero nos gustaría (la mayor parte del tiempo).

Sin embargo, cuando tienes el modelo de bigtwig, puedes valorar p (‘sentarte’) como bigram vs p (‘sitdown’) y el primero gana. Básicamente, si no usas bigtwigs, trata la probabilidad de que las palabras que estás dividiendo sean independientes, lo que 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 están pegadas entre sí en muchos casos y confunden al partidor.

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 funcionando un tiempo, pero de todos modos copiaré y pegaré la parte de segmentación del código.

 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=''): "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 

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

Esta es efectivamente una versión más general del algoritmo trie que se mencionó anteriormente. Solo lo menciono para que no tenga terminaciones completas: hasta ahora, no hay una implementación de DFA que pueda usar. RE2 funcionaría, pero no sé si los enlaces de Python te permiten ajustar el tamaño que permites que sea un DFA antes de tirar los datos comstackdos de DFA y hacer una búsqueda NFA.

Parece que bastará con hacer retroceso bastante mundano. Comenzar por el principio de la cadena. Escanea a la derecha hasta que tengas una palabra. Luego, llama a la función en el rest de la cadena. La función devuelve “falso” si se escanea hacia la derecha sin reconocer una palabra. De lo contrario, devuelve la palabra que encontró y la lista de palabras devueltas por la llamada recursiva.

Ejemplo: “Tableapple”. Busca “pestaña”, luego “salto”, pero ninguna palabra en “ple”. Ninguna otra palabra en “salto”. Encuentra “tabla”, luego “aplicación”. “le” no es una palabra, por lo que trata de apple, reconoce, devuelve.

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

Basado en la solución de unutbu, he implementado una versión de Java:

 private static List splitWordWithoutSpaces(String instring, String suffix) { if(isAWord(instring)) { if(suffix.length() > 0) { List rest = splitWordWithoutSpaces(suffix, ""); if(rest.size() > 0) { List solutions = new LinkedList<>(); solutions.add(instring); solutions.addAll(rest); return solutions; } } else { List 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 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, está CharSplit, que utiliza aprendizaje automático y funciona bastante bien con cadenas de pocas palabras.

https://github.com/dtuggener/CharSplit

Ampliando la sugerencia de @miku de usar un Trie , un Trie solo Trie es 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 diccionario basado en Trie partir de 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 verá así ( * indica el principio 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ándola con una heurística sobre cómo elegir palabras. Por ejemplo, podemos preferir palabras más largas sobre 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" ] 

Debido a que mantenemos nuestra posición en el Trie mientras buscamos palabras cada vez más largas, atravesamos el trie a lo sumo una vez por posible solución (en lugar de 2 veces para peanut : pea , peanut ). El cortocircuito final nos evita que caminemos 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 dado, lo que evita la necesidad de probar exhaustivamente las combinaciones de secuencias con un diccionario. También hace que llegar a una respuesta unsolvable solución sea relativamente barato para otras implementaciones.

Las desventajas de esta solución son una gran huella de memoria para el trie y el costo de construir el trie por adelantado.

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

Necesitas identificar tu vocabulario, tal vez cualquier lista de palabras gratuitas 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