Мне любопытно, как можно очень компактно сжать домен произвольного имени хоста IDN (как определено в RFC5890 ), и подозреваю, что это может стать интересной задачей. Хост Unicode или доменное имя (U-метка) состоит из строки символов Unicode, обычно ограниченных одним языком в зависимости от домена верхнего уровня (например, греческими буквами ниже .gr), который кодируется в строку ASCII, начинающуюся с xn--(соответствующего Этикетка).
Модели данных можно строить не только из формальных требований, которые
каждая не-Unicode метка должна соответствовать строке
^[a-z\d]([a-z\d\-]{0,61}[a-z\d])?$;каждая метка A соответствует строке
^xn--[a-z\d]([a-z\d\-]{0,57}[a-z\d])?$; иобщая длина всего домена (метки A и метки не-IDN, объединенные разделителями «.») не должна превышать 255 символов
но также из различных эвристик, в том числе:
U-метки низшего порядка часто являются лексически, синтаксически и семантически допустимыми фразами в некоторых естественных языках, включая собственные имена и цифры (не пунктурованы, за исключением дефиса, лишены пробела и свернуты в Nameprep ), с предпочтением более коротких фраз; и
метки высшего порядка взяты из словаря SLD и TLD и обеспечивают контекст для прогнозирования того, какой естественный язык используется в метках нижнего порядка.
Я боюсь, что добиться хорошего сжатия таких коротких строк будет сложно без учета этих специфических особенностей данных, и, кроме того, существующие библиотеки будут создавать ненужные накладные расходы, чтобы приспособить их к более общим случаям использования.
Читая онлайн-книгу Мэтта Махони « Сжатие данных» , становится ясно, что можно использовать ряд существующих методов, чтобы воспользоваться вышеупомянутыми (и / или другими) предположениями моделирования, которые должны привести к гораздо более высокому сжатию по сравнению с менее специфичными инструментами.
В контексте, этот вопрос является ответвлением от предыдущего вопроса о SO .
Начальные мысли
Меня поражает, что эта проблема является отличным кандидатом для обучения в автономном режиме, и я предполагаю сжатый формат данных по следующим направлениям:
Код Хаффмана « общедоступного суффикса » с вероятностями, взятыми из какого-либо опубликованного источника регистрации доменов или объемов трафика;
Кодирование Хаффмана, какая модель (на естественном языке) используется для оставшихся U-меток с вероятностями, взятыми из некоторого опубликованного источника регистрации домена или объемов трафика с учетом контекста суффикса домена;
Применить некоторые словарные преобразования из указанной модели естественного языка; и
Арифметическое кодирование каждого символа в U-метках с вероятностями, извлеченными из контекстно-адаптивных моделей естественного языка, полученных из автономного обучения (и, возможно, также онлайн, хотя я подозреваю, что данные могут быть слишком короткими, чтобы обеспечить какое-либо осмысленное понимание?).
.in-addr.arpa; также ломается, если IP когда-либо изменяется.Ответы:
Кодирование Хаффмана является оптимальным для букв и, безусловно, может быть адаптировано к последовательностям. Например, если последовательность «ab» приводит к меньшему количеству битов, чем биты для «a» и «b», то просто добавьте ее в дерево ... и так далее.
... вы также можете, вероятно, использовать некоторую простую библиотеку, которая делает все это для вас с почти оптимальными характеристиками, так что вы не получите много пользы, используя свой собственный супер-необычный алгоритм сжатия.
источник
q, то следующая буква с большей вероятностью будет a,uчем в противном случае). Но это не реалистичное предположение. На практике эти корреляции огромны и позволяют гораздо лучше, чем наивное кодирование Хаффмана на практике.