Cách hiệu quả để lưu trữ các chuỗi

Question

Giả sử tôi có hàng triệu chuỗi. Mỗi chuỗi có giá trị int. Tôi muốn lấy giá trị này bằng chuỗi đầu vào nhưng tôi không muốn lưu trữ tất cả các chuỗi này vì chúng chiếm nhiều không gian. Tôi không thể sử dụng bảng băm vì nó cần phải lưu trữ tất cả hoặc ít nhất nhiều chuỗi trong bộ nhớ. Vì vậy, cấu trúc dữ liệu tốt cho trường hợp của tôi là gì (tôi không cần thêm hoặc xóa bất kỳ chuỗi nào, tôi đã có dữ liệu chuẩn bị và chỉ đọc được phép hoạt động)

Answer 1

Lý do của bạn không sử dụng bảng băm không âm thanh hợp lệ dựa trên thông tin giới hạn trong câu hỏi của bạn hiện tại. Nó khá hiệu quả nếu được triển khai tốt. Nó cũng có thể có lợi thế là không lãng phí bộ nhớ lưu trữ chuỗi trùng lặp nếu đó là chấp nhận được cho nhu cầu của bạn, tiếp tục giảm tiêu thụ bộ nhớ nếu chuỗi trùng lặp có thể.

Bạn cũng có thể lưu trữ một biểu mẫu nén của mỗi chuỗi trong bảng băm nếu bạn sáng tạo về cách bạn tra cứu. Chuỗi dài bao lâu?

Answer 2

Sử dụng một trie để ngăn chặn việc lưu trữ chuỗi con chung ..

Answer 3

Bạn có thể muốn nhìn vào Judy tree, được thiết kế để được cả hai nhanh chóng và nhỏ gọn, và có một phiên bản được thiết kế cho các phím chuỗi. Triển khai của nó có sẵn trên sourceforge.

Answer 4

Nếu bạn có thể xử lý trước danh sách từ hãy xem các băm hoàn hảo, như CMPH. (gperf là khác, nhưng dường như tối ưu hóa cho các tập dữ liệu nhỏ hơn.)

Từ các tài liệu CMPH:

Một hàm băm hoàn hảo bản đồ một bộ tĩnh của phím n thành một tập hợp các số nguyên m mà không va chạm, trong đó m lớn hơn hoặc bằng n. Nếu m bằng n, hàm được gọi là tối thiểu.

...

Các CMPH Thư viện đóng gói các thuật toán mới nhất và hiệu quả hơn trong một, sản xuất chất lượng, API nhanh dễ sử dụng. Thư viện được thiết kế để làm việc với các mục lớn không thể vừa với bộ nhớ chính. Nó đã được sử dụng thành công để xây dựng các hàm băm hoàn hảo tối thiểu cho các bộ với hơn 100 triệu khóa, ...