압축 알고리즘 등

특정 데이터를 csv로 추출하여 압축하는 업무가 있었는데

정렬 작업을 한 후 zip파일 용량을 비교해 보니 큰 차이를 발견했다. 

 

정렬 전 : csv용량 120gb -> zip용량 28gb

정렬 후 : csv용량 120gb -> zip용량 13gb

 

왜 그런걸까?

정렬을 통해 데이터의 규칙성과 중복성이 생겨 압축 알고리즘이 데이터를 더 효율적으로 압축할 수 있기 때문이다.

• 압축 알고리즘은 반복적인 패턴을 찾아 인코딩하는 방식
• 특정 열을 기준으로 정렬하여 비슷한 값이나 행이 서로 가까이 위치하게 되며, 이런 데이터는 런렝스 인코딩이나 사전 기반 압축(zip,gzip) 같은 기법으로 더 효율적으로 압축.
• 엔트로피 감소(데이터의 무작위성 감소)

리눅스의 zip명령어는 어떤 알고리즘일까?

Deflate알고리즘. (LZ77 압축 + 허프만 코딩)

1. Laz77
   • 슬라이딩 윈도우를 사용하여 데이터 내 반복되는 시퀀스를 찾아 이전에 나온 데이터를 참조로 대체.
   • 데이터 중복을 제거하여 압축 효율을 높이는 기법.
2. 허프만 코딩
   • 데이터의 출현 빈도를 기반으로 더 자주 나타나는 패턴에는 짧은 바이너리코드, 덜 나타나는  패턴에든 긴 바이너리 코드를 할당.
   • 위 과정을 통해 데이터를 공간 효율적으로 인코딩 가능.

위 두 알고리즘을 결합한 deflate알고리즘은 효과적인 무손실 압축을 가능하게 한다.

 

슬라이딩 윈도우?

데이터의 부분 집합을 처리하기 위해 사용하는 알고리즘 기법.

고정된 크기의 윈도우를 유지하며 데이터셋 위를 점진적으로 이동하면서 처리.