본 문서는 현존하는 압축 프로그램 중 가장 빠른 것으로 보이는 LZ4 알고리즘에 대한 이해를 위해서 해당 알고리즘 저자의 블로그의 내용을 번역한 것이다. 원문은 아래 링크에 있다.
http://fastcompression.blogspot.de/p/mmc-morphing-match-chain.html
소개
MMC(Morphing Match Chain)은 2010년 11월에, LZ 압축을 위한 향상된 검색 알고리즘을 위해 개발되었다. 시작은 간단한 해시 체인 방법에서였다. 그것은 여기 포럼 글(http://encode.ru/threads/1155-A-new-match-searching-structure?p=22901&viewfull=1#post22901)에 소개되었고, 새로운 알고리즘으로 선언되었다. (MMC의 찰스 블룸의 분석(http://cbloomrants.blogspot.de/2011/09/09-23-11-morphing-matching-chain.html)도 참고하기 바란다.)
후에, Piotr Tarsa(http://fastcompression.blogspot.de/2010/12/bst-binary-search-tree.html) 씨는 이 구조에 대해서 왼쪽에 기댄 라딕스 트리처럼 설명될 수 있다고 강조했었다. 이것은 MMC를 설명하는 것과 매우 유사했다. 하지만, 거기에는 몇몇 매우 중요한 차이점 역시 있다. 그것은 바로 MMC는 검색이 행해질 때 데이터를 정렬하지만, 라딕스 트리는 삽입할 때 데이터를 정렬한다. 더구나, 해시 체인과 유사하게, 오래된 자료는 MMC에서 제약없이 삭제되고, 반면 라딕스 트리는이런 목적을 위해서 특별한 알고리즘을 요구한다. 이것은 몇몇 매우 커다란 특성 차이를 야기하고, 이것은 아래에서 시험대에 올릴 계획이다.
MMC는 오픈 소스 알고리즘(http://code.google.com/p/mmc/)이며, LPGL(http://www.gnu.org/licenses/lgpl.html) 라이센스 하에서 배포된다. 이것은 구글 코드(http://code.google.com/p/mmc/)에서 이용가능 하다.
맥락
주어진 검색 윈도우 크기에서 최고(=가장 긴) 매치를 찾는 것이 기본 목적이다. 모든 사람이 아마도 알고 있듯이 검증된 방식은 최소 적합 시퀀스(minmatch)를 해싱하여 첫 테이블에 넣고, 다음으로 같은 해시값을 가진 모든 위치들을 연결하여 두번째 테이블에 넣는 것이다. 이 때 해시값은 검색 윈도우 크기만큼 많은 위치들을 가지게 되낟. 이것은 "해시 체인"이라고 불리고 전반적으로 잘 동작한다. 사실, 검색 속도는 "순수" 검색 방식(즉, 모든 이전 위치들을 무작정 비교하는 방식)에 비해 엄청나게 증가한다.
이제, 문제는 검색 윈도우 크기를 증가시키는 경우, 체인 안의 위치 갯수는 매우 커질 것이고, 결국 검색 속도는 심각하게 느려질 것이다. 이것은 궁극적으로 발생하는 충돌(다른 문자열에 대해 같은 해시값을 가지는 경우)에 대해 아무런 해결책도 제시하지 않으며, 이것은 해시 크기를 증가시킴으로써 상대적으로 적게 발생시킬 수 있다. 이것은 알고리즘의 알고리즘의 적합한 대응이다. 거기에는 같은 접두사를 공유하는 많은 위치들이 있고, 그게 전부다.
그러므로 우리는 의아해할 수 있다. 운나쁘게도, 만약 내가 이미 4 바이트의 매칭 결과를 가지고 있다면, 나는 이전의 검색 결과를 향상시키기 위해서 단지 4바이트의 일치를 가지고 있는 다른 위치 대신에 최소한 5 바이트의 공통 바이트를 가지고 있는 위치에 대해 매칭 검색 함수를 수행하고자 할 것이다.
그것은 내가 해결했듯이 거의 동일한 자료 구조를 통해 얻어질 수 있을 것이다.
기본 개념
나는 샘플 예제를 통해 시작할 것이다.
우리가 동일한 해시를 공유하느 위치의 체인을 가지고 있다고 상상해 보자. 이제, 우리가 얻고자 하는 결과는 공통의 MinMatch 바이트의 체인이다. 그 결과, 우리는 해시 충돌을 줄이려고 한다.
이것은 간단히 "더블 체인" 방법으로 해결될 수 있다.
모든 것을 단순하게 만들기 위해서, 여기에 그것이 어떻게 동작하는 지 설명하는 그림이 있다.
단지 첫 "해시 체인"을 보통 때처럼 사용하고, 최소 MinMatch Bytes를 가진 문자열을 검색하려고한다. 우리가 그것을 찾았을 때, 그것을 두번째 체인에 연결하고, 두번째 체인에서 검색을 계속한다.
이것은 비교해야 하는 위치의 갯수를 줄일 것이다. 왜냐하면 거기에는 충돌에 대한 우려가 없기 때문이다. 하나의 작은 속도 개선으로써, 첫번재 MinMatch Bytes는 반드시 동일할 것이 보장되기 때문에 더 이상 비교할 필요가 없고, 비교는 MinMatch+1 문자로부터 시작된다.
일반화
이제 동일한 개념이 더 높은 관점에서도 이용될 수 있다.
단지 N개의 공통의 접두사를 가진 것이 보장된 위치의 체인과 함께 시작하는 것이다. 필요 없는 비교의 갯수를 줄이기 위해서, N+1개의 공통 접미사를 가진 요소의 체인을 가지고 "더 높은 관점"에 이르는 것은 매우 흥미롭다.
순수한 전략은 각각의 접두사 깊이에 대해 테이블을 생성하는 방법일 것이다. 이것은 분명히 더욱 더욱 많은 메모리를 소비할 것이고, 게다가 체인화 된 갱신 작업은 더욱 더욱 비용이 비싼 작업이 될 것이다. 그래서 이것은 막다른 골목이다.
여기에 있는 영리한 방법은 단지 두 개의 테이블로만 계속 일을하는 것이다. 이것은 무한대의 접두사 깊이 단계에 이를 수 있게 해준다.
이전의 그림에서 "the hash"라는 단어를 "prefix N"으로 바꾸고, "minmatch"를 "prefix N+1"로 변경하자. 그리고 이제 우리는 우리의 일반화를 가지게 되었다.
각 위치에 대해서, 우리는 2가지 선택을 유지한다. "나쁘다"의 의미는 이 위치가 보장된 접두사에 대해서는 개선이 되지 않는다는 것을 의미하고, 그렇기 대문에 우리는 이 체인을 계속해야만 한다. "좋다"라는 것의 의미는 이 위치는 최소한 "N+1" 공통 요소를 가지고 있고, 그래서 우리는 고차 체인에 이를 수 있는 기회로 사용할 수 있다. 이 방식을 재귀적으로 적용함으로써, 우리는 더욱 더 많은 접두사 요소를 가진 더 많은 체인들을 만들 수 있고, 이것은 차후의 연구를 더 빠르게 만든다.
여기에 알고리즘을 설명하기 위한 그림이 있다.
매칭 체인은 우리가 그것에 대해 검색을 수행함에 따라 변경될 것이기 때문에 "morphing match chain"이라고 이름지어진 것이라는 것을 알기 바란다. 좋은 점은 거기엔 아무런 "setup time"이 없다는 점이고, 검색 하는 동안 즉시로 수행된다는 점이다.
암시적 입력
전체 개념은 보기에 매우 간단하게 보이지만, 구현하는 동안 몇몇 어려운 점이 있다. 대부분 위에 설명된 동작들은 접미사 N의 체인이 이미 완전히 정렬되어 있고, 접미사 N+1의 적합한 체인에 연결되어 있음이 보증되어야 한다. 그러나 이 경우는 아니다. 왜냐하면 요소들이 체인에 "암시적으로 입력"되어져 있기 때문에, 거기에는 그들이 N+1 문자열을 가리키고 있다는 보증이 없다. 그것이 발생할 때, N+1 레벨까지 적합한 연결을 찾는 지점까지 체인 N을 계속적으로 갱신해야할 필요가 있다.
이러한 복잡한 "불안정한" 상황을 다루는 것은 더 큰 민첩함을 주지만 말이다. 어떤 체인에든 위치를 추가하는 것은 어려운 일이 아니고, 추가적인 아무런 연산도 요구하지 않는다. 그들은 나중에 필요하다면야 정렬될 것이다.
다중 승급
위의 그림은 한 개의 N+1 레벨로의 게이트웨이가 새로운 게이트웨이가 생성되었을 때, N+1 체인의 한 요소가 되는지를 설명한다. 이러한 동작을 "승급"이라고 부른다. 그림에서, 승급은 언제나 "한 단계 위"를 의미하며, 이것은 설명하기 쉽다. 하지만 위치들이 단일 패스에서 여러 단계 승급하는 것을 사용하는 더 강한 알고리즘을 만드는 것도 가능하다. 이것을 가능하게 만들기 위해서, 우리는 "가상 레벨"과 "현재 레벨" 두 가지 레벨 모두를 다뤄야할 필요가 있다. 가상 레벨은 언제나 현재 레벨보다 높거나 같다. 조건이 맞는경우, 위치는 가상 레벨로 승급될 수 있고, 이 가상 레벨은 현재 레벨 보다 몇 단계 위에 있을 수 있다. 이것은 "다중 승급"이라고 부르고, 검색 알고리즘이 훨씬 더 빠르게 동작하도록 해준다.
이차 승급
Piotr씨의 답글에 자극받아서 생각한 것은 우리가 요소들을 검사하는 동안 비록 우리가 그들을 현재 찾으려고 하는 것은 아니지만, 그들을 승급시키는 것이다. 그것은 조금더 복잡한 자료 구조를 요구한다. 하지만, 단일 패스에서, 더욱 더 많은 요소들이 승급되는 것은, 차후의 검색을 더욱 빠르게 만든다.
알고리즘은 더욱 복잡해졌지만, 이 알고리즘은 더 커다란 윈도우 크기에서만 그럴만한 가치가 있게 되었다. (여기(http://fastcompression.blogspot.de/2010/12/mmc-secondary-promotion-experimental.html)에 설명되어 있다.그것은 오픈 소스 버전 MMC(http://code.google.com/p/mmc/)에 구현되어있지만, LZ4 HC(http://fastcompression.blogspot.de/p/lz4.html)에서는 비활성화 되어 있다.
스트림 가속화
MMC에 특성화된 것은 아니지만, 동일하거나 혹은 반복적인 문자열을 가진 긴 스트림을 감지하거나 검색하기 위해 전용의 최적화가 쉽게 MMC에 통합될 수 있음을 언급할 가치가 있다. 그것은 압축할 파일에 그러한 스트림이 있는 경우 몇몇 흥미로운 속도 향상을 보인다.
레벨 일반화
이전 설명에서 한 레벨은 한 바이트를 의미하였지만, MMC 알고리즘을 유지하는 동안 아무런 크기의 레벨을 만드는 것이 가능하다. 예를 들어, 구글 코드에 호스팅되어 있는 오픈소스 구현(http://code.google.com/p/mmc/)은 첫 레벨은 MINMATCH 바이트를 가진 것으로 시작하고, 다른 모든 레벨들은 1 바이트이다.
Eugene Shelwien 씨(http://encode.ru/threads/1278-Nibble-MMC-matchfinder)는 각 레벨이 4비트(니블이라고 불리는)를 가진 MMC의 버전을 만들었다.
한 레벨은 비트나 바이트 단위에서 아무런 크기가 될 수 있고, 심지어 정적으로 매핑된 경우나 동적으로 발견되어진 어떤 경우에라도 다른 레벨 크기들을 혼합하여 이용할 수 있다.
BST(이진 검색 트리)와의 비교
이것은 여기에서(http://fastcompression.blogspot.de/2010/12/bst-first-experimental-results.html) 연구되었고, 설명되었다.
BST(Binary Search Tree)는 잘 알려진 검색 구조이고, 여러 최정상의 압축기들에서 사용되어진다. 특히 7zip과 FreeArc와 같은 압축기들에서 사용된다.
요약하면, BST는 MMC보다 빠르게 검색하고, 이것은 BST가 이미 정렬된 자료 구조에 검색을 수행하기 때문에 예상된 결과이다.
하지만, 삽입 시간이 고려된다면, 이러한 양상은 심하게 달라진다. BST는 MMC보다 심하게 느려지는데, 입력 비용 때문이다. 위에 설명 했듯이, MMC에 대한 데이터 입력은 거의 비용이 들지 않는다. 위치들은 암시적으로 입력되고, 정렬은 나중에 필요할 때만 일어난다. 반면, BST는 입력하는 동안 자료를 정렬할 필요가 있고, 최적의 일치 길이를 찾기 위해서 많은 CPU 연산을 사용한다. 균형 BST 또한 트리에서 요소를 제거하기 위한 특별한 기능을 요구하는데, 반면 MMC는 이러한 동작을 수행하지 않으며, 이는 그것의 해시 체인 루트 때문이다.
결론적으로, BST가 최적 파싱에서 최선의 선택인 동안에 MMC는 탐욕적, 그리고 지연된 검색 매칭에 더 좋은 선택처럼 보인다.
실험 결과
우리는 두가지 버전을 비교한다. 바로 "해시 체인"과, "Morphing Match Chain"이다. 모든 검색 알고리즘은 윈도우에서 최선의 매칭을 찾고, 결과적으로 정확히 동일한 압축 비율을 얻는다. 아래 결과는 전체 파일을 압축하기 위해서 수행되는 체인 비교 횟수를 측정했다. 낮은 값이 더 좋은 값이다.
윈도우 검색 크기 64K
데이터/알고리즘 |
해시 체인 |
|
MMC |
Calgary |
71.6M |
|
4.84M |
Firefox |
261M |
|
34.0M |
Enwik8 |
355M |
|
116.0M |
윈도우 검색 크기 512K
데이터/알고리즘 |
해시 체인 |
|
MMC |
Calgary |
300M |
|
9.13M |
Firefox |
1.26G |
|
70.7M |
Enwik8 |
1.89G |
|
367.0M |
윈도우 검색 크기 4M
데이터/알고리즘 |
해시 체인 |
|
MMC |
Calgary |
368M |
|
11.6M |
Firefox |
4.15G |
|
128.0M |
Enwik8 |
8.99G |
|
612.0M |
결과는 예측과 일치한다. 검색 윈도우 크기를 키울 수록, Morphing Match Chain 방식이 더 효율적이다. 파일의 타입에 따라서 그 효율의 차이는 매우 다르다는 것에 주의하자.
명백히, MMC를 이용하여 검색하는 것은 좀더 복잡하다. 왜냐하면, 체인 테이블에 대한 변경과 그에 따른 비용 때문이다. 하지만, 그것은 끔찍하지 않다. 한 가지 말해주자면, 압축할 수 없는 파일을 압축하는 것에 대해 전통적인 단일 해시 체인 방식에 비교해서 10% 이하의 속도 감소만이 일어난다.
사설
여기에 이 자료 구조가 최고라는 말은 없다.
확실히 단순한 해시 체인 방식의 구현에 비해 적당한 성능향상이 있었다. 더 큰 검색 깊이가 요구되는 상황에서는 더 복잡한 자료 구조가 더 나은 성능을 보일 것처럼 보인다. 해야할 것은 성능 비교 테스트뿐이다.
그런 까닭에, 성능 비교를 위해 적절한 단계는 MMC 검색 알고리즘을 훨씬 더 큰 윈도우 크기(64MB 이살)에서 하는 것이다.
[수정]: Charles Bloom 씨는 다중 일치 검색 알고리즘에 대해 매우 자세한 분석을 그의 블로그(http://cbloomrants.blogspot.de/)를 통해서 수행했다.
결론은 MMC는 사실 최적 파싱 상황에는 적합하지 않다는 것이다.
댓글