인기있는 DEFLATE 알고리즘은 Lempel-Ziv 위에 Huffman 코딩을 사용합니다.
우리는 데이터의 임의의 소스가 있다면, 일반적으로, (1 비트 엔트로피 / 비트 =) 에는 허프만 인코딩을 포함하여, 평균을 압축 할 가능성이 없다. Lempel-Ziv가 “완벽”한 경우 (길이가 무한대가됨에 따라 대부분의 소스에 접근하는 경우) Huffman을 사용한 포스트 인코딩은 도움이되지 않습니다. 물론, Lempel-Ziv 는 최소한 유한 한 길이로 완벽 하지 않으므로 일부 중복성이 남아 있습니다.
허프만 코딩이 부분적으로 제거되어 압축을 개선하는 것이이 잔여 리던던시이다.
내 질문은 : 왜이 중복이 LZ가 아닌 허프만 코딩에 의해 성공적으로 제거됩니까? 허프만 대 LZ의 어떤 속성이 이것을 가능하게합니까? 단순히 LZ를 다시 실행하는 것 (즉, LZ로 LZ 압축 데이터를 두 번째로 인코딩)이 비슷한 것을 달성합니까? 그렇지 않다면 왜 안됩니까? 마찬가지로, 먼저 허프만으로 압축 한 다음 LZ로 압축하면 안됩니까?
업데이트 :
LZ 후에도 일부 중복성이 남아 있음이 분명합니다. 여러 사람들이 그 점을 지적했습니다. 분명하지 않은 것은 : 왜 Huffman이 남아있는 중복성을 LZ보다 더 잘 처리 하는가? LZ가 허프만보다 더 잘 작동하는 원래의 소스 리던던시와 달리 독특한 점은 무엇입니까?
답변
이것은 원래 의견이지만 너무 길었습니다.
DEFLATE를 보면 Huffman이 압축하는 것은 LZ77의 출력입니다. LZ77은 압축 할 문자열에 포인터를 더 일찍 전송하고 포인터 뒤의 심볼 수를 알려주는 일치 길이를 사용하여 (원시 데이터보다 적은 비트를 사용하는 경우) 작동합니다. 이론은 추가 압축 없이도이 기술이 결국 소스 엔트로피로 수렴됨을 보여줍니다. 그러나 데이터 압축에서는 완전히 임의적이지 않은 분포가있을 때마다 압축 할 수도 있습니다. LZ77의 출력 (포인터 및 일치 길이)이 완전히 임의적이라고 믿을 이유는 없습니다. LZ77은 점진적으로 최적이기 때문에 점근선 한계에서 임의성을 완성하기 위해 수렴해야하지만 실제로는 유한 사전 만 사용합니다. 그래서 그들은 아마도 당신이 그들에 대해 더 많은 압축을함으로써 이길 수있는 완전히 임의적이지 않을 정도로 멀리 떨어져있을 것입니다. 당연히, 두 프로세스가 서로 다른 통계를 가지기 때문에 하나의 포인터와 일치 길이에 대해 하나의 허프만 코드를 사용합니다.
두 번째 압축 라운드에 LZ 대신 Huffman을 사용하는 이유는 무엇입니까? 허프만에 비해 LZ의 큰 장점은 심볼 간의 종속성을 처리하는 것입니다. 영어에서 한 문자가 ‘q’이면 다음 문자는 ‘u’가 될 가능성이 높습니다. 심볼이 독립적 인 이벤트 인 경우 허프만은 더 단순하고 짧은 문자열에 대해 잘 작동합니다. LZ77의 출력을 위해, 직감은 기호가 상당히 독립적이어야하므로 허프만이 더 잘 작동해야한다는 것입니다.
답변
데이터 압축은 실제로 모델링과 인코딩의 두 가지입니다. LZ 제품군의 알고리즘은 텍스트를 정확한 반복의 연결로 모델링합니다. 이는 많은 임의의 소스에 대해 무조건 최적이며 많은 실제 텍스트에 합리적으로 좋습니다. 그러나 일부 입력의 경우이 모델은 상당히 나쁠 수 있습니다. 예를 들어 접미사 배열이 원본 텍스트와 같이 압축 가능하더라도 LZ를 사용하여 접미사 배열을 직접 압축 할 수 없습니다.
(p,ℓ,c)
p
ℓ
c
logn
n
간단히 말해 Huffman은 모델 (고정 분포와 정확한 반복)이 데이터에 더 적합하기 때문에 튜플 압축에서 LZ를 능가합니다.
답변
대답은 조회 사전 크기에 있다고 믿습니다.
데이터는 위치 감이 있으며 (즉, 데이터가 사용 된 경우 곧 다시 사용될 가능성이 높음) LZ 알고리즘은 조회 사전 구성에서이를 활용합니다. 검색 속도를 높이기 위해 유한 한 양의 노드로 트라이를 생성합니다 . 크기 제한에 도달하면 이전 시도를 “잊어 버린”또 다른 시도를 만듭니다. 따라서 더 간단한 문자에 대한 조회 테이블을 다시 작성해야하지만 더 이상 사용되지 않는 단어는 더 이상 메모리에 저장되지 않으므로 더 작은 인코딩을 사용할 수 있습니다.
따라서 Huffman 인코딩을 사용하면 LZ 출력을 더 줄일 수 있습니다. 조회 시도 생성시 이러한 중복성을 통계 분석으로 감지 할 수 있습니다.
답변
아마도 나는 여기서 벗어나고 있지만 허프만 인코딩은 전체 입력을보고 인코딩 테이블 (트리)을 빌드하는 반면 Lempel-Ziv는 인코딩을 진행합니다. 이것은 허프만의 장점이자 단점입니다. 단점은 명백하지 않습니다. 즉, 시작하기 전에 전체 입력 내용을 확인해야합니다. 이점은 Huffman이 입력의 모든 위치에서 발생하는 통계를 고려하는 반면, Lempel-Ziv는 점진적으로이를 축적해야한다는 것입니다. 또는 다른 방식으로 표현하기 위해 Lempel-Ziv에는 허프만이하지 않는 “방향”이 있습니다.
그러나이 모든 것이 상황이 어떻게 상상되는지의 순진한 방법입니다. 허프만이 렘펠-지브를 능가하는 성능을 보려면 여기에서 실제 증거가 필요합니다.
답변
짧은 대답은 LZ는 소스의 정확한 분포를 알 필요가 없다는 점에서 “유니버설”알고리즘입니다 (소스가 정지적이고 인체 공학적이라는 가정 만하면 됨). 허프만은 그렇지 않습니다. (허프만 트리를 만들기 위해) 소스가 샘플링 된 정확한 분포를 알아야합니다. 이 추가 정보는 Huffman이 엄격한 압축 보장을 달성하도록합니다. 그러나 실제 파일 압축 알고리즘의 경우 허프만은 파일의 경험적 통계를 수집 한 다음 하반기에 실제 압축을 수행해야하지만 LZ는 온라인으로 구현할 수 있기 때문에 덜 유리할 수 있습니다.
자세한 내용은 표준 정보 이론 텍스트 (예 : Cover and Thomas의 정보 요소 이론)에서 확인할 수 있습니다.