Huffman Kod: Permohonan contoh

Pada masa ini, tidak ramai yang berfikir tentang hakikat, bagaimana mampatan fail. Berbanding dengan penggunaan sebelumnya komputer peribadi telah menjadi lebih mudah. Dan hampir setiap orang yang bekerja dengan sistem fail yang menggunakan fail. Tetapi tidak ramai yang berfikir tentang bagaimana mereka bekerja dan apa asas pemampatan fail. Versi pertama proses ini kod Huffman, dan ia digunakan hari ini di pelbagai archivers popular. Ramai pengguna tidak berfikir bagaimana mudah fail mampatan berlaku dan ia bekerja pada skim. Dalam artikel ini kita melihat bagaimana mampatan adalah apa nuansa kelajuan membantu dan memudahkan proses pengekodan, serta melihat apa prinsip pengekodan pokok itu.

algoritma Sejarah

Algoritma pertama pengekodan berkesan maklumat elektronik telah menjadi satu kod Huffman dicadangkan seawal pertengahan abad kedua puluh, iaitu pada tahun 1952. Ia adalah orang yang pada masa ini adalah elemen asas majoriti program dicipta untuk memampatkan maklumat. Pada masa ini, salah satu sumber yang paling popular menggunakan kod ini adalah arkib ZIP, ARJ, RAR dan lain-lain lagi. Juga, algoritma Huffman yang digunakan untuk memampatkan JPEG-imej dan objek grafik lain. Well, semua faks juga menggunakan pengekodan moden, dicipta pada 1952. Walaupun fakta bahawa sejak penciptaan kod mengambil begitu banyak masa untuk hari ini ia digunakan dalam pelbagai membran baru dan peralatan lama dan moden jenis.

Prinsip pengekodan berkesan

Asas algoritma Huffman termasuk satu skim yang membolehkan anda untuk menggantikan paling boleh dipercayai, yang paling sering berlaku simbol yang berkod perduaan sistem. Dan mereka yang kurang biasa, digantikan dengan kod lagi. Melangkah kod Huffman lama berlaku hanya selepas sistem menggunakan semua nilai minimum. Teknik ini membolehkan anda untuk mengurangkan panjang kod untuk setiap simbol mesej asal secara keseluruhannya. Perkara yang penting ialah bahawa pada awal kebarangkalian pengekodan berlakunya huruf harus sudah diketahui. Ia adalah dari mereka akan bersedia dan mesej yang akhir. Berdasarkan data ini, ia menjalankan pembinaan dari pohon kod Huffman, atas dasar yang akan huruf proses pengekodan dalam arkib diadakan.

kod Huffman, contoh

Untuk menggambarkan algoritma, pertimbangkan varian grafik pembinaan pokok kod. Untuk menggunakan kaedah ini menjadi berkesan, ia adalah perlu untuk menjelaskan takrif nilai-nilai tertentu yang diperlukan untuk konsep proses. Set kepelbagaian nod dan lengkok, yang diarahkan dari nod ke nod, yang dipanggil graf. Pokok itu sendiri adalah graf dengan satu set ciri-ciri khusus:

• di setiap nod mungkin termasuk tidak lebih daripada satu lengkok;
• salah satu daripada nod perlu menjadi akar pohon, iaitu, ia tidak seharusnya menjadi sebahagian daripada arka sama sekali;
• jika batang mula bergerak di sepanjang lengkok, proses itu perlu membenarkan untuk mendapatkan sepenuhnya dalam mana-mana nod.

Terdapat juga benda itu, sebahagian daripada kod Huffman sebagai daun pokok itu. Ia adalah nod yang tidak boleh pergi mana-mana arka. Jika dua nod yang dihubungkan dengan arka, salah satunya adalah dengan ibubapa kanak-kanak lain, bergantung kepada yang nod arka padam dan apa yang datang dalam. Jika dua nod mempunyai nod induk yang sama, mereka dipanggil laman rakan. Jika, di daun, daun dari nod beberapa lengkok, maka ia dipanggil pokok binari. Hanya jadi adalah pokok Huffman itu. The keanehan pembinaan unit adalah bahawa berat setiap ibu bapa adalah sama dengan jumlah wajaran semua kanak-kanak nod itu.

Algoritma untuk membina pokok Huffman

Pembinaan kod Huffman adalah input dari huruf abjad. Dijana senarai laman web yang bebas di pokok kod di masa depan. Berat setiap nod dalam senarai mestilah sama kerana kemungkinan berlakunya jawatan huruf yang sepadan dengan nod ini. Dalam kes ini, orang yang mempunyai berat sekurang-kurangnya dipilih dari kalangan beberapa laman web percuma pokok masa depan. Dalam kes ini, jika kadar minimum diperhatikan dalam beberapa laman web, anda boleh dengan bebas memilih mana-mana pasangan. Kemudian datang penciptaan nod induk, yang mesti berat sebanyak jumlah berat daripada sepasang nod. Selepas itu, ibu bapa menghantar senarai dengan tandas percuma, dan anak-anak dikeluarkan. Dalam arka ini adalah petunjuk yang sesuai, satu dan sifar. Proses ini diulang sebanyak yang diperlukan untuk memastikan hanya nod tunggal. Kemudian menulis digit binari dari atas ke bawah.

Meningkatkan kecekapan mampatan

Dalam usaha untuk meningkatkan kecekapan mampatan, adalah perlu semasa kod bangunan pokok menggunakan semua data mengenai kebarangkalian berlakunya huruf dalam fail tertentu, melekat pada pokok, dan tidak membenarkan hakikat bahawa mereka bertaburan sebilangan besar dokumen teks. Jika sebelum berjalan kaki melalui fail ini, anda boleh terus mengira statistik kekerapan terdapat huruf kemudahan tertakluk kepada mampatan.

Pecutan proses pemampatan

Untuk mempercepatkan algoritma, definisi huruf perlu dilakukan bukan dari segi kebarangkalian berlakunya suatu surat tertentu, dan kekerapan kejadiannya. Dengan algoritma ini menjadi lebih mudah, dan bekerja dengan mereka lebih cepat. ia juga mengelakkan operasi yang berkaitan dengan pembahagian titik apung. Di samping itu, bekerja dalam mod ini, kod Huffman dinamik, atau sebaliknya algoritma itu sendiri tidak tertakluk kepada sebarang perubahan. Ini adalah disebabkan oleh hakikat bahawa kebarangkalian adalah berkadar terus dengan kekerapan. Ia adalah bernilai memberi perhatian kepada fakta bahawa berat akhir fail, atau nod akar yang dipanggil adalah sama dengan jumlah bilangan aksara dalam objek yang hendak dirawat.

kesimpulan

Kod Huffman - mudah dan lama bertapak algoritma, yang masih digunakan oleh banyak program dan syarikat-syarikat terkenal. kesederhanaan dan kejelasan boleh mencapai keputusan yang berkesan memampatkan fail mana-mana jumlah dan ketara mengurangkan ruang storan cakera. Dalam erti kata lain, algoritma Huffman - telah lama disiasat dan diagram kerja yang mendesak tidak dikurangkan oleh hari ini. Dan dengan keupayaan untuk mengurangkan saiz fail, memindahkan mereka melalui rangkaian atau dengan cara lain ia adalah lebih mudah, cepat dan mudah. Bekerja dengan algoritma, anda boleh memampatkan apa-apa maklumat sepenuhnya tanpa kemudaratan kepada struktur dan kualiti, tetapi dengan kesan maksimum untuk mengurangkan fail berat. Dengan kata lain, pengekodan kod Huffman yang telah dan masih kaedah yang paling popular dan relevan memampatkan saiz fail.