Dividir una cadena en una cadena de palabras válidas usando la Programación Dinámica

Question

Necesito encontrar un algoritmo de programación dinámico para resolver este problema. Lo intenté pero no pude resolverlo. Aquí está el problema:

Te dan una cadena de n caracteres s [1 ... n], que crees que es un documento de texto dañado en el que toda la puntuación se ha desvanecido (para que se parezca a "itwasthebestoftimes ... "). Desea reconstruir el documento utilizando un diccionario, que está disponible en forma de una función booleana dict (*) tal que, para cualquier cadena w, dict (w) tiene valor 1 si w es una palabra válida, y tiene valor 0 de otra manera.

1. Proporcione un algoritmo de programación dinámico que determine si la cadena s [*] se puede reconstituir como una secuencia de palabras válidas. El tiempo de ejecución debe ser como máximo O (n^2), suponiendo que cada llamada a dict toma un tiempo de unidad.
2. En el caso de que la cadena sea válida, haga que su algoritmo genere la secuencia de palabras correspondiente.

Answer 1

La cadena s [] se puede dividir en más de una forma. El siguiente método encuentra la cantidad máxima de palabras en la que podemos dividir s []. A continuación se muestra el boceto/pseudocódigo del algoritmo

bestScore [i] -> almacena el número máximo de palabras en el que los primeros personajes que se pueden dividir (sería MINUS_INFINITY lo contrario)

for (i = 1 to n){ 
    bestScore[i] = MINUS_INFINITY 
    for (k = 1 to i-1){ 
     bestScore[i] = Max(bestSCore[i], bestScore[i-k]+ f(i,k)) 
    } 
} 

Donde f (i, k) se define como:

f(i,k) = 1 : if s[i-k+1 to i] is in dictionary 
     = MINUS_INFINITY : otherwise 

bestScore [n] sería almacenar el número máximo de palabras en la que s se puede dividir [] (si el valor es MINUS_INFINIY, s no se pueden dividir [])

Claramente el tiempo de ejecución es O (n^2)

Como esto parece un ejercicio de libro de texto, no escribiré el código para reconstruir las posiciones de división reales.

Answer 2

Vamos a la longitud de su documento compactado sea N.

Let b (n) ser un valor booleano: true si el documento se puede dividir en palabras a partir de la posición n en el documento.

b (N) es verdadero (ya que la cadena vacía se puede dividir en 0 palabras). Dado b (N), b (N - 1), ... b (N - k), puede construir b (N - k - 1) considerando todas las palabras que comienzan en el carácter N - k - 1. Si hay alguna palabra, w, con b (N - k - 1 + len (w)) establecida, luego establezca b (N - k - 1) en verdadero. Si no hay tal palabra, entonces configure b (N - k - 1) en falso.

Finalmente, calcula b (0) que le indica si todo el documento se puede dividir en palabras.

En pseudo-código:

def try_to_split(doc): 
    N = len(doc) 
    b = [False] * (N + 1) 
    b[N] = True 
    for i in range(N - 1, -1, -1): 
    for word starting at position i: 
     if b[i + len(word)]: 
     b[i] = True 
     break 
    return b 

Hay algunos trucos que puede hacer para conseguir 'palabra que empiece en la posición i' eficiente, pero le piden un O (n^2) algoritmo, por lo que puede buscar todas las cadenas comenzando en el diccionario i.

para generar las palabras, puede modificar el algoritmo anterior para almacenar las buenas palabras, o simplemente generar de esta manera:

def generate_words(doc, b, idx=0): 
    length = 1 
    while true: 
    assert b(idx) 
    if idx == len(doc): return 
    word = doc[idx: idx + length] 
    if word in dictionary and b(idx + length): 
     output(word) 
     idx += length 
     length = 1 

Aquí b es la matriz booleana generado a partir de la primera parte del algoritmo .

Answer 3

O(N^2) Dp es claro, pero si conoce las palabras del diccionario, creo que puede utilizar algunas precomputaciones para hacerlo aún más rápido en O(N). Aho-Corasick

Answer 4

Una solución dp en C++:

int main() 
{ 
    set<string> dict; 
    dict.insert("12"); 
    dict.insert("123"); 
    dict.insert("234"); 
    dict.insert("12345"); 
    dict.insert("456"); 
    dict.insert("1234"); 
    dict.insert("567"); 
    dict.insert("123342"); 
    dict.insert("42"); 
    dict.insert("245436564"); 
    dict.insert("12334"); 

    string str = "123456712334245436564"; 

    int size = str.size(); 
    vector<int> dp(size+1, -1); 
    dp[0] = 0; 
    vector<string > res(size+1); 
    for(int i = 0; i < size; ++i) 
    { 
     if(dp[i] != -1) 
     { 
      for(int j = i+1; j <= size; ++j) 
      { 
       const int len = j-i; 
       string substr = str.substr(i, len); 
       if(dict.find(substr) != dict.end()) 
       { 
        string space = i?" ":""; 
        res[i+len] = res[i] + space + substr; 
        dp[i+len] = dp[i]+1; 
       } 
      } 
     } 
    } 
    cout << *dp.rbegin() << endl; 
    cout << *res.rbegin() << endl; 

    return 0; 
} 

Answer 5

Para formalizar lo que sugiere @MinhPham.

Esta es una solución de programación dinámica.

Dada una cadena str, dejar que

b [i] = verdadero si la subcadena str [0 ... i] (ambos inclusive) se puede dividir en palabras válidas.

Anteponga un carácter inicial a str, por ejemplo!, Para representar la palabra vacía. str = "!" + Str

El caso base es la cadena vacía, por lo

b [0] = verdadero.

Para el caso iterativo:

b [j] = TRUE si b [i] == true y str [i..j] es una palabra para todo i < j

Answer 6

A continuación se muestra una solución O (n^2) para este problema.

void findstringvalid() { 
string s = "itwasthebestoftimes"; 
set<string> dict; 
dict.insert("it"); 
dict.insert("was"); 
dict.insert("the"); 
dict.insert("best"); 
dict.insert("of"); 
dict.insert("times"); 

vector<bool> b(s.size() + 1, false); 
vector<int> spacepos(s.size(), -1); 
//Initialization phase 
b[0] = true; //String of size 0 is always a valid string 
for (int i = 1; i <= s.size(); i++) { 
    for (int j = 0; j <i; j++) { 
     //string of size s[ j... i] 
     if (!b[i]) { 
      if (b[j]) { 
       //check if string "j to i" is in dictionary 
       string temp = s.substr(j, i - j); 
       set<string>::iterator it = dict.find(temp); 
       if (it != dict.end()) { 
        b[i] = true; 
        spacepos[i-1] = j; 
       } 
      } 
     } 
    } 
} 
if(b[s.size()]) 
    for (int i = 1; i < spacepos.size(); i++) { 
     if (spacepos[i] != -1) { 
      string temp = s.substr(spacepos[i], i - spacepos[i] + 1); 
      cout << temp << " "; 
    } 
    } 
}