Detecta las palabras más probables del texto sin espacios/palabras combinadas

Question

¿Existe una buena biblioteca que pueda detectar y dividir palabras de una cadena combinada?

Ejemplo:

"cdimage" -> ["cd", "image"] 
"filesaveas" -> ["file", "save", "as"] 

Answer 1

Aquí es una solución de programación dinámica (implementado como una función memoized).Dado un diccionario de palabras con sus frecuencias, divide el texto de entrada en las posiciones que dan la frase más probable general. Tendrás que encontrar una lista de palabras real, pero incluí algunas frecuencias inventadas para una prueba simple.

WORD_FREQUENCIES = { 
    'file': 0.00123, 
    'files': 0.00124, 
    'save': 0.002, 
    'ave': 0.00001, 
    'as': 0.00555 
} 

def split_text(text, word_frequencies, cache): 
    if text in cache: 
     return cache[text] 
    if not text: 
     return 1, [] 
    best_freq, best_split = 0, [] 
    for i in xrange(1, len(text) + 1): 
     word, remainder = text[:i], text[i:] 
     freq = word_frequencies.get(word, None) 
     if freq: 
      remainder_freq, remainder = split_text(
        remainder, word_frequencies, cache) 
      freq *= remainder_freq 
      if freq > best_freq: 
       best_freq = freq 
       best_split = [word] + remainder 
    cache[text] = (best_freq, best_split) 
    return cache[text] 

print split_text('filesaveas', WORD_FREQUENCIES, {}) 

--> (1.3653e-08, ['file', 'save', 'as']) 

Answer 2

No sé de cualquier biblioteca para ella, pero no debería ser difícil de implementar la funcionalidad básica.

1. Obtenga una lista de palabras, como UNIX words.
2. Rellene los contenidos de su lista de palabras en un trie.
3. Toma la cadena que quieras dividir y sigue su camino en el trie. Cada vez que llegue a una palabra válida, cree una nueva rama que busque una palabra que comience desde el punto de la cadena a la que llegó. Una vez que termine su rama actual, retroceda a la que creó, como en una primera búsqueda en profundidad.
4. Desambiguar las listas resultantes de forma manual, utilizando heurísticas o mediante un analizador de lenguaje natural.

Ejemplo:

1. Palabra: "filesaveasstring"
2. Primera palabra válida es "archivo". Intenta hacer coincidir "saveas". La primera palabra válida es "guardar". Intenta hacer coincidir "asstring". La primera palabra válida es "como". Intenta hacer coincidir "cadena". La primera palabra válida es "cadena". Emparejado hasta el final; pon el [archivo guardar como cadena] en tu lista de resultados.
3. Retroceder a la "secuencia" correspondiente - no hay otras posibilidades. Retroceda a "asstring". La primera palabra válida no visitada es "culo". Intenta hacer coincidir "tring". No hay coincidencias posibles Retroceda a "asstring". No hay coincidencias posibles Retroceda a "filesaveasstring".
4. La primera coincidencia no visitada es "archivos". Intenta emparejar "aveasstring". El primer partido es "ave". Intente hacer coincidir "asstring" (los mismos resultados que los pasos 2/3), agregue [archivos ave como cadena] a su lista de resultados y retroceda hasta el comienzo.
5. Intenta hacer coincidir "filesaveasstring". Sin partidos no visitados. Hecho.
6. Seleccione lo más probable desde [[file save as string] [files ave as string]] usando un heurístico o un analizador de lenguaje natural.

Answer 3

no sé una biblioteca que hace esto, pero no es demasiado difícil escribir si usted tiene una lista de palabras:

wordList = file('words.txt','r').read().split() 
words = set(s.lower() for s in wordList) 

def splitString(s): 
    found = [] 

    def rec(stringLeft, wordsSoFar): 
     if not stringLeft: 
      found.append(wordsSoFar) 
     for pos in xrange(1, len(stringLeft)+1): 
      if stringLeft[:pos] in words: 
       rec(stringLeft[pos:], wordsSoFar + [stringLeft[:pos]]) 

    rec(s.lower(), []) 
    return found 

Esto devolverá todas las formas posibles de dividir la cadena en las palabras dadas

Ejemplo:

>>> splitString('filesaveas') 
[['file', 'save', 'as'], ['files', 'ave', 'as']] 

Answer 4

si usted no está haciendo esto por diversión, pero es realmente haciendo algo para el trabajo, etc, mi consejo es hacer frente a este en la fuente. ¿Por qué tienes estas cuerdas combinadas así? ¿De dónde sacaste esas cuerdas? Si es posible, inserte espacios en la fuente de donde provienen esas cadenas.

Answer 5

que la gente a resolverlos como un código de imagen en su página web :)

Answer 6

Sé que esta pregunta está marcada para Python, pero necesitaba una implementación de JavaScript. Al salir de las respuestas anteriores, pensé que compartiría mi código. Parece que funciona decentemente.

function findWords(input){ 
    input = input.toLowerCase().replace(/\s/g, ""); //Strip whitespace 

    var index = 0; 
    var validWords = []; 
    for (var len = input.length; len > 0; len--){ //Go backwards as to favor longer words 
     var testWord = input.substr(index, len); 
     var dictIndex = _dictionary.indexOf(testWord.replace(/[^a-z\']/g, "")); //Remove non-letters 
     if (dictIndex != -1){ 
      validWords.push(testWord); 
      if (len == input.length){ 
       break; //We are complete 
      } 
      var nextWords = findWords(input.substr(len, input.length - len)); //Recurse 
      if (!nextWords.words.length){ //No further valid words 
       validWords.pop(); 
      } 
      validWords = validWords.concat(nextWords.words); 
      if (nextWords.complete === true){ 
       break; //Cascade complete 
      } 
     } 
    } 
    return { 
     complete:len > 0, //We broke which indicates completion 
     words:validWords 
    }; 
} 

Nota: "_dictionary" se espera que sea una matriz de palabras ordenadas por frecuencia. Estoy usando una lista de palabras del Proyecto Gutenberg.