Edit Distance: ít phép chèn, xóa, thay ký tự nhất

Biến kitten thành sitting trong ba bước

Từ kitten, thay k thành s được sitten. Thay e thành i được sittin. Chèn g ở cuối được sitting. Ta có một cách biến đổi dùng ba phép; DP sẽ xác nhận không có cách nào dùng ít hơn theo đúng bộ phép đã cho.

Một chuỗi thao tác hợp lệ chỉ chứng minh cận trên cho đáp án. Ví dụ xóa hết A rồi chèn lại B luôn cho một cách, nhưng thường không tối ưu. Nhiệm vụ là tìm số phép nhỏ nhất trong tất cả cách biến đổi, không phải chỉ viết một kịch bản làm hai xâu giống nhau.

Khoảng cách này thường dùng để so mức khác nhau giữa hai dãy ký tự. Tuy nhiên, nó chỉ phản ánh mô hình thao tác và chi phí đang chọn; không phải mọi lỗi gõ hoặc mức giống nhau về ý nghĩa đều được biểu diễn tốt bằng ba phép đơn vị.

Trạng thái DP theo hai tiền tố

Đặt dp[i][j] là số phép ít nhất để biến A[0:i] thành B[0:j]. Chỉ số i,j là số lượng ký tự, vì thế ký tự cuối hai tiền tố nằm ở A[i−1], B[j−1] khi i,j dương. Bảng có thêm hàng 0 và cột 0 cho xâu rỗng.

Muốn biến i ký tự thành rỗng, bắt buộc xóa i lần, nên dp[i][0]=i. Muốn từ rỗng thành j ký tự, chèn j lần, nên dp[0][j]=j. Khởi tạo toàn bộ hàng đầu và cột đầu bằng 0 là lỗi thường gặp khi chuyển từ bảng LCS sang Edit Distance.

Trạng thái chỉ cần hai vị trí tiền tố bởi các phép sửa không có ràng buộc lịch sử bổ sung. Nếu đề tính một chuỗi chèn liên tiếp theo giá mở khoảng trống cộng giá kéo dài, cần biết đang ở trong khoảng chèn/xóa hay không; công thức hai chiều đơn giản này chưa giữ đủ thông tin cho mô hình đó.

Ba lựa chọn ở bước cuối

Xóa ký tự cuối của tiền tố A: trước đó biến A[0:i−1] thành B[0:j], rồi thêm một phép xóa. Ứng viên là dp[i−1][j]+1. Chèn ký tự cuối B vào A: trước đó đã biến thành B[0:j−1], rồi chèn B[j−1], cho dp[i][j−1]+1.

Cuối cùng, ghép vị trí cuối của hai tiền tố: nếu ký tự đã bằng nhau, không mất phép nào; nếu khác, thay một lần. Ứng viên là dp[i−1][j−1] cộng 0 hoặc 1. Lấy min ba giá trị vì ta đang chọn cách ít phép nhất, không đếm tổng số kịch bản.

Khi hai ký tự bằng nhau, chọn ô chéo không trả phí là cách tự nhiên; code vẫn lấy min cùng hai lựa chọn còn lại để giữ một công thức thống nhất. Không được luôn cộng 1 vào ô chéo vì sẽ tính cả việc giữ nguyên ký tự là một phép sửa.

Bảng nhỏ: biến cat thành cut

Bảng dưới chỉ dùng ba ký tự mỗi phía để quan sát công thức. Hàng là tiền tố cat, cột là tiền tố cut. Ký hiệu ∅ là xâu rỗng.

Tại ô c,c, hai ký tự bằng nhau nên từ 0 chéo giữ nguyên 0. Tại ô ca,cu, a khác u nên thay từ ô c,c, được 1. Ô cuối cat,cut ghép t với t miễn phí, giữ đáp án 1. Một thao tác thay a thành u khớp với bảng.

Bạn có thể thấy có những ô lớn hơn đáp án cuối vì chúng so hai tiền tố lệch độ dài hoặc khác nội dung. Không lấy min toàn bảng làm kết quả; bài hỏi biến đủ cả hai xâu nên đọc đúng dp[n][m].

Code C++ và Python

#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
using namespace std;
int edit_distance(const string& a,const string& b){
    int n=a.size(),m=b.size();vector<vector<int>> d(n+1,vector<int>(m+1));
    for(int i=0;i<=n;++i)d[i][0]=i;
    for(int j=0;j<=m;++j)d[0][j]=j;
    for(int i=1;i<=n;++i)for(int j=1;j<=m;++j){
        int replace=d[i-1][j-1]+(a[i-1]!=b[j-1]);
        d[i][j]=min({d[i-1][j]+1,d[i][j-1]+1,replace});
    }
    return d[n][m];
}
int main(){
    string a="kitten",b="sitting",line;
    if(getline(cin,line)){a=line;if(!getline(cin,b))b="";}
    cout<<edit_distance(a,b)<<'\n';
}

import sys

def edit_distance(a,b):
    n,m=len(a),len(b)
    d=[[0]*(m+1) for _ in range(n+1)]
    for i in range(n+1):
        d[i][0]=i
    for j in range(m+1):
        d[0][j]=j
    for i in range(1,n+1):
        for j in range(1,m+1):
            d[i][j]=min(d[i-1][j]+1,d[i][j-1]+1,d[i-1][j-1]+(a[i-1]!=b[j-1]))
    return d[n][m]

if __name__=='__main__':
    lines=sys.stdin.read().splitlines()
    a,b=(lines+[''])[:2] if lines else ('kitten','sitting')
    print(edit_distance(a,b))

Không nhập dữ liệu, chương trình in 3 cho kitten và sitting. Input riêng là hai dòng; dòng rỗng hợp lệ, khoảng trắng bên trong cũng được tính như một ký tự. Ví dụ dùng ASCII để C++ string và Python str cùng xét một đơn vị ký tự. Hàm hiện trả số phép, chưa xuất danh sách thao tác.

Với văn bản Unicode, C++ string UTF-8 lưu byte còn Python str dùng điểm mã. Muốn hai cách cài cùng một định nghĩa cho tiếng Việt, cần thống nhất cách giải mã và đơn vị so sánh trước. Một chữ hiển thị có thể gồm nhiều điểm mã khi dùng dấu kết hợp, nên ngay cả điểm mã và ký tự nhìn thấy cũng không phải luôn giống nhau.

Code giữ bảng đầy đủ để dễ quan sát. Thời gian O(nm), bộ nhớ O(nm) cho hai độ dài dương. Cần chọn giới hạn theo khả năng cấp phát thật của ngôn ngữ; Python list và đối tượng số nguyên không có chi phí giống một mảng int C++ cùng số ô.

Nếu cần in thao tác chỉnh sửa

Bắt đầu từ ô n,m rồi chọn một bước trước đã tạo giá trị hiện tại. Nếu ký tự bằng nhau và ô chéo giữ giá trị, đi chéo mà không ghi phép sửa. Nếu ô chéo cộng 1 khớp, ghi thay; nếu ô trên cộng 1 khớp, ghi xóa; nếu ô trái cộng 1 khớp, ghi chèn.

Truy ngược ghi thao tác theo chiều cuối về đầu, nên cần đảo hoặc diễn giải lại thứ tự trước khi áp vào xâu thật. Chỉ số vị trí có thể thay đổi sau các phép chèn/xóa; không nên in trực tiếp chỉ số tiền tố của quá trình truy ngược rồi áp lên xâu đang sửa mà không quy đổi.

Có thể có nhiều chuỗi thao tác tối ưu. Nếu chỉ yêu cầu một cách, phá hòa ổn định là đủ. Nếu yêu cầu dãy thao tác theo thứ tự ưu tiên hoặc nhỏ nhất từ điển, điều kiện đó cần được xử lý riêng; số phép tối thiểu chưa tự giải quyết quy tắc chọn.

Giảm bộ nhớ khi chỉ cần con số

Một ô cần hàng trước và ô trái của hàng hiện tại, nên có thể giữ hai hàng. Chọn xâu ngắn hơn làm chiều cột để bộ nhớ phụ còn O(min(n,m)). Mỗi hàng mới phải đặt ô đầu bằng i và bảo đảm không dùng dữ liệu thừa của hàng cũ.

Nếu chỉ giữ một hàng, cần lưu riêng giá trị chéo cũ trước khi ghi đè. Đây là tối ưu dễ làm sai vì một ô d[j] đổi vai từ hàng trước sang hàng hiện tại trong cùng vòng. Hãy đối chiếu bản giảm bộ nhớ với bảng đầy đủ trên xâu ngắn trước khi dùng cho giới hạn lớn.

Giảm bảng cũng làm mất thông tin truy vết của cách đơn giản bên trên. Không thể xóa toàn bộ hàng cũ rồi vẫn truy ngược bằng những ô không còn tồn tại. Cần giữ quyết định hoặc dùng kỹ thuật tái dựng phù hợp nếu vừa muốn bộ nhớ thấp vừa cần thao tác cụ thể.

Các biến thể dễ nhầm

Nếu chỉ cho chèn và xóa, phép thay một ký tự phải thực hiện thành xóa rồi chèn, có thể tốn 2 thay vì 1. Quan hệ với LCS có ích cho đúng biến thể đó, nhưng không được mang nguyên công thức dựa trên LCS sang Levenshtein có phép thay giá 1.

Nếu cho đổi chỗ hai ký tự kề nhau bằng một phép, ab thành ba có thể chỉ tốn 1 trong mô hình mới. Code Levenshtein chuẩn ở đây trả 2. Nếu mỗi loại thao tác có trọng số riêng, cộng đúng chi phí thay vì hằng 1, đồng thời xem lại những tính chất như đối xứng khi giá chèn và xóa khác nhau.

Kiểm bằng BFS trên các xâu nhỏ

Để tự kiểm tra trên các xâu thật ngắn (độ dài ≤ 5), bạn có thể dùng BFS coi mỗi xâu là một đỉnh và mỗi phép chèn, xóa hoặc thay một ký tự là một cạnh chi phí 1 để tìm số bước biến đổi ít nhất tới xâu đích, qua đó kiểm tra độc lập công thức quy hoạch động và hàng/cột cơ sở.

Các test có xâu rỗng, một phía rỗng, ký tự lặp, đảo thứ tự và khoảng trắng. Ngoài kết quả cụ thể, có thể kiểm cận dưới bằng chênh lệch độ dài và cận trên max(n,m) trong mô hình đơn vị: thay phần chung chiều dài rồi chèn/xóa phần dư luôn cho một cách trong cận đó.

Luyện ngay trên Big-O Coding

Hai bài dưới tập trung vào khoảng cách chỉnh sửa giữa hai chuỗi. Hãy kiểm bộ thao tác và chi phí mà đề cho, rồi tự làm ca xâu rỗng và ab/ba trước khi nộp. Nếu cần tối ưu bộ nhớ, giữ bản bảng làm đối chứng khi thử trên dữ liệu nhỏ.

Câu hỏi thường gặp

Nguồn tham khảo

• CSES: Edit Distance
• MIT: Dynamic programming lecture notes
• Python FAQ: multidimensional lists