Tôi có một bộ 100 triệu chuỗi, mỗi chuỗi dài tối đa 63 ký tự. Tôi có rất nhiều không gian đĩa và bộ nhớ rất ít (512 MB). Tôi cần truy vấn sự tồn tại một mình và không lưu trữ siêu dữ liệu bổ sung.Cách hiệu quả để kiểm tra sự tồn tại trong một tập hợp lớn các chuỗi
Giải pháp thực tế của tôi là btree BDB. Có lựa chọn thay thế nào thích hợp hơn không? Tôi biết về leveldb và Kyoto Cabinet, nhưng không đủ quen thuộc để xác định ưu điểm.
Nếu dương tính giả được chấp nhận, thì một giải pháp có thể là sử dụng bloom filter. Các bộ lọc Bloom tương tự như các bảng băm, nhưng thay vì sử dụng một giá trị băm để lập chỉ mục một bảng các nhóm, nó sử dụng nhiều băm để lập chỉ mục một mảng bit. Các bit tương ứng với các chỉ số đó được thiết lập. Sau đó, để kiểm tra xem một chuỗi có nằm trong bộ lọc hay không, chuỗi được băm một lần nữa và nếu các chỉ mục tương ứng được đặt thì chuỗi đó là "trong" bộ lọc.
Nó không lưu trữ bất kỳ thông tin nào về các chuỗi, vì vậy nó sử dụng rất ít bộ nhớ - nhưng nếu có xung đột giữa hai chuỗi, không có độ phân giải xung đột nào là có thể. Điều này có nghĩa là có thể có các kết quả dương tính giả (vì một chuỗi không có trong bộ lọc có thể băm thành các chỉ mục giống như một chuỗi trong bộ lọc). Tuy nhiên, có thể không có âm bản sai; bất kỳ chuỗi nào thực sự nằm trong tập hợp sẽ được tìm thấy trong bộ lọc nở.
Có một số fewPythonimplementations. Nó cũng không khó để cuộn của riêng bạn; Tôi nhớ lại mã hóa một bộ lọc nở nhanh và bẩn ngay khi sử dụng bitarray s đã hoạt động khá tốt.
Làm thế nào để "thực hiện nhanh chóng và bẩn của bạn giải quyết các mặt tích cực sai? – martineau
@martineau, vâng, nó không thực sự. Các tích cực sai được chấp nhận trong trường hợp của tôi. Tôi đã lặp lại trên một tập dữ liệu rất lớn, tìm kiếm các bản sao có thể.Tôi không cần phải biết chắc chắn rằng chúng trùng lặp; Tôi chỉ đang làm mỏng bộ dữ liệu để xử lý thêm. – senderle
Bạn nói bạn có nhiều đĩa, phải không? Một tùy chọn là lưu trữ các chuỗi dưới dạng tên tệp trong các thư mục con lồng nhau. Bạn có thể có thể sử dụng các dây trực tiếp:
d/r/e/w/ searshoặc bằng cách lấy một hash của chuỗi và sau một quá trình tương tự:
f0/10/fe/6e/20d12ed895c10b93b2f81c6e.Hãy nghĩ về nó như một cơ sở dữ liệu NoSQL được tối ưu hóa dựa trên bảng băm.
lợi ích Side:
+1 cho sự sáng tạo - nhưng có thể chậm bằng cách sử dụng hệ điều hành để kiểm tra sự tồn tại của các tệp lồng nhau sâu sắc như vậy, chưa kể đến việc tạo tất cả chúng ngay từ đầu. – martineau
Thực tế bây giờ tôi nghĩ về nó nhiều hơn, tại sao có một loạt các thư mục con lồng nhau? Thay vào đó, chỉ cần tạo một tệp rỗng cho mỗi chuỗi và lưu trữ tất cả chúng trong một thư mục duy nhất. Tất nhiên có thể có một số vấn đề về hệ thống tập tin ... – martineau
Nếu không có thử nghiệm, tôi không chắc liệu nó có bị chậm hay không. Nó thực sự có thể được khá spritely tùy thuộc vào hệ thống tập tin. Rất nhiều hệ thống tập tin nhanh hơn nhiều với các thư mục nhỏ hơn, và hầu hết (tất cả?) Tìm kiếm thư mục bộ nhớ cache FSes hiện đại. Đó là động lực cho các thư mục con lồng nhau. –
Bạn có thể chịu đựng một số lần dương tính giả không? – senderle
Phủ định sai là không thể chấp nhận; thỉnh thoảng những kết quả dương tính giả có khả năng chấp nhận được. –
Chỉ cần lưu trữ tất cả trong một tập hợp 'và để cho trình quản lý bộ nhớ ảo của hệ điều hành nó vào đĩa khi cần thiết. Bạn cũng có thể lưu nó vào đĩa bằng cách sử dụng 'pickle'. Không cần phải xây dựng một cơ sở dữ liệu. – martineau