Bienvenido a proyecto on line, aquí hallarás la respuesta de lo que buscabas.
Solución:
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 wordcost para reflejar el significado pretendido.)
La idea
La mejor forma de proceder es modelo 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, esa es la palabra con rango norte en la lista de palabras tiene una probabilidad de aproximadamente 1 / (norte Iniciar sesión norte) dónde norte es el número de palabras del 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 personascomcomentarios que se separan de html, pero no hay personajes delimitados en ellos, por ejemplo, pulgar verde manzanaasignación activa semanalmetafo rap, aparentemente, hay pulgar verde manzana en la cadena de caracteres, por lo que tiene una gran pregunta médica sobre si la palabra es más rápida.
Después: hay una gran cantidad de información de texto de los comentarios de la gente que se analiza de html pero no hay caracteres delimitados en ellos, por ejemplo, pulgar manzana verde asignación activa metáfora semanal aparentemente hay pulgar manzana verde, etc.en el string 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?
Antes: Fue oscuro y tormentosonochela lluvia cayó en el sexo actual en intervalos ocasionales cuando fue controlado por una ráfaga de viento violenta que barrió las calles para estar en el interior de que nuestros cenelos pelean por los tejados de las casas y agitan ferozmente la llama ardiente de las lámparas que luchan contra la oscuridad.
Después: Era una noche oscura y tormentosa, la lluvia caía a torrentes, excepto en 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 escasa llama. de las lámparas que lucharon 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 gran cantidad consecutiva string Sería razonable dividir el string para evitar el uso excesivo de memoria. Por ejemplo, podría 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 casi con certeza no tendrá ningún efecto en la calidad.
Basado en el excelente trabajo en la respuesta principal, he creado un pip paquete 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 list preferible a 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 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']
Si eres capaz, tienes el poder dejar una división acerca de qué le añadirías a este post.