Cấu trúc dữ liệu và Giải thuật Bài 25: Thuật toán Boyer-Moore Majority Vote.

Trong các hệ thống phân tán hoặc xử lý luồng dữ liệu lớn (Data Streaming), chúng ta thường xuyên đối mặt với bài toán tìm kiếm phần tử chiếm đa số. Bài toán được phát biểu đơn giản: Tìm phần tử xuất hiện nhiều hơn $\lfloor n/2 \rfloor$ lần trong một mảng có kích thước $n$.

Nếu dùng Bảng băm (Hash Map) để đếm tần số, bạn giải quyết bài toán trong thời gian $O(n)$ nhưng phải trả giá bằng $O(n)$ không gian bộ nhớ. Nếu sắp xếp mảng rồi lấy phần tử ở giữa, bạn tốn $O(1)$ bộ nhớ nhưng thời gian lại bị đẩy lên $O(n \log n)$.

Thuật toán Boyer-Moore Majority Vote được phát minh năm 1981 bởi Robert S. Boyer và J Strother Moore đã phá vỡ rào cản này, tìm ra phần tử đa số với thời gian tuyến tính $O(n)$ và bộ nhớ tĩnh tuyệt đối $O(1)$.

1. Tư duy "Đấu trường sinh tử"

Thuật toán Boyer-Moore không đếm chính xác số lần xuất hiện của từng phần tử. Thay vào đó, nó dựa trên một nguyên lý logic toán học cực kỳ sắc bén: Nếu một phần tử chiếm hơn một nửa số lượng trong mảng, thì số lượng của nó chắc chắn lớn hơn tổng số lượng của tất cả các phần tử khác cộng lại.

Hãy tưởng tượng mảng là một đấu trường, và các con số là những chiến binh thuộc các bộ tộc khác nhau.

• Bạn đưa 2 chiến binh thuộc 2 bộ tộc khác nhau ra đấu tay đôi. Cả hai sẽ "triệt tiêu" lẫn nhau (cùng chết).

• Nếu chiến binh thuộc cùng một bộ tộc, họ sẽ hợp sức lại (tăng sức mạnh).

• Vì bộ tộc đa số có số quân đông hơn tất cả các bộ tộc khác gộp lại, nên dù tất cả các bộ tộc khác có liên minh để triệt tiêu bộ tộc đa số, cuối cùng bộ tộc đa số vẫn sẽ còn sống sót ít nhất 1 chiến binh.

2. Cơ chế hoạt động của thuật toán

Thuật toán sử dụng đúng 2 biến: candidate (Ứng viên hiện tại) và count (Sức mạnh/Số phiếu của ứng viên).

1. Duyệt qua từng phần tử của mảng.

2. Nếu count == 0: Trạng thái trống. Đặt phần tử hiện tại làm candidate mới và gán count = 1.

3. Nếu phần tử hiện tại giống với candidate: Ghi nhận thêm đồng minh, count++.

4. Nếu phần tử hiện tại khác với candidate: Triệt tiêu lẫn nhau, count--.

Dù mảng có bị xáo trộn thế nào, sau khi duyệt hết 1 lượt, phần tử trụ lại cuối cùng trong biến candidate chắc chắn là phần tử đa số (nếu phần tử đa số thực sự tồn tại).

3. Triển khai thuật toán bằng Golang

Đoạn mã sau thể hiện sự tối giản và sức mạnh của thuật toán ở mức cao nhất:

Go

func majorityElement(nums []int) int {
    candidate := 0
    count := 0
    
    for _, num := range nums {
        if count == 0 {
            // Không có ai giữ "ngai vàng", phần tử hiện tại lên nắm quyền
            candidate = num
        }
        
        // Gặp đồng minh thì tăng sức mạnh, gặp kẻ thù thì suy yếu
        if num == candidate {
            count++
        } else {
            count--
        }
    }
    
    return candidate
}

Mô phỏng với mảng [2, 2, 1, 1, 1, 2, 2]:

• num = 2: count = 0 $\rightarrow$ candidate = 2, count = 1.

• num = 2: Giống candidate $\rightarrow$ count = 2.

• num = 1: Khác candidate $\rightarrow$ count = 1 (Một cặp 1 và 2 triệt tiêu nhau).

• num = 1: Khác candidate $\rightarrow$ count = 0 (Ngai vàng trống).

• num = 1: count = 0 $\rightarrow$ candidate = 1, count = 1.

• num = 2: Khác candidate $\rightarrow$ count = 0 (Ngai vàng lại trống).

• num = 2: count = 0 $\rightarrow$ candidate = 2, count = 1.

• Kết quả cuối cùng: candidate = 2. Đúng với phần tử chiếm 4/7 vị trí trong mảng.

4. Nguyên tắc "Tin tưởng nhưng phải Xác minh" (Trust but Verify)

Bản gốc của thuật toán Boyer-Moore mặc định rằng chắc chắn có một phần tử đa số tồn tại trong mảng.

Nếu đề bài thay đổi thành: "Tìm phần tử đa số nếu có, nếu không có trả về -1". Ví dụ mảng [1, 2, 3]. Thuật toán sẽ trả về 3 làm candidate (do 3 là phần tử cuối cùng chiếm ngai vàng sau khi 1 và 2 triệt tiêu nhau), nhưng 3 chỉ xuất hiện 1 lần, hoàn toàn không phải phần tử đa số (không lớn hơn $3/2$).

Để khắc phục, chúng ta cần duyệt thêm Pass 2 (Vòng lặp thứ 2) để đếm lại chính xác tần suất của candidate duy nhất mà vòng 1 tìm được, nhằm xác minh xem nó có thực sự xuất hiện lớn hơn $\lfloor n/2 \rfloor$ lần hay không.

Go

func majorityElementVerified(nums []int) int {
    // Pass 1: Tìm Candidate
    candidate, count := 0, 0
    for _, num := range nums {
        if count == 0 {
            candidate = num
        }
        if num == candidate {
            count++
        } else {
            count--
        }
    }
    
    // Pass 2: Xác minh
    verifyCount := 0
    for _, num := range nums {
        if num == candidate {
            verifyCount++
        }
    }
    
    if verifyCount > len(nums)/2 {
        return candidate
    }
    return -1 // Không có phần tử đa số
}

Việc thêm một vòng lặp khiến tổng thời gian là $O(2n)$, nhưng theo quy tắc Big-O, nó vẫn rút gọn hoàn hảo về $O(n)$.

5. Ứng dụng trong Hệ thống thực tế

• Đồng thuận phân tán (Distributed Consensus): Trong mạng lưới blockchain hoặc các cụm database (Raft/Paxos algorithm), quyết định được thông qua nếu có trên $50\%$ số node đồng ý. Boyer-Moore được dùng như một cơ chế lọc nhanh để tìm ra kết quả ứng viên từ hàng ngàn bản tin log trước khi chạy bước xác minh cuối cùng.

• Xử lý Heavy Hitters trong Data Streaming: Khi các cảm biến IoT hoặc router mạng (Cisco, Juniper) cần theo dõi xem IP nào đang spam nhiều nhất (vượt quá 50% tổng băng thông). Việc lưu Hash Map trên thiết bị mạng là không thể do thiếu RAM, Boyer-Moore cho phép con chip đếm trực tiếp trên đường truyền chỉ với 2 thanh ghi (Registers) nhỏ gọn.