Dòng họ Bloom
Đây là bài đầu tiên trong chuỗi bài "Từ gốc đến ngọn". Tất nhiên, đây chỉ là mong muốn của bản thân muốn trình bày ngọn ngành vấn đề, nhưng hiểu biết của một người thì có hạn, không thể trình bày hết được, những thứ mình còn không biết nó tồn tại thì không cách nào trình bày được.
Nói sơ qua về cái dòng họ bloom này, đây là một dòng cấu trúc dữ liệu xác suất, mà thú vị ở chỗ nó rất tham lam. Tôn chỉ của các cấu trúc dữ liệu trong dòng này là làm sao để kiểm tra sự tồn tại của một phần tử trong tập hợp với chị phí thấp cả về tốc độ và bộ nhớ. Thường thì tốc độ thực thi và bộ nhớ nó sẽ đi ngược với nhau, và mình phải chọn lựa cho phù hợp cho từng bài toán (trade-off).
Đễ dẫn nhập vô dòng họ này, trước tiên mình nên biết về tìm kiếm trong từ điểm. Để tìm kiếm từ điển có thể dùng trie (khác với tree nha, đọc kĩ, không lại nhầm) nó thường nhanh hơn bảng băm và tốn ít bộ nhớ hơn. Bảng băm thì chắc ai cũng biết rồi, không cần nói nhiều.
Với việc dùng bảng băm để kiểm tra liệu một phần tử có nằm trong tập hợp hay không thì nó sẽ tốn nhiều chi phí bộ nhớ để lưu hash. Và kích thước bộ nhớ sẽ tăng lên theo thời gian, khi mà mình liên tục thêm các phần tử vào tập hợp. Vậy có cách gì để thực hiện điều này mà ít tốn bộ nhớ hơn không? Câu trả lời là bloom filter. Tuy nhiên, điểm yếu của bloom filter là nó có trường hợp false positive, và tốn thêm ít chi phí (do phải thực hiện k hàm băm với phần tử cần kiểm tra), thực ra thì nó cũng không nhiều hơn mấy, nhưng bù lại, bộ nhớ nó sử dụng là cố định. (Tìm đọc thêm về bloom filter để hiểu rõ hơn)
Sau khi bloom filter ra đời thì lại tiếp tục nảy sinh vấn đề mới: với bloom filter thông thường, chỉ có thể thêm phần tử vào, mà không có cách nào để xóa nó đi, điều này thật nguy hiểm, nếu ta thêm nhầm phần tử, giả sử như mình xài bloom filter 4 năm rồi, thêm quá trời phần tử, rồi hôm nay thêm nhầm, xác định là phải tạo bloom filter mới rồi thêm các phần tử trước giờ đã thêm. Có một giải pháp được đưa ra là dùng 2 bloom filter, một cái ghi nhận phần tử thêm vào và một cái khác ghi nhận phần tử đã bị xóa. Tuy nhiên, việc này thì tầm thường quá. Người ta đã làm ra cái filter mới tên là cukoo filter.
Tuy nhiên, vấn đề chưa dừng lại ở đó. Thêm rồi, xóa rồi, nhưng người ta còn tham lam làm được nhiều việc hơn trên cái bộ nhớ bé nhỏ mà bloom filter sử dụng. Người ta muốn đếm xem một phần tử đã được thêm vào bloom filter mấy lần. Ứng dụng trong việc, đếm xem người ta đã truy cập trang web của mình mấy lần. Và giải pháp người ta dùng là counting filter và deletable bloom filter (DlBF).Giải pháp này cho phép xóa phần tử, nhưng vẫn đảm bảo không có false negative và có thể xấp xỉ được số lần xuất hiện của phần tử đó. Các bạn thấy cấu trúc dữ liệu này phế lắm không, xác định phần tử có thuộc tập hợp cũng không được 100% rồi số lần xuất hiện cũng chỉ xấp xỉ. Vì vậy sức mạnh của nó chỉ dành cho những ai hiểu được nó. Tra wiki để biết thêm những ứng dụng của bloom filter. Có loại layer bloom filter cũng đếm được số lượng, nhưng mình không tìm hiểu về nó.
Một hướng phát triển khác là stable bloom filter. Nó phá vỡ quy tắc false negative mà các dòng này luôn theo đuổi. Tất nhiên, mọi thứ trên đời đều có lý do của nó. Thằng này xuất hiện là vì trong thực tế có trường hợp dữ liệu dạng streaming. Các phần tử thì cứ đi vào liên tục, mà bộ nhớ của filter có hạn, khi vào quá ngưỡng thì false positive sẽ tăng lên. Nên một khi nó đã "đầy" thì nó sẽ bỏ bớt những thằng vào đầu, nhường chỗ trống cho những thằng vào sau mà vẫn đảm bản tỉ lệ false positive (lưu ý là bộ nhớ không tăng lên).
Rồi có bạn sẽ hỏi, vậy có cái filter nào như cái stable bloom filter mà không có false negative không? Và câu trả lời là có luôn, hầu như cái gì bạn nghỉ tới thì người ta đã làm hết rồi. Đó là scalable bloom filter, thằng này sẽ tự tăng kích thước bộ nhớ để đảm bảm tỉ lệ false positive khi ta cứ liên tục thêm phần tử vào. Tất nhiên, việc tăng kích thước cũng không nhiều so với số lượng phần tử thêm vào.
Dòng này cũng còn một số con cháu nữa, mà mình không biết hoặc biết mà lười trình bày, nên muốn tìm hiểu thêm thì các bạn tự thân vận động.
Nói sơ qua về cái dòng họ bloom này, đây là một dòng cấu trúc dữ liệu xác suất, mà thú vị ở chỗ nó rất tham lam. Tôn chỉ của các cấu trúc dữ liệu trong dòng này là làm sao để kiểm tra sự tồn tại của một phần tử trong tập hợp với chị phí thấp cả về tốc độ và bộ nhớ. Thường thì tốc độ thực thi và bộ nhớ nó sẽ đi ngược với nhau, và mình phải chọn lựa cho phù hợp cho từng bài toán (trade-off).
Đễ dẫn nhập vô dòng họ này, trước tiên mình nên biết về tìm kiếm trong từ điểm. Để tìm kiếm từ điển có thể dùng trie (khác với tree nha, đọc kĩ, không lại nhầm) nó thường nhanh hơn bảng băm và tốn ít bộ nhớ hơn. Bảng băm thì chắc ai cũng biết rồi, không cần nói nhiều.
Với việc dùng bảng băm để kiểm tra liệu một phần tử có nằm trong tập hợp hay không thì nó sẽ tốn nhiều chi phí bộ nhớ để lưu hash. Và kích thước bộ nhớ sẽ tăng lên theo thời gian, khi mà mình liên tục thêm các phần tử vào tập hợp. Vậy có cách gì để thực hiện điều này mà ít tốn bộ nhớ hơn không? Câu trả lời là bloom filter. Tuy nhiên, điểm yếu của bloom filter là nó có trường hợp false positive, và tốn thêm ít chi phí (do phải thực hiện k hàm băm với phần tử cần kiểm tra), thực ra thì nó cũng không nhiều hơn mấy, nhưng bù lại, bộ nhớ nó sử dụng là cố định. (Tìm đọc thêm về bloom filter để hiểu rõ hơn)
Sau khi bloom filter ra đời thì lại tiếp tục nảy sinh vấn đề mới: với bloom filter thông thường, chỉ có thể thêm phần tử vào, mà không có cách nào để xóa nó đi, điều này thật nguy hiểm, nếu ta thêm nhầm phần tử, giả sử như mình xài bloom filter 4 năm rồi, thêm quá trời phần tử, rồi hôm nay thêm nhầm, xác định là phải tạo bloom filter mới rồi thêm các phần tử trước giờ đã thêm. Có một giải pháp được đưa ra là dùng 2 bloom filter, một cái ghi nhận phần tử thêm vào và một cái khác ghi nhận phần tử đã bị xóa. Tuy nhiên, việc này thì tầm thường quá. Người ta đã làm ra cái filter mới tên là cukoo filter.
Tuy nhiên, vấn đề chưa dừng lại ở đó. Thêm rồi, xóa rồi, nhưng người ta còn tham lam làm được nhiều việc hơn trên cái bộ nhớ bé nhỏ mà bloom filter sử dụng. Người ta muốn đếm xem một phần tử đã được thêm vào bloom filter mấy lần. Ứng dụng trong việc, đếm xem người ta đã truy cập trang web của mình mấy lần. Và giải pháp người ta dùng là counting filter và deletable bloom filter (DlBF).Giải pháp này cho phép xóa phần tử, nhưng vẫn đảm bảo không có false negative và có thể xấp xỉ được số lần xuất hiện của phần tử đó. Các bạn thấy cấu trúc dữ liệu này phế lắm không, xác định phần tử có thuộc tập hợp cũng không được 100% rồi số lần xuất hiện cũng chỉ xấp xỉ. Vì vậy sức mạnh của nó chỉ dành cho những ai hiểu được nó. Tra wiki để biết thêm những ứng dụng của bloom filter. Có loại layer bloom filter cũng đếm được số lượng, nhưng mình không tìm hiểu về nó.
Một hướng phát triển khác là stable bloom filter. Nó phá vỡ quy tắc false negative mà các dòng này luôn theo đuổi. Tất nhiên, mọi thứ trên đời đều có lý do của nó. Thằng này xuất hiện là vì trong thực tế có trường hợp dữ liệu dạng streaming. Các phần tử thì cứ đi vào liên tục, mà bộ nhớ của filter có hạn, khi vào quá ngưỡng thì false positive sẽ tăng lên. Nên một khi nó đã "đầy" thì nó sẽ bỏ bớt những thằng vào đầu, nhường chỗ trống cho những thằng vào sau mà vẫn đảm bản tỉ lệ false positive (lưu ý là bộ nhớ không tăng lên).
Rồi có bạn sẽ hỏi, vậy có cái filter nào như cái stable bloom filter mà không có false negative không? Và câu trả lời là có luôn, hầu như cái gì bạn nghỉ tới thì người ta đã làm hết rồi. Đó là scalable bloom filter, thằng này sẽ tự tăng kích thước bộ nhớ để đảm bảm tỉ lệ false positive khi ta cứ liên tục thêm phần tử vào. Tất nhiên, việc tăng kích thước cũng không nhiều so với số lượng phần tử thêm vào.
Dòng này cũng còn một số con cháu nữa, mà mình không biết hoặc biết mà lười trình bày, nên muốn tìm hiểu thêm thì các bạn tự thân vận động.
Comments
Post a Comment