Bài đăng
Công nghệ nén dữ liệu luôn luôn làm tôi cảm thấy một chút bí ẩn của một thuật toán toán học, và khi tôi tiếp xúc với các thuật toán cụ thể, tôi đã tìm thấy nguyên tắc rất đơn giản, vì vậy tôi đã viết tài liệu này để nói về cảm xúc của mình. Tuy nhiên, bài viết là có hạn, để chỉ một trong các thuật toán LZ77 đơn giản nhất như là một ví dụ để giải thích.
Việc áp dụng công nghệ nén dữ liệu được phổ biến rộng rãi, WinRar, WinZip và các phần mềm nén dữ liệu thông thường khác cần thiết bây giờ đã trở thành phần mềm máy tính. Kết nối đường truyền có thể được nhìn thấy gói file nén ở khắp mọi nơi. Các thuật toán nén thông thường, ngay cả các tập tin đa phương tiện nhúng vào trong các tiêu chuẩn định dạng tập tin. Các khía cạnh của hình ảnh đồ họa jpeg, png, gif, âm thanh mp3, video VCD, DVD cũng đều có thể được nén lại
Phân loại các công nghệ nén dữ liệu
Thuật toán nén dữ liệu được chia thành hai loại nén mất dữ liệu và nén lossless. Nén Lossless là thuật toán nén có thể phục hồi hoàn toàn và mất dữ liệu nén được các thuật toán nén không thể hoàn toàn phục hồi.. Một ví dụ điển hình là một thuật toán nén mất dữ liệu âm thanh mp3, mặc dù nó bị mất một số thông tin âm thanh ban đầu, nhưng nó có thể cải thiện tỉ lệ nén, và sự mất mát thông tin điểm đó không có nhiều trong các clip âm nhạc. Bài viết này mô tả các thuật toán nén dữ liệu nói chung không phải là nhằm vào một âm thanh cụ thể hoặc các thông tin video, nhưng một thông tin dữ liệu phổ biến, chúng tôi không biết những thông tin có thể bị mất, và những thông tin đặt chỗ, do đó, nó chắc chắn là một Lossless nén. Chúng tôi thường sử dụng trong Windows, WinZip, WinRar là một tiêu chuẩn nén dữ liệu chung, các thuật toán của bài này là để giải thích các thuật toán này
Universal công nghệ nén dữ liệu
Mã Huffman dựa trên công nghệ nén dữ liệu. DAHuffman năm 1952 xuất bản bài báo của ông, "việc xây dựng các phương pháp mã dự phòng tối thiểu" đã mở hình thức ban đầu của công nghệ nén dữ liệu. Công nghệ nén dữ liệu đầu dựa trên các kỹ thuật tối ưu hóa mã. Nhưng chúng ta đều biết rằng tối ưu mã hóa các dữ liệu thống kê cho sự xuất hiện của xác suất. Tuy nhiên, khi làm việc với các tập tin lớn, thống kê, xác suất của các ký tự bên trong tập tin là một thời gian rất phiền hà, để ghi một thời gian tính toán dài. phương pháp thực hành dựa vào phương pháp mã hóa được gọi là thích nghi, nghĩa là, khi nén để giữ các xác suất thống kê của nhân vật. Điều này dẫn đến cách tiếp cận trong quá trình nén không phải là tốt để bắt đầu, nhưng để nén lại, nó sẽ đạt được hiệu năng tốt hơn.
Năm 1977, Israel Jacob Lempel Ziv và Abraham xuất bản một bài báo, "theo lệnh của một thuật toán nén dữ liệu chung chung", năm 1978, họ công bố một phần tiếp theo của bài báo "của các trình tự mã hóa tỷ lệ nén biến độc lập." Kể từ đó, công nghệ nén dữ liệu được phổ biến. Thuật toán nén dữ liệu từ điển là rất dễ hiểu, là cố gắng để không lưu những thông tin trùng lặp. Israel hai phát minh ra các thuật toán LZ77, LZ78 hiện nay là thuật toán nén Zip phổ biến của người tiền nhiệm.
Độ dài tối thiểu của mã Huffman
Ở đây chúng ta bắt đầu nén dữ liệu với chủ đề.
Hầu như mỗi bài viết sẽ giải thích về nén dữ liệu, các "entropy thông tin" đưa ra để giải thích. Nhưng điều này không gian hạn chế, không có ý định giải thích. Bởi vì thông tin một khi các dữ liệu ngẫu nhiên để giải thích, sau đó, sau khi nén sẽ được liên kết với entropy thông tin, và rất phiền hà. Chúng tôi có quyền truy cập trực tiếp vào các dữ liệu mã hóa một phần. Đừng nghĩ rằng chỉ có tối ưu hóa đầu chỉ liên quan đến mã hóa nén dữ liệu mã hóa, trong thực tế, Zip, nén Rar cũng được sử dụng trong mã hóa dữ liệu theo cách tốt nhất để thu hẹp thông tin là dài dòng.
Trước tiên, chúng ta cần phải biết thiết kế của một mã hóa biến đổi chiều dài. Cách thông thường là sử dụng mã tiền tố. Các mã được gọi là tiền tố là để mã hóa các thông tin tính năng của việc thực hiện các mã ở đầu trang. Hãy xem một ví dụ.
Có ba tin nhắn A, B, C, các mã nhị phân họ đã 0,1,01, và nếu chúng tôi nhận được một tin nhắn là 01010, làm thế nào để chúng ta phân biệt giữa thời gian giải mã là CCA hay Ababa, hoặc ABCA? Nếu sử dụng mã tiền tố , chúng ta có thể tránh những xung đột đó. Mã tiền tố sau vào C A, B, mã hóa.
A: 0 B: 10 C: 110
Vì vậy, 01010 chỉ có thể được dịch ra tiếng ABB. Do đó, chiều dài này biến mã hóa là không mâu thuẫn. Tuy nhiên, sau đây có một vấn đề, từ mã tiền tố 0,10,110,1110 ... điều này sẽ không sản xuất bất kỳ sự kết hợp của giải mã các xung đột, nếu việc sắp xếp A, B, C mã hóa có thể làm cho A, B, C đại diện cho các thông tin tối thiểu ? Vấn đề này được nêu ra bởi các nhà xây dựng đã đề cập trước tối thiểu mã hóa Huffman.
Mã Huffman là một mã tiền tố tối ưu (còn các mã nhỏ nhất). Như vậy là A, B, C, D, tương ứng, số lượng các ký tự xuất hiện như là 12,3,4,5 Sau đó, xây dựng. Huffman cây nhị phân.
root
A @
D @
C B
(Bài viết này chỉ đề cập đến ở đây, Huffman mã hóa, các phương pháp xây dựng cụ thể và các nguyên tắc xin tham khảo sách liên quan đến toán học rời rạc.) Theo xây dựng cây nhị phân Huffman:
Một mã hóa: 0 B mã hóa: 111 C của mã này: 110 D của Bộ luật: 10
Sau đó A chỉ được sử dụng một chút, B với một 3, C với một 3, D với 2. Sau đó sử dụng thông tin này trên tổng số 12 * 1 +3 * 3 4 * 3 +5 * 2 = 43 bit. Việc cài đặt mã hex chung 2-10, sau đó là A, B, C, D mỗi yêu cầu sử dụng hai bit, vì như việc sử dụng tổng cộng 12 * 2 +3 * 2 +3 * 2 5 * 2 = 46 bit.
Trong thực tế, điều này là không có gì hơn một mã tiền tố để sử dụng một từ mã ngắn, cho biết, biểu tượng xác suất cao, các bức điện mã Morse nổi tiếng là lý do tương tự. Moss mã điện tín là tên phổ biến nhất trong tiếng Anh trong mã ngắn nhất e biên dịch.
Phân loại bất bình đẳng mà nói về Toán học:. Tự,> = trong trật tự, trật tự> = đảo ngược, và Và đây là code để có được "tối thiểu", do đó, cách sử dụng "để đảo ngược" được xây dựng.
Để chắc chắn, không có vấn đề gì bạn sử dụng mã hóa, có thể không xung đột với các bảng mã, việc sử dụng mã hóa Huffman thông tin từ các chiều dài nhỏ nhất.
Ngoài Huffman mã hóa, có nhiều loại mã hóa tốt hơn về số học, nhưng những nguyên tắc có một chút phức tạp, bài viết này không có ý định giải thích. Chúng tôi muốn được nổi tiếng, thuật toán LZ77
Từ điển LZ77 lý thuyết thuật toán nén
Nén thuật toán rất dễ dàng để nghĩ về các từ điển được xây dựng một thực tế từ điển. Ví dụ, một bài viết bằng tiếng Anh, trên thực tế, miễn là chúng ta tiết kiệm được mỗi từ trong từ điển tiếng Anh và số lượng các trang xuất hiện trên đó. Các trang với hai byte, số với byte một, sau đó trung bình một từ của 3 byte để lưu trữ, và chúng ta biết độ dài của các từ tiếng Anh nói chung có nhiều hơn 3. Vì vậy, dữ liệu của chúng tôi trong bài viết này bằng tiếng Anh để đạt được nén. Nhưng thực tế thuật toán nén dữ liệu chung chung không thể làm điều đó, bởi vì chúng tôi cần một thời gian giảm áp của hàng ngàn các trang của các từ điển tiếng Anh, và phần này của máy nén thông tin đầu tiên không thể đoán trước, nhưng nó cũng không thể được lưu trong nén bên trong thông tin (bằng tiếng Anh hơn so với từ điển tiếng Anh bài viết cũng dày). Chúng tôi LZ77 nén thuật toán trình bày ở đây là phương pháp được sử dụng để tự động tạo ra một từ điển. Nói cách khác, từ điển thông tin được nén ở phía trước của các thông tin riêng của mình.
Như đã đề cập, thuật toán LZ77 là chủ yếu để tránh trùng lặp của các tin nhắn dài sẽ xuất hiện. Ví dụ, sau một chuỗi ký tự
AABAABAAB
Chúng tôi nơi sinh có ba kỳ AAB, nhưng miễn là chúng ta có thể tiết kiệm một AAB, và sau đó đặt hai xuất hiện AAB khác chỉ cần vị trí của sự xuất hiện đầu tiên của AAB và độ dài của các cửa hàng xuống trên nó. Sau đó, chúng tôi lưu AAB hai cuối cùng để chỉ một
Vâng, chúng ta hãy xem một ví dụ thực tế, các chuỗi AABAABCDDABC
Bước
Đầu vào
Bộ nhớ hiện tại
Đầu ra
1.
AABAABCDDABC
Rỗng
Rỗng
2.
ABAABCDDABC
A
A
3.
BAABCDDABC
AA
<0,1>
4.
AABCDDABC
AAB
B
5.
CDDABC
AABAAB
<0,3>
6.
DDABC
AABAABC
C
7.
DABC
AABAABCD
D
8.
ABC
AABAABCDD
<7,1>
9.
Rỗng
AABAABCDDABC
<4,3>
Dưới đây là một vấn đề rắc rối trong chiết xuất một số thông tin về làm thế nào để phân biệt khi dữ liệu là nguồn gốc của thông tin hoặc kết hợp? Nếu dữ liệu nguồn, sau đó chúng ta trích xuất trực tiếp sao chép vào bộ đệm, nếu được kết hợp thông tin, chúng tôi phải di chuyển từ vị trí hiện tại của bộ đệm trích xuất kết hợp thông tin để tìm thấy bản sao. Đa truy cập giải pháp là sử dụng một bit (bit) để phân biệt nguồn gốc của thông tin nén bên trong các dữ liệu và kết hợp thông tin. Bạn có thể lo lắng, chúng tôi giới thiệu một thông tin mới đây ở, sẽ không để cho trọng lượng của tập tin nén nhưng lớn hơn các tập tin mã nguồn? Nhưng thực tế đã chứng minh rằng nói chung các dữ liệu không nén, sau đó hơn một chút so với việc giới thiệu các thông tin thẻ không có tác động nhiều. Nhưng đồng thời lặp lại các file nén, file không chỉ có áp lực không nhỏ nhưng cũng ép hơn trước.
Lặp lại các thông tin phù hợp với thông tin ghi lại bao gồm hai, một là vị trí của trận đấu, một trận đấu dài. Làm thế nào để phân bổ, bảo quản của hai thông điệp là một vấn đề chính Phù hợp với vị trí của vị trí này không thể hoàn toàn tùy ý,. Bởi vì một số kích thước tập tin lên đến một vài MB, hoặc thậm chí hàng trăm MB, sau đó chỉ cần phù hợp với vị trí để lưu lại một vài byte của information'll sẵn sàng giải pháp thực tế là sử dụng sự sắp xếp để tiết kiệm một trận đấu hai byte thông tin phù hợp với vị trí của 0,12 bit, 4 bit để biểu diễn. phù hợp với chiều dài. sau đó bạn có thể tìm thấy một trận đấu
Chiều dài lên tới 4096 vị trí, trong khi bốn nói rằng trận đấu có thể đạt chiều dài 16 byte. Các thông tin phù hợp cho phù hợp để tìm cũng tìm thấy độ dài ít nhất là 3 byte vì nếu chiều dài phù hợp với ít hơn 3 byte, sau đó chỉ số byte của thông tin được lưu trữ để phù hợp với độ nén cao hơn làm giảm số byte ra nhiều tác hại hơn là có lợi. Nhiều phân phối thực tế của phần mềm nén được như thế này, tôi cũng đã thử nghiệm riêng của họ, kế hoạch này phân bổ thực sự là tốt nhất.
Độ dài cố định phù hợp sau đó khoảng này là nhiều người đã nói để tìm cửa sổ từ điển
Chức vụ hiện nay Phân tích
Nguồn dữ liệu được nén
Từ điển để tìm những thông tin phù hợp
4.096 byte
Vị trí trong phân tích hiện tại của dữ liệu chiết xuất được nén, trong bộ đệm dữ liệu nguồn trước khi các vị trí hiện tại của một chiều dài cố định của khu vực thông tin để tìm chuỗi trận dài nhất cho phù hợp. Nếu tìm thấy, các vị trí hiện tại của điện thoại di động phù hợp với chiều dài của byte, và sau đó cũng di chuyển cửa sổ để phù hợp với từ điển của byte chiều dài. Như vậy, phân tích liên tục di chuyển ngược con trỏ, các cửa sổ từ điển đã được di chuyển trở lại cho đến khi phân tích các bộ đệm dữ liệu nguồn con trỏ đến cùng.
Được đăng bởi Why vào lúc 01:22
Gửi email bài đăng này
BlogThis!
Chia sẻ lên Twitter
Chia sẻ lên Facebook
Chia sẻ lên Google Buzz
Nhãn: Thuật Toán
Không có nhận xét nào:
Đăng nhận xét