Chuyên đề bồi dưỡng hsg tin học THPT NĂM 2021 - 2022: CHUYÊN ĐỀ TÌM KIẾM CHUỖI

[Yopovn]

Chuyên đề bồi dưỡng hsg tin học THPT NĂM 2021 - 2022: CHUYÊN ĐỀ TÌM KIẾM CHUỖI

Tìm kiếm chuỗi​

I. Mở đầu​

Dữ liệu trong máy tính được lưu trữ dưới rất nhiều dạng khác nhau, nhưng sử dụng chuỗi vẫn là một trong những cách rất phổ biến. Trên chuỗi các đơn vị dữ liệu không có ý nghĩa quan trọng bằng cách sắp xếp của chúng. Ta có thể thấy các dạng khác nhau của chuỗi như ở các file dữ liệu, trên biểu diễn của các gen, hay chính văn bản chúng ta đang đọc.



Một phép toán cơ bản trên chuỗi là đối sánh mẫu (pattern matching), bài toán yêu cầu ta tìm ra một hoặc nhiều vị trí xuất hiện của mẫu trên một văn bản.. Trong đó mẫu và văn bản là các chuỗi có độ dài N và M (M ≤ N), tập các ký tự được dùng gọi là bảng chữ cái å, có số lượng là d.



Việc đối sánh mẫu diễn ra với nhiều lần thử trên các đoạn khác nhau của văn bản. Trong đó cửa sổ là một chuỗi M ký tự liên tiếp trên văn bản. Mỗi lần thử chương trình sẽ kiểm tra sự giống nhau giữa mẫu với cửa sổ hiện thời. Tùy theo kết quả kiểm tra cửa sổ sẽ được dịch đi sang phải trên văn bản cho lần thử tiếp theo.



Trong trình bày này chúng ta sẽ quan tâm đến việc tìm kiếm tất cả các vị trí xuất hiện của mẫu trên một văn bản. Cài đặt sẽ dùng một hàm ra : Output để thông báo vị trí tìm thấy mẫu.

II. Thuật toán Brute Force​

Có lẽ cái tên của thuật toán này đã nói lên tất cả (brute nghĩa là xúc vật, force nghĩa là sức mạnh). Thuật toán brute force thử kiểm tra tất cả các vị trí trên văn bản từ 1 cho đến n-m+1. Sau mỗi lần thử thuật toán brute force dịch mẫu sang phải một ký tự cho đến khi kiểm tra hết văn bản.



Thuật toán brute force không cần công việc chuẩn bị cũng như các mảng phụ cho quá trình tìm kiếm. Độ phức tạp tính toán của thuật toán này là O(n*m)

function IsMatch(const X: string; m: integer; const Y: string; p: integer): boolean; var i: integer; begin IsMatch := false; Dec(p); for i := 1 to m do if X <> Y[p + i] then Exit; IsMatch := true; end; procedure BF(const X: string; m: integer; const Y: string; n: integer); var i: integer; begin for i := 1 to n - m + 1 do if IsMatch(X, m, Y, i) then Output(i); { Thông báo tìm thấy mẫu tại vị trí i của văn bản } end;

III. Thuật toán Knuth-Morris-Pratt​

Thuật toán Knuth-Morris-Pratt là thuật toán có độ phức tạp tuyến tính đầu tiên được phát hiện ra, nó dựa trên thuật toán brute force với ý tưởng lợi dụng lại những thông tin của lần thử trước cho lần sau. Trong thuật toán brute force vì chỉ dịch cửa sổ đi một ký tự nên có đến m-1 ký tự của cửa sổ mới là những ký tự của cửa sổ vừa xét. Trong đó có thể có rất nhiều ký tự đã được so sánh giống với mẫu và bây giờ lại nằm trên cửa sổ mới nhưng được dịch đi về vị trí so sánh với mẫu. Việc xử lý những ký tự này có thể được tính toán trước rồi lưu lại kết quả. Nhờ đó lần thử sau có thể dịch đi được nhiều hơn một ký tự, và giảm số ký tự phải so sánh lại.

Xét lần thử tại vị trí j, khi đó cửa sổ đang xét bao gồm các ký tự y[j…j+m-1] giả sử sự khác biệt đầu tiên xảy ra giữa hai ký tự x và y[j+i-1].