Giải thuật kiểm tra tính tách được của bảng mã
Thủ tục sau đây do Sardinas (1960), Patterson (1963) và Abramson (1963) đưa ra nhằm kiểm tra xem một bảng mã nào đó có phải là bảng mã tách được (bảng mã cho phép giải mã duy nhất) hay không.
Input: Bảng mã W
Output: Kết luận bảng mã tách được hay không tách được.
Giải thuật:
Bước khởi tạo: Gán tập hợp S 0 =W.
xác định tập hợp S1 từ S0:
- Khởi tạo S1={}
- Với ∀ wi, wj thuộc S0, ta xét: nếu wi=wjA (wj là tiền tố của wi) hoặc wj=wi A (wi là tiền tố của wj) thì thêm A (phần hậu tố) vào S1.
Bước k: xác định tập hợp Sk (k≥2) từ tập hợp S0 và Sk-1:
- Khởi tạo: Sk={}
- Với ∀ withuộc S0 và ∀ vj thuộcSk-1, ta xét: nếu wi=vjA (vj là tiền tố của wi) hoặc vj=wi A (wi là tiền tố của vj) thì thêm A (phần hậu tố) vào Sk.
Điều kiện để dừng vòng lặp:
Nếu Sk={} thì dừng và kết luận bảng mã tách được (k≥1).
Nếu tồn tại từ mã wi trong Sk hay Sk giao S0 khác rỗng thì dừng và kết luận bảng mã không tách được.
Nếu Sk=St<k thì dừng và kết luận bảng mã tách được (k≥1).
Bài toán 1- yêu cầu
Bài toán: Kiểm tra xem bảng mã W={a, c, ad, abb, bad, deb, bbcde} có phải là bảng mã tách được hay không?
Áp dụng Giải thuật kiểm tra tính tách được của một bảng mã:
Bước khởi tạo: S0={a, c, ad, abb, bad, deb, bbcde}
Bước 1: Tính S1
Khởi tạo S1={}
Vì a là tiền tố của ad nên đưa phần hậu tố “d” vào S1 => S1={d}.
Vì a là tiền tố của abb nên đưa phần hậu tố “bb” vào S1 => S1={d, bb}.
Kiểm tra điều kiện dừng: không thỏa -> qua bước 2.
Bước 2: Tính S2 từ S0 và S1.
Khởi tạo S2={}.
Vì d thuộc S1 là tiền tố của deb thuộc S0 nên đưa phần hậu tố “eb” vào S2
=> S2={eb}
Vì bbthuộc S1 là tiền tố của bbcde thuộc S0 nên đưa phần hậu tố “cde” vào S2
=> S2={eb, cde}
Kiểm tra điều kiện dừng: không thỏa -> qua bước 3.
Bài toán 1 - Áp dụng giải thuật
Bước 3: Tính S3 từ S0 và S2.
Khởi tạo S3={}.
Vì cthuộc S0 là tiền tố của cde thuộc S2 nên đưa phần hậu tố “de” vào S3
=> S3={de}
Kiểm tra điều kiện dừng: không thỏa -> qua bước 4.
Bước 4: Tính S4 từ S0 và S3.
Khởi tạo S4={}.
Vì dethuộc S3 là tiền tố của deb thuộc S0 nên đưa phần hậu tố “b” vào S4
=> S4={b}
Kiểm tra điều kiện dừng: không thỏa -> qua bước 5.
Bước 5: Tính S5 từ S0 và S4.
+ khởi tạo S5={}.
+ Vì bthuộc S4 là tiền tố của bad thuộc S0 nên đưa phần hậu tố “ad” vào S5 => S5={ad}
+ Vì bthuộc S4 là tiền tố của bbcde thuộc S0 nên đưa “bcde” vào S5
=> S5={ad, bcde}
Kiểm tra điều kiện dừng: Vì S5 có chứa từ mã ad nên dừng lại và kết luận đây là bảng mã không tách được.
Tags:
Môn học chuyên ngành