Cấu trúc dữ liệu và Giải thuật Bài 18: Kỹ thuật đếm tần số (Frequency Array) với không gian bộ nhớ hẹp.

Trong quá trình xây dựng các dịch vụ backend hoặc lập trình vi điều khiển, bài toán đếm số lần xuất hiện của một giá trị (tần số) là cực kỳ phổ biến. Bạn có thể cần thống kê xem mã lỗi HTTP 404 xuất hiện bao nhiêu lần trong log, hoặc đếm tần suất các ký tự được gửi qua cổng Serial của vi điều khiển ESP32.

Phản xạ đầu tiên của các kỹ sư thời nay là sử dụng Bảng băm (Hash Map / map[int]int trong Golang). Tuy nhiên, Hash Map mang theo một độ trễ nhất định khi băm dữ liệu và tiêu tốn một lượng RAM đáng kể cho các cấu trúc con trỏ ngầm bên dưới. Khi làm việc trong những môi trường bộ nhớ hẹp (chỉ có vài chục KB RAM) hoặc cần xử lý hàng triệu luồng dữ liệu theo thời gian thực cực kỳ khắt khe, chúng ta cần một kỹ thuật thô sơ nhưng đạt tốc độ vật lý tối đa: Kỹ thuật đếm tần số bằng Mảng (Frequency Array).

1. Bản chất của Frequency Array (Direct Access Table)

Kỹ thuật này dựa trên một nguyên lý cốt lõi của Mảng tĩnh: Biến chính giá trị của dữ liệu đầu vào thành Chỉ mục (Index) của một mảng mới.

Giả sử bạn có một luồng dữ liệu chứa các đánh giá sao của sản phẩm (từ 1 đến 5 sao):

A = [5, 4, 5, 2, 1, 5, 4, 3, 4]

Thay vì dùng vòng lặp lồng nhau $O(n^2)$ hay Hash Map, bạn chỉ cần khởi tạo một mảng đếm freq có kích thước bằng giới hạn tối đa của giá trị đầu vào (ở đây là 6 phần tử, từ index 0 đến 5). Ban đầu, mảng chứa toàn số 0.

Duyệt qua mảng A đúng một lần:

• Gặp số 5 $\rightarrow$ Tăng freq[5]++

• Gặp số 4 $\rightarrow$ Tăng freq[4]++

• ...

Kết quả mảng freq sẽ là: [0, 1, 1, 1, 3, 3] (0 sao có 0 lượt, 1 sao có 1 lượt, 5 sao có 3 lượt).

• Thời gian thực thi: $O(n)$ để đếm, và $O(1)$ để truy vấn xem một giá trị xuất hiện bao nhiêu lần.

• Bộ nhớ tiêu tốn: $O(K)$, với $K$ là khoảng giá trị (từ Min đến Max). Ở đây chỉ tốn đúng 6 ô nhớ kiểu int liền kề nhau, không tốn bất kỳ overhead nào của cấu trúc dữ liệu phức tạp.

2. Kỹ thuật Dịch dải hạt giống (Offsetting) xử lý số âm

Điểm yếu lớn nhất của Frequency Array là không thể xử lý số âm, vì RAM không có khái niệm "Chỉ mục âm" (freq[-5] sẽ gây lỗi Out of Bounds ngay lập tức). Nếu tập dữ liệu có chứa nhiệt độ đo được dao động từ $-50^\circ C$ đến $50^\circ C$, làm sao để đếm?

Giải pháp là sử dụng Kỹ thuật Tịnh tiến (Offset):

1. Tìm giá trị nhỏ nhất trong tập dữ liệu (Min = -50).

2. Khi đếm, thay vì truy cập freq[value], ta truy cập freq[value - Min].

Ví dụ với mảng nhiệt độ T = [-5, 10, -5, 0]:

• Min là -5. Kích thước mảng đếm cần thiết là $Max - Min + 1 = 10 - (-5) + 1 = 16$.

• Gặp nhiệt độ -5: Lưu vào freq[-5 - (-5)] = freq[0].

• Gặp nhiệt độ 10: Lưu vào freq[10 - (-5)] = freq[15].

Bằng một phép trừ cực kỳ nhẹ nhàng $O(1)$ ở mức CPU, bạn đã có thể "bẻ cong" giới hạn của mảng tĩnh để lưu trữ tần số cho các giá trị âm mà vẫn giữ được tốc độ truy xuất tuyệt đối.

3. Tối ưu hóa đếm ký tự (Character Hashing)

Một ứng dụng kinh điển khác của Frequency Array là xử lý chuỗi (String). Bảng mã ASCII quy định mỗi ký tự thực chất là một số nguyên từ 0 đến 255. Chữ a thường là 97, chữ z là 122.

Nếu bài toán yêu cầu: Kiểm tra xem hai chuỗi có phải là đảo chữ của nhau không (Anagram), việc sắp xếp chuỗi sẽ tốn $O(n \log n)$. Nhưng với mảng tần số, bạn giải quyết nó trong $O(n)$ không gian hẹp.

Vì bảng chữ cái tiếng Anh in thường chỉ có 26 ký tự, bạn không cần mảng 256 phần tử, chỉ cần mảng 26 phần tử và dùng công thức tịnh tiến ASCII: index = char - 'a'.

Go

func isAnagram(s string, t string) bool {
    if len(s) != len(t) {
        return false
    }
    
    // Mảng tĩnh đúng 26 phần tử (Cực kỳ thân thiện với CPU Cache)
    var freq [26]int 
    
    // Đếm tần số cho cả 2 chuỗi trong 1 vòng lặp
    for i := 0; i < len(s); i++ {
        freq[s[i] - 'a']++ // Chuỗi s cộng vào
        freq[t[i] - 'a']-- // Chuỗi t trừ đi
    }
    
    // Kiểm tra tính đồng nhất
    for _, count := range freq {
        if count != 0 {
            return false
        }
    }
    return true
}

Đoạn code trên là tiêu chuẩn vàng về tối ưu hóa bộ nhớ và tốc độ khi xử lý văn bản. Kích thước bộ nhớ $O(1)$ (luôn là 26 ô nhớ độc lập với độ dài chuỗi $n$) giúp nó chạy mượt mà ngay cả trên những hệ thống vi điều khiển yếu nhất mà không gây tràn vùng nhớ Heap.

4. Giới hạn chết người: Bộ nhớ thưa thớt (Sparse Data)

Dù siêu tốc, Frequency Array sẽ biến thành thảm họa nếu bạn sử dụng sai chỗ. Giả sử hệ thống cần đếm tần suất xuất hiện của các ID người dùng. Hệ thống có 3 user mua hàng hôm nay với ID là: 1, 5, và 1,000,000,000.

Nếu dùng mảng tần số, công thức $Max - Min + 1$ sẽ yêu cầu hệ điều hành cấp phát một mảng tĩnh chứa 1 tỷ phần tử chỉ để lưu 3 con số, gây lãng phí hàng Gigabyte RAM vô ích (Out of Memory).

Quy tắc ra quyết định:

• Dùng Frequency Array khi: Khoảng cách giữa các giá trị (Range) rất nhỏ và sát nhau (như điểm số 0-10, ký tự a-z, mã HTTP status 200-500, nhiệt độ).

• Dùng Hash Map khi: Tập dữ liệu khổng lồ, thưa thớt, hoặc giá trị là kiểu chuỗi ID phức tạp (UUID).

Kỹ thuật đếm tần số không chỉ dừng lại ở việc tìm số lượng. Nếu nâng tầm nó lên, nó chính là lõi của thuật toán sắp xếp siêu tốc Counting Sort (sẽ được bàn ở Chương 12).

Tiếp nối việc làm chủ các mảnh ghép tư duy thuật toán, chúng ta sẽ bước vào hai bài toán kinh điển định hình lịch sử phỏng vấn lập trình. Bài đầu tiên là một viên ngọc toán học giúp bạn tìm ra giai đoạn sinh lời cao nhất trong một biểu đồ tài chính hỗn loạn.