Ich bin gespannt, wie man die Domain eines beliebigen IDN- Hostnamens (wie in RFC5890 definiert ) sehr kompakt komprimieren kann, und vermute, dass dies eine interessante Herausforderung werden könnte. Ein Unicode-Host- oder -Domänenname (U-Label) besteht aus einer Zeichenfolge von Unicode-Zeichen, die in der Regel auf eine Sprache beschränkt ist, abhängig von der Domäne der obersten Ebene (z. B. griechische Buchstaben darunter ), die in einer ASCII-Zeichenfolge codiert ist, die mit (der entsprechenden) beginnt Ein Etikett)..grxn--
Man kann Datenmodelle nicht nur aus den formalen Anforderungen erstellen, die
Jedes Nicht-Unicode-Label ist eine Zeichenfolge, die übereinstimmt
^[a-z\d]([a-z\d\-]{0,61}[a-z\d])?$.Jedes A-Label ist eine Zeichenfolge, die übereinstimmt
^xn--[a-z\d]([a-z\d\-]{0,57}[a-z\d])?$. undDie Gesamtlänge der gesamten Domain (A-Labels und Nicht-IDN-Labels, die mit '.' - Trennzeichen verkettet sind) darf 255 Zeichen nicht überschreiten
sondern auch aus verschiedenen Heuristiken, darunter:
U-Bezeichnungen niedrigerer Ordnung sind oft lexikalisch, syntaktisch und semantisch gültige Phrasen in einer natürlichen Sprache, einschließlich Eigennamen und Ziffern (unpunktiert mit Ausnahme von Bindestrich, Leerzeichen und gefaltet nach Nameprep ), wobei kürzere Phrasen bevorzugt werden. und
Bezeichnungen höherer Ordnung werden aus einem Wörterbuch von SLDs und TLDs erstellt und bieten einen Kontext für die Vorhersage, welche natürliche Sprache in den Bezeichnungen niedrigerer Ordnung verwendet wird.
Ich befürchte, dass es schwierig sein wird, eine gute Komprimierung derart kurzer Zeichenfolgen zu erreichen, ohne diese spezifischen Merkmale der Daten zu berücksichtigen, und außerdem, dass vorhandene Bibliotheken unnötigen Overhead verursachen, um ihren allgemeineren Anwendungsfällen gerecht zu werden.
Lesen Sie das Online-Buch Data Compression Explained von Matt Mahoney. Es ist klar, dass eine Reihe vorhandener Techniken eingesetzt werden könnten, um die oben genannten (und / oder andere) Modellannahmen zu nutzen, die zu einer weitaus besseren Komprimierung im Vergleich zu weniger spezifischen Tools führen sollten.
Im Kontext ist diese Frage ein Ableger einer früheren Frage zu SO .
Erste Gedanken
Mir fällt auf, dass dieses Problem ein hervorragender Kandidat für das Offline-Training ist, und ich stelle mir ein komprimiertes Datenformat wie folgt vor:
Eine Huffman-Codierung des " öffentlichen Suffix " mit Wahrscheinlichkeiten, die aus einer veröffentlichten Quelle für die Domainregistrierung oder dem Verkehrsaufkommen stammen.
Eine Huffman-Codierung, deren Modell (in natürlicher Sprache) für die verbleibenden U-Labels verwendet wird, wobei Wahrscheinlichkeiten aus einer veröffentlichten Quelle für die Domainregistrierung oder dem Verkehrsaufkommen bezogen auf den Kontext des Domain-Suffix stammen.
Wenden Sie einige wörterbuchbasierte Transformationen aus dem angegebenen natürlichen Sprachmodell an. und
Eine arithmetische Kodierung jedes Zeichens in den U-Labels mit Wahrscheinlichkeiten aus kontextuell adaptiven natürlichen Sprachmodellen, die aus dem Offline-Training abgeleitet wurden (und möglicherweise auch online, obwohl ich vermute, dass die Daten möglicherweise zu kurz sind, um einen aussagekräftigen Einblick zu gewähren?).
.in-addr.arpa; Bricht auch ab, wenn sich die IP jemals ändert.Antworten:
Die Huffman-Codierung ist für Buchstaben optimal und kann durchaus an Sequenzen angepasst werden. Wenn zum Beispiel die Sequenz "ab" weniger Bits ergibt als die Bits für "a" und "b", dann fügen Sie sie einfach dem Baum hinzu ... und so weiter.
... Sie können wahrscheinlich auch eine einfache Bibliothek verwenden, die das alles für Sie mit nahezu optimaler Leistung erledigt, sodass Sie mit Ihrem maßgeschneiderten Super-Fancy-Komprimierungsalgorithmus nicht viel gewinnen.
quelle
q, ist der nächste Buchstabe viel wahrscheinlicher ein,uals dies sonst der Fall wäre). Dies ist jedoch keine realistische Annahme. In der Praxis sind diese Korrelationen sehr groß und ermöglichen es einem, in der Praxis viel besser als die naive Huffman-Codierung vorzugehen.