Kompresi nama domain

21

Saya ingin tahu bagaimana seseorang dapat dengan sangat kompak mengompres domain dari nama host IDN yang sewenang-wenang (seperti yang didefinisikan oleh RFC5890 ) dan menduga ini bisa menjadi tantangan yang menarik. Host Unicode atau nama domain (U-label) terdiri dari serangkaian karakter Unicode, biasanya dibatasi pada satu bahasa tergantung pada domain tingkat atas (misalnya huruf Yunani di bawah .gr), yang dikodekan ke dalam string ASCII yang dimulai dengan xn--(yang sesuai A-label).

Seseorang dapat membangun model data tidak hanya dari persyaratan formal itu

  • setiap label non-Unicode menjadi pencocokan string ^[a-z\d]([a-z\d\-]{0,61}[a-z\d])?$;

  • setiap A-label menjadi pencocokan string ^xn--[a-z\d]([a-z\d\-]{0,57}[a-z\d])?$; dan

  • panjang total seluruh domain (label A dan label non-IDN yang digabungkan dengan pembatas '.') tidak melebihi 255 karakter

tetapi juga dari berbagai heuristik, termasuk:

  • U-label tingkat rendah sering merupakan frasa yang valid secara leksikal, sintaksis, dan semantik dalam beberapa bahasa alami termasuk nomina dan angka yang tepat (tidak diselingi kecuali tanda hubung, dihilangkan spasi dan dilipat menurut Nameprep ), dengan preferensi untuk frasa yang lebih pendek; dan

  • label tingkat tinggi diambil dari kamus SLD dan TLD dan memberikan konteks untuk memprediksi bahasa alami mana yang digunakan dalam label tingkat rendah.

Saya khawatir bahwa mencapai kompresi string pendek yang baik akan sulit tanpa mempertimbangkan fitur spesifik data ini dan, lebih lanjut, bahwa perpustakaan yang ada akan menghasilkan overhead yang tidak perlu untuk mengakomodasi kasus penggunaan yang lebih umum.

Membaca buku online Matt Mahoney Data Compression Dijelaskan , jelas bahwa sejumlah teknik yang ada dapat digunakan untuk mengambil keuntungan dari asumsi pemodelan di atas (dan / atau lainnya) yang seharusnya menghasilkan kompresi yang jauh lebih unggul dibandingkan alat yang kurang spesifik.

Secara konteks, pertanyaan ini adalah cabang dari yang sebelumnya pada SO .


Pikiran awal

Itu mengejutkan saya bahwa masalah ini adalah kandidat yang sangat baik untuk pelatihan offline dan saya membayangkan format data terkompresi di sepanjang baris berikut:

  • Pengodean Huffman dari " sufiks publik ", dengan probabilitas diambil dari beberapa sumber yang diterbitkan untuk pendaftaran domain atau volume lalu lintas;

  • Pengodean Huffman yang modelnya (bahasa alami) digunakan untuk label-U yang tersisa, dengan probabilitas diambil dari beberapa sumber yang diterbitkan dari pendaftaran domain atau volume lalu lintas dengan konteks akhiran domain;

  • Terapkan beberapa transformasi berbasis kamus dari model bahasa alami yang ditentukan; dan

  • Pengodean aritmatika dari masing-masing karakter dalam label-U, dengan probabilitas yang diambil dari model bahasa alami adaptif kontekstual yang berasal dari pelatihan offline (dan mungkin juga online, meskipun saya menduga datanya mungkin terlalu pendek untuk memberikan wawasan yang berarti?).

eggyal
sumber
4
Mungkin Anda bisa mengunduh daftar semua nama domain, dan memberikan masing-masing nomor. Ini akan sangat kompak.
@Dietrich Epp: Memang - dan sebenarnya, saya berpikir bahwa mungkin pendaftar mungkin mempublikasikan di WHOIS nomor seri setiap pendaftaran yang darinya ini dapat dibangun, tetapi sayangnya tidak. Secara realistis, saya pikir tantangan praktis dalam mempertahankan database seperti itu membuatnya tidak mungkin: belum lagi bahwa database seperti itu tidak menangani subdomain.
eggyal
... yah, jika jumlahnya cukup, cukup ambil 4/6 byte dari alamat ipv4 / 6: /
@arnaud: Membalikkan masalah - bergantung pada penunjuk yang benar di .in-addr.arpa; juga rusak jika IP pernah berubah.
eggyal
1
Dengan metode Dietrich Epp (berdasarkan perkiraan 196m domain) Anda dapat menyimpan nama domain dalam 28 bit (dua karakter unicode), dan Anda tidak dapat melakukan yang lebih baik. Tentu saja, distribusi probabilitas atas nama domain dapat memberi Anda jumlah bit yang diharapkan jauh lebih baik. Anda setidaknya bisa menggunakan kode aritmatika untuk 1 juta domain paling populer dan menggunakan beberapa skema ad-hoc untuk yang lainnya.
Peter

Jawaban:

0

Pengodean Huffman optimal untuk huruf dan tentu saja dapat disesuaikan dengan urutan. Misalnya, jika urutan "ab" menghasilkan bit lebih sedikit daripada bit untuk "a" dan "b", maka cukup tambahkan ke pohon ... dan seterusnya.

... Anda mungkin juga dapat menggunakan beberapa pustaka sederhana yang melakukan itu semua untuk Anda dengan kinerja mendekati optimal, sehingga Anda tidak akan mendapatkan banyak menggunakan algoritma kompresi super mewah yang dibuat khusus.


sumber
Saya pikir Huffman tidak cukup optimal (itu bulat ke bit terdekat): pengkodean aritmatika harus selalu mengungguli. Dan kecuali seseorang menerapkan model akurat dari data yang dikompres, ia akan selalu mencapai hasil yang optimal ... jadi jika setiap bit penting, perpustakaan umum tidak cukup.
eggyal
4
Pengodean Huffman optimal asimtotik jika Anda mengabaikan korelasi antara huruf (misalnya, jika Anda melihat a q, maka huruf berikutnya jauh lebih mungkin menjadi udaripada yang seharusnya). Tapi itu bukan asumsi yang realistis. Dalam praktiknya, korelasi tersebut sangat besar dan memungkinkan seseorang untuk melakukan jauh lebih baik daripada pengkodean Huffman yang naif dalam praktiknya.
DW
@DW apakah Anda punya rekomendasi untuk bagaimana orang bisa melakukan yang lebih baik? Apakah mungkin membantu untuk memungkinkan pasangan atau tiga kali lipat dari karakter yang berdekatan untuk dikodekan melalui Huffman?
ryan