# Compression of domain names

I am curious as to how one might very compactly compress the domain of an arbitrary IDN hostname (as defined by RFC5890) and suspect this could become an interesting challenge. A Unicode host or domain name (U-label) consists of a string of Unicode characters, typically constrained to one language depending on the top-level domain (e.g. Greek letters under .gr), which is encoded into an ASCII string beginning with xn-- (the corresponding A-label).

One can build data models not only from the formal requirements that

• each non-Unicode label be a string matching ^[a-z\d]([a-z\d\-]{0,61}[a-z\d])?$; • each A-label be a string matching ^xn--[a-z\d]([a-z\d\-]{0,57}[a-z\d])?$; and

• the total length of the entire domain (A-labels and non-IDN labels concatenated with '.' delimiters) not exceed 255 characters

but also from various heuristics, including:

• lower-order U-labels are often lexically, syntactically and semantically valid phrases in some natural language including proper nouns and numerals (unpunctuated except hyphen, stripped of whitespace and folded per Nameprep), with a preference for shorter phrases; and

• higher-order labels are drawn from a dictionary of SLDs and TLDs and provide context for predicting which natural language is used in the lower-order labels.

I fear that achieving good compression of such short strings will be difficult without considering these specific features of the data and, furthermore, that existing libraries will produce unnecessary overhead in order to accomodate their more general use cases.

Reading Matt Mahoney's online book Data Compression Explained, it is clear that a number of existing techniques could be employed to take advantage of the above (and/or other) modelling assumptions which ought to result in far superior compression versus less specific tools.

By way of context, this question is an offshoot from a previous one on SO.

Initial thoughts

It strikes me that this problem is an excellent candidate for offline training and I envisage a compressed data format along the following lines:

• A Huffman coding of the "public suffix", with probabilities drawn from some published source of domain registration or traffic volumes;

• A Huffman coding of which (natural language) model is used for the remaining U-labels, with probabilities drawn from some published source of domain registration or traffic volumes given context of the domain suffix;

• Apply some dictionary-based transforms from the specified natural language model; and

• An arithmetic coding of each character in the U-labels, with probabilities drawn from contextually adaptive natural language models derived from offline training (and perhaps online too, although I suspect the data may well be too short to provide any meaningful insight?).

• Perhaps you could download a list of all domain names, and assign each one a number. This would be very compact.
– Dietrich Epp
Oct 18 '11 at 6:59
• @Dietrich Epp: Indeed - and actually, I had thought that perhaps registrars might publish in WHOIS a serial number of each registration from which this could reliably be built, but sadly they do not. Realistically, I think the practical challenges in maintaing such a database make it infeasible: not to mention that such databases do not handle subdomains. Oct 18 '11 at 7:09
• ...well, if a number is enough, just take the 4/6 bytes of the ipv4/6 address :/
– arnaud
Oct 21 '11 at 9:09
• By Dietrich Epp's method (based on an estimated 196m domains) you could store a domain name in 28 bits (two unicode characters), and you cannot do better. Of course, a probability distribution over domain names can give you a much better expected number of bits. You could at least use arithmetic coding for the 1 million most popular domains and use some ad-hoc scheme for the rest. Feb 4 '13 at 14:16
• @eggyal Do you mean all domain names in use, or all legal domain names? Mar 9 '17 at 20:59

• Huffman coding is asymptotically optimal if you ignore correlations between letters (e.g., if you see a q, then the next letter is a lot more likely to be a u than it otherwise would be). But that's not a realistic assumption. In practice, those correlations are huge and enable one to do a lot better than naive Huffman coding in practice.