압축의 필요
제가 유치원에 다녔을 때만 해도 플로피 디스크에 1MB면 엄청난 용량이었는데 이제는 1TB가 넘는 외장하드가 비일비재합니다. 데이터가 점점 커지면서 압축은 매우 필요한 기술이 되었습니다.
LZW 압축
LZW 압축 알고리즘은 Lempel, Ziv, Welch라는 세 사람이 고안한 압축 알고리즘의 변형입니다.
허프만 코드의 압축 알고리즘의 핵심은 일반적인 아이템에는 더 짧은 인코딩을, 빈도가 낮은 아이템에 긴 인코딩을 사용하는 것입니다.
한 글자를 가지고 인코딩하는 방식이 아닌, 인코딩하는 아이템의 길이를 변경하는 것이 LZW 압축 알고리즘의 핵심입니다.
아스키로 인코딩된 텍스트에서 인코딩하는데 더 많은 비트를 사용합니다. (7bit -> 8bit)
8bit으로는 256가지의 아이템을 표현할 수 있습니다. 0 ~ 127까지는 ascii code를 표현하고, 그 이후의 숫자까지는 원하는 문자열을 표현합니다.
압축하는 방법?
LZW 압축은 일련의 입력 데이터를 스캔하면서 반복되는 패턴을 찾아냅니다. 초기에는 사전에 ASCII 문자 집합과 대응하는 코드를 저장해놓고, 입력 데이터를 한 문자씩 읽어들입니다. 그리고 사전에 해당 문자가 이미 등록되어 있는지 확인합니다.
만약 현재 문자와 이전까지 읽은 문자들의 조합이 사전에 등록되어 있다면, 이를 하나의 패턴으로 간주합니다. 이전 문자들에 현재 문자를 추가하여 다음 문자까지 읽어들입니다. 이 과정에서 새로운 패턴이 발견되면 사전에 추가하고, 그 패턴을 표현하는 새로운 코드를 생성합니다.
만약 패턴이 사전에 등록되어 있지 않다면, 이전까지 읽은 문자들을 표현하는 코드를 출력하고, 새로운 패턴을 사전에 추가합니다. 그리고 새로운 패턴을 표현하는 코드를 생성합니다.
이 과정을 계속해서 진행하면서 입력 데이터를 스캔하고, 출력 데이터를 생성합니다. 출력 데이터는 코드의 연속으로 이루어져 있으며, 코드는 일반적으로 고정된 길이를 가지는 비트열로 표현됩니다. 이렇게 생성된 출력 데이터는 입력 데이터보다 작은 크기를 가지는 압축된 형태로 나타납니다.
n-gram
문자열을 표현하는데 두 개 문자로 구성된 문자열을 바이그램(bigram) 이라고 하고, 세 개 문자로 구성된 문자열을 트라이그램(trigram) 이라고 합니다. 이보다 더 긴 문자열은 구성하는 문자 수에 gram이란 접미사를 붙여서 n-gram이라고 부릅니다.
PSEUDO CODE
LZW 압축(Compressed)
function LZW_Compress(input):
initialize the dictionary (create an initial dictionary mapping of ASCII char)
initialize the output codes
initialize the current pattern as an empty string
Create an empty list to store the compressed data
for char c in the input data:
add c to the current_pattern
if current_pattern exists in the dictionary:
Update the current_pattern as current_pattern + c
else:
output the code for the current_pattern
add the current_pattern + c to the dictionary and generate a new code
Output the code for the current pattern
return compressed_data
LZW 압축해제(Decompress)
function LZW_Decompress(compressed):
initialize the dictionary(create an initial dictionary mapping of ASCII char)
initialize the previous code
Create an empty string to store the decompressed data
for code in compressed_data:
if code exists in the dictionary:
output the striing corresponding to the current code
add the prev_code + the first char of the current_code
else:
output the string corresponding to the prev_code + the first char of the prev_code
add the prev_code + first char of the prev_code to the dict & generate a new code
update the prev_code as the current_code
return compressed_data
C++ 코드
#include <iostream>
#include <unordered_map>
#include <vector>
#include <string>
std::vector<int> LZW_Compress(const std::string& input) {
std::unordered_map<std::string, int> dictionary;
for (int i = 0; i < 256; ++i) {
dictionary[std::string(1, static_cast<char>(i))] = i;
}
std::string currentPattern;
std::vector<int> compressedData;
for (char c : input) {
std::string pattern = currentPattern + c;
if (dictionary.count(pattern)) {
currentPattern = pattern;
} else {
compressedData.push_back(dictionary[currentPattern]);
dictionary[pattern] = dictionary.size();
currentPattern = std::string(1, c);
}
}
if (!currentPattern.empty()) {
compressedData.push_back(dictionary[currentPattern]);
}
return compressedData;
}
std::string LZW_Decompress(const std::vector<int>& compressed) {
std::unordered_map<int, std::string> dictionary;
for (int i = 0; i < 256; ++i) {
dictionary[i] = std::string(1, static_cast<char>(i));
}
std::string decompressedData;
std::string previousPattern = dictionary[compressed[0]];
decompressedData += previousPattern;
for (size_t i = 1; i < compressed.size(); ++i) {
int currentCode = compressed[i];
std::string currentPattern;
if (dictionary.count(currentCode)) {
currentPattern = dictionary[currentCode];
} else {
currentPattern = previousPattern + previousPattern[0];
}
decompressedData += currentPattern;
dictionary[dictionary.size()] = previousPattern + currentPattern[0];
previousPattern = currentPattern;
}
return decompressedData;
}
int main() {
std::string input = "TOBEORNOTTOBEORTOBEORNOT";
std::vector<int> compressed = LZW_Compress(input);
std::string decompressed = LZW_Decompress(compressed);
std::cout << "Input: " << input << std::endl;
std::cout << "Compressed: ";
for (int code : compressed) {
std::cout << code << " ";
}
std::cout << std::endl;
std::cout << "Decompressed: " << decompressed << std::endl;
return 0;
}
시간 복잡도
LZW 압축 알고리즘의 시간 복잡도는 O(n)입니다. n은 입력 데이터의 크기를 나타냅니다.
LZW 압축 알고리즘은 입력 데이터를 한 번 스캔하는 과정을 거칩니다. 입력 데이터를 한 번 읽으면서 패턴을 인식하고, 사전을 구축하며, 출력 코드를 생성합니다. 이러한 과정은 입력 데이터의 크기에 비례해 실행되기 때문에 선형 시간 복잡도인 O(n)을 가집니다.
더 좋은 압축 알고리즘?
1. Deflate 알고리즘
LZ77 알고리즘과 허프만(Huffman) 코딩을 결합해서 데이터를 효율적으로 압축하는 알고리즘으로, ZIP 파일 형식과 함께 gzip, zlib 등의 압축 포맷에서 널리 사용됩니다.
2. LZMA 압축 알고리즘
LZMA (Lempel-Ziv-Markov chain Algorithm)는 데이터 압축을 위한 고급 압축 알고리즘입니다. LZMA는 다른 압축 알고리즘에 비해 높은 압축률을 제공하면서도 상대적으로 긴 압축 시간을 가지는 특징이 있습니다. LZMA는 7-Zip 압축 프로그램에서 주로 사용되며, .7z 확장자를 가진 압축 파일 형식으로 알려져 있습니다.
