Thuật toán tìm kiếm xâu kí tự

Các thuật toán tìm kiếm xâu ký tự

Đinh Quang Huy

Bài toán tìm kiếm xâu ký tự (string searching, hay đôi khi gọi là đối sánh xâu - string

matching) là một trong những bài toán cơ bản và quan trọng trong các thuật toán xử lý về

xâu ký tự hay xử lý văn bản (text processing). Ứng dụng của nó được áp dụng phổ biến

trong các trình soạn thảo văn bản hay các chương trình tìm kiếm văn bản trên internet dựa

vào các từ khóa, tất nhiên để thực thi các bài toán phức tạp này cần rất nhiều kỹ thuật và

cách xử lý khác đi kèm. Trong khuôn khổ bài báo giành cho học sinh phổ thông chuyên

Tin, tôi muốn trình bày một số phương pháp từ đơn giản đến phức tạp đối với bài toán tìm

kiếm xâu ký tự ở thể loại đơn giản nhất. Hy vọng qua bài báo các bạn có một cách nhìn

toàn diện và sâu sắc về bài toán này, trong bài viết tác giả có chú thích một số thuật ngữ

tiếng Anh nhằm giúp bạn đọc có thêm một số thuật ngữ hay dùng trong tin học.

1. Phát biểu bài toán

Bài toán được phát biểu một cách đơn giản như sau : Tìm một (hoặc nhiều) vị trí xuất hiện

cuả một xâu ký tự P[1..m] (thường được gọi là một mẫu tìm kiếm - pattern) ở trong một

xâu ký tự lớn hơn hay trong một đoạn văn bản nào đó T[1..n], m<=n. Ví dụ ta có thể tìm

thấy vị trí của xâu “abc” trong xâu “abcababc” là 1 và 6.

Phát biểu hình thức bài toán như sau :

Gọi Σ là một tập hữu hạn (finite set) các ký tự. Thông thường, các ký tự của cả mẫu tìm

kiếm và đoạn văn bản gốc đều nằm trong Σ. Tập Σ tùy từng ứng dụng cụ thể có thể là bảng

chữ cái tiếng Anh từ A đến Z thông thường, cũng có thể là một tập nhị phân chỉ gồm hai

phần tử 0 và 1 (Σ = {0,1}) hay có thể là tập các ký tự DNA trong sinh học (Σ =

{A,C,G,T}).

Có rất nhiều cách tiếp cận, trong khuôn khổ bài báo, tác giả muốn trình bày cách tiếp cận

đầu tiến và đơn giản nhất, sau đó là một số cách tiếp cận nổi tiếng, cùng với những phân

tích và đánh giá về từng thuật toán cụ thể.

2. Cách tiếp cận đầu tiên

Phương pháp đầu tiên và đơn giản nhất có thể nghĩ đến ngay là lần lượt xét từng vị trí i

trong xâu ký tự gốc từ 1 đến n-m+1, so sánh T[i…(i+m-1)] với P[1..m] bằng cách xét từng

cặp ký tự một và đưa ra kết quả tìm kiếm. Người ta còn gọi phương pháp này là cách tiếp

cận ngây thơ (Naïve string search).

Dưới đây là thủ tục đặc tả của phương pháp này :

NAÏVE_STRING_MATCHER (T, P)