|
|
저는 HBO 시리즈 실리콘 밸리를 시청한 이후로 압축 알고리즘에 관심이 많았습니다. 리처드 헨드릭스와 그의 미들 아웃 압축 알고리즘은 물론 가짜였지만, 열심히 검색한 끝에 실제 이런 압축 알고리즘의 천재가 있다는 사실을 알게 되었습니다.
얀 콜렛은 2011년에 LZ4 압축 알고리즘을 발명했는데, 물론 미들 아웃만큼 대단하지는 않지만 일정한 압축률을 유지하면서 압축 속도와 압축 해제 속도가 매우 빠른 것으로 유명합니다.
압축 속도에 대한 리뷰는 여기서 반복하지 않겠습니다. 관심이 있으시다면 이 비교 기사를 읽어보시기 바랍니다: https: //blog.csdn.net/leilonghao/article/details/73200859
LZ4의 깃허브 주소도 첨부되어 있습니다: https: //github.com/lz4/lz4/
이 글은 LZ4 압축 알고리즘의 원리를 설명하는 데 중점을 두고 있습니다. LZ4 알고리즘에 대한 좋은 글이 있습니다: https: //blog.csdn.net/zhangskd/article/details/17282895 하지만 제가 배우다 보니 이 글이 초보자에게는 그리 친절하지 않다고 느껴서 저 같은 초보자를 위해 다른 글을 시작하게 되었습니다.
LZ4를 한 문장으로 요약하면 LZ4는 사전을 저장하고 검색을 간소화하기 위한 16k 해시 테이블을 가진 LZ77입니다.
LZ4는 코어당 500MB/s 이상의 압축 속도를 제공하는 무손실 압축 알고리즘으로, 멀티코어 CPU로 확장할 수 있습니다. 코어당 수 GB/s의 속도로 매우 빠른 디코더를 갖추고 있어 멀티코어 시스템에서 RAM 속도 제한에 도달하는 경우가 많습니다.
압축률과 빠른 속도를 맞바꾸는 '가속' 계수를 선택하여 속도를 동적으로 조정할 수 있습니다. 반면에 높은 압축률인 LZ4_HC는 CPU 시간을 희생하여 압축률을 높이기 위해 제공됩니다. 모든 버전의 압축 해제 속도는 동일합니다.
그렇다면 LZ77은 어떨까요?
LZ77 압축 및 원리
LZ77은 압축에 사전을 적용하는 알고리즘입니다. 쉽게 설명하자면, 프로그램이 현재 보고 있는 데이터가 중복되는지 여부를 관찰(사전을 살펴봄)하고, 중복되는 경우 중복된 두 필드의 오프셋과 중복된 필드를 대체할 길이를 저장하고 이런 방식으로 데이터를 압축한다는 뜻입니다.
https://msdn.microsoft.com/en-us/library/ee916854.aspx 참조
문자열 A A B C B B B B B B C의 경우, 두 번째 A를 읽을 때 프로그램은 ( 1, 1)(이전 반복에서 1비트 떨어진 거리, 길이 1)로 저장하고, 마찬가지로 두 번째 B를 읽을 때 프로그램은 (2, 1)(거리 2, 길이 1)로 저장합니다.
그러나 문자열이 더 길고 프로그램이 항상 데이터를 사전에 기록하면 최악의 경우 프로그램이 새 문자를 읽을 때마다 전체 사전을 검토하기 때문에 반복되는 필드를 검색하는 데 시간이 매우 많이 걸립니다. LZ77은 이 문제를 해결하기 위해 슬라이딩 윈도우 방식을 사용합니다.
TCP의 슬라이딩 윈도우 사용과 마찬가지로, 슬라이딩 윈도우는 캐시 크기를 줄여 동시에 너무 많은 캐시 데이터를 처리하지 않도록 합니다. LZ77에서는 사전이 계속 커지는 것이 아니라 사전의 최대 크기를 초과하면 가장 먼저 추가된 문자가 삭제되므로 사전의 크기가 항상 지정된 최대 크기로 유지됩니다.
사전이 3
| 사전 |
| a | a b c b b b b a b c
Output(0,0,A)
| a a | b c b b a b c
Output(1,1)
| a a b | c b b b b b c
Output(0,0,B) | A A | A B C | C B A B C
A | A B C | B B A B C
Output(0,0,C)
A A | B C B | B A B C
Output(2,1)
슬라이딩 윈도우의 다른 부분은 룩어워드 버퍼입니다. 룩어워드 버퍼는 가장 가까운 사전의 길이 중 압축되지 않은 부분입니다. LZ77 알고리즘은 이 버퍼에서 사전과 동일한 가장 긴 문자열을 일치시킵니다. 앞의 예는 1의 룩어워드 버퍼로 생각할 수 있습니다.
사전이 5이고 미리 보기 버퍼가 3이라고 가정해 보겠습니다.
| 사전 | 미리 보기 버퍼 |
ㅏ | ㅏ ㅏ ㅏ | ㅏ ㅏ | ㅏ ㅏ |
Output(5,3)
일치하는 가장 긴 문자열은 ABC입니다.
완전한 압축 과정입니다:
사전의 길이가 5이고 검색할 캐시의 크기가 3이라고 가정합니다.
| 사전 | 미리 보기 버퍼 |
| A A B | C B B A B A B
output(0,0,A)
| A | A B C | B B A B B C
Output(1,1)
| a a | b c b | b a B C
Output(0,0,B)
| A A B | C B B | A B C
Output(0,0,C)
| A A B C | B B A | B   B
Output(2,1)
| A A B C B | B A B |   ;C
Output(1,1) | A | A B C B | B A B | C
A | A B C B | A B C
Output(5,3)
A A B C | B B A B C | Output(5,3) A A B C | .
압축 해제 절차가 출력의 일치하는 단위로 사전을 복원하기 때문에 압축 절차의 출력 파일에 사전을 저장할 필요가 없습니다.
압축 해제 프로세스
LZ77 알고리즘의 장점 중 하나는 압축 해제 속도가 매우 빠르다는 것입니다.
첫 번째 일치 항목이 (0,0,A)이면 A가 출력됩니다.
두 번째 일치 항목이 (1,1)이면 출력 문자열의 첫 번째 비트가 복사되고 복사본의 길이가 1이면 A가 출력됩니다.
마지막 일치 단위가 (5,1)이면 출력 문자열의 이전 비트를 복사하고 길이를 1로 복사한 다음 A를 출력합니다.
마지막 일치 단위가 (5,3)이면 출력 문자열에서 5비트를 다시 복사하고 복사본의 길이를 3으로 복사한 다음 A,B,C를 출력합니다.
압축을 위한 LZ77 알고리즘에서 가장 시간이 많이 걸리는 부분은 검색할 캐시에서 사전에서 가장 긴 일치하는 문자를 찾는 것입니다. 사전과 검색할 캐시가 너무 짧으면 일치하는 문자를 찾을 확률이 적습니다. 그래서 LZ4는 매칭 알고리즘을 위해 LZ77을 변경합니다.
첫째, LZ4 알고리즘의 사전은 해시 테이블입니다. 사전의 키는 4바이트 문자열이며, 각 키는 하나의 슬롯에만 해당하고 슬롯의 값은 문자열의 위치입니다.
LZ4는 검색할 캐시가 없지만 입력 파일에서 한 번에 4바이트를 읽은 다음 해시 테이블에서 이 문자열의 해당 슬롯을 조회하며, 이를 현재 문자열이라고 합니다.
마지막 12자에 도달하면 출력 파일에 바로 넣습니다.
슬롯에 할당된 값이 없으면 이 4바이트가 처음 나타나는 것으로, 이 4바이트와 위치를 해시 테이블에 추가한 다음 검색을 계속합니다.
슬롯에 값이 있으면 일치하는 값을 찾은 것입니다.
슬롯의 값과 슬라이딩 창의 크기가 문자의 현재 위치보다 작고 일치하는 위치가 블록의 크기를 초과하면 프로그램은 해시 슬롯의 값을 문자열의 현재 위치로 업데이트합니다.
LZ4는 해시 충돌이 발생했는지 확인합니다. 4바이트의 슬롯 값 위치가 현재 문자열과 동일하지 않으면 해시 충돌이 발생한 것입니다. 저자가 사용하는 xxhash도 효율적이라고 알려져 있지만 필연적으로 충돌이 발생할 수밖에 없습니다. 충돌이 발생하면 프로그램은 해시 슬롯의 값을 현재 문자열의 위치로 업데이트합니다.
마지막으로 일치 항목이 유효한지 확인하고 프로그램은 일치 문자열의 후속 문자도 동일한지 계속 확인합니다. 마지막으로, 마지막 유효한 일치의 끝부터 현재 유효한 일치의 시작까지의 모든 문자를 zip 파일에 복사하고 현재 유효한 일치에 대한 일치 시퀀스를 추가합니다.
Collet은 LZ4 일치 시퀀스에 의해 출력된 일치 단위를 호출하여 LZ4 zip 파일을 구성합니다. 구체적으로 다음 그림과 같습니다:
토큰의 길이는 1바이트이며, 이 중 처음 4개의 단어는 리터럴 길이, 다음 4개의 단어는 매치 길이입니다. 이전 섹션에서 언급했듯이 마지막 유효한 일치의 끝부터 이 유효한 일치의 시작까지의 모든 문자는 압축 파일로 복사되며, 이러한 압축되지 않은 파일은 리터럴이며, 그 길이가 리터럴 길이입니다.
리터럴 뒤에는 편차가 뒤따릅니다. LZ77의 편차 및 일치 길이와 마찬가지로 편차는 일치 항목에서 현재 문자열의 길이를 의미하며, 일치 길이는 현재 문자열과 사전의 동일한 문자열 간의 일치 길이를 의미합니다. 압축을 풀 때 복사할 문자열과 복사할 길이를 찾는 데 필요합니다. 편차의 크기는 고정되어 있습니다.
그림에서 리터럴 길이+와 일치 길이+는 토큰의 리터럴 또는 일치 길이 4자가 충분하지 않은 경우 추가되며, 4자는 0-15를 나타낼 수 있고, 바이트가 255에 부족할 때까지 255를 더하는 식으로 1바이트가 더 추가됩니다. 일치 길이에서 0은 4바이트를 나타냅니다.
마지막 12바이트는 리터럴 바로 위에 복사되므로 리터럴 다음에 끝납니다.
코드를 살펴봅시다(파이썬은 더 추상적입니다).
요약 이 모든 것이 끝난 후에도 LZ4가 왜 그렇게 빠른지에 대한 요약은 아직 없습니다. LZ77과 LZ4의 사전 검색을 비교하는 것부터 시작해 보겠습니다. 기본 LZ77은 보류 중인 검색 캐시와 사전에서 가장 큰 일치 항목을 찾아서 사전을 검색합니다. 이는 두 문자열에서 가장 큰 동일한 문자열을 찾는 문제입니다. 동적 프로그래밍을 사용하지 않는다면 최악의 경우 한 문자열의 모든 하위 문자열을 고려한 다음 다른 문자열에서 일치하는 것을 찾아야 합니다. 이 경우 O(m^2×n)이 소요됩니다. 동적 계획을 사용하면 테이블을 사용하여 동적으로 가장 긴 일치 항목을 보관할 수 있으며, 그렇게 하면 O(m*n) 이내에만 일치를 완료할 수 있습니다. 그리고 이는 한 쌍의 검색 버퍼와 사전의 경우에만 해당됩니다. 최악의 경우, 일치하는 항목이 하나도 없는 경우 LZ77은 (전체 파일의 길이 - 검색 버퍼의 길이) 수많은 일치 문제를 해결해야 합니다. LZ4는 실제로 더 큰 수준의 동적 프로그래밍을 사용합니다. 4바이트와 그 위치를 해시 테이블에 저장한 다음, 새로운 4바이트의 데이터와 일치할 때마다 해시 테이블을 살펴보고 유효한 값인지 확인합니다. 그리고 후속 데이터의 두 세트의 일치하는 값을 살펴본 후 유효한 일치 항목을 찾으면 가장 긴 일치 항목을 찾을 수 있습니다. 각 키의 LZ4 해시 테이블은 하나의 슬롯에만 대응하기 때문에 해시 테이블을 찾고 변경하는 작업은 O(1)만 필요합니다. 이후 일치하는 항목이 더 많이 발견되면 더 많은 비교 세트가 필요하지만, 이러한 비교는 해시 테이블을 조회하는 데 소요되는 시간을 대체하므로 총 시간에서 LZ4 알고리즘의 총 시간은 O(n)에 불과합니다. Collet 알고리즘의 아름다움에 감탄하지 않을 수 없습니다! 알고리즘을 더욱 빠르게 만들기 위해 Collet은 기본 해시 테이블 크기를 16k로 설정하고, 거의 모든 CPU(인텔)의 1레벨 캐시에 넣을 수 있도록 32k를 넘지 않도록 권장합니다. 우리 모두는 CPU 레벨 1 캐시의 속도와 메모리 비율이 매우 높다는 것을 알고 있으므로 LZ4의 해시 테이블이 해시 방정식 또는 가장 빠른 xxhash를 사용한다는 것은 말할 것도없고 LZ4의 비행 속도가 놀랍지 않습니다. 물론 이러한 설계에는 단점이 있습니다. 해시 테이블이 작을수록 더 적은 수의 키를 갖게 됩니다. 이는 더 많은 해시 충돌이 발생한다는 것을 의미하며, 이는 불가피한 현상입니다. 그리고 해시 충돌이 많다는 것은 일치하는 항목이 적다는 것을 의미합니다. 그리고 해시 테이블이 작을수록 슬라이딩 창이 작아지므로 너무 멀리 떨어져 있기 때문에 더 많은 일치 항목이 삭제됩니다. 일치하는 항목이 적을수록 압축률이 낮아지므로 LZ4의 압축률은 더욱 떨어집니다. Outlook LZ4는 다양한 활용 시나리오가 있습니다. VR에서 미들 아웃이 사용된 실리콘 밸리에서와 같이, LZ4는 매우 빠른 압축으로 인해 지연 시간이 매우 짧아지는 대신 IO를 적게 가져와 대역폭 사용량을 늘릴 수 있습니다. 그리고 약간의 추측이지만, CPU의 경우 아웃 레벨 1 캐시가 더 크다면 LZ4는 속도를 해치지 않으면서 압축률을 높일 수 있지 않을까요?
원본 기사: https: //www.cnblogs.com/z-blog/p/8860799.html |
이전글：트루나스 코어뷰 스냅샷(스냅샷) 위치 변경하기다음 글：자바 , OkHttp를 사용해 HTTP 네트워크 요청 보내기
|
게시됨 2022-1-3 13:54:23
즐겨찾기0 