LZ77算法 - 元素码农

发布时间: 2025-03-21 20:06

↑

# LZ77算法

LZ77（Lempel-Ziv 1977）是一种经典的无损数据压缩算法，它通过在输入数据流中查找重复出现的字符串来实现压缩。该算法是许多现代压缩技术的基础，如DEFLATE（ZIP、gzip）等。

## 基本概念

### 滑动窗口

LZ77的核心概念是滑动窗口，它包含两个部分：
- 搜索缓冲区（已编码的数据）
- 前视缓冲区（待编码的数据）

### 编码方式

每个匹配用三元组表示：(offset, length, next)
- offset：匹配串在搜索缓冲区中的位置
- length：匹配的长度
- next：未匹配的下一个字符

## 实现原理

### 基本实现

```go
// LZ77编码器
type LZ77Encoder struct {
    searchSize    int  // 搜索缓冲区大小
    lookAheadSize int  // 前视缓冲区大小
    minMatch      int  // 最小匹配长度
}

// 创建新的LZ77编码器
func NewLZ77Encoder(searchSize, lookAheadSize, minMatch int) *LZ77Encoder {
    return &LZ77Encoder{
        searchSize:    searchSize,
        lookAheadSize: lookAheadSize,
        minMatch:      minMatch,
    }
}

// 编码结果
type Token struct {
    Offset int
    Length int
    Next   byte
}

// 编码
func (lz *LZ77Encoder) Encode(data []byte) []Token {
    result := make([]Token, 0)
    pos := 0
    
    for pos < len(data) {
        // 计算当前窗口范围
        searchStart := max(0, pos-lz.searchSize)
        lookAheadEnd := min(pos+lz.lookAheadSize, len(data))
        
        // 在搜索缓冲区中查找最长匹配
        maxLength := 0
        maxOffset := 0
        
        for i := searchStart; i < pos; i++ {
            length := 0
            for j := 0; j < lookAheadEnd-pos; j++ {
                if i+j < pos && data[i+j] == data[pos+j] {
                    length++
                } else {
                    break
                }
            }
            
            if length > maxLength {
                maxLength = length
                maxOffset = pos - i
            }
        }
        
        // 生成编码token
        if maxLength >= lz.minMatch {
            next := byte(0)
            if pos+maxLength < len(data) {
                next = data[pos+maxLength]
            }
            result = append(result, Token{
                Offset: maxOffset,
                Length: maxLength,
                Next:   next,
            })
            pos += maxLength + 1
        } else {
            result = append(result, Token{
                Offset: 0,
                Length: 0,
                Next:   data[pos],
            })
            pos++
        }
    }
    
    return result
}

// 解码
func (lz *LZ77Encoder) Decode(tokens []Token) []byte {
    result := make([]byte, 0)
    
    for _, token := range tokens {
        if token.Length > 0 {
            start := len(result) - token.Offset
            for i := 0; i < token.Length; i++ {
                result = append(result, result[start+i])
            }
        }
        if token.Next != 0 {
            result = append(result, token.Next)
        }
    }
    
    return result
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}
```

### 优化实现

```go
// 优化的LZ77编码器
type OptimizedLZ77 struct {
    encoder    *LZ77Encoder
    hashTable  map[string][]int  // 哈希表加速匹配查找
    hashSize   int              // 哈希长度
}

// 创建优化的编码器
func NewOptimizedLZ77(searchSize, lookAheadSize, minMatch, hashSize int) *OptimizedLZ77 {
    return &OptimizedLZ77{
        encoder:   NewLZ77Encoder(searchSize, lookAheadSize, minMatch),
        hashTable: make(map[string][]int),
        hashSize:  hashSize,
    }
}

// 更新哈希表
func (olz *OptimizedLZ77) updateHash(data []byte, pos int) {
    if pos+olz.hashSize <= len(data) {
        hash := string(data[pos:pos+olz.hashSize])
        olz.hashTable[hash] = append(olz.hashTable[hash], pos)
    }
}

// 优化的编码过程
func (olz *OptimizedLZ77) Encode(data []byte) []Token {
    result := make([]Token, 0)
    pos := 0
    
    // 初始化哈希表
    for i := 0; i < len(data)-olz.hashSize+1; i++ {
        olz.updateHash(data, i)
    }
    
    for pos < len(data) {
        // 使用哈希表查找潜在匹配
        maxLength := 0
        maxOffset := 0
        
        if pos+olz.hashSize <= len(data) {
            hash := string(data[pos:pos+olz.hashSize])
            if positions, ok := olz.hashTable[hash]; ok {
                searchStart := max(0, pos-olz.encoder.searchSize)
                
                for _, start := range positions {
                    if start >= pos || start < searchStart {
                        continue
                    }
                    
                    length := 0
                    for pos+length < len(data) && 
                        start+length < pos && 
                        data[start+length] == data[pos+length] {
                        length++
                    }
                    
                    if length > maxLength {
                        maxLength = length
                        maxOffset = pos - start
                    }
                }
            }
        }
        
        // 生成编码token
        if maxLength >= olz.encoder.minMatch {
            next := byte(0)
            if pos+maxLength < len(data) {
                next = data[pos+maxLength]
            }
            result = append(result, Token{
                Offset: maxOffset,
                Length: maxLength,
                Next:   next,
            })
            pos += maxLength + 1
        } else {
            result = append(result, Token{
                Offset: 0,
                Length: 0,
                Next:   data[pos],
            })
            pos++
        }
    }
    
    return result
}
```

## 应用场景

### 文件压缩

```go
// 文件压缩器
type FileCompressor struct {
    lz77     *OptimizedLZ77
    blockSize int
}

// 压缩文件
func (fc *FileCompressor) CompressFile(input []byte) []byte {
    // 分块处理大文件
    result := make([]byte, 0)
    for i := 0; i < len(input); i += fc.blockSize {
        end := min(i+fc.blockSize, len(input))
        block := input[i:end]
        
        // 压缩当前块
        tokens := fc.lz77.Encode(block)
        
        // 序列化tokens
        for _, token := range tokens {
            // 写入offset（2字节）
            result = append(result, byte(token.Offset>>8))
            result = append(result, byte(token.Offset))
            
            // 写入length（1字节）
            result = append(result, byte(token.Length))
            
            // 写入next
            result = append(result, token.Next)
        }
    }
    
    return result
}
```

### 网络传输

```go
// 流式压缩器
type StreamCompressor struct {
    lz77      *OptimizedLZ77
    buffer    []byte
    maxBuffer int
}

// 处理数据流
func (sc *StreamCompressor) Process(data []byte) []byte {
    // 添加到缓冲区
    sc.buffer = append(sc.buffer, data...)
    
    // 当缓冲区足够大时进行压缩
    if len(sc.buffer) >= sc.maxBuffer {
        result := sc.lz77.Encode(sc.buffer)
        sc.buffer = sc.buffer[len(sc.buffer)-sc.lz77.encoder.searchSize:]
        return serializeTokens(result)
    }
    
    return nil
}
```

## 性能分析

### 时间复杂度

1. 基本实现
   - 编码：O(n*w)，n为数据长度，w为窗口大小
   - 解码：O(n)

2. 优化实现
   - 编码：平均O(n)，最坏O(n*w)
   - 解码：O(n)
   - 哈希表维护：O(n)

### 空间复杂度

1. 基本数据结构
   - 滑动窗口：O(w)
   - 输出缓冲：O(n)

2. 优化结构
   - 哈希表：O(n)
   - 临时缓冲：O(w)

### 压缩率

1. 影响因素
   - 窗口大小
   - 数据重复性
   - 最小匹配长度

2. 典型压缩率
   - 文本文件：20%-50%
   - 二进制文件：30%-70%
   - 图像文件：5%-15%

## 实践建议

### 参数选择

1. 窗口大小
   - 较小：更快的压缩速度
   - 较大：更好的压缩率
   - 推荐：4KB-32KB

2. 最小匹配长度
   - 较小：更好的压缩率
   - 较大：更快的压缩速度
   - 推荐：3-4字节

### 优化技巧

1. 实现优化
   - 使用哈希表
   - 并行处理
   - 缓存优化

2. 应用优化
   - 分块处理
   - 自适应参数
   - 混合压缩

## 总结

1. 优点
   - 实现简单
   - 解码快速
   - 压缩效果好

2. 缺点
   - 编码较慢
   - 内存占用大
   - 压缩率受限

3. 适用场景
   - 通用压缩
   - 流式处理
   - 实时压缩