Kompresja nazw domen

Jestem ciekawy, jak można bardzo kompaktowo skompresować domenę dowolnej nazwy hosta IDN (zgodnie z definicją w RFC5890 ) i podejrzewam, że może to stać się ciekawym wyzwaniem. Host lub nazwa domeny Unicode (etykieta U) składa się z ciągu znaków Unicode, zwykle ograniczonego do jednego języka w zależności od domeny najwyższego poziomu (np. Litery greckie poniżej .gr), która jest zakodowana w ciąg ASCII rozpoczynający się od xn--(odpowiadający Etykieta).

Modele danych można budować nie tylko na podstawie wymogów formalnych, które

• każda etykieta inna niż Unicode musi być pasującym ciągiem ^[a-z\d]([a-z\d\-]{0,61}[a-z\d])?$;

• każda etykieta A musi pasować do ciągu ^xn--[a-z\d]([a-z\d\-]{0,57}[a-z\d])?$; i

• całkowita długość całej domeny (etykiety A i etykiety inne niż IDN połączone z ogranicznikami „.”) nie może przekraczać 255 znaków

ale także z różnych heurystyk, w tym:

• Znaczniki U niższego rzędu są często poprawnymi leksykalnie, składniowo i semantycznie frazami w pewnym języku naturalnym, w tym odpowiednimi rzeczownikami i cyframi (nieokreślone z wyjątkiem łącznika, pozbawionego białych znaków i pofałdowane według Nameprep ), z preferencją dla krótszych fraz; i

• etykiety wyższego rzędu są pobierane ze słownika SLD i TLD i zapewniają kontekst do przewidywania, który język naturalny jest używany w etykietach niższego rzędu.

Obawiam się, że uzyskanie dobrej kompresji takich krótkich ciągów będzie trudne bez uwzględnienia tych specyficznych cech danych, a ponadto, że istniejące biblioteki spowodują niepotrzebne koszty ogólne, aby dostosować się do ich bardziej ogólnych przypadków użycia.

Czytając książkę online Matta Mahoneya Wyjaśnienie kompresji danych , jasne jest, że można wykorzystać szereg istniejących technik, aby wykorzystać powyższe (i / lub inne) założenia modelowania, które powinny skutkować znacznie lepszą kompresją w porównaniu z mniej specyficznymi narzędziami.

Tytułem kontekstu to pytanie jest pochodną poprzedniej wersji SO .

Wstępne przemyślenia

Uderza mnie, że ten problem jest doskonałym kandydatem do szkolenia offline i przewiduję skompresowany format danych według następujących zasad:

• Kod Huffmana „ publicznego przyrostka ”, z prawdopodobieństwem zaczerpniętym z niektórych opublikowanych źródeł rejestracji domen lub natężenia ruchu;

• Kod Huffmana, którego model (język naturalny) jest stosowany dla pozostałych etykiet U, z prawdopodobieństwami zaczerpniętymi z opublikowanego źródła rejestracji domeny lub natężenia ruchu w kontekście sufiksu domeny;

• Zastosuj niektóre transformacje słownikowe z określonego modelu języka naturalnego; i

• Arytmetyczne kodowanie każdego znaku w etykietach U, z prawdopodobieństwami zaczerpniętymi z kontekstowo adaptacyjnych modeli języka naturalnego pochodzących ze szkolenia offline (i być może także online, chociaż podejrzewam, że dane mogą być zbyt krótkie, aby zapewnić jakiś znaczący wgląd?).

Kodowanie Huffmana jest optymalne dla liter i z pewnością może być dostosowane do sekwencji. Na przykład, jeśli sekwencja „ab” daje mniej bitów niż bitów dla „a” i „b”, to po prostu dodaj ją do drzewa ... i tak dalej.

... prawdopodobnie możesz również użyć prostej biblioteki, która robi to wszystko za sprawą prawie optymalnej wydajności, dzięki czemu nie zyskasz wiele dzięki niestandardowemu algorytmowi kompresji.