25.3 LCS และ edit distance

โจทย์ที่ให้สตริงสองตัวแล้วถามว่าคล้ายกันแค่ไหน ใช้ DP บนตารางสองมิติที่แถวเป็นตัวอักษรของคำแรก คอลัมน์เป็นตัวอักษรของคำที่สอง หน้านี้มีสองโจทย์ที่เป็นแม่แบบของโจทย์กลุ่มนี้ LCS (longest common subsequence) หาลำดับย่อยร่วมที่ยาวที่สุด ใช้เทียบไฟล์สองรุ่นว่าบรรทัดไหนเหมือนเดิม และ edit distance นับจำนวนครั้งน้อยสุดที่ต้องแก้คำหนึ่งให้เป็นอีกคำ ใช้ในระบบตรวจคำสะกด ทั้งสองโจทย์ต้องเติมตารางให้ถูกลำดับ แล้วย้อนรอยจากมุมตารางเพื่อหาคำตอบจริง ท้ายหน้าลดหน่วยความจำเหลือสองแถว

LCS ลำดับย่อยร่วมที่ยาวที่สุด

ชื่อจังหวัด TRANG กับ RAYONG มีลำดับย่อยร่วมกันยาวที่สุดเท่าไร ลำดับย่อยมีความหมายเดียวกับหน้า 25.2 คือเลือกบางตัวโดยคงลำดับเดิม RANG เป็นลำดับย่อยของทั้งสองคำ ใน TRANG คือตัวที่ 2 ถึง 5 ใน RAYONG คือตัวที่ 1 2 5 6 ยาว 4 ส่วน RAG ก็ร่วมกันแต่สั้นกว่า

ทำตามวิธีคิดสี่ขั้นในหน้า 24.2 ให้ s ยาว n และ t ยาว m

• นิยามสถานะ common[i][j] คือความยาว LCS ของ i ตัวแรกของ s กับ j ตัวแรกของ t
• หาความสัมพันธ์ ดูตัวสุดท้ายของสองส่วนนั้น คือ s[i - 1] กับ t[j - 1] ถ้าตรงกัน จับคู่สองตัวนี้ได้เลย ได้ common[i - 1][j - 1] + 1 ถ้าไม่ตรง อย่างน้อยตัวหนึ่งในสองตัวนี้ไม่อยู่ใน LCS จึงลองตัด s ทิ้งหนึ่งตัว หรือตัด t ทิ้งหนึ่งตัว เอาทางที่ยาวกว่า max(common[i - 1][j], common[i][j - 1])
• กรณีฐาน คำใดคำหนึ่งว่าง LCS ยาว 0 คือแถว 0 กับคอลัมน์ 0 เป็น 0 ทั้งหมด
• ลำดับการเติมและคำตอบสุดท้าย ช่องหนึ่งใช้ช่องบน ช่องซ้าย และช่องทแยงซ้ายบน จึงเติมทีละแถวจากบนลงล่าง ในแถวเติมจากซ้ายไปขวา คำตอบอยู่ที่ common[n][m]

ตอนที่ตัวอักษรตรงกัน ทำไมจับคู่ได้เลยโดยไม่ต้องลองทางอื่น ถ้ามี LCS ที่ไม่ได้ใช้คู่นี้ ตัวสุดท้ายของ LCS นั้นจับคู่กับตัวอื่นอยู่ เปลี่ยนให้มาจับคู่ตัวสุดท้ายทั้งสองนี้แทน ความยาวเท่าเดิม จึงไม่เสียอะไร

ภาพซ้ายคือจังหวะที่เติมมาถึงแถว N คอลัมน์ N ทุกช่องก่อนหน้าตามลำดับการเติมมีค่าแล้ว ช่องนี้ตัวอักษรตรงกัน จึงหยิบช่องทแยงซ้ายบนที่เป็น 2 มาบวกหนึ่งได้ 3 ส่วนช่องบนกับช่องซ้าย (เส้นประ) ใช้เฉพาะตอนตัวอักษรไม่ตรง ภาพขวาคือตารางที่เติมครบ ช่องที่มีกรอบสีคือทางที่ย้อนรอยผ่าน ช่องที่ระบายสีเข้มคือตัวอักษรที่จับคู่กัน

#include <bits/stdc++.h>
using namespace std;

int main()
{
    string s, t;
    cin >> s >> t;
    int n = s.size(), m = t.size();
    vector<vector<int>> common(n + 1, vector<int>(m + 1, 0));
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (s[i - 1] == t[j - 1]) { // (1)!
                common[i][j] = common[i - 1][j - 1] + 1;
            } else {
                common[i][j] = max(common[i - 1][j], common[i][j - 1]); // (2)!
            }
        }
    }
    for (int i = 0; i <= n; i++) {
        for (int j = 0; j <= m; j++) {
            cout << common[i][j] << (j == m ? '\n' : ' ');
        }
    }
    string answer;
    int i = n, j = m;
    while (i > 0 && j > 0) {
        if (s[i - 1] == t[j - 1]) {
            answer += s[i - 1];
            i--;
            j--;
        } else if (common[i - 1][j] >= common[i][j - 1]) { // (3)!
            i--;
        } else {
            j--;
        }
    }
    reverse(answer.begin(), answer.end());
    cout << "LCS length = " << common[n][m] << '\n';
    cout << "LCS = " << answer << '\n';
    return 0;
}

1. แถว i หมายถึง i ตัวแรก ตัวสุดท้ายของมันจึงอยู่ที่ช่อง i - 1 ของสตริง ตารางเริ่มที่ 1 แต่สตริงเริ่มที่ 0
2. ตัวไม่ตรง เอาทางที่ดีกว่าระหว่างตัด s ทิ้งหนึ่งตัว (ช่องบน) กับตัด t ทิ้งหนึ่งตัว (ช่องซ้าย)
3. ย้อนไปทางที่ให้ค่ามา ถ้าเท่ากันเลือกขึ้นบน ถ้าเลือกไปซ้ายแทน ความยาวยังเท่าเดิม แต่ LCS ที่ได้อาจเป็นอีกแบบ

TRANG RAYONG

0 0 0 0 0 0 0
0 0 0 0 0 0 0
0 1 1 1 1 1 1
0 1 2 2 2 2 2
0 1 2 2 2 3 3
0 1 2 2 2 3 4
LCS length = 4
LCS = RANG

ย้อนรอยเริ่มที่มุมขวาล่าง G ตรง G จึงเก็บ G แล้วไปทแยง N ตรง N เก็บ N แล้วไปทแยง ถึงแถว A คอลัมน์ O ไม่ตรง ช่องบนเป็น 1 ช่องซ้ายเป็น 2 ค่า 2 มาจากทางซ้าย จึงไปซ้าย เจอแถว A คอลัมน์ Y ก็ไปซ้ายอีก แล้วเจอ A ตรง A กับ R ตรง R ได้ตัวอักษรจากท้ายไปหน้าเป็น G N A R กลับลำดับเป็น RANG

ตารางมี (n + 1)(m + 1) ช่อง ช่องละ O(1) เป็น O(nm) ทั้งเวลาและหน่วยความจำ ย้อนรอยเดินไม่เกิน n + m ก้าว

edit distance

คนพิมพ์ชื่อจังหวัดผิดบ่อยเป็น CHAINGMAI แทน CHIANGMAI ระบบค้นหาจะแนะนำคำที่ถูกได้ ต้องวัดว่าสองคำห่างกันแค่ไหน ให้แก้คำได้สามแบบ แบบละ 1 ครั้ง คือ แทรก ตัวอักษรหนึ่งตัว ลบ หนึ่งตัว หรือ แทนที่ หนึ่งตัวด้วยตัวอื่น edit distance คือจำนวนครั้งน้อยที่สุดที่เปลี่ยน s ให้เป็น t

• นิยามสถานะ cost[i][j] คือจำนวนครั้งน้อยสุดที่เปลี่ยน i ตัวแรกของ s ให้เป็น j ตัวแรกของ t
• หาความสัมพันธ์ ดูตัวสุดท้าย ถ้า s[i - 1] ตรงกับ t[j - 1] ไม่ต้องแก้ตัวนี้ ได้ cost[i - 1][j - 1] ถ้าไม่ตรง ลองสามทาง แทนที่ตัวสุดท้ายของ s ด้วยตัวสุดท้ายของ t มาจากช่องทแยง ลบตัวสุดท้ายของ s มาจากช่องบน แทรกตัวสุดท้ายของ t ต่อท้าย มาจากช่องซ้าย เลือกทางที่น้อยสุดแล้วบวก 1
• กรณีฐาน เปลี่ยน i ตัวให้เป็นคำว่าง ต้องลบ i ครั้ง cost[i][0] = i เปลี่ยนคำว่างให้เป็น j ตัว ต้องแทรก j ครั้ง cost[0][j] = j ต่างจาก LCS ที่ขอบเป็น 0
• ลำดับการเติมและคำตอบสุดท้าย เหมือน LCS ทุกอย่าง คำตอบอยู่ที่ cost[n][m]

ย้อนรอยแบบเดียวกับ LCS ดูว่าค่าของช่องมาจากทางไหน แล้วพิมพ์สองคำเรียงกัน ใส่ - ตรงที่ไม่มีตัวอักษร บรรทัดกลางบอกว่าตรงนั้นเกิดอะไร | คือตัวเดียวกัน R คือแทนที่ D คือลบ I คือแทรก

#include <bits/stdc++.h>
using namespace std;

int main()
{
    string s, t;
    cin >> s >> t;
    int n = s.size(), m = t.size();
    vector<vector<int>> cost(n + 1, vector<int>(m + 1, 0));
    for (int i = 0; i <= n; i++) {
        cost[i][0] = i;
    }
    for (int j = 0; j <= m; j++) {
        cost[0][j] = j;
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (s[i - 1] == t[j - 1]) {
                cost[i][j] = cost[i - 1][j - 1];
            } else {
                cost[i][j] = 1 + min({cost[i - 1][j - 1], cost[i - 1][j], cost[i][j - 1]}); // (1)!
            }
        }
    }
    cout << "edit distance = " << cost[n][m] << '\n';
    string top, bottom, mark;
    int i = n, j = m;
    while (i > 0 || j > 0) {
        if (i > 0 && j > 0 && s[i - 1] == t[j - 1]) {
            top += s[i - 1];
            bottom += t[j - 1];
            mark += '|';
            i--;
            j--;
        } else if (i > 0 && j > 0 && cost[i][j] == cost[i - 1][j - 1] + 1) { // (2)!
            top += s[i - 1];
            bottom += t[j - 1];
            mark += 'R';
            i--;
            j--;
        } else if (i > 0 && cost[i][j] == cost[i - 1][j] + 1) {
            top += s[i - 1];
            bottom += '-';
            mark += 'D';
            i--;
        } else {
            top += '-';
            bottom += t[j - 1];
            mark += 'I';
            j--;
        }
    }
    reverse(top.begin(), top.end());
    reverse(mark.begin(), mark.end());
    reverse(bottom.begin(), bottom.end());
    cout << top << '\n' << mark << '\n' << bottom << '\n';
    return 0;
}

1. min ที่ใส่ค่าในปีกกาหาค่าน้อยสุดของกี่ค่าก็ได้ ไม่ต้องซ้อน min สองชั้น
2. ตรวจทางแทนที่ก่อน แล้วค่อยลบ แล้วค่อยแทรก ถ้าหลายทางให้ค่าเท่ากัน ลำดับการตรวจนี้กำหนดว่าจะพิมพ์แบบไหน จำนวนครั้งยังเท่าเดิม

CHAINGMAI CHIANGMAI

edit distance = 2
CHAINGMAI
||RR|||||
CHIANGMAI

การสลับตัวอักษรสองตัวที่ติดกันนับเป็นการแทนที่สองครั้ง เพราะไม่มีการสลับในสามแบบที่อนุญาต ลองป้อนคู่อื่นกับโปรแกรมเดียวกัน BANGKOK BKK ได้ 4 (ลบ A N G O) และ PATTAYA PATAYA ได้ 1 (ลบ T หนึ่งตัว) เวลาและหน่วยความจำเป็น O(nm) เหมือน LCS

เหลือแค่สองแถว

ทั้งสองโจทย์ แถว i ใช้แค่แถว i กับแถว i - 1 เหมือน knapsack ในหน้า 25.1 แต่คราวนี้ช่องหนึ่งใช้ทั้งช่องทแยงซ้ายบนที่เป็นของแถวบน และช่องซ้ายที่เป็นของแถวเดียวกัน ใช้แถวเดียววนถอยหลังแบบ knapsack ไม่ได้ เพราะช่องซ้ายต้องเป็นค่าใหม่ ทางที่ตรงที่สุดคือเก็บสองแถว above คือแถวบน row คือแถวที่กำลังเติม เติมเสร็จแล้วสลับกัน

#include <bits/stdc++.h>
using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    string s, t;
    cin >> s >> t;
    int n = s.size(), m = t.size();
    vector<int> above(m + 1, 0), row(m + 1, 0);
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (s[i - 1] == t[j - 1]) {
                row[j] = above[j - 1] + 1;
            } else {
                row[j] = max(above[j], row[j - 1]);
            }
        }
        swap(above, row); // (1)!
    }
    cout << above[m] << '\n';
    return 0;
}

1. swap ของ vector สลับแค่ตัวชี้ข้างใน ใช้เวลาคงที่ ไม่ได้คัดลอกทีละช่อง หลังสลับ above คือแถวที่เพิ่งเติมเสร็จ ส่วน row เป็นแถวเก่าที่จะถูกเขียนทับในรอบถัดไป ช่อง 0 ของทั้งสองแถวเป็น 0 ตลอดเพราะไม่เคยถูกเขียน

TRANG RAYONG

4

เวลายังเป็น O(nm) แต่หน่วยความจำเหลือ O(m) วัดหน่วยความจำสูงสุดที่โปรแกรมใช้จริงบนเครื่องเดียวกับหน้า 19.1 ด้วยสตริง DNA สุ่มจากตัวอักษร A C G T

ตารางเต็มที่ 10000 ตัวต้องมี 10001 × 10001 ช่อง ช่องละ 4 byte ราว 400 ล้าน byte ถ้าโจทย์จำกัดหน่วยความจำ 256 MB ก็ไม่ผ่านแล้ว แม้เวลาจะทัน ข้อเสียของสองแถวคือย้อนรอยไม่ได้ เพราะแถวเก่าถูกทิ้งไปแล้ว ใช้ได้เมื่อโจทย์ถามแค่ความยาวหรือจำนวนครั้ง

เร็วขึ้นแค่ไหน

วิธีตรงไปตรงมาคือ recursion ที่ลองตัดทีละตัวตามความสัมพันธ์ข้างบน แต่ไม่จดคำตอบ แบบที่บทที่ 24 เริ่มต้น ถ้าตัวอักษรตรงกันเรียกตัวเองครั้งเดียว ถ้าไม่ตรงเรียกสองครั้ง กรณีที่ช้าที่สุดคือสองคำที่ไม่มีตัวอักษรร่วมกันเลย เช่น A ล้วนกับ C ล้วน ทุกครั้งแตกเป็นสองทาง วัดบนเครื่องเดียวกับหน้า 19.1 รันแต่ละแบบ 5 รอบ

recursion ยาวขึ้นแค่สองตัว ช้าลง 6 ถึง 18 เท่า สตริงยาว 16 ตัวก็เกินวินาทีแล้ว ส่วน DP ทำสตริงยาวหมื่นตัวได้ในเสี้ยววินาทีเมื่อคอมไพล์ -O2 สองแถวเร็วกว่าตารางเต็มด้วย เพราะข้อมูลสองแถวเล็กพอจะอยู่ใน cache ของซีพียู ไม่ต้องวิ่งไปอ่านหน่วยความจำหลักบ่อย สังเกตว่าแบบ Code::Blocks ช้ากว่า -O2 ราว 4.5 ถึง 12 เท่า ลูปซ้อนที่ทำงานเป็นร้อยล้านรอบแบบนี้ต้องทดสอบความเร็วด้วย -O2 เหมือน grader

ลองทำให้พัง

แบบที่ 1 ใช้ s[i] แทน s[i - 1]

ลืมว่าตารางเริ่มนับที่ 1 แต่สตริงเริ่มที่ 0 แล้วเทียบ s[i] == t[j]

#include <bits/stdc++.h>
using namespace std;

int main()
{
    string s, t;
    cin >> s >> t;
    int n = s.size(), m = t.size();
    vector<vector<int>> common(n + 1, vector<int>(m + 1, 0));
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (s[i] == t[j]) {
                common[i][j] = common[i - 1][j - 1] + 1;
            } else {
                common[i][j] = max(common[i - 1][j], common[i][j - 1]);
            }
        }
    }
    cout << "LCS length = " << common[n][m] << '\n';
    return 0;
}

PHUKET RAYONG

LCS length = 1

PHUKET กับ RAYONG ไม่มีตัวอักษรร่วมกันเลย คำตอบต้องเป็น 0 แต่ได้ 1 โปรแกรมไม่พังเพราะ s[n] ของ string อ่านได้และได้ตัวอักษรว่าง '\0' แถวสุดท้ายจึงเทียบ '\0' กับ '\0' แล้วนับว่าตรงกัน ส่วนตัวแรกของทั้งสองคำไม่เคยถูกเทียบเลย ที่น่ากลัวคือ TRANG กับ RAYONG ที่ใช้ตลอดหน้านี้ได้ 4 ถูกต้องพอดี เพราะ R ตัวแรกของ RAYONG ที่ไม่เคยถูกเทียบหายไปจาก LCS แต่คู่ '\0' มาชดเชยแทนพอดี ทดสอบ LCS ทุกครั้งด้วยคำที่ไม่มีตัวอักษรร่วมกันเลย ซึ่งคำตอบต้องเป็น 0

แบบที่ 2 ย้อนรอยด้วยสองแถว

ถ้าโจทย์ให้พิมพ์ LCS แล้วใช้สองแถวเพื่อประหยัดหน่วยความจำ จะย้อนรอยไม่ได้ เพราะการย้อนรอยต้องดูช่องบนและช่องซ้ายของทุกแถวที่เดินผ่าน ตั้งแต่แถว n ขึ้นไปถึงแถว 0 แต่ตอนจบเหลือแค่แถว n กับแถว n - 1 ก่อนเลือกวิธีให้อ่านขอบเขตก่อน ถ้าต้องพิมพ์คำตอบและตารางเต็มใส่หน่วยความจำได้ ใช้ตารางเต็ม ถ้าถามแค่ตัวเลข ใช้สองแถว

สรุป

• LCS common[i][j] ตัวสุดท้ายตรงกันได้ช่องทแยงบวกหนึ่ง ไม่ตรงได้ค่ามากกว่าของช่องบนกับช่องซ้าย ขอบเป็น 0
• edit distance cost[i][j] ตรงกันได้ช่องทแยง ไม่ตรงได้ 1 บวกค่าน้อยสุดของสามช่อง (แทนที่ ลบ แทรก) ขอบคือ i กับ j
• เติมทีละแถวจากบนลงล่าง ซ้ายไปขวา ทั้งคู่เป็น O(nm) ย้อนรอยจากมุมขวาล่างตามทางที่ให้ค่ามา
• ตารางเริ่มที่ 1 สตริงเริ่มที่ 0 เทียบ s[i - 1] กับ t[j - 1]
• ถ้าถามแค่ตัวเลข เก็บสองแถวพอ หน่วยความจำเหลือ O(m) แต่ย้อนรอยไม่ได้