Apa cara paling efisien untuk menyimpan rentang angka?

Pertanyaan ini adalah tentang berapa banyak bit yang diperlukan untuk menyimpan rentang. Atau dengan kata lain, untuk jumlah bit tertentu, berapa kisaran maksimum yang dapat disimpan dan bagaimana caranya?

Bayangkan kita ingin menyimpan sub-rentang dalam kisaran 0-255.

Jadi misalnya, 45-74.

Kita dapat menyimpan contoh di atas sebagai dua byte yang tidak ditandai, tetapi menurut saya harus ada redundansi informasi di sana. Kita tahu bahwa nilai kedua lebih besar dari yang pertama, jadi dalam hal nilai pertama besar, bit lebih sedikit diperlukan untuk nilai kedua, dan dalam hal nilai kedua besar, bit lebih sedikit diperlukan untuk yang pertama .

Saya menduga bahwa teknik kompresi apa pun akan menghasilkan hasil marjinal, jadi mungkin pertanyaan yang lebih baik untuk bertanya "berapa kisaran maksimum yang dapat disimpan dalam satu byte?". Ini harus lebih besar dari apa yang dapat dicapai dengan menyimpan dua angka secara terpisah.

Apakah ada algoritma standar untuk melakukan hal semacam ini?

Hitung saja jumlah rentang yang mungkin. Ada 256 rentang dengan batas bawah 0 (0-0, 0-1, ... 0-254, 0-255), 255 rentang dengan batas bawah 1, ... dan akhirnya 1 rentang dengan batas bawah 255 (255- 255). Jadi jumlah totalnya adalah (256 + 255 + ... + 1) = 257 * 128 = 32.896. Karena ini sedikit lebih tinggi dari 2 ¹⁵ = 32.768, Anda masih memerlukan setidaknya 16 bit (2 byte) untuk menyimpan informasi ini.

Secara umum, untuk angka dari 0 hingga n-1, jumlah rentang yang mungkin adalah n * (n + 1) / 2. Ini kurang dari 256 jika n adalah 22 atau kurang: n = 22 memberikan 22 * ​​23/2 = 253 kemungkinan. Jadi satu byte sudah cukup untuk sub-rentang 0-21 .

Cara lain untuk melihat masalah adalah sebagai berikut: menyimpan sepasang bilangan bulat dalam kisaran 0 hingga n-1 hampir sama dengan menyimpan subrange dari 0 (n-1) ditambah bit tunggal yang menentukan apakah angka pertama lebih rendah atau lebih tinggi dari yang kedua. (Perbedaannya datang dari kasus ketika kedua bilangan bulat adalah sama, tetapi kesempatan ini menjadi semakin kecil karena n tumbuh lebih besar.) Itulah sebabnya Anda hanya dapat menghemat sekitar satu bit dengan teknik ini, dan mungkin alasan utama mengapa itu jarang digunakan.

Untuk sejumlah kecil bit, tidak mungkin menyimpan banyak bit seperti yang ditunjukkan Glorfindel . Namun, jika domain yang Anda gunakan memiliki beberapa bit lebih banyak, Anda dapat mencapai penghematan yang signifikan untuk kasus rata-rata dengan menyandikan rentang dengan nilai awal dan delta.

Mari kita asumsikan domain adalah bilangan bulat, jadi 32 bit. Dengan pendekatan naif, Anda perlu 64 bit (mulai, akhir) untuk menyimpan rentang.

Jika kita beralih ke penyandian (mulai, delta), kita dapat membuat akhir rentang dari itu. Kita tahu bahwa dalam kasus terburuk, awal adalah 0 dan delta memiliki 32 bit.

2 ^ 5 adalah 32, jadi kami menyandikan panjang delta dalam lima bit (tanpa panjang nol, selalu menambahkan 1), dan enkode menjadi (mulai, panjang, delta). Dalam kasus terburuk, harganya 32 * 2 + 5 bit, jadi 69 bit. Jadi dalam kasus terburuk, jika semua rentang panjang, ini lebih buruk daripada pengkodean naif.

Dalam kasus terbaik, harganya 32 + 5 + 1 = 38 bit.

Ini berarti jika Anda harus menyandikan banyak rentang, dan rentang itu masing-masing hanya mencakup sebagian kecil dari domain Anda, Anda akhirnya menggunakan lebih sedikit ruang rata - rata menggunakan pengodean ini. Tidak masalah bagaimana start didistribusikan, karena start akan selalu mengambil 32 bit, tetapi tidak masalah bagaimana panjang rentang didistribusikan. Jika semakin kecil panjang yang Anda miliki, semakin baik kompresi, semakin banyak rentang yang Anda miliki yang mencakup seluruh panjang domain, semakin buruk pengkodean ini.

Namun, jika Anda memiliki banyak rentang yang dikelompokkan di sekitar titik awal yang sama, (misalnya karena Anda mendapatkan nilai dari sensor), Anda dapat mencapai penghematan yang lebih besar. Anda bisa menerapkan teknik yang sama dengan nilai awal dan menggunakan bias untuk mengimbangi nilai awal.

Katakanlah Anda memiliki 10.000 rentang. Rentang dikelompokkan di sekitar nilai tertentu. Anda menyandikan bias dengan 32 bit.

Dengan menggunakan pendekatan naif, Anda akan membutuhkan 32 * 2 * 10 000 = 640 000 bit untuk menyimpan semua rentang tersebut.

Pengkodean bias membutuhkan 32 bit, dan pengodean setiap rentang dalam kasus terbaik maka 5 + 1 + 5 + 1 = 12 bit, dengan total 120 000 + 32 = 120 032 bit. Dalam kasus terburuk, Anda membutuhkan 5 + 32 + 5 + 32 bit, sehingga 74 bit, dengan total 740 032 bit.

Ini berarti, untuk 10.000 nilai pada domain yang membutuhkan 32 bit untuk menyandikan, kita dapatkan

• 120 032 bit dengan pengkodean delta pintar dalam kasus terbaik
• 640 000 bit dengan awal yang naif, end encoding, selalu (tidak ada kasus terbaik atau terburuk)
• 740 032 bit dengan pengkodean delta pintar dalam kasus terburuk

Jika Anda menggunakan pengkodean naif sebagai baseline, itu berarti penghematan hingga 81,25% atau hingga 15,625% lebih banyak biaya.

Bergantung pada bagaimana nilai Anda didistribusikan, penghematan itu penting. Ketahui domain bisnis Anda! Ketahui apa yang ingin Anda enkode.

Sebagai ekstensi, Anda juga dapat mengubah bias. Jika Anda menganalisis data dan mengidentifikasi kelompok nilai, Anda dapat mengurutkan data ke dalam kotak dan menyandikan masing-masing kotak secara terpisah, dengan biasnya sendiri. Ini berarti Anda dapat menerapkan teknik ini tidak hanya untuk rentang yang dikelompokkan di sekitar nilai awal tunggal, tetapi juga untuk rentang yang dikelompokkan di sekitar beberapa nilai.

Jika titik awal Anda didistribusikan secara merata, pengkodean ini tidak benar-benar berfungsi dengan baik.

Pengkodean ini jelas sangat buruk untuk diindeks. Anda tidak bisa begitu saja membaca nilai x-th. Cukup banyak hanya dapat dibaca secara berurutan. Yang sesuai dalam beberapa situasi, misalnya streaming melalui jaringan atau penyimpanan massal (misalnya pada kaset atau HDD).

Mengevaluasi data, mengelompokkannya, dan memilih bias yang tepat dapat menjadi pekerjaan yang substansial dan mungkin memerlukan beberapa penyesuaian untuk hasil yang optimal.

Masalah semacam ini adalah subjek dari makalah seminal Claude Shannon, A The Mathematical Theory of Communication , yang memperkenalkan kata "bit" dan lebih atau kurang diciptakan kompresi data.

Gagasan umum adalah bahwa jumlah bit yang digunakan untuk mengkodekan suatu rentang berbanding terbalik dengan probabilitas rentang itu terjadi. Misalnya, kisaran 45-74 muncul sekitar 1/4 dari waktu. Anda dapat mengatakan bahwa urutan 00 sesuai dengan 45-74. Untuk menyandikan kisaran 45-74, Anda menghasilkan "00" dan berhenti di sana.

Mari kita juga mengira bahwa kisaran 99-100 dan 140-155 masing-masing muncul sekitar 1/8 waktu. Anda dapat menyandikan masing-masing dengan urutan 3 bit. Setiap 3 bit akan dilakukan selama mereka tidak memulai dengan "00", yang telah dicadangkan untuk kisaran 45-74.

00: 45-74
010: 99-100
101: 140-155

Anda dapat melanjutkan dengan cara ini sampai setiap rentang yang memungkinkan memiliki penyandian. Kisaran yang paling kecil kemungkinan membutuhkan lebih dari 100 bit. Tapi tidak apa-apa karena jarang muncul.

Ada yang algoritma untuk menemukan optimal coding. Saya tidak akan mencoba menjelaskannya di sini, tetapi Anda dapat menemukan lebih banyak dengan mengunjungi tautan di atas atau mencari "Teori Informasi", "Pengodean Shannon-fano", atau "Pengodean Huffman".

Seperti yang telah ditunjukkan orang lain, mungkin lebih baik untuk menyimpan nomor awal dan perbedaan antara nomor awal dan akhir. Anda harus menggunakan satu pengkodean untuk memulai dan yang lainnya untuk perbedaan, karena mereka memiliki distribusi probabilitas yang berbeda (dan saya rasa yang terakhir lebih berlebihan). Seperti yang disarankan polygnome, algoritma terbaik tergantung pada domain Anda.

Untuk memperluas jawaban dari @Glorfindel:

Seperti n → ∞, (n - 1) → n. Dengan demikian, Ω (rentang) → n² / 2 dan log (Ω (rentang)) → (2n - 1). Karena pengodean naif membutuhkan 2n bit, kompresi maksimal asimptotik hanya menghemat 1 bit.

Ada jawaban yang serupa, tetapi untuk mencapai kompresi optimal, Anda perlu:

1. Metode pengkodean entropi yang optimal (baca tentang pengkodean Aritmatika dan yang pada dasarnya setara (rasio kompresi yang sama, sedikit lebih cepat tetapi juga lebih sulit untuk dipahami) ANS )
2. Sebanyak mungkin informasi tentang distribusi data. Yang terpenting, ini tidak hanya melibatkan "menebak" seberapa sering satu angka muncul, tetapi Anda sering dapat mengesampingkan kemungkinan tertentu. Misalnya, Anda dapat mengesampingkan interval ukuran negatif, dan mungkin ukuran 0, tergantung pada bagaimana Anda menentukan interval yang valid. Jika Anda memiliki beberapa interval untuk menyandikan sekaligus, Anda dapat mengurutkannya misalnya dalam urutan penurunan lebar, atau meningkatkan nilai awal / akhir, dan mengesampingkan banyak nilai (misalnya jika Anda menjamin pesanan dengan mengurangi lebar, interval sebelumnya memiliki lebar 100, dan nilai awal untuk yang berikutnya adalah 47, Anda hanya perlu mempertimbangkan kemungkinan hingga 147 untuk nilai akhir).

Yang penting, angka 2 berarti Anda ingin menyandikan hal-hal sedemikian rupa sehingga nilai paling informatif (per bit dikodekan) datang terlebih dahulu. Misalnya, sementara saya menyarankan untuk menyandikan daftar yang disortir "apa adanya", biasanya akan lebih pintar untuk menyandikannya sebagai "pohon biner" - yaitu jika mereka disortir berdasarkan lebar, dan Anda memiliki lenelemen, mulailah dengan menyandikan elemen. len/2. Katakanlah itu memiliki lebar w. Sekarang Anda tahu semua elemen sebelum memiliki lebar di suatu tempat di [0, w], dan semua elemen setelahnya memiliki lebar di suatu tempat di [w, maks val yang Anda terima]. Ulangi secara berulang (membagi lagi setiap setengah menjadi dua, dll) sampai Anda membahas lenelemen (kecuali jika sudah diperbaiki, Anda akan ingin menyandikanlenpertama, jadi Anda tidak perlu repot dengan mengakhiri token). Jika "max val you accept" benar-benar terbuka, mungkin pintar untuk terlebih dahulu menyandikan nilai tertinggi yang sebenarnya muncul dalam data Anda, yaitu elemen terakhir, dan kemudian melakukan partisi biner. Sekali lagi, apapun yang paling informatif per bit pertama

Juga, jika Anda mengkodekan lebar interval terlebih dahulu, dan Anda tahu nilai maksimum yang mungkin Anda hadapi, jelas Anda dapat mengesampingkan semua nilai awal yang akan membuatnya melimpah ... Anda mendapatkan ide. Ubah dan pesan data Anda sedemikian rupa sehingga Anda dapat menyimpulkan sebanyak mungkin tentang sisa data saat Anda mendekode, dan algoritma pengodean entropi yang optimal akan memastikan Anda tidak membuang-buang bit untuk mengenkode info yang Anda "sudah tahu" .