Thuật toán nén dữ liệu

Question

Tôi đã tự hỏi liệu có ai có danh sách thuật toán nén dữ liệu hay không. Tôi biết về cơ bản không có gì về nén dữ liệu và tôi đã hy vọng tìm hiểu thêm về các thuật toán khác nhau và xem những thuật toán nào là mới nhất và chưa được phát triển trên nhiều ASIC.

tôi hy vọng để thực hiện một ASIC nén dữ liệu mà không phụ thuộc vào loại dữ liệu đến trong (âm thanh, video, hình ảnh, vv.)

Nếu câu hỏi của tôi là quá mở kết thúc, xin vui lòng cho tôi biết và tôi sẽ sửa lại. Cảm ơn bạn

Answer 1

Có rất nhiều thuật toán nén trên mạng. Những gì bạn cần ở đây là một thuật toán nén không mất dữ liệu. Một thuật toán nén không mất dữ liệu nén dữ liệu sao cho nó có thể được giải nén để đạt được chính xác những gì đã được đưa ra trước khi nén. Ngược lại sẽ là một thuật toán nén mất dữ liệu. Nén mất dữ liệu có thể xóa dữ liệu khỏi tệp. Hình ảnh PNG sử dụng nén không mất dữ liệu trong khi hình ảnh JPEG có thể và thường sử dụng nén mất dữ liệu.

Một số thuật toán nén biết đến rộng rãi nhất bao gồm:

• RLE
• Huffman
• LZ77

tài liệu lưu trữ ZIP sử dụng một sự kết hợp của Mã hóa Huffman và LZ77 để cung cấp cho nén nhanh và thời gian giải nén và nén tốt hợp lý tios.

LZ77 là khá nhiều dạng RLE tổng quát và thường sẽ mang lại kết quả tốt hơn nhiều.

Huffman cho phép các byte lặp lại nhiều nhất để biểu thị số bit ít nhất. Hãy tưởng tượng một tập tin văn bản trông như thế này:

aaaaaaaabbbbbcccdd 

Một thực hiện điển hình của Huffman sẽ cho kết quả trong bản đồ sau:

Bits Character 
    0   a 
    10   b 
110   c 
1110   d 

Vì vậy, các tập tin sẽ được nén như thế này:

00000000 10101010 10110110 11011101 11000000 
             ^^^^^ 
           Padding bits required 

18 byte giảm xuống 5. Tất nhiên, bảng phải được bao gồm trong tệp. Thuật toán này hoạt động tốt hơn với nhiều dữ liệu hơn: P

Alex Allain có a nice article trên Thuật toán nén Huffman trong trường hợp Wiki không đủ.

Vui lòng hỏi thêm thông tin. Chủ đề này khá rộng.

Answer 2

Thuật toán LZW hoặc Lempel Ziv là một thuật toán không mất mát lớn. Mã giả ở đây: http://oldwww.rasip.fer.hr/research/compress/algorithms/fund/lz/lzw.html

Answer 3

Có rất nhiều thuật toán nén dữ liệu khủng khiếp. Nếu bạn đang tìm kiếm một thứ gì đó trong bách khoa toàn thư, tôi khuyên bạn nên sử dụng Cẩm nang nén dữ liệu của Salomon và cộng sự, bạn có thể nhận được (và có các phần tốt về nguyên tắc và thực hành nén dữ liệu, tốt).Tôi nghĩ tốt nhất là nén ASIC thường được thực hiện cho một ứng dụng cụ thể, hoặc như một phần tử chuyên biệt của SoC, chứ không phải là một chip nén độc lập. Tôi cũng nghi ngờ rằng tìm kiếm một định dạng nén "mới nhất và lớn nhất" là cách để đi tới đây - tôi mong đợi sự chuẩn hóa, trưởng thành và thể lực cho một mục đích cụ thể quan trọng hơn.

Answer 4

Giấy của tôi A Survey Of Architectural Approaches for Data Compression in Cache and Main Memory Systems (permalink here) đánh giá nhiều thuật toán nén và cũng là kỹ thuật để sử dụng chúng trong bộ xử lý hiện đại. Nó xem xét cả các thuật toán/kỹ thuật nén cấp độ nghiên cứu và thương mại, vì vậy bạn có thể tìm thấy một thuật toán chưa được triển khai trong ASIC.

Answer 5

Dưới đây là một số thuật toán lossless (hoàn toàn có thể phục hồi dữ liệu gốc sử dụng này):

• Huffman đang
• LZ78 (và biến thể LZW)
• LZ77
• Arithmetic mã hóa
• sequitur
• dự đoán có khớp một phần (ppm)

Nhiều định dạng nổi tiếng như biến thể sử dụng png hoặc gif hoặc kết hợp các định dạng này.

Mặt khác cũng có thuật toán mất dữ liệu (thỏa hiệp tính chính xác để nén dữ liệu của bạn, nhưng thường hoạt động khá tốt).

Để tìm hiểu thêm về nén dữ liệu, tôi khuyên bạn nên https://www.elsevier.com/books/introduction-to-data-compression/sayood/978-0-12-809474-7. Nó là một văn bản giới thiệu rất dễ tiếp cận. Phiên bản thứ 3 hiện có trên pdf trực tuyến.