Compression des noms de domaine

21

Je suis curieux de savoir comment on pourrait compresser de manière très compacte le domaine d'un nom d'hôte IDN arbitraire (tel que défini par RFC5890 ) et je pense que cela pourrait devenir un défi intéressant. Un hôte ou un nom de domaine Unicode (U-label) se compose d'une chaîne de caractères Unicode, généralement limitée à une langue en fonction du domaine de premier niveau (par exemple, les lettres grecques sous .gr), qui est codée dans une chaîne ASCII commençant par xn--(le correspondant Une marque).

On peut construire des modèles de données non seulement à partir des exigences formelles

  • chaque étiquette non Unicode doit correspondre à une chaîne ^[a-z\d]([a-z\d\-]{0,61}[a-z\d])?$;

  • chaque étiquette A doit correspondre à une chaîne ^xn--[a-z\d]([a-z\d\-]{0,57}[a-z\d])?$; et

  • la longueur totale de l'ensemble du domaine (étiquettes A et étiquettes non IDN concaténées avec des délimiteurs «.») ne doit pas dépasser 255 caractères

mais aussi à partir de diverses heuristiques, dont:

  • les U-labels d'ordre inférieur sont souvent des expressions lexiquement, syntaxiquement et sémantiquement valides dans certains langages naturels, y compris les noms et les chiffres appropriés (non ponctués sauf le trait d'union, dépourvus d'espaces et pliés par Nameprep ), avec une préférence pour les phrases plus courtes; et

  • les étiquettes d'ordre supérieur sont tirées d'un dictionnaire de SLD et de TLD et fournissent un contexte pour prédire quel langage naturel est utilisé dans les étiquettes d'ordre inférieur.

Je crains qu'il soit difficile d'obtenir une bonne compression de telles chaînes courtes sans prendre en compte ces caractéristiques spécifiques des données et, en outre, que les bibliothèques existantes produiront une surcharge inutile afin de s'adapter à leurs cas d'utilisation plus généraux.

En lisant le livre en ligne de Matt Mahoney intitulé Data Compression Explained , il est clair qu'un certain nombre de techniques existantes pourraient être utilisées pour tirer parti des hypothèses de modélisation ci-dessus (et / ou d'autres) qui devraient se traduire par une compression bien supérieure par rapport à des outils moins spécifiques.

À titre de contexte, cette question est une ramification d'une précédente sur SO .


Pensées initiales

Il me semble que ce problème est un excellent candidat pour la formation hors ligne et j'envisage un format de données compressé selon les lignes suivantes:

  • Un codage Huffman du « suffixe public », avec des probabilités tirées d'une source publiée d'enregistrement de domaine ou de volumes de trafic;

  • Un codage Huffman dont le modèle (en langage naturel) est utilisé pour les U-labels restants, avec des probabilités tirées d'une source publiée d'enregistrement de domaine ou de volumes de trafic étant donné le contexte du suffixe de domaine;

  • Appliquer des transformations basées sur un dictionnaire à partir du modèle de langage naturel spécifié; et

  • Un codage arithmétique de chaque caractère dans les U-labels, avec des probabilités tirées de modèles de langage naturel contextuellement adaptatifs dérivés de la formation hors ligne (et peut-être aussi en ligne, bien que je soupçonne que les données peuvent bien être trop courtes pour fournir un aperçu significatif?).

eggyal
la source
4
Vous pouvez peut-être télécharger une liste de tous les noms de domaine et attribuer à chacun un numéro. Ce serait très compact.
@Dietrich Epp: En effet - et en fait, j'avais pensé que peut-être les bureaux d'enregistrement pourraient publier dans WHOIS un numéro de série de chaque enregistrement à partir duquel cela pourrait être construit de manière fiable, mais malheureusement ils ne le font pas. De façon réaliste, je pense que les défis pratiques liés à la maintenance d'une telle base de données la rendent irréalisable: sans oublier que ces bases de données ne gèrent pas les sous-domaines.
eggyal
... eh bien, si un nombre est suffisant, il suffit de prendre les 4/6 octets de l'adresse ipv4 / 6: /
@arnaud: L'inverser est un problème - repose sur un pointeur correct dans .in-addr.arpa; se casse également si l'IP change.
eggyal
1
Par la méthode de Dietrich Epp (basée sur environ 196 millions de domaines), vous pouvez stocker un nom de domaine en 28 bits (deux caractères unicode), et vous ne pouvez pas faire mieux. Bien sûr, une distribution de probabilité sur les noms de domaine peut vous donner un bien meilleur nombre attendu de bits. Vous pouvez au moins utiliser le codage arithmétique pour le million de domaines les plus populaires et utiliser un schéma ad hoc pour le reste.
Peter

Réponses:

0

Le codage Huffman est optimal pour les lettres et peut certainement être adapté aux séquences. Par exemple, si la séquence "ab" produit moins de bits que les bits pour "a" et "b", ajoutez-la simplement à l'arborescence ... et ainsi de suite.

... vous pouvez également probablement utiliser une bibliothèque simple qui fait tout cela pour vous avec des performances presque optimales, de sorte que vous ne gagnerez pas beaucoup en utilisant votre algorithme de compression super sophistiqué sur mesure.


la source
Je pense que Huffman n'est pas tout à fait optimal (il arrondit au bit le plus proche): le codage arithmétique devrait toujours surperformer. Et à moins que l'on applique un modèle précis des données compressées, on va toujours obtenir des résultats sous-optimaux ... donc si chaque bit compte, les bibliothèques génériques ne peuvent pas suffire.
eggyal
4
Le codage Huffman est asymptotiquement optimal si vous ignorez les corrélations entre les lettres (par exemple, si vous voyez un q, alors la lettre suivante est beaucoup plus susceptible d'être un uqu'elle ne le serait autrement). Mais ce n'est pas une hypothèse réaliste. En pratique, ces corrélations sont énormes et permettent de faire beaucoup mieux que le codage Huffman naïf dans la pratique.
DW
@DW avez-vous des recommandations sur la façon de faire mieux? Serait-il peut-être utile d'autoriser le codage de paires ou triplets de caractères contigus via Huffman?
ryan