MySQL
LZ77
빈 도를 체크해서 치환하는 방식 자세한 구현은 -> 여기
알고리즘 LZ77_압축(입력문자열):
압축결과 = 빈 리스트
검색버퍼크기 = N
전방버퍼크기 = M
현재위치 = 0
while 현재위치 < 입력문자열의 길이:
// 검색 버퍼와 전방 버퍼 설정
검색버퍼시작 = max(0, 현재위치 - 검색버퍼크기)
검색버퍼끝 = 현재위치
전방버퍼끝 = min(현재위치 + 전방버퍼크기, 입력문자열의 길이)
최대일치위치 = 0
최대일치길이 = 0
// 검색 버퍼에서 가장 긴 일치 찾기
for 검색위치 = 검색버퍼시작 to 검색버퍼끝 - 1:
현재일치길이 = 0
while 현재위치 + 현재일치길이 < 전방버퍼끝 AND
검색위치 + 현재일치길이 < 현재위치 AND
입력문자열[검색위치 + 현재일치길이] == 입력문자열[현재위치 + 현재일치길이]:
현재일치길이 += 1
if 현재일치길이 > 최대일치길이:
최대일치길이 = 현재일치길이
최대일치위치 = 검색위치
if 최대일치길이 > 0:
// 상대적 위치 계산 (검색 버퍼 내의 오프셋)
오프셋 = 현재위치 - 최대일치위치
다음문자 = 입력문자열[현재위치 + 최대일치길이] (전방버퍼끝에 도달했다면 null 또는 특수 문자)
압축결과.추가((오프셋, 최대일치길이, 다음문자))
현재위치 += 최대일치길이 + 1
else:
// 일치하는 것이 없으면 현재 문자를 그대로 출력
압축결과.추가((0, 0, 입력문자열[현재위치]))
현재위치 += 1
return 압축결과
“abracadabra"를 압축하는 과정 예시(검색버퍼 =7, 전방버퍼 =4)
- 초기 상태:
- 현재위치: 0
- 검색버퍼: [] (비어있음)
- 전방버퍼: [a,b,r,a]
- 일치 없음 → (0,0,‘a’) 출력
- 현재위치: 1
- 두 번째 단계:
- 현재위치: 1
- 검색버퍼: [a]
- 전방버퍼: [b,r,a,c]
- 일치 없음 → (0,0,‘b’) 출력
- 현재위치: 2
- 세 번째 단계:
- 현재위치: 2
- 검색버퍼: [a,b]
- 전방버퍼: [r,a,c,a]
- 일치 없음 → (0,0,‘r’) 출력
- 현재위치: 3
- 네 번째 단계:
- 현재위치: 3
- 검색버퍼: [a,b,r]
- 전방버퍼: [a,c,a,d]
- ‘a’가 검색버퍼의 첫 위치(오프셋=3)와 일치 → (3,1,‘c’) 출력
- 현재위치: 5
- 다섯 번째 단계:
- 현재위치: 5
- 검색버퍼: [a,b,r,a,c]
- 전방버퍼: [a,d,a,b]
- ‘a’가 검색버퍼의 여러 위치와 일치하지만 가장 최근 위치(오프셋=2)를 선택 → (2,1,’d’) 출력
- 현재위치: 7
- 여섯 번째 단계:
- 현재위치: 7
- 검색버퍼: [a,b,r,a,c,a,d]
- 전방버퍼: [a,b,r,a]
- 검색버퍼에서 “abra"를 찾음(오프셋=7, 길이=4) → (7,4,null) 출력
- 현재위치: 11 (문자열 끝)
결과 :
(0,0,'a'), (0,0,'b'), (0,0,'r'), (3,1,'c'), (2,1,'d'), (7,4,null)
Huffman Encoding
허프만 코딩은 데이터의 문자 빈도수를 이용하여 가변 길이의 이진 코드로 압축하는 방식. 자주 등장하는 문자에는 짧은 코드를, 드물게 등장하는 문자에는 긴 코드를 할당하여 효율적인 압축을 수행한다.
인코딩
각 문자의 빈도수 계산 입력 데이터에서 각 문자의 빈도를 계산한다.
우선순위 큐(Priority Queue) 활용 빈도가 낮은 순서대로 정렬된 노드들을 관리하는 우선순위 큐를 사용한다.
허프만 트리(Huffman Tree) 생성 빈도가 가장 작은 두 개의 노드를 선택하여 새로운 노드를 생성한다. 새 노드의 빈도수는 두 자식 노드의 빈도수를 합한 값이다. 이를 반복하여 하나의 트리가 완성될 때까지 수행한다.
코드 할당 트리의 왼쪽 가지는 0, 오른쪽 가지는 1을 할당하여 각 문자에 고유한 이진 코드 부여한다.
데이터 인코딩 원래 데이터를 허프만 코드로 변환하여 압축한다.
디코딩
인코딩된 값을 트리에서 읽어감
0001001011 이런식이라면,
0에서 리프를 만나면 치환
001 에서 리프를 만났으니 치환
이런식으로 트리를 기반으로 치환해가며 디코딩