Chia chuỗi thành chuỗi các từ hợp lệ sử dụng Lập trình động

Question

Tôi cần tìm thuật toán lập trình động để giải quyết vấn đề này. Tôi đã thử nhưng không thể tìm ra. Đây là vấn đề:

Bạn được cung cấp một chuỗi ký tự n [1 ... n], mà bạn cho là tài liệu văn bản bị hỏng trong đó tất cả các dấu câu đều biến mất (để trông giống như "itwasthebestoftimes" ... "). Bạn muốn xây dựng lại tài liệu bằng cách sử dụng từ điển, có sẵn dưới dạng một hàm boolean dict (*) sao cho, với bất kỳ chuỗi w, dict (w) có giá trị 1 nếu w là một từ hợp lệ và có giá trị 0 nếu không thì.

1. Cung cấp thuật toán lập trình động xác định chuỗi có thể được tái tạo dưới dạng chuỗi các từ hợp lệ hay không. Thời gian chạy tối đa phải là O (n^2), giả sử rằng mỗi cuộc gọi đến dict mất thời gian đơn vị.
2. Trong trường hợp chuỗi ký tự hợp lệ, hãy đặt thuật toán của bạn ra chuỗi thứ tự tương ứng.

Answer 1

Chuỗi s [] có thể được chia thành nhiều cách. Phương pháp dưới đây tìm số lượng từ tối đa mà chúng ta có thể chia s []. Dưới đây là phác thảo/giả của thuật toán

bestScore [i] -> Lưu trữ các số lượng tối đa của các từ trong đó các nhân vật tôi lần đầu tiên có thể được chia (nó sẽ là MINUS_INFINITY khác)

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

đâu f (i, k) được định nghĩa là:

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

bestScore [n] sẽ lưu trữ số lượng tối đa của các từ trong đó s [] có thể được chia (nếu giá trị là MINUS_INFINIY, s [] không có thể được chia)

Rõ ràng thời gian chạy là O (n^2)

Vì đây trông giống như bài tập sách giáo khoa, tôi sẽ không viết mã để tái tạo lại vị trí chia tách thực tế.

Answer 2

Hãy chiều dài của tài liệu đầm của bạn được N.

Hãy b (n) là một boolean: true nếu tài liệu có thể được chia thành các từ bắt đầu từ vị trí n trong tài liệu.

b (N) là đúng (vì chuỗi trống có thể được chia thành 0 từ). Cho b (N), b (N - 1), ... b (N - k), bạn có thể xây dựng b (N - k - 1) bằng cách xem xét tất cả các từ bắt đầu từ ký tự N - k - 1. Nếu có bất kỳ từ nào, w, với b (N - k - 1 + len (w)) được đặt, sau đó đặt b (N - k - 1) thành true. Nếu không có từ đó, thì đặt b (N - k - 1) thành false.

Cuối cùng, bạn tính b (0) cho bạn biết nếu toàn bộ tài liệu có thể được chia thành các từ.

Trong pseudo-code:

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 

Có một số thủ thuật bạn có thể làm để có được 'từ bắt đầu từ vị trí i' hiệu quả, nhưng bạn được yêu cầu cho một O (N^2) thuật toán, vì vậy bạn chỉ có thể tra cứu mọi chuỗi bắt đầu từ i trong từ điển.

Để tạo ra các từ, bạn có thể sửa đổi các thuật toán ở trên để lưu trữ những lời tốt, hoặc chỉ tạo ra nó như thế này:

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 

Ở đây b là mảng boolean được tạo ra từ phần đầu tiên của thuật toán .

Answer 3

O(N^2) Dp là rõ ràng nhưng nếu bạn biết các từ của từ điển, tôi nghĩ bạn có thể sử dụng một số precomputations để có được nó nhanh hơn trong O(N). Aho-Corasick

Answer 4

Một giải pháp dp trong 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

Để chính thức hóa những gì @MinhPham gợi ý.

Đây là giải pháp lập trình động.

Cho một chuỗi str, chúng ta hãy

b [i] = true nếu chuỗi str [0 ... i] (bao gồm) có thể được chia thành các từ hợp lệ.

Hãy thêm một số ký tự bắt đầu vào str, nói !, để đại diện cho từ trống. str = "!" + Str

Trường hợp cơ sở là chuỗi rỗng, vì vậy

b [0] = true.

Đối với trường hợp lặp đi lặp lại:

b [j] = true nếu b [i] == true và str [i..j] là một từ cho tất cả i < j

Answer 6

Dưới đây là giải pháp O (n^2) cho vấn đề này.

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 << " "; 
    } 
    } 
}