Bisakah data dikompres dengan ukuran lebih kecil dari batas kompresi data Shannon?

17

Saya sedang membaca tentang algoritma kompresi data dan batas teoritis untuk kompresi data. Baru-baru ini saya menemukan metode kompresi yang disebut "Combinatorial Entropy Encoding", ide utama dari metode ini adalah untuk menyandikan file sebagai karakter yang disajikan dalam file, frekuensi mereka dan indeks permutasi karakter ini diwakili oleh file.

Dokumen-dokumen ini dapat membantu menjelaskan metode ini:

https://arxiv.org/pdf/1703.08127

http://www-video.eecs.berkeley.edu/papers/vdai/dcc2003.pdf

https://www.thinkmind.org/download.php?articleid=ctrq_2014_2_10_70019

Namun, dalam dokumen pertama saya telah membaca bahwa dengan menggunakan metode ini mereka dapat memampatkan beberapa teks menjadi kurang dari batas Shannon (Mereka tidak mempertimbangkan ruang yang diperlukan untuk menyimpan frekuensi karakter dan ruang yang diperlukan untuk menyimpan meta data file). Saya memikirkannya dan saya menemukan bahwa metode ini tidak akan sangat efisien untuk file yang sangat kecil tetapi di sisi lain itu dapat bekerja dengan baik dengan file besar. Sebenarnya saya tidak sepenuhnya memahami algoritma ini atau batas Shannon sangat baik, saya hanya tahu itu jumlah dari probabilitas masing-masing karakter dikalikan dengan dari timbal balik dari probabilitas.log2

Jadi saya punya beberapa pertanyaan:

  1. Apakah metode kompresi ini benar-benar memampatkan file menjadi lebih kecil dari batas Shannon?

  2. Apakah ada algoritma kompresi yang memampatkan file hingga kurang dari batas Shannon (jawaban untuk pertanyaan ini sejauh yang saya tahu tidak)?

  3. Bisakah metode kompresi yang mengkompres file menjadi lebih kecil dari batas Shannon pernah ada?

  4. Jika pengkodean kombinatorial benar-benar memampatkan file di luar batas Shannon, apakah tidak mungkin untuk memampatkan file berulang-ulang sampai kita mencapai ukuran file yang kita inginkan?

information-theory data-compression HTG
sumber
26
Shannon membuktikan bahwa Anda tidak dapat memampatkan di bawah batas Shannon.
Yuval Filmus
11
Anda dapat pergi di bawah batas Shannon dengan kompresi lossy . Shannon hanya menunjukkan Anda tidak dapat memampatkan di bawah batas tanpa kehilangan informasi . @YuvalFilmus. Seperti, pada gambar RGB, Anda dapat membuang bit orde rendah komponen R, G, B.
smci
Relevan: cs.stackexchange.com/a/44643/26146
Quuxplusone
6
@smci Itu sebagian besar tidak relevan dalam diskusi tentang teori kompresi. Jelas saya bisa membuang setiap bit dan menyebutnya kompresi.
pipa
1
Katakanlah saya memiliki file besar seperti gambar. Sekarang dalam model saya memetakan seluruh gambar menjadi "1" ha..Saya telah mengompresi di bawah batas Shannon karena seluruh gambar dikompresi menjadi "1" ......
Pieter B

Jawaban:

34

Sebenarnya saya tidak sepenuhnya memahami algoritma ini atau batas Shannon dengan sangat baik, saya hanya tahu itu adalah jumlah dari probabilitas setiap karakter dikalikan dengan log2 dari kebalikan dari probabilitas.

Di sinilah letak intinya. Batas Shannon bukan properti universal string teks. Ini adalah properti dari string teks ditambah model yang menyediakan (mungkin tergantung konteks) probabilitas simbol. Ini memberi tahu kita seberapa baik model itu dapat memampatkan teks, dengan asumsi model itu akurat .

Jika Anda menggunakan satu model untuk menghitung batas Shannon dan kemudian model yang berbeda untuk kompres, jika model kedua lebih akurat Anda dapat mengalahkan batas Shannon asli yang telah Anda hitung, tetapi itu tidak terlalu relevan.

orlp
sumber
4
Untuk membuat contoh praktis, jika Anda tahu data Anda terdiri dari satu huruf yang diulang N kali, Anda dapat mencapai tingkat kompresi besar secara sewenang-wenang (yaitu mulai dari 10 miliar 'a' menjadi tuple ('a', 10000000))
Sem
12

Sangat mudah untuk menunjukkan bahwa Anda dapat mengompres di bawah batas Shannon - ambil kompresor curang yang memiliki banyak file umum yang ditetapkan untuk token. File-file tersebut disimpan sebagai token tersebut. (Jelas, kompresor harus sangat besar, atau menggambar di perpustakaan yang sangat besar.)

Kompresor pada dasarnya akan kurang efisien dalam menangani file apa pun yang tidak ada di pustaka, karena kompresor harus membedakan token dari kompresi normal.

Yang tidak bisa Anda lakukan adalah memiliki kompresor yang mengalahkan batas Shannon pada semua file .

Loren Pechtel
sumber
11

1/21/31/6plog2(1/p)

Tetapi jika Anda menerapkan model lain, Anda akan mendapatkan urutan probabilitas lainnya. Jika huruf "u" agak jarang, maka kemungkinannya untuk seluruh teks mungkin 3%, dan itu adalah probabilitas Anda harus menetapkan untuk surat ini menggunakan model Markov pesanan-0 .

Tetapi dalam teks bahasa Inggris, setelah "q" biasanya muncul "u", jadi menggunakan model order-1, Anda dapat menetapkan probabilitas yang jauh lebih tinggi untuk "u" setelah "q", sehingga meningkatkan rasio kompresi.

Selain itu, beberapa model menghasilkan simbol yang lebih sedikit daripada yang dimasukkan, fe LZ77 menggantikan pengulangan teks dengan referensi-belakang, sehingga "abababab" berubah menjadi "ab [2,8]".

Ketika seseorang berbicara tentang entropi Shannon dari beberapa data alih-alih data yang dikompresi oleh model tertentu, ia biasanya berarti entropi Shannon yang diproduksi oleh model order-0, yaitu menetapkan masing-masing simbol kemungkinannya atas seluruh teks. Jelas, Anda dapat mengalahkan margin ini dengan menerapkan model yang lebih canggih untuk data.

Bulat
sumber
3

Kemungkinan interpretasi lain dari teks: algoritma kompresi yang diberikan akan memberi Anda kompresi yang lebih baik dari beberapa teks, dan kompresi yang lebih buruk pada yang lain. Namun, pengguna umumnya lebih memperhatikan beberapa jenis file (halaman HTML dalam bahasa Inggris, 80386 kode mesin) lebih dari yang lain (tabel angka yang benar-benar acak, suara tidak berarti yang dipilih untuk meminimalkan pengulangan). Skema kompresi apa pun akan menjadi lebih baik dalam mengompresi data dunia nyata dengan menjadi lebih buruk daripada tidak berguna dalam mengompresi jenis string tertentu lainnya.

Davislor
sumber