BigIntCompress

一种算法，旨在压缩每个元素只有少数可能值的大型集合。例如，可以用 enum 表示的类型。

它的灵感来源于生物信息学领域，该领域中，庞大的集合通常被压缩成各种格式，但没有利用其组成部分只有极少数可能值这一事实，例如，DNA 的核苷酸只有四种：A、C、G 和 T。

算法

public func encode() -> Data? {
    var number: CompressionNumber = 0

    for element in self {
        number = number * Self.maxUniqueComponentCount + Self.compressionNumberValue(for: element)
    }

    let string = number.hexString

    let mutableData = NSMutableData()

    var i = 0
    while i < (string.count - 1) {
        if let byte = string.getHexByte(startIndex: i, endIndex: i+2) {
            mutableData.append(Data(repeating: byte, count: 1))
        }
        i += 2
    }
    if string.count % 2 == 1,
        let byte = string.getHexByte(startIndex: string.count-1, endIndex: string.count) {

        mutableData.append(Data(repeating: byte, count: 1))
    }

    let finalData = NSMutableData()

    var count = self.count
    let countData = Data(bytes: &count,
                         count: sizeOfInt)

    finalData.append(countData)
    finalData.append(mutableData as Data)
    return finalData as Data
}

如何使用

Swift 包管理器

.package(url: "https://github.com/valdirunars/BigIntCompress.git", from: "1.0.0"),

使你的集合 Compressable

首先，我们必须找到一个大整数类型，并使其符合 BigIntCompress 的 BigIntType 协议。市面上有很多优秀的 Swift 库可以做到这一点。我通常使用 BigInt

extension BigInt: BigIntType {

    public var hexString: String {
        return String(self, radix: 16)
    }

    public init?(hexString: String) {
        self.init(hexString, radix: 16)
    }

    public init<T>(_ value: T) where T : Numeric {
        self.init(value)
    }
}

太棒了！现在我们准备好成为 Compressable 了。假设我们正在处理字符串，其中每个字符的可能值是 A、C、G 和 T，就像 DNA 的核苷酸的情况一样。

extension String: Compressable {
    public typealias CompressionNumber = BigInt

    public static var possibleComponents: [Element] {
        return [ "A", "C", "G", "T" ]
    }

    public static func single(_ element: Element) -> String {
        return "\(element)"
    }
}

现在 String 有了两个新的属性。一个用于解码的静态变量 bic 和一个用于编码的同名实例变量。

编码和解码

let expected = """
CCAAGGATTTCCAAGGATTTTTCTCCACTGTTCTCCACTGTTCTCCACTGACAACCCTGGCCACGTATTCTCCACTGGCCACGTAACAACCCTGGCCACGTACCAAGGATTTGGACGGCTCCCCAAGGATTTGGACGGCTCCGCCACGTAGCCACGTATTCTCCACTGACAACCCTGACAACCCTGGCCACGTAGGACGGCTCCACAACCCTGCCAAGGATTTTTCTCCACTGGCCACGTATTCTCCACTGGGACGGCTCCGGACGGCTCCCCAAGGATTTGCCACGTATTCTCCACTGGGACGGCTCCGCCACGTAGGACGGCTCCGGACGGCTCCCCAAGGATTTTTCTCCACTGGGACGGCTCCTTCTCCACTGCCAAGGATTTCCAAGGATTTGCCACGTACCAAGGATTTGGACGGCTCCGCCACGTAGCCACGTACCAAGGATTTCCAAGGATTTGGACGGCTCCTTCTCCACTGTTCTCCACTGCCAAGGATTTTTCTCCACTGGGACGGCTCCACAACCCTGGGACGGCTCCACAACCCTGTTCTCCACTGTTCTCCACTGTTCTCCACTGCCAAGGATTTGGACGGCTCCCCAAGGATTTTTCTCCACTGTTCTCCACTGGGACGGCTCCGCCACGTAGGACGGCTCCACAACCCTGTTCTCCACTGGCCACGTAGCCACGTAACAACCCTGGCCACGTAACAACCCTGCCAAGGATTTCCAAGGATTTCCAAGGATTTACAACCCTGGCCACGTAGGACGGCTCCGCCACGTATTCTCCACTGGCCACGTAACAACCCTGGCCACGTAACAACCCTGGCCACGTAGCCACGTAGCCACGTATTCTCCACTGGGACGGCTCCCCAAGGATTTGCCACGTAGGACGGCTCCTTCTCCACTGGGACGGCTCCGCCACGTAACAACCCTGTTCTCCACTGGCCACGTACCAAGGATTTCCAAGGATTTGGACGGCTCCCCAAGG
"""

let compressed = expected.bic.encode()
let back = try! String.bic.decode(compressed!)!

XCTAssert(back == expected)

性能

let asciiData: Data! = expected.data(using: .ascii)
XCTAssert(compressed.count * 3 < asciiData.count)

缺点

该算法在某种意义上是有损的，因为它主要关注集合的对象，因此会丢失这些集合的元数据。BigIntCompress 可以实现为支持将元数据附加到压缩数据，事实上这已在我的 TODO 列表中。

但就目前而言，它仅适用于压缩“原始”数据格式