태그 보관물: strings

strings

도메인 이름 압축

나는 사람이 수 방법에 대한 궁금 매우 컴팩트 임의의 도메인 압축 IDN의 (에 의해 정의 된 호스트 이름을 RFC5890 )과 흥미로운 도전이 될 수이 의심. 유니 코드 호스트 또는 도메인 이름 (U-라벨)은 일반적으로 하나 개의 언어 (예 : 아래의 그리스 문자를 최상위 도메인에 따라 구속 유니 코드 문자의 문자열로 구성 .gr로 시작하는 ASCII 문자열로 인코딩되는) xn--(대응을 라벨).

공식적인 요구 사항뿐만 아니라 데이터 모델을 구축 할 수 있습니다.

  • 각 비 유니 코드 레이블은 문자열 일치입니다 ^[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의 사전에서 상위 레이블을 가져 와서 하위 레이블에 사용되는 자연 언어를 예측하기위한 컨텍스트를 제공합니다.

데이터의 이러한 특정 기능을 고려하지 않고 이러한 짧은 문자열을 잘 압축하는 것이 어려울뿐만 아니라 기존 라이브러리가보다 일반적인 사용 사례를 수용하기 위해 불필요한 오버 헤드를 생성 할 수 있습니다.

Matt Mahoney의 온라인 데이터 압축 설명을 읽으면 위의 (및 / 또는 다른) 모델링 가정을 활용하기 위해 여러 가지 기존 기술을 사용하여 특정 도구보다 압축률이 훨씬 뛰어나다는 것이 분명합니다.

문맥 상,이 질문은 SO이전 질문에서 파생 된 것 입니다.


초기 생각

이 문제는 오프라인 교육의 훌륭한 후보이며 다음 줄을 따라 압축 된 데이터 형식을 예상합니다.

  • 공개 접미사 ” 의 허프만 코딩. 일부 공개 된 도메인 등록 소스 또는 트래픽 볼륨에서 발생하는 확률.

  • 허프만 코딩은 (자연 언어) 모델이 나머지 U- 라벨에 사용되며, 도메인 접미사와 관련하여 주어진 도메인 등록 소스 또는 트래픽 볼륨에서 나온 확률;

  • 지정된 자연어 모델에서 일부 사전 기반 변환을 적용하십시오. 과

  • 오프라인 교육에서 파생 된 상황에 따라 적응할 수있는 자연 언어 모델에서 파생 된 확률을 사용하여 U- 라벨에있는 각 문자의 산술 코딩 (그리고 온라인도 가능하지만 데이터가 너무 짧아서 의미있는 통찰력을 제공 할 수 없다고 생각하십니까?)



답변

허프만 코딩은 문자에 최적이며 시퀀스에 확실히 적용 할 수 있습니다. 예를 들어, 시퀀스 “ab”의 결과가 “a”및 “b”의 비트보다 적은 비트 수이면 트리에 추가하면됩니다.

… 아마도 최적의 성능으로 거의 모든 것을 수행하는 간단한 라이브러리를 사용할 수 있으므로 맞춤형 슈퍼 멋진 압축 알고리즘을 사용하지 않아도됩니다.


답변