Dividere una stringa in una stringa di parole valide utilizzando la programmazione dinamica

Question

Ho bisogno di trovare un algoritmo di programmazione dinamica per risolvere questo problema. Ho provato ma non riuscivo a capirlo. Ecco il problema:

Ti viene assegnata una stringa di n caratteri s [1 ... n], che ritieni essere un documento di testo corrotto in cui tutti i segni di punteggiatura sono scomparsi (in modo che assomigli a "itwasthebestoftimes ... "). Desiderate ricostruire il documento usando un dizionario, che è disponibile sotto forma di una funzione booleana dict (*) tale che, per ogni stringa w, dict (w) ha valore 1 se w è una parola valida e ha valore 0 altrimenti.

1. Fornire un algoritmo di programmazione dinamica che determina se la stringa s [*] può essere ricostituita come una sequenza di parole valide. Il tempo di esecuzione dovrebbe essere al massimo O (n^2), assumendo che ogni chiamata a dettare richiede tempo unitario.
2. Nel caso in cui la stringa sia valida, fai in modo che l'algoritmo generi la sequenza di parole corrispondente.

Answer 1

La stringa s [] può potenzialmente essere suddivisa in più di un modo. Il metodo seguente trova il numero massimo di parole in cui possiamo dividere s []. Di seguito è riportato il disegno/pseudocodice dell'algoritmo

bestScore [i] -> memorizza il numero massimo di parole in cui i primi personaggi che possono essere divisi (sarebbe MINUS_INFINITY altrimenti)

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

dove f (i, k) è definito come:

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

bestScore [n] avrebbe memorizzare il numero massimo di parole in cui s [] può essere diviso (se il valore è MINUS_INFINIY, s [] non può essere diviso)

Ovviamente il tempo di esecuzione è O (n^2)

Poiché questo sembra un esercizio da manuale, non scriverò il codice per ricostruire le posizioni di divisione effettive.

Answer 2

Facciamo la lunghezza del documento compattato essere N.

Sia b (n) essere un valore booleano: true se il documento può essere suddiviso in parole che iniziano dalla posizione n nel documento.

b (N) è vero (poiché la stringa vuota può essere divisa in 0 parole). Dato b (N), b (N - 1), ... b (N - k), puoi costruire b (N - k - 1) considerando tutte le parole che iniziano con il carattere N - k - 1. Se c'è una parola simile, w, con b (N - k - 1 + len (w)) impostata, quindi impostare b (N - k - 1) su true. Se non esiste una parola, quindi impostare b (N - k - 1) su false.

Alla fine, si calcola b (0), che ti dice se l'intero documento può essere suddivisa in parole.

In pseudo-codice:

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 

Ci sono alcuni trucchi che potete fare per ottenere 'la parola a partire dalla posizione i' efficiente, ma ti viene chiesto per un O (N^2) algoritmo, in modo da puoi solo cercare ogni stringa a partire da i nel dizionario.

per generare le parole, è possibile modificare l'algoritmo di cui sopra per memorizzare le buone parole, o semplicemente generare in questo modo:

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 

Ecco b è l'array booleano generato dalla prima parte dell'algoritmo .

Answer 3

Il O(N^2) Dp è chiaro ma se si conoscono le parole del dizionario, penso che sia possibile utilizzare alcune precomputazioni per ottenere ancora più rapidamente in O(N). Aho-Corasick

Answer 4

Una soluzione dp in 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

di formalizzare ciò @MinhPham suggerito.

Questa è una soluzione di programmazione dinamica.

Data una stringa str, lasciate

b [i] = true se la stringa str [0 ... i] (compreso) può essere suddivisa in parole valide.

Preordina un carattere iniziale a str, say!, Per rappresentare la parola vuota. str = "!" + Str

Il caso base è la stringa vuota, così

b [0] = TRUE.

Per il caso iterativo:

b [j] = vero se b [i] == vero e str [i..j] è una parola per ogni i < j

Answer 6

Di seguito è una soluzione O (n^2) per questo 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 << " "; 
    } 
    } 
}