API đơn giản để truy cập ngẫu nhiên vào một tệp dữ liệu nén

Question

Vui lòng đề xuất một công nghệ phù hợp với nhiệm vụ sau.

Tôi có một đoạn dữ liệu khá lớn (500MB), về cơ bản là ma trận số. Các entropy dữ liệu là thấp (nó nên được nén tốt) và lưu trữ là đắt tiền, nơi nó ngồi.

Điều tôi đang tìm kiếm, là nén nó bằng thuật toán nén tốt (Giống như, nói, GZip) với các điểm đánh dấu cho phép truy cập ngẫu nhiên rất thường xuyên. Truy cập ngẫu nhiên như trong "đọc byte từ vị trí [địa chỉ 64 bit] trong luồng gốc (không nén)". Đây là một chút khác biệt so với các thư viện làm lệch hướng cổ điển như ZLIB, điều này sẽ cho phép bạn giải nén luồng liên tục. Những gì tôi muốn, là có sự truy cập ngẫu nhiên ở độ trễ của, nói rằng, càng nhiều càng tốt 1MB công việc giải nén cho mỗi byte đọc.

Tất nhiên, tôi hy vọng sẽ sử dụng thư viện hiện có thay vì phát minh lại bánh xe NIH.

Answer 1

Thuật toán nén thường hoạt động trong các khối mà tôi nghĩ để bạn có thể tìm ra thứ gì đó dựa trên kích thước khối.

Answer 2

Tôi khuyên bạn nên sử dụng Boost Iostreams Library. Boost.Iostreams có thể được sử dụng để tạo luồng để truy cập các kết nối TCP hoặc như một khuôn khổ cho mật mã và nén dữ liệu. Thư viện bao gồm các thành phần để truy cập các tệp ánh xạ bộ nhớ, để truy cập tệp bằng cách sử dụng các mô tả tệp hệ điều hành, để chuyển đổi mã, để lọc văn bản với các biểu thức chính quy, để chuyển đổi dòng và nén và giải nén ở định dạng zlib, gzip và bzip2.

Thư viện Boost được chấp nhận bởi ủy ban tiêu chuẩn C++ như là một phần của TR2, vì vậy nó sẽ được tích hợp sẵn cho hầu hết các trình biên dịch (under std::tr2::sys). Nó cũng tương thích với nhiều nền tảng.

Boost Releases

Boost Getting Started Guide LƯU Ý: Chỉ có một số bộ phận của boost::iostreams được tiêu đề chỉ thư viện mà đòi hỏi binaries thư viện không riêng biên soạn hoặc đối xử đặc biệt khi liên kết.

Answer 3

Byte Pair Encoding cho phép truy cập ngẫu nhiên vào dữ liệu.

Bạn sẽ không nhận được nén tốt với nó, nhưng bạn đang hy sinh cây băm thích ứng (biến) cho một cây duy nhất, để bạn có thể truy cập nó.

Tuy nhiên, bạn vẫn sẽ cần một số loại chỉ mục để tìm một "byte" cụ thể. Vì bạn ổn với 1 MB độ trễ, bạn sẽ tạo chỉ mục cho mỗi 1 MB. Hy vọng rằng bạn có thể tìm ra cách để làm cho chỉ số của bạn đủ nhỏ để vẫn được hưởng lợi từ việc nén.

Một trong những lợi ích của phương pháp này là chỉnh sửa truy cập ngẫu nhiên. Bạn có thể cập nhật, xóa và chèn dữ liệu vào các đoạn tương đối nhỏ.

Nếu nó hiếm khi được truy cập, bạn có thể nén chỉ mục bằng gzip và giải mã nó khi cần.

Answer 4

Nếu bạn muốn giảm thiểu công việc liên quan, tôi chỉ cần chia nhỏ dữ liệu thành 1 MB (hoặc bất kỳ phần nào), sau đó đặt các phần vào một kho lưu trữ PKZIP. Sau đó bạn sẽ cần một chút nhỏ của mã front-end để lấy một tập tin bù đắp, và chia cho 1M để có được quyền tập tin để giải nén (và, rõ ràng, sử dụng phần còn lại để có được để bù đắp đúng trong tập tin đó).

Chỉnh sửa: Có, có mã hiện tại để xử lý việc này. Các phiên bản gần đây của giải nén Thông tin-zip (6.0 là hiện tại) bao gồm api.c.Trong số những thứ khác, bao gồm UzpUnzipToMemory - bạn chuyển tên của tệp ZIP và tên của một tệp trong lưu trữ mà bạn muốn truy xuất. Sau đó bạn nhận được một bộ đệm giữ nội dung của tập tin đó. Để cập nhật, bạn cần có api.c từ zip3.0, sử dụng ZpInit và ZpArchive (mặc dù chúng không đơn giản để sử dụng như bên giải nén).

Ngoài ra, bạn chỉ có thể chạy bản sao zip/giải nén trong nền để thực hiện công việc. Đây không phải là khá gọn gàng, nhưng chắc chắn một chút đơn giản để thực hiện (cũng như cho phép bạn chuyển đổi định dạng khá dễ dàng nếu bạn chọn).

Answer 5

1. Sắp xếp các tập tin lớn đầu tiên
2. chia nó trong khối kích thước mong muốn của bạn (1MB) với một số chuỗi trong tên (File_01, File_02, .., File_NN)
3. lấy ID đầu tiên từ mỗi đoạn cộng với tên tệp và đặt cả hai dữ liệu vào một tệp khác
4. nén các khối
5. bạn có thể tìm kiếm tệp ID bằng phương pháp bạn muốn, có thể là tìm kiếm nhị phân và mở từng tệp khi bạn cần.

Nếu bạn cần lập chỉ mục sâu, bạn có thể sử dụng thuật toán BTree với "trang" là các tệp. trên web tồn tại một số việc thực hiện điều này bởi vì có rất ít mã phức tạp.

Answer 6

Nếu bạn đang làm việc trong Java, tôi vừa xuất bản một thư viện cho điều đó: http://code.google.com/p/jzran.

Answer 7

Bạn có thể sử dụng bzip2 và làm cho API của riêng bạn khá dễ dàng dựa trên James Taylor seek-bzip2

Answer 8

Hãy nhìn vào dự án của tôi - csio. Tôi nghĩ rằng đó là chính xác những gì bạn đang tìm kiếm: giao diện giống như stdio và máy nén đa luồng bao gồm.

Đó là thư viện, được viết bằng C, cung cấp cấu trúc và chức năng CFILE cfopen, cfseek, cftello và các loại khác. Bạn có thể sử dụng nó với các tệp thông thường (không nén) và với các tệp, được nén với sự trợ giúp của tiện ích dzip. Tiện ích này có trong dự án và được viết bằng C++. Nó tạo ra kho lưu trữ gzip hợp lệ, có thể được xử lý bởi các tiện ích chuẩn cũng như với csio. dzip có thể nén trong nhiều chủ đề (xem tùy chọn -j), vì vậy nó có thể nén rất nhanh các tệp rất lớn.

sử dụng Tipical:

dzip -j4 myfile 

... 

CFILE file = cfopen("myfile.dz", "r"); 
off_t some_offset = 673820; 
cfseek(file, some_offset); 
char buf[100]; 
cfread(buf, 100, 1, file); 
cfclose(file); 

Nó được MIT cấp phép, vì vậy bạn có thể sử dụng nó trong các dự án của bạn mà không hạn chế. Để biết thêm thông tin, hãy truy cập trang dự án trên github: https://github.com/hoxnox/csio