Bagaimana cara mengukur entropi file?

9

Saya mencoba mengukur sekarang banyak informasi yang tidak berlebihan (aktual) yang terkandung dalam file saya. Ada yang menyebut ini jumlah entropi.

Tentu saja ada standar p (x) log {p (x)}, tapi saya pikir Shannon hanya mempertimbangkannya dari sudut pandang transmisi melalui saluran. Karena itu rumus membutuhkan ukuran blok (misalnya dalam bit, 8 biasanya). Untuk file besar, perhitungan ini cukup berguna, mengabaikan korelasi jarak pendek ke jarak jauh antara simbol.

Ada metode pohon biner dan Ziv-Lempel, tetapi ini sifatnya sangat akademis.

Kompresibilitas juga dianggap sebagai ukuran entropi, tetapi tampaknya tidak ada batas yang lebih rendah untuk tingkat kompresi. Untuk file saya hiss.wav,

  • original hiss.wav = 5.2 MB
  • entropi melalui rumus Shannon = 4,6 MB
  • hiss.zip = 4,6 MB
  • hiss.7z = 4.2 MB
  • hiss.wav.fp8 = 3.3 MB

Apakah ada beberapa metode yang masuk akal untuk mengukur berapa banyak entropi yang ada dalam hiss.wav?

entropy Paul Uszak
sumber
1
Saya tidak mengerti apa yang Anda maksud dengan "sangat akademis".
David Richerby
Mati. Saya akan berpikir bahwa dengan skala dana penelitian yang dikeluarkan secara global untuk memaksimalkan pengiriman dan penyimpanan data, akan ada cara yang lebih maju untuk memperkirakan berapa banyak barang yang terkutuk yang sebenarnya Anda hadapi. Saya tidak akan berpikir itu di luar bidang kemungkinan bahwa akan ada utilitas file yang Anda lewati beberapa data yang menampilkan perkiraan entropi teoritis. Hanya apa yang perusahaan telekomunikasi dan disk mainkan?
Paul Uszak

Jawaban:

9

Entropi adalah fitur dari variabel acak . File yang diberikan tidak memiliki entropi, karena konstan. Entropi masuk akal dalam banyak situasi di mana tidak ada saluran, dan Anda dapat menerapkannya pada ansambel acak, misalnya, file WAV, yang dihasilkan dari sumber tertentu. Dalam hal ini, Anda adalah seluruh file WAV.x

NNHNHN+Hai(N)gzip

Karena hasil Lempel dan Ziv ini, entropi sumber dapat diperkirakan dengan mengompresi urutan sampel yang panjang menggunakan algoritma Lempel-Ziv. Ini tidak memperkirakan entropi sampel spesifik, yang bukan konsep yang terdefinisi dengan baik (urutan konstan memiliki nol entropi), melainkan entropi dari sumber yang menghasilkannya.

Konsep terkait adalah entropi algoritmik , juga dikenal sebagai kompleksitas Kolmogorov . Ini adalah panjang dari program terpendek yang menghasilkan file Anda. Kuantitas ini masuk akal untuk file individual. Dalam kasus file yang dihasilkan oleh sumber acak, teorema Lempel-Ziv menunjukkan bahwa entropi algoritme file dibatasi, dengan probabilitas tinggi, oleh entropi Shannon-nya. Sayangnya, entropi algoritmik tidak dapat dihitung, jadi ini lebih merupakan konsep teoretis.

Untuk melengkapi gambar, saya sarankan membaca makalah Shannon tentang Prediksi dan entropi bahasa Inggris yang dicetak untuk pendekatan yang berbeda untuk memperkirakan entropi sumber.

Yuval Filmus
sumber
Saya sudah. Dan kertas Schurmann & Grassberger. Berdasarkan estimasi entropi mereka untuk bahasa Inggris, tampaknya estimasi entropi terbaik yang bisa kita dapatkan adalah melalui kompresi dengan varian PAQ8 seperti fp8. Ada dan hasil saya menikah dengan cukup baik untuk prosa Shakespeare.
Paul Uszak
Masalahnya tampaknya adalah bahwa saya akan berpikir bahwa harus ada nilai teoritis yang membatasi untuk entropi sumber. Penentuan dengan kompresi hanya mencerminkan efisiensi dari algoritma kompresi. Secara empiris, gzip Anda baik, tetapi 7z lebih baik. Dan FP8 jauh lebih baik seperti yang ditunjukkan dalam pertanyaan saya. Bisakah saya menemukan bahwa hiss.wav hanya berisi 10 byte total entropi ketika saya menggunakan fp12000 di masa mendatang?
Paul Uszak
Entropi bukan properti file; setiap file tidak memiliki entropi. Sebaliknya, entropi adalah properti dari sumber acak. Ukuran keacakan yang sesuai untuk file tertentu adalah kompleksitas Kolmogorov (juga dikenal sebagai entropi algoritmik), tetapi sayangnya ukuran ini tidak dapat dihitung.
Yuval Filmus
Saat Anda mengompresi file untuk memperkirakan entropi sumber, Anda menggunakan teorema yang menjamin bahwa tingkat kompresi data yang dihasilkan oleh sumber mendekati entropi sumber. Namun, utilitas kompresi yang sebenarnya tidak menerapkan algoritma vanilla Lempel-Ziv, melainkan versi yang lebih praktis. Jika Anda ingin memperkirakan entropi, mungkin Anda harus mengimplementasikan algoritma dengan mengingat tujuan ini.
Yuval Filmus
Saya menghapus diskusi yang tidak konstruktif; komentar bukan untuk diskusi panjang kecuali untuk memperbaiki pos yang ada. Jika Anda ingin secara jujur ​​mendiskusikan masalah entropi, silakan buat ruang obrolan. Ingatlah untuk tetap sopan.
Raphael