Kompresi nama domain

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?).

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.