聲明：算法和數(shù)據(jù)結(jié)構(gòu)的文章均是作者從github上翻譯過來揭措，為方便大家閱讀。如果英語閱讀能力強的朋友，可以直接到swift算法俱樂部查看所有原文柑潦，以便快速學習。作者同時也在學習中肢扯，歡迎交流
在編程過程中妒茬，我們可能會遇到某些情況，需要我們壓縮數(shù)據(jù)蔚晨，而行程編碼（RLE）可以說是最簡單的壓縮算法乍钻。假定我們有需要壓縮的數(shù)據(jù)如下：
aaaaabbbcdeeeeeeef...
經(jīng)過行程編碼壓縮后：
5a3b1c1d7e1f...
原始數(shù)據(jù)中，不斷重復出現(xiàn)的字母變成了其出現(xiàn)次數(shù)以及字母本身铭腕。即5a便是aaaaa银择。如果數(shù)據(jù)里面出現(xiàn)很多類似情況，那么RLE算法將可以節(jié)省很多空間累舷。特別是對于圖像數(shù)據(jù)浩考。
我們有很多種不同的方法可以實現(xiàn)RLE。下面要介紹的方法是通過對Data進行拓展的一個版本被盈，靈感來源于老式的PCX圖像格式
具體規(guī)則如下：
1.對于每一個字節(jié)來說析孽，當某一字節(jié)重復出現(xiàn)多次搭伤，我們用兩個字節(jié)來表示這種情況--第一個字節(jié)記錄這個字節(jié)重復出現(xiàn)的次數(shù)，第二個字節(jié)記錄這個字節(jié)本身袜瞬。第一個字節(jié)表示的格式為：191+count所以這里的count最多只能為64個重復字節(jié)的長度怜俐。（255-191）
2.在區(qū)間0-191的單一字節(jié)，不需要壓縮邓尤，可以直接復制
3.在區(qū)間192-255的單一字節(jié)拍鲤，用兩個字節(jié)來表示，第一個字節(jié)為192汞扎，意思是這個字節(jié)只出現(xiàn)一次季稳，第二個字節(jié)為其真實值，也就是字節(jié)本身澈魄。
以下為壓縮算法的代碼景鼠。算法最后返回的是一個經(jīng)過RLE處理的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
}
代碼解析：
1.使用UnsafePointer來逐一查看原始Data對象的每一個字節(jié)
2.在這個步驟中一忱，我們已經(jīng)讀到當前字節(jié)的數(shù)值莲蜘，并賦值到byte變量里。如果下一個字節(jié)是一樣的帘营，我們會一直繼續(xù)讀取新數(shù)值票渠，直到我們發(fā)現(xiàn)不一樣的新數(shù)值，或者完全所有數(shù)據(jù)讀取芬迄。當前问顷，如果某一字節(jié)重復出現(xiàn)64次，我們也需要停止禀梳，因為這是我們可以進行編碼的最大值杜窄。
3.第三步中，我們需要決定剛剛讀取到的字節(jié)的編碼方式算途。第一種可能性是我們剛剛讀到的字節(jié)塞耕，重復出現(xiàn)次數(shù)大于1次，當然最大值為64嘴瓤。在這種情況我們需要寫出兩個字節(jié)扫外，即長度+字節(jié)本身。 第二種可能性為我們讀取到的字節(jié)大于191廓脆，這種情況也需要用兩個字節(jié)來編碼筛谚。
4.第四步中表示的是第三種可能性，也就是讀取到的字節(jié)小于192.此時我們只需要復制此字節(jié)即可停忿。
我們可以在playground中用以下代碼進行測試：
let originalString = aaaaabbbcdeeeeeeef
let utf8 = originalString.data(using: String.Encoding.utf8)!
let compressed = utf8.compressRLE()
此時被壓縮后的Data對象為<c461c262 6364c665 66>驾讲。解析過程如下：
c4 十進制為196. 表示下一個字節(jié)會重復出現(xiàn)五次
61 表示字節(jié) "a".
c2 下一個字節(jié)重復出現(xiàn)3次.
62 表示字節(jié) "b".
63 表示字節(jié) "c". 因為 < 192, 所以是單一字節(jié).
64 表示字節(jié) "d". 同上，只出現(xiàn)一次.
c6 下一個字節(jié)出現(xiàn)7次.
65 表示字節(jié) "e".
66 表示字節(jié) "f". 只出現(xiàn)一次.
壓縮后的數(shù)據(jù)為9個字節(jié)，而原始數(shù)據(jù)為18個字節(jié)吮铭。節(jié)約了50%时迫。當然，這里只是舉了一個簡單的例子谓晌。如果你剛好非常不幸運别垮，遇到一組原始數(shù)據(jù)沒有任何重復又都大于191，那你可能將會得到一個2倍于原始數(shù)據(jù)的壓縮結(jié)果扎谎。所以，次算法的效率與輸入的原始數(shù)據(jù)相關(guān)性很大烧董。
以下為解壓縮的代碼：
public func decompressRLE() -> Data {
var data = Data()
self.withUnsafeBytes { (uPtr: UnsafePointer<UInt8>) in
var ptr = uPtr
let end = ptr + count
while ptr < end {
// Read the next byte. This is either a single value less than 192,
// or the start of a byte run.
var byte = ptr.pointee // 1
ptr = ptr.advanced(by: 1)
if byte < 192 { // 2
data.append(&byte, count: 1)
} else if ptr < end { // 3
// Read the actual data value.
var value = ptr.pointee
ptr = ptr.advanced(by: 1)
// And write it out repeatedly.
for _ in 0 ..< byte - 191 {
data.append(&value, count: 1)
}
}
}
}
return data
}
代碼解析：
- 再一次利用
UnsafePointer讀取Data毁靶，這里有可能是一個數(shù)值小于192單一字節(jié)，也有可能是下一個字節(jié)需要重復出現(xiàn)的次數(shù)逊移。
2.判斷結(jié)果為單一字節(jié)预吆，直接復制到輸出數(shù)據(jù)里
3.判斷結(jié)果為下一個字節(jié)的出現(xiàn)次數(shù)，立刻讀取下一個字節(jié)的數(shù)值胳泉，并根據(jù)次數(shù)添加到輸出數(shù)據(jù)里
將被壓縮的數(shù)據(jù)還原拐叉，你需要用以下命令：
let decompressed = compressed.decompressRLE()
let restoredString = String(data: decompressed, encoding: NSUTF8StringEncoding)
此時originalString == restoredString返回肯定為true！
