Tìm kiếm một từ trong văn bản theo cách nhanh nhất.

Bài đăng này đã không được cập nhật trong 6 năm

Nguồn https://stackjava.com/mot-so-thuat-toan-tim-kiem-mau##

Thầy giáo bắt code 1 chương trình tìm 1 từ nào đó trong văn bản và in ra các vị trị của nó. ok, viết vèo cái là xong. Nhưng khi văn bản của bản lên tới hàng trăm trang, hàng nghìn trang, dữ liệu tới cả hàng GB hoặc hơn thế nữa thì tìm bao giờ mới xong? Lên google gõ 'tìm kiếm xâu', 'string matching' thì trời hỡi nó ra bao nhiêu là thuật toán khác nhau.

Giới thiệu vấn đề

Đối sánh xâu (String matching) là một chủ đề quan trọng trong lĩnh vực xử lý văn bản. Các thuật toán đối sánh xâu được xem là những thành phần cơ sở được cài đặt cho các hệ thống thực tế đang tồn tại trong hầu hết các hệ điều hành. Hơn thế nữa, các thuật toán đối sánh xâu cung cấp các mô hình cho nhiều lĩnh vực khác nhau của khoa học máy tính: xử lý ảnh, xử lý ngôn ngữ tự nhiên, tin sinh học và thiết kế phần mềm.

String-matching được hiểu là việc tìm một hoặc nhiều xâu mẫu (pattern) xuất hiện trong một văn bản (có thể là rất dài). Ký hiệu xâu mẫu hay xâu cần tìm là X =(x0, x1,..,xm-1) có độ dài m. Văn bản Y =(y0, y1,..,yn-1) có độ dài n. Cả hai xâu được xây dựng từ một tập hữu hạn các ký tự Alphabet ký hiệu là S với kích cỡ là s. Như vậy một xâu nhị phân có độ dài n ứng dụng trong mật mã học cũng được xem là một mẫu. Một chuỗi các ký tự ABD độ dài m biểu diễn các chuỗi AND cũng là một mẫu.

Input:

Xâu mẫu X =(x0, x1,.., xm-1), độ dài m.
Văn bản Y =(y0, x1,.., yn-1), độ dài n. Output: Tất cả vị trí xuất hiện của X trong Y.

Các thuật toán tìm kiếm mẫu, string.

Chính vì sự cần thiết và quan trọng của chủ đề này dẫn tới sự xuất hiện của hàng chục, hàng trăm thuật toán liên quan nhằm cải thiện tốc độ so sánh xâu, cải thiện độ phức tạp… Ở bài này mình sẽ giới thiệu 1 số thuật toán tìm kiếm mẫu khác sau: