Video: (38) Graph theory: Luồng cực đại và Thuật toán Ford-Fulkerson (Phần 2) – Bui The Tam 2025
Việc học để đếm các đối tượng trong luồng có thể giúp bạn tìm ra các mục thường xuyên nhất hoặc sắp xếp các sự kiện thông thường và bất thường. Thuật toán này thúc đẩy các hàm băm và phác thảo gần đúng. Nó làm như vậy sau khi lọc các đối tượng trùng lặp và đếm các phần tử riêng biệt đã xuất hiện trong luồng dữ liệu.
Bạn sử dụng kỹ thuật này để giải quyết các vấn đề như tìm kiếm các truy vấn thường xuyên nhất trong công cụ tìm kiếm, các mặt hàng bán chạy nhất từ một nhà bán lẻ trực tuyến, các trang phổ biến cao trong một trang web, hoặc các cổ phiếu dễ bay hơi nhất (bằng cách đếm thời gian một cổ phiếu bán và mua).
Bạn áp dụng giải pháp cho vấn đề này, Count-Min Sketch đến luồng dữ liệu. Nó chỉ đòi hỏi một lần truyền dữ liệu và lưu giữ càng ít thông tin càng tốt. Thuật toán này được áp dụng trong nhiều tình huống thực tế (chẳng hạn như phân tích lưu lượng mạng hoặc quản lý luồng dữ liệu phân tán). Công thức đòi hỏi sử dụng một loạt các hàm băm, mỗi một liên kết với một vector bit, theo một cách tương tự như một bộ lọc Bloom, như thể hiện trong hình:
- Khởi tạo tất cả các vectơ bit thành zero trong tất cả các vị trí.
- Áp dụng hàm băm cho mỗi vector bit khi nhận một đối tượng từ một dòng. Sử dụng địa chỉ số kết quả để tăng giá trị tại vị trí đó.
- Áp dụng hàm băm cho một đối tượng và lấy giá trị tại vị trí liên quan khi được yêu cầu ước tính tần số của một đối tượng. Trong tất cả các giá trị nhận được từ các vectơ bit, bạn lấy nhỏ nhất là tần số của dòng.
Vì các vụ va chạm luôn luôn có thể xảy ra khi sử dụng hàm băm, đặc biệt là nếu vectơ bit có liên quan có vài khe, có nhiều vectơ bit ở bàn tay đảm bảo với bạn rằng ít nhất một trong số chúng giữ đúng giá trị. Giá trị của sự lựa chọn nên là nhỏ nhất vì nó không phải là hỗn hợp với số dương tính giả do va chạm.
