声明：算法和数据结构的文章均是作者从github上翻译过来，为方便大家阅读。如果英语阅读能力强的朋友，可以直接到swift算法俱乐部查看所有原文，以便快速学习。作者同时也在学习中，欢迎交流
在编程过程中，我们可能会遇到某些情况，需要我们压缩数据，而行程编码（RLE）可以说是最简单的压缩算法。假定我们有需要压缩的数据如下：
aaaaabbbcdeeeeeeef...
经过行程编码压缩后：
5a3b1c1d7e1f...
原始数据中，不断重复出现的字母变成了其出现次数以及字母本身。即5a便是aaaaa。如果数据里面出现很多类似情况，那么RLE算法将可以节省很多空间。特别是对于图像数据。
我们有很多种不同的方法可以实现RLE。下面要介绍的方法是通过对Data进行拓展的一个版本，灵感来源于老式的PCX图像格式
具体规则如下：
1.对于每一个字节来说，当某一字节重复出现多次，我们用两个字节来表示这种情况--第一个字节记录这个字节重复出现的次数，第二个字节记录这个字节本身。第一个字节表示的格式为：191+count所以这里的count最多只能为64个重复字节的长度。（255-191）
2.在区间0-191的单一字节，不需要压缩，可以直接复制
3.在区间192-255的单一字节，用两个字节来表示，第一个字节为192，意思是这个字节只出现一次，第二个字节为其真实值，也就是字节本身。
以下为压缩算法的代码。算法最后返回的是一个经过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对象的每一个字节
2.在这个步骤中，我们已经读到当前字节的数值，并赋值到byte变量里。如果下一个字节是一样的，我们会一直继续读取新数值，直到我们发现不一样的新数值，或者完全所有数据读取。当前，如果某一字节重复出现64次，我们也需要停止，因为这是我们可以进行编码的最大值。
3.第三步中，我们需要决定刚刚读取到的字节的编码方式。第一种可能性是我们刚刚读到的字节，重复出现次数大于1次，当然最大值为64。在这种情况我们需要写出两个字节，即长度+字节本身。 第二种可能性为我们读取到的字节大于191，这种情况也需要用两个字节来编码。
4.第四步中表示的是第三种可能性，也就是读取到的字节小于192.此时我们只需要复制此字节即可。
我们可以在playground中用以下代码进行测试：
let originalString = aaaaabbbcdeeeeeeef
let utf8 = originalString.data(using: String.Encoding.utf8)!
let compressed = utf8.compressRLE()
此时被压缩后的Data对象为<c461c262 6364c665 66>。解析过程如下：
c4 十进制为196. 表示下一个字节会重复出现五次
61 表示字节 "a".
c2 下一个字节重复出现3次.
62 表示字节 "b".
63 表示字节 "c". 因为 < 192, 所以是单一字节.
64 表示字节 "d". 同上，只出现一次.
c6 下一个字节出现7次.
65 表示字节 "e".
66 表示字节 "f". 只出现一次.
压缩后的数据为9个字节，而原始数据为18个字节。节约了50%。当然，这里只是举了一个简单的例子。如果你刚好非常不幸运，遇到一组原始数据没有任何重复又都大于191，那你可能将会得到一个2倍于原始数据的压缩结果。所以，次算法的效率与输入的原始数据相关性很大。
以下为解压缩的代码：
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，这里有可能是一个数值小于192单一字节，也有可能是下一个字节需要重复出现的次数。
2.判断结果为单一字节，直接复制到输出数据里
3.判断结果为下一个字节的出现次数，立刻读取下一个字节的数值，并根据次数添加到输出数据里
将被压缩的数据还原，你需要用以下命令：
let decompressed = compressed.decompressRLE()
let restoredString = String(data: decompressed, encoding: NSUTF8StringEncoding)
此时originalString == restoredString返回肯定为true！
网友评论