CFSDN nhấn mạnh vào giá trị tạo ra nguồn mở và chúng tôi cam kết xây dựng nền tảng chia sẻ tài nguyên để mọi nhân viên CNTT có thể tìm thấy thế giới tuyệt vời của bạn tại đây.

Bài viết blog CFSDN bitmap và bộ lọc nở cho ứng dụng băm C++ này được tác giả sưu tầm và biên soạn. Nếu bạn quan tâm đến bài viết này, hãy nhớ thích nó.

Bộ lọc bitmap và nở cho ứng dụng băm C++

1. Bản đồ bit

1. Khái niệm bitmap

Cái gọi là bitmap sử dụng mỗi bit để lưu trữ một trạng thái nhất định. Nó phù hợp với các tình huống trong đó dữ liệu lớn và dữ liệu không được lặp lại. Nó thường được sử dụng để xác định xem một dữ liệu nhất định có tồn tại hay không.

2. Câu hỏi phỏng vấn Bitmap

Cho 4 tỷ số nguyên không dấu duy nhất, chưa được sắp xếp. Cho một số nguyên không dấu, làm thế nào để xác định nhanh xem một số có nằm trong 4 tỷ số này hay không. 【Tencent】.

• Truyền tải, độ phức tạp thời gian O(N).
• Sắp xếp (O(NlogN)), sử dụng tìm kiếm nhị phân: logN.
• Giải pháp bitmap.

Cho dù dữ liệu có nằm trong dữ liệu số nguyên đã cho hay không, kết quả có tồn tại hay không, chính xác là hai trạng thái. Sau đó, một bit nhị phân có thể được sử dụng để biểu thị thông tin về việc dữ liệu có tồn tại hay không. Nếu bit nhị phân là 1, điều đó có nghĩa là nó. tồn tại, nếu bằng 0 nghĩa là không tồn tại. Ví dụ:

3. Triển khai bitmap

#include#include#includekhông gian tên yyw{class bitset{public:bitset(size_t N){ _bits.resize(N / 32 + 1, 0); /Đặt bit x thành 1void set(size_t x){ size_t index = x / 32 //Ánh xạ số nguyên size_t trong đó x là pos = x % 32; //Ánh xạ vị trí của x trong số nguyên_bits[index] |= (1 << pos); _num++;}//Đặt bit của x bit thành 0void reset(size_t x ){ size_t index = x / 32; size_t pos = x % 32; _bits[index] &= ~(1 << pos); _num--;}//Xác định xem bit x có tồn tại hay không bool test(size_t x){ size_t index = x / 32; size_t pos = x % 32; return _bits[index] & (1 << pos); }// Tổng số bit trong bitmap size_t size(){ return _num;}private:std::vector _bits;size_t _num; //Lượng dữ liệu được lưu trữ trong ánh xạ};void tes_bitset(){bitset bs(100);bs.set(99);bs.set(98);bs.set(97);bs.set(10) ;for (size_t i = 0; i < 100; i++){ printf("[%d]:%d\n", i, bs.test(i));}//4 tỷ dữ liệu, xác định xem có một số nhất định trong dữ liệu//bs.reset(-1);//bs.reset(pow(2, 32));}}

4. Ứng dụng bitmap

• Nhanh chóng tìm thấy liệu một dữ liệu số nguyên nhất định có nằm trong một tập hợp hay không.
• Loại.
• Tìm giao điểm, hợp, v.v. của hai tập hợp.
• Đánh dấu khối đĩa trong hệ điều hành.

2. Bộ lọc hoa

1. Đề xuất bộ lọc Bloom

Khi chúng tôi sử dụng ứng dụng tin tức để xem tin tức, nó sẽ liên tục đề xuất nội dung mới cho chúng tôi. Mỗi lần đề xuất, nó sẽ nhắc lại và xóa nội dung mà chúng tôi đã xem. Câu hỏi đặt ra là, hệ thống đề xuất ứng dụng khách tin tức thực hiện loại bỏ trùng lặp đẩy như thế nào? Máy chủ được sử dụng để ghi lại tất cả các hồ sơ lịch sử mà người dùng đã xem. Khi hệ thống khuyến nghị đưa ra tin tức, nó sẽ lọc ra các hồ sơ lịch sử của từng người dùng và lọc ra những hồ sơ đã tồn tại. Làm thế nào để tìm kiếm nhanh chóng?

• Việc sử dụng bảng băm để lưu trữ hồ sơ người dùng có nhược điểm là lãng phí dung lượng.
• Việc sử dụng bitmap để lưu trữ hồ sơ người dùng có nhược điểm là không thể xử lý xung đột băm.
• Kết hợp băm với bitmap, tức là bộ lọc nở.

2. Khái niệm về bộ lọc Bloom

Bộ lọc Bloom là một cấu trúc dữ liệu xác suất nhỏ gọn và thông minh được đề xuất bởi Burton Howard Bloom vào năm 1970. Nó được đặc trưng bởi tính năng chèn và truy vấn hiệu quả. Nó có thể được sử dụng để cho bạn biết "thứ gì đó không được tồn tại hoặc có thể tồn tại", nó sử dụng nhiều hàm băm. để ánh xạ dữ liệu vào cấu trúc bitmap. Phương pháp này không chỉ có thể cải thiện hiệu quả truy vấn mà còn tiết kiệm rất nhiều dung lượng bộ nhớ.

3. Chèn bộ lọc Bloom

Lớp cơ bản của bộ lọc Bloom là một bitmap:

struct HashStr1{//BKDR1size_t operator()(const std::string& str){ size_t hash = 0; for (size_t i = 0; i < str.size(); i++) { hash *= 131; [i]; } hàm băm trả về;}};struct HashStr2{//RSHashsize_t operator()(const std::string& str){ size_t hash = 0; size_t magic = 63689; //Số ma thuật cho (size_t i = 0; i < str.size();i++) { hash *= magic hash += str[i] magic *; = 378551; } hàm băm trả về;}};struct HashStr3{//SDBHashsize_t operator()(const std::string& str){ size_t hash = 0; for (size_t i = 0; i < str.size(); i++) { hash *= 65599; hash += str[i]; return hash;}};//Giả sử các phần tử lọc nở Kiểu là K. Nếu loại là K, bạn cần định cấu hình mẫu functorclass Bloomfilter{public:bloomfilter(size_t num) :_bs(5*num) , _N(5*num){}void set(const K& key){ size_t index1 = Hash1()(key) % _N; )(khóa) % _N; size_t index3 = Hash3()(key) % _N; _bs.set(index1); //Đặt cả ba vị trí thành 1 _bs.set(index2); _bs.set(index3);}}

4. Tìm kiếm bộ lọc Bloom

Ý tưởng của bộ lọc Bloom là ánh xạ một phần tử vào một bitmap bằng cách sử dụng nhiều hàm băm, do đó bit ở vị trí được ánh xạ phải là 1. Do đó, bạn có thể tìm kiếm theo cách sau: Tính toán xem vị trí bit tương ứng với từng giá trị băm có được lưu bằng 0 hay không, nghĩa là phần tử đó không được nằm trong bảng băm, nếu không nó có thể nằm trong bảng băm. bảng băm.

bool test(const K& key){ size_t index1 = Hash1()(key) % _N; if (_bs.test(index1) == false) { return false; } size_t index2 = Hash1()(key) % _N; (_bs.test(index2) == false) { return false; } size_t index3 = Hash3()(key) % _N; (_bs.test(index3) == false) { return false; } return true; //Nhưng ở đây nó không nhất thiết đúng và có thể có phán đoán sai // Phán đoán không đúng và có thể có phán đoán sai lầm về việc bị phán xét}

Lưu ý: Nếu bộ lọc Bloom cho biết một phần tử không tồn tại thì phần tử đó không được tồn tại. Nếu phần tử đó tồn tại, phần tử đó có thể tồn tại, bởi vì một số hàm băm có những đánh giá sai nhất định.

Ví dụ: khi tìm kiếm "alibaba" trong bộ lọc Bloom, giả sử rằng các giá trị băm được tính toán bởi ba hàm băm là: 1, 3, 7, trùng lặp với các bit của các phần tử khác. bộ lọc Bloom cho biết phần tử tồn tại, nhưng phần tử không tồn tại.

5. Xóa bộ lọc Bloom

Bộ lọc Bloom không thể hỗ trợ trực tiếp việc xóa vì khi một phần tử bị xóa thì các phần tử khác có thể bị ảnh hưởng.

Ví dụ: xóa phần tử "tencent" trong hình trên. Nếu bạn đặt trực tiếp vị trí bit nhị phân tương ứng với phần tử này thành 0 thì phần tử "baidu" cũng sẽ bị xóa, vì hai phần tử này nằm trên vị trí bit được tính bằng nhiều hàm băm xảy ra sự chồng chéo.

Phương pháp hỗ trợ xóa: mở rộng từng bit trong bộ lọc Bloom thành một bộ đếm nhỏ, thêm một vào k bộ đếm (địa chỉ băm được tính bằng k hàm băm) khi chèn phần tử và xóa phần tử When, giảm k bộ đếm đi một và tăng mức xóa hoạt động với chi phí chiếm nhiều không gian lưu trữ hơn.

khuyết điểm:

• Không có cách nào để xác nhận xem phần tử có thực sự nằm trong bộ lọc nở hay không.
• Có số lượng bao quanh.

6. Ưu điểm và nhược điểm của Bộ lọc Bloom

• Ưu điểm: tiết kiệm không gian, hiệu quả, có thể dán nhãn và lưu trữ mọi loại
• Nhược điểm: Có khả năng đánh giá sai và không hỗ trợ xóa

bitmap.

• Ưu điểm: tiết kiệm không gian
• Nhược điểm: Chỉ có thể phẫu thuật thẩm mỹ

3. Câu hỏi phỏng vấn dữ liệu lớn

1. Cắt băm

① Cho một file log có dung lượng lớn hơn 100G và các địa chỉ IP được lưu trong log, hãy thiết kế thuật toán tìm địa chỉ IP xuất hiện nhiều nhất? Điều kiện tương tự như câu hỏi trước, làm thế nào để tìm IP của top K? Làm cách nào để triển khai nó trực tiếp bằng các lệnh hệ thống Linux?

2. Ứng dụng bitmap

①Cho 10 tỷ số nguyên, hãy thiết kế thuật toán tìm số nguyên chỉ xuất hiện một lần?

② Cho hai tệp, mỗi tệp có 10 tỷ số nguyên và chúng ta chỉ có 1G bộ nhớ, làm cách nào để tìm giao điểm của hai tệp?

• Tùy chọn 1:Ánh xạ các số nguyên trong một trong các tệp 1 thành bitmap, đọc các số nguyên trong tệp 2 còn lại và xác định xem chúng có nằm trong bitmap hay không. Nếu có thì giao điểm là giao điểm. Tiêu thụ bộ nhớ 50OM
• Tùy chọn 2:Ánh xạ các số nguyên từ tệp 1 vào bitmap 1, ánh xạ các số nguyên từ tệp 2 vào bitmap 2, sau đó theo bit AND các số trong hai bitmap. Giao điểm với bit l1 là giao điểm. Tiêu thụ 1G bộ nhớ.

③Biến dạng ứng dụng Bitmap: 1 tệp có 10 tỷ int, bộ nhớ 1G, thuật toán thiết kế để tìm tất cả các số nguyên xuất hiện không quá 2 lần?

• Câu hỏi này có ý tưởng tương tự như câu hỏi 1 ở trên.
• Câu hỏi này không nên tìm kiếm quá 2 lần, tức là phải tìm thấy 1 và 2 lần.
• Câu hỏi này vẫn sử dụng hai chữ số để biểu thị một số, được biểu thị bằng số 00 xuất hiện 0 lần, 01 xuất hiện một lần nghĩa là D xuất hiện hai lần và 10 xuất hiện 3 lần trở lên được biểu thị bằng 11.

3. Bộ lọc hoa

① Cho hai tệp, mỗi tệp có 10 tỷ truy vấn và chúng ta chỉ có 1G bộ nhớ, làm cách nào để tìm giao điểm của hai tệp? Hãy đưa ra thuật toán chính xác và thuật toán gần đúng tương ứng?

②Làm cách nào để mở rộng BloomFilter để hỗ trợ thao tác xóa phần tử?

Đến đây là kết thúc bài viết về bitmap và bộ lọc Bloom trong ứng dụng băm C++. Để biết thêm thông tin về bitmap và bộ lọc Bloom trong ứng dụng băm C++, vui lòng tìm kiếm các bài viết trước của tôi hoặc tiếp tục duyệt các bài viết liên quan bên dưới. Tôi hy vọng bạn sẽ hỗ trợ tôi nhiều hơn trong tương lai! .

Liên kết gốc: https://blog.csdn.net/qq_44918090/article/details/120000787.

Cuối cùng, bài viết này về bitmap và bộ lọc Bloom trong các ứng dụng băm C++ kết thúc ở đây. Nếu bạn muốn biết thêm về bitmap và bộ lọc Bloom trong các ứng dụng băm C++, vui lòng tìm kiếm bài viết CFSDN hoặc duyệt các bài viết liên quan, tôi hy vọng bạn sẽ ủng hộ tôi. blog trong tương lai! .