HBO 드라마 "실리콘밸리"를 본 후, 저는 항상 압축 알고리즘에 관심이 많았습니다. 리처드 헨드릭스와 그의 중간 압축 알고리즘은 물론 가짜지만, 구글 검색을 해보니 실제로 그런 압축 알고리즘 천재가 있다는 걸 알게 됐어요.
얀 콜렛은 2011년에 LZ4 압축 알고리즘을 발명했습니다. 물론 LZ4 알고리즘은 미들 아웃만큼 뛰어나진 않지만, 무적의 압축 속도와 특정 압축률이 보장될 때 더 빠른 압축 속도로 알려져 있습니다.
압축 속도 평가에 대해서는 여기서 자세히 다루지 않겠습니다. 관심 있으시면 이 비교 기사를 읽어보실 수 있습니다:하이퍼링크 로그인이 보입니다.
또한 LZ4의 깃허브 주소도 첨부되어 있습니다:하이퍼링크 로그인이 보입니다.
이 글에서는 LZ4 압축 알고리즘의 원리를 설명하는 데 중점을 둡니다. 위대한 신이 이전에 LZ4 알고리즘에 대한 설명을 썼습니다:하이퍼링크 로그인이 보입니다.하지만 이전에 공부할 때는 이 글이 초보자에게 그리 친절하지 않다고 느껴서, 저와 같은 초보자들을 위한 또 다른 글을 시작했습니다.
한 문장으로 요약하자면, LZ4는 16k 크기의 해시 테이블이 있는 사전을 저장하고 검색을 단순화하는 LZ77입니다.
LZ4는 무손실 압축 알고리즘으로, 코어당 > 500 MB/s의 압축 속도를 제공하며, 멀티코어 CPU로 확장할 수 있습니다. 이 시스템은 코어당 수 GB/s의 매우 빠른 디코더를 탑재하고 있으며, 멀티코어 시스템에서는 종종 RAM 속도 제한에 도달합니다.
속도는 동적으로 조절할 수 있으며, 압축비를 대신 더 빠른 속도를 얻는 '가속' 계수를 선택할 수 있습니다. 반면, CPU 시간을 희생하여 압축을 높이기 위해 고압축 미분 LZ4_HC도 제공됩니다. 모든 버전은 동일한 감압 속도를 가지고 있습니다.
그렇다면 LZ77이란 무엇일까요?
LZ77 압축 및 원리
LZ77은 압축을 위해 사전을 적용하는 알고리즘입니다. 쉽게 말해, 프로그램이 현재 보이는 데이터가 이전 데이터와 중복되었는지 관찰(사전 확인)하고, 그렇다면 중복 필드의 거리(오프셋)와 길이를 저장해 중복 필드를 대체하고 데이터를 압축하는 것입니다.
참조하이퍼링크 로그인이 보입니다.
글자 연속 A A B C B B A B C 중 두 번째 A를 읽으면 (1,1)(이전 A에서 1자리, 길이 1)을 저장하고, 마찬가지로 두 번째 B를 읽으면 (2,1)(거리 2, 길이 1)를 저장합니다.
하지만 문자열이 길고 프로그램이 데이터를 계속 사전에 기록한다면, 중복 필드를 찾는 데 매우 시간이 많이 걸리는데, 최악의 경우 프로그램이 새로운 글자를 읽을 때마다 사전 전체를 다 뒤지게 되기 때문입니다. LZ77은 이 문제를 해결하기 위해 슬라이딩 윈도우 방식을 사용합니다.
슬라이딩 윈도우를 사용하는 TCP의 시작점과 유사하게, 슬라이딩 윈도우는 동시에 너무 많은 캐시 데이터를 처리하지 않도록 캐시 영역을 줄일 수 있습니다. LZ77에서는 사전이 항상 증가하지 않고, 사전이 지정한 최대 크기를 초과하면 첫 번째 문자를 버려 사전의 크기가 항상 최대 크기로 유지되도록 합니다.
사전 길이가 3이라고 가정하자.
| 사전 |
| A | A B C B B A B C
출력 (0,0,A)
| A A | 비 아 아 비
출력(1,1)
| A A B | C B B A B C
출력 (0,0,B)
A | A B C | B B A B C
출력 (0,0,C)
A A | B C B | B A B C
출력(2,1)
슬라이딩 윈도우의 다른 부분은 검색할 캐시입니다(룩어헤드 버퍼에는 공식 번역이 없습니다). 검색할 캐시는 사전에 가장 가까운 비압축 부분입니다. LZ77 알고리즘은 이 부분에서 사전과 동일한 가장 긴 문자열을 조합합니다. 앞서 본 예시는 1의 앞으로를 보는 버퍼로 볼 수 있습니다.
사전 길이가 5이고 검색할 캐시 크기가 3이라고 가정하자.
| 사전 | 앞으로를 보기 버퍼 |
A | A B C B B | A B C |
출력(5,3)
가장 긴 연속 연속 중 일치하는 것은 ABC입니다
완전한 압축 과정:
사전 길이가 5이고 검색할 캐시 크기가 3이라고 가정하자.
| 사전 | 앞으로를 보기 버퍼 |
| A A B | C B B A B C
출력 (0,0,A)
| A | A B C | B B A B C
출력(1,1)
| A A | B C B | B A B C
출력 (0,0,B)
| A A B | C B B | A B C
출력 (0,0,C)
| A A B C | B B A | B C
출력(2,1)
| A A B C B | 비 아 비 | C
출력(1,1)
A | A B C B B | A B C |
출력(5,3)
A A B C | B A B C | 。。|
컴프레서의 출력 파일에 사전을 저장할 필요가 없으며, 압축 해제 프로그램이 출력 단위를 맞춰 사전을 복원합니다.
감압 과정
LZ77 알고리즘의 큰 장점 중 하나는 매우 빠른 디컴프레션(압축 해제)이라는 점입니다.
첫 번째 매칭 단위가 (0,0,A)이라면, A가 출력됩니다.
두 번째 매칭 유닛은 (1,1)로, 출력 문자열의 이전 비트를 복사하고, 복사 길이가 1일 때 A를 출력합니다.
。。。
마지막 일치 단위가 (5,3)이라면 복사 출력 문자열의 5비트를 되돌아보고, 복사 길이가 3이면 출력 A, B, C를 사용합니다.
LZ77 알고리즘 압축 중 가장 시간이 많이 드는 부분은 사전에서 검색할 캐시에서 가장 긴 일치 문자를 찾는 것입니다. 사전과 검색할 캐시가 너무 짧으면 일치하는 것을 찾을 가능성이 매우 낮습니다. 따라서 LZ4는 LZ77의 매칭 알고리즘을 변경했습니다.
첫째, LZ4 알고리즘의 사전은 해시 테이블입니다. 사전의 키는 4바이트 문자열이며, 각 키는 단 하나의 슬롯에만 해당하며, 슬롯 내 값은 이 문자열의 위치입니다.
캐시를 검색하는 대신, LZ4는 입력 파일에서 한 번에 4바이트씩 읽고, 이후 해시 테이블에서 문자열에 해당하는 슬롯을 찾습니다. 이를 이하 현재 문자열이라고 부릅니다.
마지막 12자까지 도달했다면, 출력 파일에 직접 입력하세요.
슬롯에 값이 할당되지 않는다면, 네 바이트가 처음 나타나 이 네 바이트와 위치를 해시 테이블에 더한 후 계속 검색을 진행합니다.
슬롯에 할당이 있다면, 이는 매칭 값을 찾았다는 뜻입니다.
슬롯 값과 슬라이더 창 크기가 현재 문자 위치< 같다면, 매칭 위치가 블록 크기를 초과하며, 프로그램은 해시 슬롯 값을 현재 문자열 위치로 업데이트합니다.
LZ4는 해시 충돌이 발생했는지 확인합니다. 슬롯 내 4바이트가 현재 문자열과 다르면 해시 충돌이 있을 것입니다. 저자의 xxhash도 효율성으로 유명하지만, 충돌은 불가피합니다. 충돌이 발생할 경우, 프로그램은 해시 슬롯의 값을 문자열의 현재 위치로 업데이트합니다
마지막으로, 매칭이 유효한지 확인할 수 있고, 프로그램은 매칭 문자열의 후속 문자들이 동일한지 계속 확인할 것입니다. 마지막으로, 이전 유효한 매칭의 끝에서 압축된 매칭의 시작 부분으로 모든 문자를 복사하고, 이 유효한 매칭의 매칭 시퀀스를 추가합니다.
Collet은 LZ4 시퀀스에서 출력되는 매칭 유닛을 호출하며, 이들은 LZ4 압축 파일을 구성합니다. 자세한 내용은 다음과 같습니다:
토큰 길이는 1바이트이며, 처음 4단어가 문자 그대로, 마지막 4단어가 매칭 길이입니다. 앞서 언급했듯이, 이전 유효한 일치의 끝부터 그 유효한 일치의 시작 지점까지의 모든 문자는 압축된 파일에 복사되며, 이 압축되지 않은 파일은 문자 그대로이고 길이는 문자 그대로입니다.
말 그대로 일탈이 뒤따른다. LZ77과 마찬가지로, 편차와 매칭 길이는 현재 문자열이 매칭된 스트링에서 매칭되는 길이를 의미하며, 매칭 길이는 현재 스트링이 사전에서 같은 스트링과 매칭 길이로 가는 길이를 의미합니다. 압축 해제는 복사할 문자열과 복사할 길이를 찾기 위해 그 부분을 거치는 것입니다. 편차의 크기는 고정되어 있습니다.
그림에서 리터럴 길이+와 매칭 길이+는 만약 토큰의 리터럴 또는 매칭 길이 4단어가 충분하지 않으면, 해당 위치에서 계속 증가합니다. 4개의 단어는 0부터 15까지 나타날 수 있으며, 더 있으면 1바이트를 더해 255를 더해 255 바이트가 255보다 작아질 때까지 반복합니다. 매칭 길이에서 0은 4바이트를 의미합니다.
마지막 12바이트는 문자 그대로 복사되었기 때문에 끝납니다.
코드를 살펴보겠습니다(파이썬이 더 추상적입니다)
요약 이 모든 말을 했음에도 불구하고, LZ4가 왜 그렇게 빠른지 아직 요약하지 못했습니다. 먼저 LZ77과 LZ4의 사전 검색을 비교해 봅시다. 기본 LZ77은 검색할 캐시와 사전 내에서 가장 큰 일치 사전을 찾아 사전을 검색합니다. 이는 두 개의 줄에서 가장 큰 동일한 문자열을 찾는 문제입니다. 동적 프로그래밍을 사용하지 않는다면, 최악의 경우 한 문자열의 모든 부분문자열을 고려한 후 다른 문자열에서 맞춰야 합니다. ×동적 프로그래밍을 사용한다면, 동적 프로그래밍에서 가장 긴 일치를 저장하는 테이블을 사용하며, 이는 O(m*n)의 경우에만 매칭을 완성할 수 있게 합니다. 그리고 이건 단지 두 개의 검색 캐시와 사전 한 쌍에 해당하는 이야기입니다. 최악의 경우, 매칭이 없으면 LZ77은 (전체 파일 길이 - 검색할 캐시 길이) 매칭 문제의 수를 계산해야 합니다. LZ4는 실제로 더 높은 수준의 동적 프로그래밍을 사용합니다: 4바이트와 그 위치를 해시 테이블에 저장한 후, 매번 새로운 4바이트의 데이터를 매치하여 해시 테이블의 값이 유효한지 확인합니다. 유효한 일치 값을 찾은 후, 두 짝짓는 값 집합의 후속 데이터를 보면 가장 긴 일치 값도 찾을 수 있습니다. LZ4 해시 테이블의 각 키는 단 1개의 슬롯에 해당하기 때문에, 해시 테이블을 찾고 추가하며 수정하는 작업은 O(1)만 필요합니다. 매칭 후 더 많은 일치가 발견되면 더 많은 그룹 비교가 필요하지만, 전체 시간 동안 이 비교들이 해시 테이블을 조회하는 시간을 대체하므로 LZ4 알고리즘의 총 시간은 O(n)에 불과합니다. Collet 알고리즘의 아름다움에 감탄하지 않을 수 없습니다! 알고리즘을 더욱 빠르게 만들기 위해 Collet은 기본 해시 테이블 크기를 16k로 설정했으며, 이는 32k를 넘지 않는 것이 권장되어 거의 모든 CPU(인텔)의 L1 캐시에 넣을 수 있도록 합니다. CPU L1 캐시의 속도와 메모리 비율이 매우 다르다는 것은 모두가 알고 있기에 LZ4가 빠르게 작동하는 것은 놀라운 일이 아니며, LZ4 해시 테이블에 사용되는 해시 방정식이 여전히 가장 빠른 xx해시입니다. 물론, 이런 설계에는 단점도 있습니다. 해시 테이블이 작을수록 키 수가 적습니다. 이는 더 많은 해시 충돌이 발생할 것임을 의미하며, 이는 불가피한 일입니다. 그리고 해시 충돌이 많아질수록 매치 수가 줄어듭니다. 그리고 해시 테이블이 작아질수록 슬라이딩 창도 작아져, 너무 멀리 떨어져 버려진 매치가 더 많아집니다. 매칭 수가 적을수록 압축비가 낮아지기 때문에, LZ4는 압축비가 덜 두드러집니다. 앞으로를 내다보며 LZ4는 다양한 응용 시나리오를 가지고 있습니다. 실리콘밸리의 VR에서 중간 출력이 사용되었던 것처럼, LZ4는 매우 빠른 압축 속도 덕분에 IO를 적게 가져와서 대역폭 활용도를 높일 수 있습니다. 또 약간의 추측도 있는데, 만약 레벨 1에서 더 큰 캐시를 가진 CPU가 있다면, LZ4가 속도를 해치지 않고 압축비를 높일 수 있을까요?
원문 언어:하이퍼링크 로그인이 보입니다. |
게시됨 2022. 1. 3. 오후 1:54:23
|
|
|
|
