Nén dữ liệu: Mã hóa số học không rõ ràng

Question

Có ai vui lòng giải thích mã hóa số học để nén dữ liệu với chi tiết triển khai không? Tôi đã lướt qua internet và tìm thấy bài viết của nelson đánh dấu nhưng kỹ thuật thực hiện thực sự là không rõ ràng với tôi sau khi cố gắng nhiều giờ. giải thích

Đánh dấu nelson về số học mã hóa có thể được đặt tại

http://marknelson.us/1991/02/01/arithmetic-coding-statistical-modeling-data-compression/

Answer 1

Ý tưởng chính với nén số học là khả năng mã hóa xác suất bằng cách sử dụng lượng thời lượng dữ liệu chính xác được yêu cầu.

lượng dữ liệu này được biết đến, đã được chứng minh bởi Shannon, và có thể được tính toán đơn giản bằng cách sử dụng công thức sau: -log2 (p)

Ví dụ, nếu p = 50%, sau đó bạn cần 1 chút. Và nếu p = 25%, bạn cần 2 bit.

Điều đó đơn giản đủ cho xác suất là sức mạnh của 2 (và trong trường hợp đặc biệt này, mã hóa huffman có thể là đủ). Nhưng nếu xác suất là 63% thì sao? Sau đó, bạn cần -log2 (0,63) = 0,67 bit. Âm thanh khó khăn ...

Thuộc tính này đặc biệt quan trọng nếu xác suất của bạn cao. Nếu bạn có thể dự đoán một cái gì đó với độ chính xác 95%, thì bạn chỉ cần 0,074 bit để thể hiện một phỏng đoán tốt. Có nghĩa là bạn sẽ nén rất nhiều.

Bây giờ, làm thế nào để làm điều đó?

Vâng, nó đơn giản hơn âm thanh. Bạn sẽ chia phạm vi của bạn tùy thuộc vào xác suất. Ví dụ: nếu bạn có phạm vi 100, 2 sự kiện có thể và xác suất 95% cho giá trị thứ nhất, thì giá trị 95 đầu tiên sẽ là "Sự kiện 1" và 5 giá trị còn lại cuối cùng sẽ cho biết "Sự kiện 2" .

OK, nhưng trên máy tính, chúng tôi quen với việc sử dụng quyền hạn của 2. Ví dụ, với 16 bit, bạn có một loạt các giá trị có thể là 65536. Chỉ cần làm tương tự: lấy 95% đầu tiên của phạm vi (là 62259) để nói "Sự kiện 1" và phần còn lại để nói "Sự kiện 2". Bạn rõ ràng có một vấn đề "làm tròn" (chính xác), nhưng miễn là bạn có đủ giá trị để phân phối, nó không quan trọng quá nhiều. Hơn nữa, bạn không bị ràng buộc với 2 sự kiện, bạn có thể có vô số sự kiện. Tất cả những gì quan trọng là giá trị được phân bổ tùy thuộc vào xác suất của mỗi sự kiện.

OK, nhưng bây giờ tôi có 62259 giá trị có thể để nói "Sự kiện 1" và 3277 để nói "Sự kiện 2". Tôi nên chọn cái nào ? Vâng, bất kỳ người trong số họ sẽ làm. Thời tiết là 1, 30, 5500 hoặc 62256, nó vẫn có nghĩa là "Sự kiện 1".

Thực tế, việc quyết định giá trị nào sẽ chọn sẽ không phụ thuộc vào phỏng đoán hiện tại, nhưng trên các giá trị tiếp theo.

Giả sử tôi đang có "Sự kiện 1". Vì vậy, bây giờ tôi phải chọn bất kỳ giá trị nào giữa 0 và 62256. Trong lần đoán tiếp theo, tôi có cùng phân phối (95% Sự kiện 1, 5% Sự kiện 2). Tôi sẽ chỉ phân bổ bản đồ phân phối với những xác suất này. Ngoại trừ thời gian này, nó được phân phối trên 62256 giá trị. Và chúng tôi tiếp tục như thế này, giảm phạm vi giá trị với mỗi lần đoán.

Vì vậy, trên thực tế, chúng tôi đang xác định "phạm vi", thu hẹp với mỗi lần đoán. Tuy nhiên, tại một số điểm, có một vấn đề về tính chính xác, bởi vì rất ít giá trị vẫn còn.

Ý tưởng, chỉ đơn giản là "tăng thêm" phạm vi một lần nữa. Ví dụ, mỗi lần phạm vi đi dưới 32768 (2^15), bạn xuất bit cao nhất, và nhân phần còn lại bằng 2 (hiệu quả chuyển các giá trị bằng một bit còn lại). Bằng cách liên tục làm như thế này, bạn sẽ xuất hiện từng bit một, vì chúng đang được giải quyết bằng một loạt các dự đoán.

Bây giờ mối quan hệ với nén trở nên rõ ràng: khi phạm vi được thu hẹp nhanh chóng (ví dụ: 5%), bạn xuất ra rất nhiều bit để có được phạm vi trở lại vượt quá giới hạn. Mặt khác, khi xác suất rất cao, phạm vi thu hẹp rất chậm. Bạn thậm chí có thể có rất nhiều dự đoán trước khi xuất các bit đầu tiên của mình. Đó là cách có thể nén một sự kiện thành "một phần nhỏ của một chút".

Tôi đã cố tình sử dụng cụm từ "xác suất", "đoán", "sự kiện" để giữ cho bài viết này chung chung. Nhưng để nén dữ liệu, bạn chỉ cần thay thế chúng bằng cách bạn muốn mô hình dữ liệu của mình. Ví dụ, sự kiện tiếp theo có thể là byte tiếp theo; trong trường hợp này, bạn có 256 trong số đó.

Answer 2

Trước hết nhờ giới thiệu tôi đến khái niệm về nén số học!

tôi có thể thấy rằng phương pháp này có các bước sau:

1. Tạo lập bản đồ: Tính toán phần xảy ra cho mỗi chữ cái mà đưa ra một kích thước phạm vi cho mỗi bảng chữ cái. Sau đó sắp xếp chúng và gán dãy thực tế 0-1
2. Cho một thông điệp tính toán phạm vi (IMHO khá đơn giản)
3. Tìm mã tối ưu

Phần thứ ba là một chút khéo léo. Sử dụng thuật toán sau.

Cho b là biểu diễn tối ưu. Khởi tạo nó thành chuỗi rỗng (''). Cho x là giá trị nhỏ nhất và y giá trị lớn nhất.

1. x đôi và y: x = 2 * x, y = 2 * y
2. Nếu cả hai trong số đó là lớn hơn 1 append 1 tới b. Chuyển đến bước 1.
3. Nếu cả hai đều nhỏ hơn 1, hãy thêm từ 0 đến b. Tới bước 1.
4. Nếu x < 1, nhưng y> 1, sau đó nối từ 1 tới b và dừng

b chủ yếu chứa các phần phân số của số bạn đang truyền tải. Ví dụ. Nếu b = 011, thì phân số tương ứng với 0,001 trong nhị phân.

Bạn không hiểu phần nào của việc triển khai?

Answer 3

Có thể tập lệnh này có thể hữu ích để xây dựng mô hình tinh thần tốt hơn về trình mã hóa số học: gen_map.py. Ban đầu nó được tạo ra để tạo điều kiện gỡ lỗi của thư viện coder số học và đơn giản hóa việc tạo ra các bài kiểm tra đơn vị cho nó. Tuy nhiên nó tạo ra trực quan ASCII tốt đẹp mà cũng có thể hữu ích trong việc hiểu mã hóa số học.

Ví dụ nhỏ. Hãy tưởng tượng chúng tôi có một bảng chữ cái của 3 biểu tượng: 0, 1 và 2 với xác suất 1/10, 2/10 và 7/10 tương ứng. Và chúng tôi muốn mã hóa chuỗi [1, 2].Script sẽ cho kết quả như sau (bỏ qua -b N lựa chọn cho bây giờ):

$ ./gen_map.py -b 6 -m "1,2,7" -e "1,2" 
000000111111|1111|111222222222222222222222222222222222222222222222 
------011222|2222|222000011111111122222222222222222222222222222222 
---------011|2222|222-------------00011111122222222222222222222222 
------------|----|-------------------------00111122222222222222222 
------------|----|-------------------------------01111222222222222 
------------|----|------------------------------------011222222222 
================================================================== 
000000000000|0000|000000000000000011111111111111111111111111111111 
000000000000|0000|111111111111111100000000000000001111111111111111 
000000001111|1111|000000001111111100000000111111110000000011111111 
000011110000|1111|000011110000111100001111000011110000111100001111 
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 
001100110011|0011|001100110011001100110011001100110011001100110011 
010101010101|0101|010101010101010101010101010101010101010101010101 

Đầu 6 dòng (trước ==== line) đại diện cho một loạt 0,0-1,0 được đệ quy chia vào khoảng thời gian tương ứng với xác suất biểu tượng. Chú thích dòng đầu tiên:

[1/10][  2/10 ][     7/10      ] 
000000111111|1111|111222222222222222222222222222222222222222222222 

Sau đó chúng tôi chia nhỏ mỗi khoảng thời gian một lần nữa:

[ 0.1][  0.2  ][     0.7      ] 
000000111111|1111|111222222222222222222222222222222222222222222222 
     [ 0.7 ][.1][ 0.2 ][   0.7     ] 
------011222|2222|222000011111111122222222222222222222222222222222 
            [.1][ .2][ 0.7    ] 
---------011|2222|222-------------00011111122222222222222222222222 

Lưu ý, rằng một số khoảng thời gian không được chia nhỏ. Điều đó xảy ra khi không có đủ không gian để biểu diễn mọi khoảng con trong độ chính xác đã cho (được chỉ định bởi tùy chọn -b).

Mỗi dòng tương ứng với một biểu tượng từ đầu vào (trong trường hợp của chúng tôi - trình tự [1, 2]). Bằng cách làm theo các khoảng con cho mỗi ký hiệu đầu vào, chúng ta sẽ có một khoảng thời gian cuối cùng mà chúng ta muốn mã hóa với số lượng bit tối thiểu. Trong trường hợp của chúng tôi đó là một 2 subinterval đầu tiên trên một dòng thứ hai:

  [ This one ] 
------011222|2222|222000011111111122222222222222222222222222222222 

Sau 7 dòng (sau ====) đại diện cho cùng một khoảng 0.0 đến 1.0, nhưng chia theo ký hiệu nhị phân. Mỗi dòng là một bit đầu ra và bằng cách chọn giữa 0 và 1, bạn chọn nửa bên trái hoặc nửa bên phải. Ví dụ bit 01 tương ứng với subinterval [0.25, 05) trên một dòng thứ hai:

    [ This one ] 
000000000000|0000|111111111111111100000000000000001111111111111111 

Ý tưởng về số học coder là bit đầu ra (0 hoặc 1) cho đến khi khoảng thời gian tương ứng sẽ được hoàn toàn bên trong (hoặc tương đương) khoảng xác định bởi chuỗi đầu vào. Trong trường hợp của chúng tôi là 0011. Dòng ~~~~ hiển thị nơi chúng tôi có đủ bit để xác định rõ ràng khoảng thời gian chúng tôi muốn.

Đường dọc được tạo thành bởi biểu tượng | hiển thị phạm vi chuỗi bit (hàng) có thể được sử dụng để mã hóa chuỗi đầu vào.