Menyusun kembali data (serangkaian string) untuk mengoptimalkan kompresi?

12

Apakah ada algoritma untuk menata ulang data untuk mengoptimalkan kompresi? Saya mengerti ini khusus untuk data dan algoritma kompresi, tetapi apakah ada kata untuk topik ini? Di mana saya dapat menemukan penelitian di bidang ini?

Secara khusus, saya memiliki daftar json berisi 1,5 juta string, dan saya ingin menyusun ulang string sehingga kompresi gzip (untuk HTTP) dioptimalkan. Menyortir string tidak cukup baik, tetapi saya tidak benar-benar tahu apakah itu optimal.

optimization permutations Jayen
sumber
1
Menyusun ulang string secara optimal untuk kompresi gzip (LZ77 dengan jendela geser kecil) terdengar seperti masalah NP-hard. Anda mungkin dapat menemukan pengurangan dari masalah superstring umum terpendek.
Jouni Sirén
@ JouniSirén Saya pikir substring umum terpanjang adalah pendekatan yang lebih baik karena superstring umum terpendek membatasi saya untuk memiliki bagian umum back-to-back, kan? Saya tidak keberatan NP-keras selama itu dapat ditelusuri (seperti membutuhkan satu hari untuk berjalan pada mesin modern).
Jayen

Jawaban:

6

Ini adalah tambahan untuk jawaban Navin Goyal.

Karena file JSON dapat dianggap sebagai struktur data pohon, Anda dapat menggunakan XBW-transform untuk pohon, yang merupakan perpanjangan dari transformasi Burrows-Wheeler untuk string.

Hiroki Yanagisawa
sumber
1
Terima kasih untuk itu. Saya hanya memiliki daftar / array JSON, bukan objek JSON, jadi saya tidak melihat bagaimana itu dapat dianggap sebagai pohon. Saya bisa mengubah string menjadi trie, tapi kemudian saya tidak melihat bagaimana ini berhubungan dengan XBW-transform.
Jayen
4

Burrows - Transformasi Wheeler adalah algoritma kompresi terkenal yang bekerja dengan menyusun ulang karakter dalam string yang akan dikompresi.

Navin Goyal
sumber
1
Terima kasih untuk itu, tetapi saya tidak yakin bagaimana saya bisa menggunakan informasi ini. Saya ingin memesan ulang string dalam daftar untuk dikompresi, tetapi saya tidak peduli jika saya bisa mendapatkan kembali urutan aslinya.
Jayen
1

Untuk meningkatkan kompresi gzip, Anda ingin string "mirip" berada dekat dalam daftar. Ada sejumlah cara untuk mendefinisikan kesamaan tersebut; biarkan saya menggambarkan yang masuk akal yang bekerja dengan baik dalam praktik. Ingat bahwa ukuran blok gzip adalah 64K. Dengan demikian, data Anda akan dibagi menjadi blok-blok 64K byte dan setiap blok akan dikompresi secara independen. Untuk mengoptimalkan kompresi, kita perlu meminimalkan jumlah k-mers yang berbeda (substring ukuran k) di setiap blok. Motivasinya adalah bahwa semua substring tersebut akan diganti dengan pengenal.

Sementara masalah di atas sulit secara teori (ini adalah varian dari partisi hypergraph), ada algoritma praktis yang cepat. Saya akan merekomendasikan pengelompokan seperti LSH yang dapat diimplementasikan dengan sekali lewati data Anda. Perhatikan bahwa penyortiran (menurut abjad) adalah cara lain untuk "mengelompokkan" string yang sama menjadi satu. Namun, algoritma pengelompokan khusus dapat berkinerja lebih baik.

Alternatifnya adalah dengan menggunakan zstd , yang (i) lebih cepat, (ii) memperoleh rasio kompresi yang lebih tinggi, dan (iii) tidak memiliki batasan pada ukuran blok (dan dengan demikian, kompres string sama baiknya terlepas dari pemesanan input).

Sergey Pupyrev
sumber
0

Saya melihat suatu algoritma beberapa waktu lalu yang mungkin bisa bermanfaat. Ini menggunakan algoritma edit jarak untuk menghitung jarak antara setiap kata. Dengan demikian, itu membangun grafik yang masing-masing berat tepi jarak ini. Akhirnya, ia mendapat pesanan memilih jalur yang memiliki jumlah bobot terendah. Mungkin itu bisa meningkatkan gzip.

Rafael Ribeiro
sumber
kedengarannya tidak bisa ditelusuri, tetapi jika seseorang mencobanya, silakan kirim komentar dengan hasil Anda
Jayen
Saya akan mencoba mengujinya. Saya ingin tahu tentang masalah ini. Selain itu, menurut Anda mengapa itu tidak bisa ditelusuri?
Rafael Ribeiro
sejauh yang saya tahu, edit jarak adalah O (nm), di mana n dan m adalah jumlah huruf dalam pasangan string dan Anda harus melakukan ini untuk setiap pasangan string O (s ^ 2), jadi jika n = m, itu O (s ^ 2 * n ^ 2) yang terdengar sulit bagi saya untuk 1,5 juta string.
Jayen
Oh, saya tidak terlalu mengkhawatirkan kompleksitas karena saya pikir masalah Anda adalah mengurangi ukuran biner saja. Jadi operasi ini akan terjadi lebih sering, bukan?
Rafael Ribeiro
Saya sedang mencari di sini dan mungkin biaya edit dapat dikurangi menggunakan levenshtein automata
Rafael Ribeiro