Thuật toán nén cho dữ liệu IEEE-754

Question

Bất kỳ ai có đề xuất về thuật toán nén tốt hoạt động tốt với các giá trị dấu phẩy động chính xác gấp đôi? Chúng tôi nhận thấy rằng biểu diễn nhị phân của các giá trị dấu chấm động dẫn đến tỷ lệ nén rất kém với các chương trình nén phổ biến (ví dụ: Zip, RAR, 7-Zip v.v.).

Dữ liệu chúng tôi cần nén là mảng một chiều giá trị 8 byte được sắp xếp theo thứ tự tăng dần đơn điệu. Các giá trị đại diện cho nhiệt độ trong Kelvin với một khoảng thông thường dưới 100 độ. Số lượng các giá trị dao động từ vài trăm đến tối đa 64K.

Làm rõ

• Tất cả các giá trị trong mảng là khác biệt, mặc dù sự lặp lại không tồn tại ở mức byte do cách nổi giá trị điểm được đại diện.

• Thuật toán không mất là mong muốn vì đây là dữ liệu khoa học. Việc chuyển đổi sang một đại diện điểm cố định với độ chính xác đủ (~ 5 số thập phân) có thể chấp nhận được với điều kiện là cải thiện đáng kể hiệu quả lưu trữ.

Cập nhật

Tìm thấy một bài viết thú vị về chủ đề này. Không chắc chắn cách áp dụng phương pháp này là yêu cầu của tôi.

http://users.ices.utexas.edu/~burtscher/papers/dcc06.pdf

Answer 1

Bạn có thể tạo đồng bằng giữa các giá trị liền kề không?
Có giới hạn về giá trị có thể thay đổi giữa các phép đo không? Có thể chấp nhận giới hạn sự thay đổi này đối với một số giá trị tỷ lệ tối đa (với chi phí giới thiệu một số làm mịn?)

Rõ ràng là giới hạn chính xác của các giá trị từ cảm biến nhiệt, bạn cần lưu trữ 64 bit chính xác hoặc là bạn lưu trữ tốt hơn một số nguyên nói 0,01-Kelvin đơn vị?

Nếu bạn có thể gặp phải một số lỗi khác và mức tăng tương đối trơn tru, bạn có thể tốt hơn chỉ cần lắp một hàm vào dữ liệu và chỉ lưu trữ một vài điều khoản của hàm.

EDIT:
Hãy xem một tập dữ liệu điển hình và xem xét phạm vi chênh lệch giữa các giá trị liền kề. Sau đó, xem xét độ chính xác mà bạn cần để thể hiện điều này.

ví dụ: Nếu bạn có chênh lệch 1deg tối đa giữa các bài đọc, bạn có thể lưu trữ các thay đổi của 1/256 giá trị này theo byte. Nếu bạn cần lưu trữ phạm vi lớn hơn hoặc chính xác hơn, hãy sử dụng một đoạn ngắn được chia cho một số yếu tố.
đọc Vì vậy, tiếp theo sẽ là = last_reading + (float) increment/256,0

Answer 2

Bạn có thể suy nghĩ về tái mã hóa dữ liệu của bạn với một coder entropy (Huffman, Shannon-Fano, Arithmetic Coding). Nhưng điều này sẽ chỉ cung cấp kết quả tốt nếu bạn có nhiều lần lặp lại của các datapoints và nếu bạn biết những biểu tượng sẽ xuất hiện với xác suất đó.

Answer 3

Thuật toán nén tồn tại trên các lần lặp lại và quy luật, và các số dấu phẩy động không hoạt động tốt ở đó.

Câu hỏi đầu tiên là liệu bạn có thể sử dụng các giá trị dấu phẩy động có độ chính xác đơn hay không, điều này sẽ cho bạn ngay lập tức nén 50%. Vài nhiệt kế là chính xác đến bảy chữ số, và số mũ sẽ đại diện cho nhiệt độ đáng kể dưới bất cứ điều gì tôi đã nói với bạn thực sự có thể nhận được.

Nếu không, bạn có thể lọc nhiệt độ của bạn, làm tròn chúng ra tương đương với N chữ số (nhiều khả năng là N/.301 bit) không? Điều đó có thể giới thiệu đủ đều đặn để có ích.

Nếu bạn thực sự phải lưu trữ 64 bit thông tin cho mỗi lần đọc nhiệt độ, và tất cả các bit đều đáng kể và không thể dự đoán được từ các bit khác, thì bạn không thể nén nó một cách hiệu quả.

Answer 4

Điều đầu tiên cần cân nhắc: thử nén dữ liệu trước bạn chuyển đổi thành độ chính xác gấp đôi. Re bình luận của bạn để David Thornley, trừ khi IR của bạn hình ảnh ADC có 24 bit đáng kể, 32-bit nổi nên có đủ hơn độ chính xác; nó chỉ là yêu cầu của bạn để bảo toàn chính xác tiếng ồn được tạo ra bởi quá trình xử lý tiếp theo đó là một vấn đề. Nếu không, nó có thể hình dung được thực tế để đảo ngược kỹ sư xử lý của bạn, bằng cách xác định một bảng giá trị nó tạo ra, và lưu trữ một chỉ mục vào bảng này để thay thế.

Thứ hai: nếu thuật toán nén của bạn biết rằng dữ liệu của bạn nằm trong các khối 8 byte, nó sẽ hiệu quả hơn nhiều; điều này là bởi vì nó sẽ không ném các byte quan trọng nhất của bạn với các byte ít quan trọng nhất. Là một phương pháp tiền xử lý thô, bạn có thể thử tiền tố mỗi cặp đôi với một byte riêng biệt (dấu phẩy ASCII, có lẽ?) Trước khi đường ống nó qua một máy nén dựa trên byte như gzip; điều này sẽ cho kết quả nén tổng số tốt hơn mặc dù luồng trung gian lớn hơn 12%. Ít tốn kém nhưng nỗ lực nhiều hơn là viết nén của riêng bạn phù hợp với nhiệm vụ này - có thể sử dụng cây 8 cấp để biểu diễn các giá trị kỳ vọng của mỗi byte trong gấp đôi của bạn.

Thứ ba: vì dữ liệu hình ảnh có nhiều dự phòng, một số dạng mã hóa delta hoặc nén liên quan đến hình ảnh khác nên tiết kiệm một số không gian. Tuy nhiên, nó sẽ không giúp bạn có được một lượng lớn khủng khiếp nếu bạn yêu cầu nén không bị mất, vì tiếng ồn hình ảnh vốn không thể nén được. Ngoài ra, nó sẽ không giúp bạn đối phó với băm giả ngẫu nhiên trong các bit ít quan trọng của đôi của bạn, như đã giải thích ở trên.

Answer 5

Tất cả các bộ mã hóa mà bạn liệt kê đều được định hướng byte và được loại bỏ bởi một vài thuộc tính của đôi. Đối với một trong những có bố trí nơi 12-bit số mũ/dấu hiệu không thực sự chơi tốt với ranh giới byte, cho khác có sự ồn ào của đầu vào của bạn. Phần đầu tiên là dễ dàng để đối phó với vô số cách, thứ hai sẽ hạn chế hiệu quả của bất kỳ nén lossless mà bạn ném vào nó. Tôi nghĩ rằng ngay cả kết quả tốt nhất cũng sẽ ít hơn tuyệt vời, tôi không biết dữ liệu của bạn nhưng tôi nghi ngờ bạn có thể đếm trên chỉ 25% tiết kiệm, nhiều hơn hoặc ít hơn.

Từ đỉnh đầu của tôi, và có lẽ vô ích vì bạn đã nghĩ đến tất cả mọi thứ trong danh sách này ...

1. Hãy đối xử với các dòng như số nguyên 64-bit và giá trị liền kề delta-mã hóa. Nếu bạn đã chạy các giá trị với cùng số mũ, nó sẽ có hiệu quả bằng không, cũng như có thể một số bit ảo cao. Sẽ có tràn, nhưng dữ liệu vẫn chỉ cần 64 bit và hoạt động có thể được reveresed.

2. Ở giai đoạn này, bạn có thể tùy chọn thử một số dự đoán số nguyên thô và lưu sự khác biệt.

3. Nếu bạn đã làm theo đề xuất trước đó, bạn sẽ có gần một nửa giá trị bắt đầu với 000 ... và gần một nửa với FFF ...Để loại bỏ điều đó, xoay giá trị sang trái (ROL) 1 bit và XOR nó với tất cả Fs nếu LSB hiện tại là 1. Đảo ngược là XOR với Fs nếu LSB bằng 0 thì ROR.

Suy nghĩ thứ hai chỉ đơn giản là dự đoán XORing cho giá trị thực có thể tốt hơn sự khác biệt, bởi vì bạn không phải thực hiện bước 3 sau đó.

4. Bạn có thể thử sắp xếp lại các byte thành các nhóm có cùng ý nghĩa với nhau. Giống như, đầu tiên tất cả các byte quan trọng nhất, v.v. Ít nhất bạn sẽ nhận được một cái gì đó giống như một số lượng lớn các số 0 với nhiều bit nhiễu nhất trước.

5. Chạy qua máy nén chung hoặc thậm chí RLE đầu tiên khi chạy số 0, sau đó là bộ mã hóa entropy, như bộ mã hóa hoặc bộ mã hóa dải từ 7zip/LZMA.

Có một điều tốt về dữ liệu của bạn, nó đơn điệu. Có một điều xấu về dữ liệu của bạn: nó chỉ đơn giản là một tập hợp quá nhỏ. Bạn muốn tiết kiệm bao nhiêu, chỉ kiloby? để làm gì? Hiệu quả nén sẽ bị ảnh hưởng rất nhiều nếu có sự khác biệt về số mũ giữa các giá trị liền kề.

Nếu bạn đang xử lý số lượng lớn các tập dữ liệu đó, bạn nên cân nhắc việc sử dụng tính tương tự của chúng để nén chúng lại với nhau tốt hơn - có lẽ xen kẽ chúng ở một số giai đoạn. Nếu bạn có thể sống với một số tổn thất, việc lấy ra một số byte ít quan trọng nhất có thể là một ý tưởng hay - có lẽ cả trên dữ liệu nguồn và dự đoán để bạn không giới thiệu lại tiếng ồn ở đó.

Answer 6

Nếu bạn muốn nén cao lưu trữ lưu trữ, "High Throughput nén Double-Precision Floating-Point dữ liệu" bởi Burtscher & Patanaworabhan hoặc "Fast and E ffi cient Nén Floating-Point dữ liệu" mà Lindstrom đưa ra & Isenberg có thể hữu ích để bạn.

Nếu bạn muốn truy cập động nhanh hơn với chi phí của tốc độ nén thấp hơn thì một wavelet nâng 1D có thể phù hợp. Bạn có thể định lượng dữ liệu thành các số nguyên nhỏ hơn bằng cách chỉ định số chữ số cần giữ. Sau đó, sử dụng mã hóa delta với mô hình dự báo, sau đó chuyển đổi bằng Haar hoặc biến đổi wavelet đắt hơn và mã hóa số học của các hệ số lớn hơn giá trị được chỉ định.

hy vọng nó sẽ giúp

Bạn có thể nhận thuật toán ZFP Lindstrom ở đây: https://github.com/LLNL/zfp