Compresión de nombres de dominio.

Tengo curiosidad por saber cómo se podría comprimir de manera muy compacta el dominio de un nombre de host IDN arbitrario (según lo definido por RFC5890 ) y sospecho que esto podría convertirse en un desafío interesante. Un host Unicode o nombre de dominio (etiqueta U) consiste en una cadena de caracteres Unicode, típicamente restringida a un idioma dependiendo del dominio de nivel superior (por ejemplo, letras griegas debajo .gr), que está codificada en una cadena ASCII que comienza con xn--(el correspondiente Una etiqueta).

Uno puede construir modelos de datos no solo a partir de los requisitos formales que

• cada etiqueta no Unicode debe ser una coincidencia de cadena ^[a-z\d]([a-z\d\-]{0,61}[a-z\d])?$;

• cada etiqueta A sea una coincidencia de cadena ^xn--[a-z\d]([a-z\d\-]{0,57}[a-z\d])?$; y

• la longitud total de todo el dominio (etiquetas A y etiquetas no IDN concatenadas con delimitadores '.') no debe exceder los 255 caracteres

pero también de varias heurísticas, que incluyen:

• Las etiquetas U de orden inferior a menudo son frases válidas léxica, sintácticamente y semánticamente en algún lenguaje natural, incluidos los nombres y números correctos (no escritos, excepto guiones, despojados de espacios en blanco y doblados por Nameprep ), con preferencia por frases más cortas; y

• las etiquetas de orden superior se extraen de un diccionario de SLD y TLD y proporcionan un contexto para predecir qué lenguaje natural se usa en las etiquetas de orden inferior.

Me temo que lograr una buena compresión de cadenas tan cortas será difícil sin considerar estas características específicas de los datos y, además, que las bibliotecas existentes producirán una sobrecarga innecesaria para acomodar sus casos de uso más generales.

Al leer el libro en línea de Matt Mahoney Explicación de la compresión de datos , está claro que se podrían emplear una serie de técnicas existentes para aprovechar los supuestos de modelado anteriores (y / u otros) que deberían dar lugar a una compresión muy superior en comparación con herramientas menos específicas.

A modo de contexto, esta pregunta es una rama de una anterior en SO .

Pensamientos iniciales

Me parece que este problema es un excelente candidato para la capacitación fuera de línea y preveo un formato de datos comprimido en las siguientes líneas:

• Una codificación Huffman del " sufijo público ", con probabilidades extraídas de alguna fuente publicada de registro de dominio o volúmenes de tráfico;

• Una codificación de Huffman cuyo modelo (lenguaje natural) se utiliza para las etiquetas U restantes, con probabilidades extraídas de alguna fuente publicada de registro de dominio o volúmenes de tráfico dado el contexto del sufijo de dominio;

• Aplique algunas transformaciones basadas en el diccionario del modelo de lenguaje natural especificado; y

• Una codificación aritmética de cada carácter en las etiquetas U, con probabilidades extraídas de modelos de lenguaje natural adaptables al contexto derivados del entrenamiento fuera de línea (y tal vez también en línea, aunque sospecho que los datos pueden ser demasiado cortos para proporcionar una idea significativa).

La codificación de Huffman es óptima para letras y ciertamente puede adaptarse a secuencias. Por ejemplo, si la secuencia "ab" da como resultado menos bits que los bits para "a" y "b", simplemente agréguela al árbol ... y así sucesivamente.

... probablemente también pueda usar una biblioteca simple que lo haga todo por usted con un rendimiento casi óptimo, para que no gane mucho con su algoritmo de compresión súper elegante personalizado.