1、LZＷ算法的基本概念
LZW有三个重要对象：数据流(CharStream)、编码流(String Table)和编译表(String Table)。
(1)编码时，数据流是输入对象 (数据序列)，编码流就是输出对象(经过压缩运算的编码数据)；
(2)解码时，编码流是输入对象，数据流是输出对象；而编译表是在编码和解码时都需要借助的对象。
2、LZW压缩的基本原理
提取原始文本文件数据中的不同字符，基于这些字符创建一个编译表，然后用编译表中的字符的索引来替代原始数据中的相应字符，减少原始数据大小。注意：此处的编译表是根据原始数据动态创建的，解码时需要从已编码的数据中还原出原来的编译表。
3、LZW算法流程
步骤一：开始时词典包含所有可能的根，当前前缀字符串P和 当前字符 均为空；
步骤二：读入新的字符C，与P合并形成字符串P+C；
步骤三：判断P+C是否在字典中
如果"是"：
P = P + C；
返回步骤二；
如果"否"：
输出P的映射；
P = P+C ；
把前缀字符串P添加到字典，建立映射;
令P = C //(现在的P仅包含一个字符C);
步骤四： 判断码字流中是否还有码字要译
如果"是"：
返回步骤二；
如果"否"：
把代表当前前缀P的码字输出到码字流;
结束。
实现代码：
package main
import "fmt"
func compressLZW(testStr string) []int {
code := 256
dictionary := make(map[string]int)
for i := 0; i < 256; i++ {
dictionary[string(i)] = i
}
currChar := ""
result := make([]int, 0)
for _, c := range []byte(testStr) {
phrase := currChar + string(c)
if _, isTrue := dictionary[phrase]; isTrue {
currChar = phrase
} else {
result = append(result, dictionary[currChar])
dictionary[phrase] = code
code++
currChar = string(c)
}
}
if currChar != "" {
result = append(result, dictionary[currChar])
}
return result
}
func decompressLZW(compressed []int) string {
code := 256
dictionary := make(map[int]string)
for i := 0; i < 256; i++ {
dictionary[i] = string(i)
}
currChar := string(compressed[0])
result := currChar
for _, element := range compressed[1:] {
var word string
if x, ok := dictionary[element]; ok {
word = x
} else if element == code {
word = currChar + currChar[:1]
} else {
panic(fmt.Sprintf("Bad compressed element: %d", element))
}
result += word
dictionary[code] = currChar + word[:1]
code++
currChar = word
}
return result
}
func main() {
fmt.Print("Enter any string :")
var testStr string
fmt.Scanln(&testStr)
compressed := compressLZW(testStr)
fmt.Println("\nAfter Compression :", compressed)
uncompression := decompressLZW(compressed)
fmt.Println("\nAfter Uncompression :", uncompression)
}
输出：
Enter any string :Australia
After Compression : [65 117 115 116 114 97 108 105 97]
After Uncompression : Australia
C:\golang\example>go run test.go
Enter any string :Germany
After Compression : [71 101 114 109 97 110 121]
After Uncompression : Germany