RLE는 가장 간단한 압축 방식이다. 다음과 같은 데이터가 있다고 가정해 보자:
aaaaabbbcdeeeeeeef...
RLE는 이를 다음과 같이 인코딩한다:
5a3b1c1d7e1f...
바이트를 반복하는 대신, 해당 바이트가 몇 번 반복되는지 기록한 후 실제 값을 쓴다. 따라서 5a는 aaaaa를 의미한다. 데이터에 반복되는 바이트가 많다면 RLE는 상당한 공간을 절약할 수 있다. 특히 이미지에서 효과적이다.
RLE를 구현하는 방법은 다양하다. 여기서는 PCX 이미지 파일 포맷에서 영감을 받은 RLE 버전을 Data 확장으로 구현한다.
규칙은 다음과 같다:
특정 바이트 값이 연속으로 여러 번 나타날 경우, 두 바이트로 압축한다. 첫 번째 바이트는 반복 횟수를 기록하고, 두 번째 바이트는 실제 값을 기록한다. 첫 번째 바이트는 191 + count로 저장한다. 이는 인코딩된 바이트 런이 64바이트를 넘을 수 없음을 의미한다.
0부터 191 사이의 단일 바이트는 압축하지 않고 그대로 복사한다.
192부터 255 사이의 단일 바이트는 두 바이트로 표현된다. 첫 번째 바이트는 192(1바이트 런을 의미), 두 번째 바이트는 실제 값이다.
다음은 압축 코드이다. 런 렝스 인코딩된 바이트를 포함한 새로운 Data 객체를 반환한다:
extension Data {
public func compressRLE() -> Data {
var data = Data()
self.withUnsafeBytes { (uPtr: UnsafePointer<UInt8>) in
var ptr = uPtr
let end = ptr + count
while ptr < end { //1
var count = 0
var byte = ptr.pointee
var next = byte
while next == byte && ptr < end && count < 64 { //2
ptr = ptr.advanced(by: 1)
next = ptr.pointee
count += 1
}
if count > 1 || byte >= 192 { // 3
var size = 191 + UInt8(count)
data.append(&size, count: 1)
data.append(&byte, count: 1)
} else { // 4
data.append(&byte, count: 1)
}
}
}
return data
}
}동작 방식:
UnsafePointer를 사용해 원본 Data 객체의 바이트를 순회한다.
현재 바이트 값을 byte 변수에 읽어들인다. 다음 바이트가 동일하다면 다른 바이트 값을 찾거나 데이터의 끝에 도달할 때까지 계속 읽는다. 또한 런이 64바이트에 도달하면 멈춘다. 이는 최대 인코딩 가능한 길이이다.
여기서는 방금 읽은 바이트를 어떻게 인코딩할지 결정한다. 첫 번째 가능성은 2개 이상(최대 64개)의 바이트 런을 읽은 경우이다. 이 경우 두 바이트를 쓴다: 런의 길이와 바이트 값. 하지만 단일 바이트를 읽었는데 그 값이 192 이상인 경우도 두 바이트로 인코딩한다.
세 번째 가능성은 192 미만의 단일 바이트를 읽은 경우이다. 이는 그대로 출력에 복사한다.
플레이그라운드에서 다음과 같이 테스트할 수 있다:
let originalString = "aaaaabbbcdeeeeeeef"
let utf8 = originalString.data(using: String.Encoding.utf8)!
let compressed = utf8.compressRLE()압축된 Data 객체는 <c461c262 6364c665 66>이어야 한다. 이를 직접 디코딩해 보면:
c4 이는 십진수로 196이다. 다음 바이트가 5번 나타남을 의미한다.
61 데이터 바이트 "a".
c2 다음 바이트가 3번 나타남.
62 데이터 바이트 "b".
63 데이터 바이트 "c". 192 미만이므로 단일 데이터 바이트이다.
64 데이터 바이트 "d". 한 번만 나타난다.
c6 다음 바이트가 7번 나타남.
65 데이터 바이트 "e".
66 데이터 바이트 "f". 한 번만 나타난다.
원본 18바이트 대비 9바이트로 압축되었다. 50% 절약이다. 물론 이는 단순한 테스트 케이스이다. 운이 없어 원본 데이터에 바이트 런이 전혀 없다면 이 방법은 오히려 인코딩된 데이터를 두 배로 늘릴 수 있다. 따라서 이는 입력 데이터에 크게 의존한다.
다음은 압축 해제 코드이다:
public func decompressRLE() -> Data {
var data = Data()
self.withUnsafeBytes { (uPtr: UnsafePointer<UInt8>) in
var ptr = uPtr
let end = ptr + count
while ptr < end {
// 다음 바이트를 읽는다. 이는 192 미만의 단일 값이거나 바이트 런의 시작이다.
var byte = ptr.pointee // 1
ptr = ptr.advanced(by: 1)
if byte < 192 { // 2
data.append(&byte, count: 1)
} else if ptr < end { // 3
// 실제 데이터 값을 읽는다.
var value = ptr.pointee
ptr = ptr.advanced(by: 1)
// 그리고 반복적으로 쓴다.
for _ in 0 ..< byte - 191 {
data.append(&value, count: 1)
}
}
}
}
return data
}다시 UnsafePointer를 사용해 Data를 읽는다. 여기서 다음 바이트를 읽는다. 이는 192 미만의 단일 값이거나 바이트 런의 시작이다.
단일 값이라면 그대로 출력에 복사한다.
하지만 바이트가 런의 시작이라면 먼저 실제 데이터 값을 읽은 후 반복적으로 쓴다.
압축된 데이터를 원본으로 되돌리려면 다음과 같이 한다:
let decompressed = compressed.decompressRLE()
let restoredString = String(data: decompressed, encoding: NSUTF8StringEncoding)이제 originalString == restoredString은 참이어야 한다!
각주: 원본 PCX 구현은 약간 다르다. 여기서 바이트 값 192(0xC0)는 다음 바이트가 0번 반복됨을 의미한다. 이는 최대 런 크기를 63바이트로 제한한다. 하지만 내 구현에서는 192가 다음 바이트가 한 번 나타남을 의미하며, 최대 런 길이는 64바이트이다.
이는 아마도 PCX 포맷을 설계할 때의 트레이드오프였을 것이다. 바이너리로 보면 상위 두 비트가 바이트가 압축되었는지 여부를 나타낸다. (두 비트가 모두 설정되면 바이트 값은 192 이상이다.) 런 길이를 얻으려면 byte & 0x3F를 수행하면 되며, 이는 0부터 63 사이의 값을 제공한다.
Swift Algorithm Club을 위해 Matthijs Hollemans가 작성함
Swift3으로 Jaap Wijnen이 마이그레이션함