LZW

这个项目的目的是为了让我 (jjrscott) 了解 LZW 的工作原理。在构建此项目时，我意识到最初描述的 LZW 算法包含两个不同的部分：

  1. 将字符编码为字母表并预先填充前缀表，
  2. （通常认为是 LZW 的部分）扩展前缀表并将表索引编码为输出流。

我可以使用 Swift 的 enum 来抽象掉预填充字符串表/字母表的需要，从而以更纯粹的形式揭示该算法。

Rosetta Code

来自 Rosetta Code

Lempel-Ziv-Welch (LZW) 算法提供无损数据压缩。

您可以在 Wikipedia 文章中阅读其完整描述。它曾被授予专利，但在 2004 年进入公共领域。

经典示例

由于某种原因，所有演示都使用 TOBEORNOTTOBEORTOBEORNOT 作为输入字符串。 以下示例接受一个字符串并生成一个整数数组，就像原始演示一样。

import LZW

let original = "TOBEORNOTTOBEORTOBEORNOT"

let compressed = LZW.compress(original.utf8.map({$0}))

print("compressed: \(compressed)")

let encoded = compressed.map { unit in
    switch unit {
    case .element(let value):
        return UInt(value)
    case .index(let index):
        return UInt(UInt8.max) + UInt(index)
    }
}

print("encoded: \(encoded)")

输出

compressed: [.element(84), .element(79), .element(66), .element(69), .element(79),
             .element(82), .element(78), .element(79), .element(84), .index(0),
             .index(2), .index(4), .index(9), .index(3), .index(5), .index(7)]
encoded: [84, 79, 66, 69, 79, 82, 78, 79, 84, 256, 258, 260, 265, 259, 261, 263]

算法

一种高性能数据压缩技术:

Initialize table to contain single-character strings
Read first input character K:
        K → prefix string ω;
Step: Read next input character K
         If no such K (input exhausted):
                    code(ω) → output;
                    EXIT.
         If ωK exists in string table:
                    ωK → ω;
                    repeat Step.
         else ωK not in string table:
                    code(ω) → output;
                    ωK → string table;
                    K → ω;
                    repeat Step.