Tôi đang tạo chỉ mục chỉ là một vài tập hợp số nguyên 32 bit đặt hàng được lưu trữ liên tục trong tệp nhị phân. Vấn đề là tập tin này phát triển khá lớn. Tôi đã nghĩ đến việc thêm một số chương trình nén nhưng đó là một chút trong chuyên môn của tôi. Vì vậy, tôi tự hỏi, thuật toán nén nào sẽ hoạt động tốt nhất trong trường hợp này? Ngoài ra, giải nén phải nhanh chóng vì chỉ mục này sẽ được sử dụng để tạo nên giao diện.Nén số nguyên được sắp xếp
Nếu bạn đang lưu trữ các số nguyên gần nhau (ví dụ: 1, 3, 4, 5, 9, 10 vv ...) thay vì một số số nguyên 32 bit ngẫu nhiên (982346 ..., 3487623412 .., v.v ...) bạn có thể làm một điều:
Tìm khác biệt giữa các con số liền kề đó sẽ như thế nào 2,1,1,4,1 ... vv (trong ví dụ của chúng tôi) và sau đó Huffman mã hóa này số.
Tôi không nghĩ rằng mã hóa Huffman sẽ hoạt động nếu bạn áp dụng trực tiếp chúng vào danh sách số ban đầu bạn có. Nếu bạn có một danh sách sắp xếp các số gần, tỷ lệ cược tốt là bạn sẽ nhận được tỷ lệ nén rất tốt bằng cách thực hiện mã hóa Huffman về số khác biệt, có thể là tỷ lệ tốt hơn so với sử dụng thuật toán LZW được sử dụng trong các thư viện Zip.
Dù sao, hãy gửi câu hỏi thú vị này.
Một điều tốt với thuật toán này là các con số không cần phải gần gũi với nhau. Miễn là có một số loại cấu trúc. Nếu có một cấu trúc của các giá trị thuật toán này sẽ bắt nó, mã hóa Huffman sẽ làm phần còn lại. – dalle
Hmm .. Thú vị! Cảm ơn bạn đã chỉ ra điều đó. Ví dụ: – Niyaz
Thực sự sẽ hoạt động tốt trên 1000,2000,3000,5000,7000,800. Nhưng có những bản phân phối khác làm cho điều này tối ưu. – MSalters
Tôi sẽ tưởng tượng Huffman coding sẽ khá thích hợp cho mục đích này (và tương đối nhanh so với các thuật toán khác có tỷ lệ nén tương tự).
EDIT: Câu trả lời của tôi chỉ là một con trỏ chung. Đề nghị của Niyaz về việc mã hóa sự khác biệt giữa các số liên tiếp là một số tốt. (Tuy nhiên nếu danh sách là không phải được đặt hàng hoặc khoảng cách của các số là rất bất thường, tôi nghĩ rằng sẽ không kém hiệu quả khi sử dụng mã hóa Huffman đơn giản. Thực tế LZW hoặc tương tự có thể là tốt nhất trong trường hợp này, mặc dù có thể vẫn không rất tốt.)
Tôi nghĩ rằng Huffman mã hóa sẽ làm việc chỉ khi có một số yếu tố lặp đi lặp lại. Ở đây chúng ta có thể không có nhiều yếu tố lặp đi lặp lại. – Niyaz
Vâng tôi nghĩ rằng Niyaz là đúng: hiệu quả Huffman tăng với số lượng các biểu tượng lặp đi lặp lại. Nếu bạn đã lặp lại các ký hiệu trong danh sách nhập thô, bạn cũng có thể sử dụng RLE (xem chúng được sắp xếp) –
Có, thực tế là chúng được đặt hàng sẽ gợi ý tốt hơn là mã hóa sự khác biệt. – Noldorin
Các số nguyên được nhóm theo một cách dày đặc hay một cách thưa thớt?
By dày đặc tôi đề cập đến:
[1, 2, 3, 4, 42, 43, 78, 79, 80, 81]
By thưa thớt tôi đề cập đến:
[1, 4, 7, 9, 19, 42, 53, 55, 78, 80]
Nếu số nguyên được nhóm lại theo một cách dày đặc, bạn có thể nén vector đầu tiên giữ ba phạm vi:
[(1, 4), (42, 43), (78, 81)]
Mức nén 40%. Tất nhiên thuật toán này không hoạt động tốt trên dữ liệu thưa thớt vì dữ liệu được nén sẽ chiếm thêm 100% không gian so với dữ liệu gốc.
Tôi muốn sử dụng tiêu chuẩn bog nào đó khỏi giá trước khi đầu tư vào chương trình của riêng bạn.
Trong Java, bạn có thể sử dụng GZIPOutputStream để áp dụng nén gzip.
Điều kiện trong danh sách các số nguyên hơi khác nhau, nhưng câu hỏi Compression for a unique stream of data đề xuất một số phương pháp có thể giúp bạn.
Tôi muốn đề xuất lọc dữ liệu thành start và một loạt các offset giây. Nếu bạn biết rằng các offset sẽ nhỏ đáng tin cậy, bạn thậm chí có thể mã hóa chúng dưới dạng số lượng 1 hoặc 2 byte thay vì 4 byte. Nếu bạn không biết điều này, mỗi bù đắp vẫn có thể là 4 byte, nhưng vì chúng sẽ khác nhau nhỏ, bạn sẽ nhận được nhiều lặp lại hơn bạn sẽ lưu trữ các số nguyên ban đầu.
Sau khi lọc trước, hãy chạy đầu ra của bạn thông qua sơ đồ nén mà bạn chọn - một thứ hoạt động ở cấp độ byte, như gzip hoặc zlib, có thể thực hiện một công việc thực sự tốt.
Có thể bạn có thể lưu trữ sự khác biệt giữa các số nguyên 32 bit liên tiếp dưới dạng số nguyên 16 bit.
Như bạn đã phát hiện, một chuỗi được sắp xếp các số nguyên N 32 bit không có 32 * N bit dữ liệu. Điều này là không có gì ngạc nhiên. Giả sử không có trùng lặp, cho mỗi trình tự sắp xếp có N! seqeuences chưa phân loại chứa cùng số nguyên.
Bây giờ, làm cách nào để tận dụng lợi thế của thông tin bị giới hạn trong chuỗi được sắp xếp? Nhiều thuật toán nén cơ sở nén của họ về việc sử dụng bitstrings ngắn hơn cho các giá trị đầu vào phổ biến (Huffman chỉ sử dụng thủ thuật này). Một số áp phích đã gợi ý tính toán sự khác biệt giữa các con số và nén những khác biệt đó. Họ cho rằng đó sẽ là một loạt các con số nhỏ, nhiều trong số đó sẽ giống hệt nhau. Trong trường hợp đó, trình tự khác biệt sẽ được nén tốt bởi hầu hết các thuật toán.
Tuy nhiên, hãy thực hiện chuỗi Fibonacci. Đó chắc chắn là số nguyên được sắp xếp. Sự khác biệt giữa F (n) và F (n + 1) là F (n-1). Do đó, việc nén chuỗi các khác biệt tương đương với việc nén chuỗi chính nó - nó không giúp gì cả!
Vì vậy, những gì chúng tôi thực sự cần là mô hình thống kê dữ liệu đầu vào của bạn. Với chuỗi N [0] ... N [x], phân bố xác suất N [x + 1] là bao nhiêu? Chúng ta biết rằng P (N [x + 1] < N [x]) = 0, khi chuỗi được sắp xếp. Sự khác biệt/giải pháp dựa trên Huffman trình bày công việc vì chúng giả sử P (N [x + 1] - N [x] = d) là khá cao đối với dương d nhỏ và độc lập với x, vì vậy chúng sử dụng có thể sử dụng một vài bit cho sự khác biệt nhỏ. Nếu bạn có thể cung cấp cho một mô hình khác, bạn có thể tối ưu hóa cho điều đó.
Nếu bạn cần tra cứu truy cập ngẫu nhiên nhanh, thì mã hóa Huffman của sự khác biệt (như đề xuất của Niyaz) chỉ là một nửa câu chuyện. Bạn cũng có thể sẽ cần một số loại lược đồ phân trang/lập chỉ mục để dễ dàng trích xuất số thứ n.
Nếu bạn không làm điều này, sau đó trích xuất số thứ n là một hoạt động O (n), vì bạn phải đọc và Huffman giải mã một nửa tệp trước khi bạn có thể tìm thấy số bạn đã theo dõi. Bạn phải chọn kích thước trang cẩn thận để cân bằng chi phí lưu trữ bù trừ tốc độ tra cứu trang.
Câu trả lời của MSalters rất thú vị nhưng có thể khiến bạn mất tập trung nếu bạn không phân tích đúng cách. Chỉ có 47 số Fibonacci phù hợp với 32 bit.
Nhưng anh ấy đã tìm hiểu cách giải quyết vấn đề đúng cách bằng cách phân tích chuỗi gia số để tìm các mẫu có thể nén.
Những điều quan trọng: a) Có giá trị lặp lại không? Nếu vậy, bao lâu? (Nếu quan trọng, làm cho nó một phần của nén, nếu không làm cho nó một ngoại lệ.) b) Nó có vẻ gần như ngẫu nhiên?Điều này cũng có thể được tốt như một gia tăng trung bình thích hợp có thể được tìm thấy.
Sau khi đạt đến một số ngưỡng nhất định ở đó _will_ là các mẫu lặp lại, sẽ rất thú vị khi biết khi nào. Vì vậy, tôi nghĩ rằng bằng cách sử dụng thuật toán Niyaz đề xuất hoạt động tốt. –
Có thực sự. Nhưng như simonn lưu ý một sự thực hiện ngây thơ có thể mang lại truy cập ngẫu nhiên đối với O (n). Ngoài ra tôi nghĩ rằng có thể có những bản phân phối không giúp được gì, một người thích ứng-Huffman có thể giải quyết nó. Và cuối cùng, khá thường xuyên một RLE tầm thường (trên gia số) sẽ làm công việc trên rất ít dòng mã. – alecco
Số nguyên được đặt hàng? Bạn có thể lưu trữ một phạm vi [0-1000] thay vì các số không? Bạn có sử dụng phạm vi 32 bit đầy đủ không? Bạn có thể đóng gói nhiều số vào một số nguyên không? – JeffFoster