문자열을 짧은 대체 문자열에 매핑하는 알고리즘

Question

고유하고 최적의 짧은 대체 문자열을 결정적으로 대체하는 방법을 찾고 있습니다. 그래서 유한 한 문자열 집합을 가지고 있으며 지금까지 얻을 수있는 최상의 압축은 열거 알고리즘을 통해 입력 집합을 정렬 한 다음 문자열을 확장 된 문자 (a..z)에 대한 char 문자열의 열거 형으로 바꾸는 것입니다. , A ... Z, aa ... zz, aA ... zZ, a0 ... z9, Aa ..., aaa ... zaa, aaA ... zaaA, ....).

압축과 관련해서는 훌륭하게 작동하지만 주어진 입력 문자열에는 원자 적이지 않다는 심각한 단점이 있습니다. 오히려 그 결과는 처음부터 모든 입력 끈을 알 고 입력 세트의을 주문하면 에 달려 있습니다.

비슷한 압축 알고리즘을 가진 사람은 누구나 알고 있지만 모든 입력 문자열을 미리 알아야 할 필요는 없습니다. 예를 들어 해싱은 입력 집합의 크기에 따라 해시 길이가 고유해야 해시가 8-12 일 필요하고 대체 길이가 너무 길어서 (현재는 대체 문자열 내 사용 사례에 대해 1 ~ 3 자 길이입니다 (< 10,000 개의 입력 문자열). 또한, 우리 사이의 이론가가 이것이 낭비적인 노력이라고 알고 있다면, 나는 듣고 싶어 할 것입니다 :-).

Answer 1

열거 체계를 사용할 수 있지만 입력 문자열이 처음 나타나는 순서로 정렬됩니다.

예를 들어 처리 한 첫 번째 문자열을 "a"에 매핑 할 수 있습니다. 다음 뚜렷한 문자열은 "b"등으로 매핑됩니다.

문자열을 처리 할 때마다 이미 문자열이 매핑되어 있는지 확인해야합니다.

Answer 2

"최적으로 짧음"은 견본이 그려지는 문자열 모집단에 따라 다릅니다. 모집단에서 체계적인 중복이없는 경우, 임의의 일부 문자열 만 압축 할 수 있습니다 (예 : 임의의 비트 문자열을 압축하려는 경우).

"문자열이 주로 영어 단어로 구성 될 것으로 예상됩니다"와 같이 데이터에 대한 가정을 할 수 있다면 문자 빈도를 기반으로 간단하고 효과적인 작업을 수행 할 수 있습니다 (예 : 영어, 상대 빈도 순서 ETAOINSHRDLUGCY ...와 같기 때문에 Es를 나타 내기 위해 더 적은 비트를 사용하고 Q와 같이 드문 문자를 나타 내기 위해 더 많은 비트를 사용하려고합니다.

건배.