¿Cómo se descompone un texto dado en palabras del diccionario?

Question

Esta es una pregunta de la entrevista. Supongamos que tiene una cadena text y dictionary (un conjunto de cadenas). ¿Cómo se divide text en subcadenas de modo que cada subcadena se encuentra en el dictionary.

Por ejemplo, puede desglosar "thisisatext" en ["this", "is", "a", "text"] usando /usr/share/dict/words.

Creo que dar marcha atrás puede resolver este problema (en pseudo-Java):

 
void solve(String s, Set<String> dict, List<String> solution) { 
    if (s.length == 0) 
     return 
    for each prefix of s found in dict 
     solve(s without prefix, dict, solution + prefix) 
} 

List<String> solution = new List<String>() 
solve(text, dict, solution) 

¿Tiene sentido? ¿Optimizarías el paso de buscar los prefijos en el diccionario? ¿Qué estructuras de datos recomendarías?

Answer 1

Esta solución asume la existencia de la estructura de datos Trie para el diccionario. Además, para cada nodo en Trie, asume las siguientes funciones:

1. nodo.IsWord(): Devuelve verdadero si la ruta a ese nodo es una palabra
2. node.IsChild (char x): Devuelve verdadero si existe un niño con etiqueta x
3. node.GetChild (char x): Devuelve el niño nodo con etiqueta x

Function annotate(String str, int start, int end, int root[], TrieNode node): 
i = start 
while i<=end: 
    if node.IsChild (str[i]): 
     node = node.GetChild(str[i]) 
     if node.IsWord(): 
      root[i+1] = start 
     i+=1 
    else: 
     break; 

end = len(str)-1 
root = [-1 for i in range(len(str)+1)] 
for start= 0:end: 
    if start = 0 or root[start]>=0: 
     annotate(str, start, end, root, trieRoot) 

index 0 1 2 3 4 5 6 7 8 9 10 11 
str: t h i s i s a t e x t 
root: -1 -1 -1 -1 0 -1 4 6 -1 6 -1 7 

voy a dejar la parte de usted enumere las palabras que componen la cadena por la que atraviesa la raíz inversa.

La complejidad del tiempo es O (nk) donde n es la longitud de la cadena yk es la longitud de la palabra más larga en el diccionario.

PD: Estoy asumiendo las siguientes palabras en el diccionario: this, is, a, text, ate.

Answer 2

Enfoque 1- Trie parece ser una buena opción aquí. Genera trie de las palabras en el diccionario de inglés. Este edificio es un costo de una sola vez. Después de construir trie, entonces su string se puede comparar fácilmente letra por letra. si en algún momento encuentras una hoja en el trie, puedes asumir que encontraste una palabra, agrégala a una lista & y continúa con tu recorrido. Haga la travesía hasta que haya llegado al final de su string. La lista es salida.

Complejidad del tiempo para la búsqueda - O (word_length).

Complejidad del espacio - O (charsize * word_length * no_words). Tamaño de tu diccionario.

Approach 2 - He oído hablar de Suffix Trees, nunca los he usado, pero puede ser útil aquí.

Enfoque 3 - es más pedantic & una mala alternativa. usted ya ha sugerido esto

Puede intentar al revés. Ejecutar a través del dict es verificar la coincidencia de subcuerda. Aquí estoy asumiendo que las claves en dict son words del diccionario de inglés /usr/share/dict/words. Así pseudo código se ve algo como esto -

(list) splitIntoWords(String str, dict d) 
{ 
    words = [] 
    for (word in d) 
    { 
     if word in str 
      words.append(word); 
    } 
    return words; 
} 

Complejidad - O (n) que se ejecuta a través de todo dict + O (1) para la subcadena coincidente.

espacio - el peor caso de O (n) si len(words) == len(dict)

Como otros han señalado, esto requiere dar marcha atrás.

Answer 3

Hay una valoración crítica muy completo para la solución a este problema en este blog post.

La idea básica es sólo para memoize la función que has escrito y que tendrá un O (n^2) el tiempo, O (n) algoritmo espacial.

Answer 4

Puede resolver este problema usando Dynamic Programming y Hashing.

Calcula el hash de cada palabra en el diccionario. Use la función hash que más le guste. Yo usaría algo como (a1 * B^(n - 1) + a2 * B^(n - 2) + ... + an * B^0)% P, donde a1a2 ... an es una cadena, n es la longitud de la cuerda, B es la base del polinomio y P es un número primo grande. Si tiene el valor hash de una cadena a1a2 ... an, puede calcular el valor hash de la cadena a1a2 ... ana (n + 1) en tiempo constante: (hashValue (a1a2 ... an) * B + a (n + 1))% P.

La complejidad de esta parte es O (N * M), donde N es el número de palabras en el diccionario y M es la longitud de la palabra más larga en el diccionario.

continuación, utilizar una función DP como esto:

bool vis[LENGHT_OF_STRING]; 
    bool go(char str[], int length, int position) 
    { 
     int i; 

     // You found a set of words that can solve your task. 
     if (position == length) { 
      return true; 
     } 

     // You already have visited this position. You haven't had luck before, and obviously you won't have luck this time. 
     if (vis[position]) { 
     return false; 
     } 
     // Mark this position as visited. 
     vis[position] = true; 

     // A possible improvement is to stop this loop when the length of substring(position, i) is greater than the length of the longest word in the dictionary. 
     for (i = position; position < length; i++) { 
     // Calculate the hash value of the substring str(position, i); 
     if (hashValue is in dict) { 
      // You can partition the substring str(i + 1, length) in a set of words in the dictionary. 
      if (go(i + 1)) { 
       // Use the corresponding word for hashValue in the given position and return true because you found a partition for the substring str(position, length). 
       return true; 
      } 
     } 
     } 

     return false; 
    } 

La complejidad de este algoritmo es O (N * M), donde N es la longitud de la cadena y M es la longitud de la palabra más larga en el diccionario o O (N^2), dependiendo de si codificó la mejora o no.

Entonces la complejidad total del algoritmo será: O (N1 * M) + O (N2 * M) (o O (N2^2)), donde N1 es el número de palabras en el diccionario, M es la longitud de la palabra más larga en el diccionario y N2 es la longitud de la cadena).

Si no puede pensar en una buena función hash (donde no hay ninguna colisión), otra posible solución es usar Tries o un Patricia trie (si el tamaño del trie normal es muy grande) (No pude No publico enlaces para estos temas porque mi reputación no es lo suficientemente alta como para publicar más de 2 enlaces). Pero en usted usa esto, la complejidad de su algoritmo será O (N * M) * O (Tiempo necesario para encontrar una palabra en el trie), donde N es la longitud de la cadena y M es la longitud de la palabra más larga en el diccionario.

Espero que ayude, y me disculpo por mi pobre inglés.