Compactação de nomes de domínio

21

Estou curioso para saber como compactar de maneira muito compacta o domínio de um nome de host arbitrário de IDN (conforme definido pela RFC5890 ) e suspeito que isso possa se tornar um desafio interessante. Um host ou nome de domínio Unicode (rótulo U) consiste em uma sequência de caracteres Unicode, normalmente restritos a um idioma, dependendo do domínio de nível superior (por exemplo, letras gregas abaixo .gr), que é codificado em uma sequência ASCII iniciada por xn--(o correspondente Um rótulo).

Pode-se construir modelos de dados não apenas a partir dos requisitos formais que

  • cada rótulo não-Unicode é uma correspondência de string ^[a-z\d]([a-z\d\-]{0,61}[a-z\d])?$;

  • cada rótulo A é uma string correspondente ^xn--[a-z\d]([a-z\d\-]{0,57}[a-z\d])?$; e

  • o comprimento total de todo o domínio (rótulos A e rótulos não IDN concatenados com delimitadores '.') não deve exceder 255 caracteres

mas também de várias heurísticas, incluindo:

  • os rótulos U de ordem inferior são frequentemente frases lexicamente, sintática e semanticamente válidas em alguma linguagem natural, incluindo substantivos e numerais (não pontuados, exceto hífen, sem espaço em branco e dobrados por Nameprep ), com preferência por frases mais curtas; e

  • os rótulos de ordem superior são extraídos de um dicionário de SLDs e TLDs e fornecem contexto para prever qual idioma natural é usado nos rótulos de ordem inferior.

Receio que seja difícil obter uma boa compactação dessas cadeias curtas sem considerar esses recursos específicos dos dados e, além disso, que as bibliotecas existentes produzirão sobrecarga desnecessária para acomodar seus casos de uso mais gerais.

Lendo o livro on-line de Matt Mahoney, Data Compression Explained , fica claro que várias técnicas existentes podem ser empregadas para tirar proveito das premissas de modelagem acima (e / ou outras) que devem resultar em compressão muito superior às ferramentas menos específicas.

A título de contexto, esta pergunta é uma ramificação de uma anterior no SO .


Pensamentos iniciais

Parece-me que esse problema é um excelente candidato ao treinamento off-line e vislumbro um formato de dados compactados nas seguintes linhas:

  • Uma codificação Huffman do " sufixo público ", com probabilidades extraídas de alguma fonte publicada de registro de domínio ou volumes de tráfego;

  • Uma codificação de Huffman cujo modelo (linguagem natural) é usado para os demais rótulos em U, com probabilidades extraídas de alguma fonte publicada de registro de domínio ou volumes de tráfego, considerando o contexto do sufixo do domínio;

  • Aplique algumas transformações baseadas em dicionário do modelo de idioma natural especificado; e

  • Uma codificação aritmética de cada caractere nos rótulos em U, com probabilidades extraídas de modelos de linguagem natural contextualmente adaptáveis, derivados de treinamento offline (e talvez online também, embora eu suspeite que os dados possam ser muito curtos para fornecer algum insight significativo?).

eggyal
fonte
4
Talvez você possa baixar uma lista de todos os nomes de domínio e atribuir um número a cada um. Isso seria muito compacto.
@ Dietrich Epp: De fato - e, na verdade, eu pensei que talvez os registradores possam publicar no WHOIS um número de série de cada registro a partir do qual isso possa ser construído com segurança, mas, infelizmente, não. Realisticamente, acho que os desafios práticos de manter esse banco de dados o tornam inviável: sem mencionar que esses bancos de dados não lidam com subdomínios.
eggyal 18/10/11
... bem, se um número é suficiente, basta pegar os 4/6 bytes do endereço ipv4 / 6: /
@arnaud: Inverter é um problema - depende de um ponteiro correto .in-addr.arpa; também quebra se o IP mudar.
eggyal
1
Pelo método de Dietrich Epp (com base em um número estimado de 196 milhões de domínios), você pode armazenar um nome de domínio em 28 bits (dois caracteres unicode) e não pode fazer melhor. Obviamente, uma distribuição de probabilidade sobre nomes de domínio pode fornecer um número esperado de bits muito melhor. Você pode pelo menos usar a codificação aritmética para os 1 milhão de domínios mais populares e usar algum esquema ad-hoc para o resto.
Peter

Respostas:

0

A codificação de Huffman é ideal para letras e certamente pode ser adaptada a seqüências. Por exemplo, se a sequência "ab" resultar em menos bits que os bits para "a" e "b", basta adicioná-la à árvore ... e assim por diante.

... você também pode provavelmente usar alguma biblioteca simples, que faz tudo isso para você com desempenhos quase ideais, para que você não ganhe muito usando seu algoritmo de compactação super sofisticado.


fonte
Eu acho que Huffman não é o ideal (arredonda para o bit mais próximo): a codificação aritmética deve sempre ter um desempenho superior. E, a menos que se aplique um modelo preciso dos dados que estão sendo compactados, sempre será possível obter resultados abaixo do ideal ... portanto, se tudo for importante, as bibliotecas genéricas não serão suficientes.
eggyal 21/10
4
A codificação de Huffman é assintoticamente ideal se você ignorar as correlações entre as letras (por exemplo, se você qvir um , a próxima letra provavelmente será mais udo que seria). Mas isso não é uma suposição realista. Na prática, essas correlações são enormes e permitem que se faça muito melhor do que a ingênua codificação de Huffman na prática.
DW
@DW você tem alguma recomendação sobre como alguém poderia fazer melhor? Ajudaria talvez permitir que pares ou triplos de caracteres contíguos fossem codificados via Huffman?
ryan