Algoritma kompresi yang efisien untuk string teks pendek [tertutup]

Saya mencari algoritme untuk mengompresi string teks kecil: 50-1000 byte (yaitu URL). Algoritma mana yang paling cocok untuk ini?

Lihat Smaz :

Smaz adalah pustaka kompresi sederhana yang cocok untuk mengompresi string yang sangat pendek.

Huffman memiliki biaya statis, tabel Huffman, jadi saya tidak setuju itu pilihan yang baik.

Ada versi adaptasi yang menghilangkan ini, tetapi tingkat kompresi mungkin menderita. Sebenarnya, pertanyaan yang harus Anda tanyakan adalah "algoritma apa untuk memampatkan string teks dengan karakteristik ini". Misalnya, jika pengulangan panjang diharapkan, Pengodean Run-Lengh sederhana mungkin sudah cukup. Jika Anda dapat menjamin bahwa hanya kata-kata bahasa Inggris, spasi, tanda baca dan angka sesekali akan hadir, maka Huffman dengan tabel Huffman yang telah ditentukan sebelumnya dapat memberikan hasil yang baik.

Secara umum, algoritma dari keluarga Lempel-Ziv memiliki kompresi dan kinerja yang sangat baik, dan perpustakaan untuk mereka berlimpah. Saya akan pergi dengan itu.

Dengan informasi bahwa apa yang dikompresi adalah URL, maka saya akan menyarankan itu, sebelum mengompresi (dengan algoritma apa pun yang mudah tersedia), Anda CODIFY mereka. URL mengikuti pola yang jelas, dan beberapa bagiannya sangat mudah diprediksi. Dengan memanfaatkan pengetahuan ini, Anda dapat menyusun URL menjadi sesuatu yang lebih kecil untuk memulai, dan ide-ide di balik penyandian Huffman dapat membantu Anda di sini.

Misalnya, menerjemahkan URL ke bit stream, Anda dapat mengganti "http" dengan bit 1, dan apa pun dengan bit "0" diikuti oleh procotol yang sebenarnya (atau menggunakan tabel untuk mendapatkan protokol umum lainnya, seperti https, ftp, file). Tanda ": //" dapat dihapus seluruhnya, selama Anda dapat menandai akhir dari protokol. Dll. Baca tentang format URL, dan pikirkan bagaimana mereka dapat dikodifikasikan untuk menghemat ruang.

Saya tidak punya kode, tapi saya selalu menyukai pendekatan membangun tabel pencarian 2D ukuran 256 * 256 karakter ( RFC 1978 , PPP Predictor Compression Protocol ). Untuk mengompres string, Anda mengulangi masing-masing karakter dan menggunakan tabel pencarian untuk mendapatkan karakter berikutnya yang 'diprediksi' menggunakan karakter saat ini dan sebelumnya sebagai indeks ke dalam tabel. Jika ada kecocokan yang Anda tuliskan 1 bit, jika tidak tulis 0, char dan perbarui tabel pencarian dengan char saat ini. Pendekatan ini pada dasarnya mempertahankan tabel pencarian dinamis (dan mentah) dari karakter berikutnya yang paling mungkin dalam aliran data.

Anda bisa mulai dengan tabel looked yang memusatkan perhatian, tetapi jelas itu bekerja paling baik pada string yang sangat pendek jika diinisialisasi dengan karakter yang paling mungkin untuk setiap pasangan karakter, misalnya, untuk bahasa Inggris. Selama tabel pencarian awal sama untuk kompresi dan dekompresi Anda tidak perlu memancarkannya ke dalam data terkompresi.

Algoritme ini tidak memberikan rasio kompresi yang brilian, tetapi sangat hemat dengan memori dan sumber daya CPU dan juga dapat bekerja pada aliran data yang berkelanjutan - dekompresor menyimpan salinan tabel pencarian sendiri saat terdekompresi, sehingga tabel pencarian menyesuaikan dengan tipe data yang dikompresi.

Algoritma / pustaka apa pun yang mendukung kamus preset, mis . Zlib .

Dengan cara ini Anda dapat menggunakan kompresor dengan jenis teks yang sama yang kemungkinan akan muncul di input. Jika file serupa dalam beberapa cara (misalnya semua URL, semua program C, semua posting StackOverflow, semua gambar ASCII-art) maka substring tertentu akan muncul di sebagian besar atau semua file input.

Setiap algoritma kompresi akan menghemat ruang jika substring yang sama diulang beberapa kali dalam satu file input (misalnya "the" dalam teks bahasa Inggris atau "int" dalam kode C.)

Tetapi dalam kasus URL string tertentu (misalnya " http: // www .", ".Com", ".html", ".aspx" biasanya akan muncul satu kali di setiap file input. Jadi, Anda perlu membaginya di antara file entah bagaimana daripada memiliki satu kejadian terkompresi per file. Menempatkan mereka dalam kamus yang telah ditetapkan akan mencapai ini.

Pengodean Huffman umumnya berfungsi baik untuk ini.

Jika Anda berbicara tentang mengompres teks tidak hanya memperpendek lalu Mengempis / gzip (membungkus gzip), zip berfungsi dengan baik untuk file dan teks yang lebih kecil. Algoritma lain sangat efisien untuk file yang lebih besar seperti bzip2 dll.

Wikipedia memiliki daftar waktu kompresi. (cari perbandingan efisiensi)

Name       | Text         | Binaries      | Raw images
-----------+--------------+---------------+-------------
7-zip      | 19% in 18.8s | 27% in  59.6s | 50% in 36.4s
bzip2      | 20% in  4.7s | 37% in  32.8s | 51% in 20.0s
rar (2.01) | 23% in 30.0s | 36% in 275.4s | 58% in 52.7s
advzip     | 24% in 21.1s | 37% in  70.6s | 57& in 41.6s
gzip       | 25% in  4.2s | 39% in  23.1s | 60% in  5.4s
zip        | 25% in  4.3s | 39% in  23.3s | 60% in  5.7s

Anda mungkin ingin melihat Skema Kompresi Standar untuk Unicode .

SQL Server 2008 R2 menggunakannya secara internal dan dapat mencapai kompresi hingga 50%.