Lập trình C/C++, Lập trình Python

Thuật toán Boyer-Moore

Posted on by Đỗ Thành
Học lập trình
10
Th4
View: 75

Giới thiệu Thuật toán Boyer-Moore

Thuật toán Boyer-Moore là một thuật toán tìm kiếm chuỗi trong chuỗi được phát triển bởi Robert S. Boyer và J Strother Moore vào năm 1977. Đây là một trong những thuật toán tìm kiếm chuỗi nhanh nhất và được sử dụng rộng rãi trong các ứng dụng thực tế.

Trong quá trình tìm kiếm chuỗi, thuật toán Boyer-Moore sử dụng hai kỹ thuật: đối chiếu từ phải sang trái và bảng mẫu phù hợp (match table). Đối chiếu từ phải sang trái giúp tối ưu hóa quá trình tìm kiếm bằng cách loại bỏ các trường hợp không cần thiết. Bảng mẫu phù hợp là một bảng kỹ thuật số được tính toán trước và được sử dụng để xác định các vị trí trong mẫu mà không cần thực hiện so sánh chuỗi.

Thuật toán Boyer-Moore đã được phát triển để giải quyết vấn đề tìm kiếm chuỗi trong các văn bản lớn và được sử dụng trong các ứng dụng như tìm kiếm trong tệp tin, công cụ tìm kiếm trên web, cơ sở dữ liệu và xử lý ngôn ngữ tự nhiên.

Năm 1991, Alfred V. Aho và Margaret J. Corasick đã đưa ra một phiên bản mở rộng của thuật toán Boyer-Moore, gọi là thuật toán Aho-Corasick. Thuật toán này cho phép tìm kiếm đồng thời nhiều chuỗi trong một văn bản duy nhất.

Các bước thực hiện Thuật toán Boyer-Moore

Các bước thực hiện của thuật toán Boyer-Moore như sau:

Bước 1: Tiền xử lý tạo bảng mẫu (bad character table) cho chuỗi mẫu.

  • Bảng mẫu (bad character table) lưu trữ vị trí xuất hiện cuối cùng của mỗi ký tự trong chuỗi mẫu.
  • Nếu ký tự không có trong chuỗi mẫu, ta gán giá trị là -1.

Bước 2: Bắt đầu tìm kiếm chuỗi mẫu trong chuỗi văn bản.

  • Đặt biến i = 0 để đại diện cho vị trí hiện tại trong chuỗi văn bản.
  • Trong khi i <= (m – n) (với m là độ dài chuỗi văn bản và n là độ dài chuỗi mẫu), thực hiện các bước tìm kiếm.

Bước 3: So sánh từ phải sang trái các ký tự của chuỗi mẫu với các ký tự trong chuỗi văn bản, bắt đầu từ vị trí cuối cùng của chuỗi mẫu.

  • Nếu các ký tự phù hợp, di chuyển đến vị trí trước đó của chuỗi mẫu và chuỗi văn bản.
  • Nếu không phù hợp, di chuyển chuỗi mẫu đến vị trí của ký tự không phù hợp trong bảng mẫu (bad character table).
    • Nếu ký tự đó không xuất hiện trong chuỗi mẫu, di chuyển chuỗi mẫu đến vị trí sau ký tự không phù hợp.
    • Nếu ký tự đó xuất hiện trong chuỗi mẫu, di chuyển chuỗi mẫu đến vị trí cuối cùng xuất hiện của ký tự đó trong chuỗi mẫu và di chuyển chuỗi văn bản đến vị trí tương ứng.

Bước 4: Nếu chuỗi mẫu được tìm thấy trong chuỗi văn bản, trả về vị trí xuất hiện đầu tiên của chuỗi mẫu.

  • Nếu không tìm thấy, trả về -1.

Đây là các bước cơ bản của thuật toán Boyer-Moore. Các phiên bản cải tiến của thuật toán có thể có các bước thêm hoặc được tối ưu hóa để giảm thiểu số lượng so sánh chuỗi và tăng tốc độ tìm kiếm.

Ví dụ về thuật toán Boyer-Moore

Giả sử chúng ta muốn tìm kiếm chuỗi “abc” trong chuỗi “abacababcababc”. Đầu tiên, chúng ta sẽ xem xét vị trí cuối cùng của “c” trong “abc”, tức là vị trí thứ 2. Nếu ký tự “c” không xuất hiện trong chuỗi mẫu, chúng ta sẽ tìm kiếm tiếp tục từ phải sang trái cho đến khi tìm được một ký tự xuất hiện trong chuỗi mẫu.

Tiếp theo, chúng ta di chuyển chuỗi mẫu qua phải sao cho ký tự cuối cùng của chuỗi mẫu “c” phù hợp với ký tự đang được xem xét trong chuỗi văn bản. Nếu ký tự cuối cùng của chuỗi mẫu không phù hợp với ký tự đang xét, chúng ta sẽ di chuyển chuỗi mẫu đến vị trí cuối cùng của ký tự xuất hiện cuối cùng trong chuỗi văn bản.

Ví dụ trên được minh họa bằng cách sau:

Bước 1: Tìm vị trí cuối cùng của ký tự “c” trong chuỗi mẫu “abc”, đó là vị trí thứ 2 từ phải sang trái.

Bước 2: Bắt đầu tìm kiếm chuỗi mẫu từ vị trí cuối cùng của ký tự “c” trong chuỗi văn bản, tức là vị trí thứ 2.

abacababcababc abc

Bước 3: So sánh ký tự cuối cùng của chuỗi mẫu “c” với ký tự đang xét trong chuỗi văn bản, đó là “b”. Hai ký tự không phù hợp.

Bước 4: Di chuyển chuỗi mẫu đến vị trí cuối cùng của ký tự “b” xuất hiện cuối cùng trong chuỗi văn bản, tức là vị trí thứ 7.

abacababcababc abc

Bước 5: So sánh ký tự cuối cùng của chuỗi mẫu “c” với ký tự đang xét trong chuỗi văn bản, đó là “c”. Hai ký tự phù hợp.

Bước 6: Tìm thấy chuỗi mẫu “abc” trong chuỗi văn bản.

Cài đặt Thuật toán Boyer-Moore với Python

def boyer_moore_search(text, pattern):
    n = len(text)
    m = len(pattern)
    # Tạo bảng mẫu
    bc_table = [-1] * 256
    for i in range(m):
        bc_table[ord(pattern[i])] = i
    # Bắt đầu tìm kiếm
    i = 0
    while i <= n - m:
        j = m - 1
        while j >= 0 and pattern[j] == text[i+j]:
            j -= 1
        if j == -1:
            return i
        else:
            # Di chuyển chuỗi mẫu đến vị trí mới
            bad_char_shift = j - bc_table[ord(text[i+j])]
            if bad_char_shift < 1:
                bad_char_shift = 1
            i += bad_char_shift
    # Không tìm thấy chuỗi mẫu trong chuỗi văn bản
    return -1
text = "ABCABDABACDABABCABD"
pattern = "ABD"
result = boyer_moore_search(text, pattern)
print("Vị trí đầu tiên của chuỗi mẫu là:", result)

Cài đặt Thuật toán Boyer-Moore với C++

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

vector<int> generate_bad_char_table(const string& pattern) {
    vector<int> bad_char_table(256, -1);
    int pattern_length = pattern.length();
    for (int i = 0; i < pattern_length; i++) {
        bad_char_table[static_cast<int>(pattern[i])] = i;
    }
    return bad_char_table;
}

int boyer_moore_search(const string& text, const string& pattern) {
    int text_length = text.length();
    int pattern_length = pattern.length();

    // Tạo bảng so khớp ký tự sai (bad character table)
    vector<int> bad_char_table = generate_bad_char_table(pattern);

    // Di chuyển chuỗi mẫu theo quy tắc lùi của bảng so khớp ký tự sai (bad character table)
    int i = pattern_length - 1;
    while (i < text_length) {
        int j = pattern_length - 1;
        while (text[i] == pattern[j]) {
            if (j == 0) {
                return i;
            }
            i--;
            j--;
        }
        i += max(pattern_length - j, 1 + bad_char_table[static_cast<int>(text[i])]);
    }

    return -1;
}

int main() {
    string text = "ABCABDABACDABABCABD";
    string pattern = "ABD";
    int result = boyer_moore_search(text, pattern);
    cout << "Vị trí đầu tiên của chuỗi mẫu là: " << result << endl;
    return 0;
}

Đánh giá độ phức tạp của Thuật toán Boyer-Moore

Độ phức tạp của thuật toán Boyer-Moore phụ thuộc vào độ dài của chuỗi văn bản và chuỗi mẫu. Trong trường hợp tốt nhất, độ phức tạp là O(n/m), trong đó n là độ dài của chuỗi văn bản và m là độ dài của chuỗi mẫu. Trong trường hợp xấu nhất, độ phức tạp là O(nm).

Độ phức tạp trong trường hợp tốt nhất xảy ra khi thuật toán có thể loại bỏ nhiều ký tự của chuỗi văn bản khi tìm kiếm chuỗi mẫu. Điều này xảy ra khi các ký tự của chuỗi văn bản không có trong chuỗi mẫu hoặc chỉ xuất hiện ở cuối của chuỗi mẫu.

Độ phức tạp trong trường hợp xấu nhất xảy ra khi tất cả các ký tự của chuỗi văn bản đều trùng khớp với các ký tự của chuỗi mẫu, nên ta phải thực hiện tất cả các so sánh ký tự. Tuy nhiên, trong thực tế, thuật toán Boyer-Moore có hiệu suất cao hơn so với nhiều thuật toán tìm kiếm khác như Brute Force hay KMP (Knuth-Morris-Pratt) vì nó có khả năng loại bỏ nhiều ký tự của chuỗi văn bản khi tìm kiếm chuỗi mẫu.

7 thoughts on “Thuật toán Boyer-Moore”

  2. sklep says:

    Good day! Do you know if they make any plugins to assist with SEO?
    I’m trying to get my blog to rank for some targeted keywords but I’m not seeing very good
    success. If you know of any please share. Thanks!
    You can read similar art here: Dobry sklep

    Trả lời
  3. ecommerce says:

    Hello! Do you know if they make any plugins to assist with SEO?
    I’m trying to get my blog to rank for some targeted keywords but I’m not seeing very good gains.
    If you know of any please share. Kudos! You can read similar text here: Dobry sklep

    Trả lời

Trả lời

Email của bạn sẽ không được hiển thị công khai. Các trường bắt buộc được đánh dấu *