แยกสตริงออกเป็นสตริงคำที่ถูกต้องโดยใช้ Dynamic Programming

ให้ความยาวของเอกสารที่บีบอัดของคุณเป็น N

ให้ b(n) เป็นบูลีน: จริง หากเอกสารสามารถแยกเป็นคำโดยเริ่มต้นจากตำแหน่ง n ในเอกสาร

b(N) เป็นจริง (เนื่องจากสตริงว่างสามารถแบ่งออกเป็น 0 คำได้) เมื่อกำหนดให้ b(N), b(N - 1), ... b(N - k) คุณสามารถสร้าง b(N - k - 1) ได้โดยพิจารณาคำทั้งหมดที่ขึ้นต้นด้วยอักขระ N - k - 1 ถ้ามี คำใดๆ ก็ตาม w โดยตั้งค่า b(N - k - 1 + len(w)) แล้วกำหนดให้ b(N - k - 1) เป็นจริง หากไม่มีคำดังกล่าว ให้ตั้งค่า b(N - k - 1) เป็นเท็จ

ในที่สุดคุณคำนวณ b(0) ซึ่งจะบอกคุณว่าเอกสารทั้งหมดสามารถแบ่งออกเป็นคำได้หรือไม่

ในรหัสเทียม:

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

มีเคล็ดลับบางอย่างที่คุณสามารถทำได้เพื่อให้ 'คำเริ่มต้นที่ตำแหน่ง i' มีประสิทธิภาพ แต่ระบบจะขอให้คุณระบุอัลกอริทึม O(N^2) ดังนั้นคุณจึงสามารถค้นหาทุกสตริงที่เริ่มต้นที่ i ในพจนานุกรมได้

หากต้องการสร้างคำ คุณสามารถปรับเปลี่ยนอัลกอริทึมด้านบนเพื่อจัดเก็บคำที่ดี หรือเพียงสร้างดังนี้:

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

โดยที่ b คืออาร์เรย์บูลีนที่สร้างจากส่วนแรกของอัลกอริทึม

เพื่ออธิบายสิ่งที่ @MinhPham แนะนำอย่างเป็นทางการ

นี่คือโซลูชันการเขียนโปรแกรมแบบไดนามิก

รับสตริง str ให้

b[i] = true หากสตริงย่อย str[0...i] (รวม) สามารถแบ่งออกเป็นคำที่ถูกต้องได้

เพิ่มอักขระเริ่มต้นบางตัวไว้หน้า str พูด ! เพื่อแสดงคำว่าง STR = "!" + STR

กรณีฐานคือสตริงว่างดังนั้น

ข[0] = จริง

สำหรับกรณีวนซ้ำ:

b[j] = true ถ้า b[i] == true และ str[i..j] เป็นคำสำหรับทุก i ‹ j

O(N^2) Dp นั้นชัดเจน แต่ถ้าคุณรู้คำศัพท์ในพจนานุกรม ฉันคิดว่าคุณสามารถใช้การคำนวณล่วงหน้าบางอย่างเพื่อให้คำนั้นเร็วขึ้นใน O(N) ได้ อาโฮ-คอราซิก

โซลูชัน dp ใน 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;
}

สตริง s[] สามารถแบ่งออกเป็นได้มากกว่าหนึ่งวิธี วิธีการด้านล่างนี้จะค้นหาจำนวนคำสูงสุดที่เราสามารถแยก s[] ได้ ด้านล่างนี้คือภาพร่าง/ซูโดโค้ดของอัลกอริทึม

bestScore[i] -> เก็บจำนวนคำสูงสุดที่สามารถแยกอักขระ i ตัวแรกได้ (มิฉะนั้นจะเป็น MINUS_INFINITY)

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

โดยที่ f(i,k) ถูกกำหนดเป็น:

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

bestScore[n] จะเก็บจำนวนคำสูงสุดที่สามารถแยก s[] ได้ (หากค่าเป็น MINUS_INFINIY จะไม่สามารถแยก s[] ได้)

เห็นได้ชัดว่าเวลาทำงานคือ O(n^2)

เนื่องจากนี่ดูเหมือนแบบฝึกหัดในตำราเรียน ฉันจะไม่เขียนโค้ดเพื่อสร้างตำแหน่งการแยกจริงขึ้นมาใหม่

ด้านล่างนี้เป็นวิธีแก้ปัญหา O(n^2) สำหรับปัญหานี้

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