Go index/suffixarray 包详解

概述

index/suffixarray 包实现了一个后缀数组（Suffix Array），用于高效的字符串搜索。后缀数组是一种数据结构，通过对字符串的所有后缀进行排序来构建，支持在 O(m log n) 时间复杂度内完成模式匹配（m 为模式长度，n 为文本长度）。该包提供了 Index 类型和 New、Load、Save 等函数，广泛用于文本搜索、生物信息学和数据压缩领域。

包导入

import "index/suffixarray"

基本使用

1. 创建后缀数组

package main

import (
    "fmt"
    "index/suffixarray"
)

func main() {
    // 从字节切片创建后缀数组
    data := []byte("banana")
    index := suffixarray.New(data)
    
    fmt.Println("后缀数组创建成功")
}

2. 搜索模式

package main

import (
    "fmt"
    "index/suffixarray"
)

func main() {
    text := []byte("banana")
    index := suffixarray.New(text)
    
    // 查找所有 "ana" 出现的位置
    positions := index.Lookup([]byte("ana"), -1)
    
    fmt.Printf("找到位置：%v\n", positions)
    // 输出：找到位置：[1 3]
}

3. 保存和加载后缀数组

package main

import (
    "bytes"
    "fmt"
    "index/suffixarray"
)

func main() {
    // 创建后缀数组
    data := []byte("hello world")
    index := suffixarray.New(data)
    
    // 保存到缓冲区
    var buf bytes.Buffer
    index.Save(&buf)
    
    // 从缓冲区加载
    loadedIndex, err := suffixarray.Load(&buf)
    if err != nil {
        panic(err)
    }
    
    // 使用加载的索引搜索
    positions := loadedIndex.Lookup([]byte("world"), -1)
    fmt.Printf("找到位置：%v\n", positions)
}

一、核心函数

New

定义：

func New(data []byte) *Index

说明：

• 功能：从字节切片创建新的后缀数组索引
• 参数：data - 要索引的字节切片（文本数据）
• 返回值：*Index - 后缀数组索引指针
• 时间复杂度：O(n log n)，其中 n 为数据长度
• 空间复杂度：O(n)

示例：

package main

import (
    "fmt"
    "index/suffixarray"
)

func main() {
    // 示例 1：简单文本
    text1 := []byte("banana")
    index1 := suffixarray.New(text1)
    
    // 查找 "an"
    pos1 := index1.Lookup([]byte("an"), -1)
    fmt.Printf("'an' 在 '%s' 中的位置：%v\n", text1, pos1)
    // 输出：'an' 在 'banana' 中的位置：[1 3]
    
    // 示例 2：较长文本
    text2 := []byte("mississippi")
    index2 := suffixarray.New(text2)
    
    // 查找 "iss"
    pos2 := index2.Lookup([]byte("iss"), -1)
    fmt.Printf("'iss' 在 '%s' 中的位置：%v\n", text2, pos2)
    // 输出：'iss' 在 'mississippi' 中的位置：[1 4]
    
    // 示例 3：中文文本（UTF-8 编码）
    text3 := []byte("你好世界你好")
    index3 := suffixarray.New(text3)
    
    // 查找 "你好"
    pos3 := index3.Lookup([]byte("你好"), -1)
    fmt.Printf("'你好' 的位置：%v\n", pos3)
    // 输出：'你好' 的位置：[0 12]
}

Load

定义：

func Load(r io.Reader) (*Index, error)

说明：

• 功能：从读取器加载后缀数组索引
• 参数：r - io.Reader（如文件、字节流）
• 返回值：
  • *Index - 加载的后缀数组索引
  • error - 错误信息
• 用途：从持久化存储中恢复索引，避免重复构建
• 格式：使用 Save 方法保存的二进制格式

示例：

package main

import (
    "fmt"
    "index/suffixarray"
    "os"
)

func loadFromFile(filename string) (*suffixarray.Index, error) {
    file, err := os.Open(filename)
    if err != nil {
        return nil, err
    }
    defer file.Close()
    
    return suffixarray.Load(file)
}

func main() {
    // 从文件加载索引
    index, err := loadFromFile("index.dat")
    if err != nil {
        fmt.Println("加载失败:", err)
        return
    }
    
    // 使用加载的索引搜索
    positions := index.Lookup([]byte("search"), -1)
    fmt.Printf("找到位置：%v\n", positions)
}

Save

定义：

func (x *Index) Save(w io.Writer) error

说明：

• 功能：将后缀数组索引保存到写入器
• 接收者：x *Index - 后缀数组索引
• 参数：w - io.Writer（如文件、字节流）
• 返回值：error - 错误信息
• 用途：持久化存储索引，便于后续加载使用
• 格式：二进制格式，与 Load 配合使用

示例：

package main

import (
    "fmt"
    "index/suffixarray"
    "os"
)

func saveToFile(filename string, index *suffixarray.Index) error {
    file, err := os.Create(filename)
    if err != nil {
        return err
    }
    defer file.Close()
    
    return index.Save(file)
}

func main() {
    // 创建索引
    data := []byte("large text data...")
    index := suffixarray.New(data)
    
    // 保存到文件
    err := saveToFile("index.dat", index)
    if err != nil {
        fmt.Println("保存失败:", err)
        return
    }
    
    fmt.Println("索引已保存")
}

二、结构体

Index

定义：

type Index struct {
    // 包含未导出的字段
}

说明：

• 功能：后缀数组索引结构
• 字段：所有字段均为未导出（内部实现）
• 用途：提供高效的字符串搜索功能
• 构建成本：O(n log n) 时间，O(n) 空间
• 搜索成本：O(m log n) 时间，其中 m 为模式长度

方法总览：

示例 - 完整使用流程：

package main

import (
    "bytes"
    "fmt"
    "index/suffixarray"
)

func main() {
    // 步骤 1：准备文本数据
    text := []byte("The quick brown fox jumps over the lazy dog")
    
    // 步骤 2：创建后缀数组
    index := suffixarray.New(text)
    
    // 步骤 3：搜索模式
    pattern := []byte("the")
    positions := index.Lookup(pattern, -1)
    
    fmt.Printf("文本：%s\n", text)
    fmt.Printf("模式：%s\n", pattern)
    fmt.Printf("位置：%v\n", positions)
    
    // 步骤 4：显示匹配的上下文
    for _, pos := range positions {
        end := pos + len(pattern)
        if end > len(text) {
            end = len(text)
        }
        fmt.Printf("  位置 %d: ...%s...\n", pos, text[pos:end])
    }
    
    // 步骤 5：保存索引
    var buf bytes.Buffer
    index.Save(&buf)
    fmt.Printf("索引已保存：%d 字节\n", buf.Len())
    
    // 步骤 6：加载索引
    loadedIndex, _ := suffixarray.Load(&buf)
    positions2 := loadedIndex.Lookup(pattern, -1)
    fmt.Printf("加载后搜索：%v\n", positions2)
}

三、方法

Lookup

定义：

func (x *Index) Lookup(pattern []byte, limit int) []int

说明：

• 功能：查找模式在文本中的所有出现位置
• 接收者：x *Index - 后缀数组索引
• 参数：
  • pattern - 要搜索的模式（字节切片）
  • limit - 最大返回结果数（-1 表示无限制）
• 返回值：[]int - 按升序排列的位置索引数组
• 时间复杂度：O(m log n)，其中 m 为模式长度，n 为文本长度
• 返回值特点：位置索引按升序排列

参数详解：

示例 - 基本搜索：

package main

import (
    "fmt"
    "index/suffixarray"
)

func main() {
    text := []byte("banana")
    index := suffixarray.New(text)
    
    // 示例 1：查找所有 "an"
    pos1 := index.Lookup([]byte("an"), -1)
    fmt.Printf("'an' 的位置：%v\n", pos1)
    // 输出：'an' 的位置：[1 3]
    
    // 示例 2：限制结果数量
    pos2 := index.Lookup([]byte("a"), 1)
    fmt.Printf("'a' 的位置（限制 1 个）：%v\n", pos2)
    // 输出：'a' 的位置（限制 1 个）：[0]
    
    // 示例 3：不存在的模式
    pos3 := index.Lookup([]byte("xyz"), -1)
    fmt.Printf("'xyz' 的位置：%v\n", pos3)
    // 输出：'xyz' 的位置：[]
    
    // 示例 4：空模式
    pos4 := index.Lookup([]byte(""), -1)
    fmt.Printf("空模式的位置：%v\n", pos4)
    // 输出：空模式的位置：[0 1 2 3 4 5 6]
}

示例 - 限制结果数量：

package main

import (
    "fmt"
    "index/suffixarray"
)

func main() {
    text := []byte("abracadabra")
    index := suffixarray.New(text)
    
    // 查找所有 "a"
    all := index.Lookup([]byte("a"), -1)
    fmt.Printf("所有 'a' 的位置：%v\n", all)
    // 输出：所有 'a' 的位置：[0 3 5 7 10]
    
    // 只查找前 2 个
    limited := index.Lookup([]byte("a"), 2)
    fmt.Printf("前 2 个 'a' 的位置：%v\n", limited)
    // 输出：前 2 个 'a' 的位置：[0 3]
    
    // 只查找第 1 个
    first := index.Lookup([]byte("a"), 1)
    fmt.Printf("第 1 个 'a' 的位置：%v\n", first)
    // 输出：第 1 个 'a' 的位置：[0]
}

示例 - 实际应用场景：

package main

import (
    "fmt"
    "index/suffixarray"
    "strings"
)

// FindAllOccurrences 查找所有出现位置及上下文
func FindAllOccurrences(text, pattern string, contextSize int) {
    index := suffixarray.New([]byte(text))
    positions := index.Lookup([]byte(pattern), -1)
    
    fmt.Printf("在文本中查找 '%s'\n", pattern)
    fmt.Printf("找到 %d 处匹配:\n", len(positions))
    
    for i, pos := range positions {
        // 计算上下文范围
        start := pos - contextSize
        end := pos + len(pattern) + contextSize
        
        if start < 0 {
            start = 0
        }
        if end > len(text) {
            end = len(text)
        }
        
        // 提取上下文
        context := text[start:end]
        
        // 标记匹配位置
        markerPos := pos - start
        
        fmt.Printf("%2d. 位置 %d: ...%s...\n", i+1, pos, context)
        fmt.Printf("    %s\n", strings.Repeat(" ", markerPos)+"^")
    }
}

func main() {
    text := `Go is an open source programming language that makes it easy to build 
    simple, reliable, and efficient software. Go's standard library is well-designed 
    and provides many useful packages.`
    
    pattern := "Go"
    
    FindAllOccurrences(text, pattern, 10)
}

四、典型示例

示例 1：文本搜索引擎

package main

import (
    "fmt"
    "index/suffixarray"
    "os"
    "strings"
)

// TextSearcher 文本搜索器
type TextSearcher struct {
    text  string
    index *suffixarray.Index
}

// NewTextSearcher 创建文本搜索器
func NewTextSearcher(text string) *TextSearcher {
    return &TextSearcher{
        text:  text,
        index: suffixarray.New([]byte(text)),
    }
}

// Search 搜索文本
func (ts *TextSearcher) Search(pattern string, limit int) []Result {
    positions := ts.index.Lookup([]byte(pattern), limit)
    
    results := make([]Result, len(positions))
    for i, pos := range positions {
        results[i] = Result{
            Position: pos,
            Context:  ts.getContext(pos, len(pattern)),
        }
    }
    
    return results
}

// getContext 获取上下文
func (ts *TextSearcher) getContext(pos int, patternLen int) string {
    contextSize := 50
    start := pos - contextSize
    end := pos + patternLen + contextSize
    
    if start < 0 {
        start = 0
    }
    if end > len(ts.text) {
        end = len(ts.text)
    }
    
    context := ts.text[start:end]
    
    // 添加省略号
    if start > 0 {
        context = "..." + context
    }
    if end < len(ts.text) {
        context = context + "..."
    }
    
    return context
}

// Result 搜索结果
type Result struct {
    Position int
    Context  string
}

func main() {
    // 读取大文本文件
    content, err := os.ReadFile("large_text.txt")
    if err != nil {
        panic(err)
    }
    
    text := string(content)
    
    // 创建搜索器
    searcher := NewTextSearcher(text)
    
    // 搜索
    pattern := "algorithm"
    results := searcher.Search(pattern, 10)
    
    fmt.Printf("搜索 '%s' 的结果:\n\n", pattern)
    for i, result := range results {
        fmt.Printf("%d. 位置：%d\n", i+1, result.Position)
        fmt.Printf("   上下文：%s\n\n", result.Context)
    }
}

示例 2：DNA 序列分析

package main

import (
    "fmt"
    "index/suffixarray"
)

// DNAAnalyzer DNA 序列分析器
type DNAAnalyzer struct {
    sequence string
    index    *suffixarray.Index
}

// NewDNAAnalyzer 创建 DNA 分析器
func NewDNAAnalyzer(sequence string) *DNAAnalyzer {
    return &DNAAnalyzer{
        sequence: sequence,
        index:    suffixarray.New([]byte(sequence)),
    }
}

// FindMotif 查找基序（motif）
func (da *DNAAnalyzer) FindMotif(motif string) []int {
    return da.index.Lookup([]byte(motif), -1)
}

// CountMotif 统计基序出现次数
func (da *DNAAnalyzer) CountMotif(motif string) int {
    positions := da.FindMotif(motif)
    return len(positions)
}

// FindRepeatedPatterns 查找重复模式
func (da *DNAAnalyzer) FindRepeatedPatterns(minLength int, minOccurrences int) []PatternInfo {
    var results []PatternInfo
    
    // 尝试不同长度的模式
    for length := minLength; length <= 20; length++ {
        for i := 0; i <= len(da.sequence)-length; i++ {
            pattern := da.sequence[i : i+length]
            count := da.CountMotif(pattern)
            
            if count >= minOccurrences {
                // 检查是否已记录
                exists := false
                for _, r := range results {
                    if r.Pattern == pattern {
                        exists = true
                        break
                    }
                }
                
                if !exists {
                    results = append(results, PatternInfo{
                        Pattern:     pattern,
                        Length:      length,
                        Occurrences: count,
                        Positions:   da.FindMotif(pattern),
                    })
                }
            }
        }
    }
    
    return results
}

// PatternInfo 模式信息
type PatternInfo struct {
    Pattern     string
    Length      int
    Occurrences int
    Positions   []int
}

func main() {
    // DNA 序列示例
    dna := "ATCGATCGATCGATCGATCGATCG"
    
    analyzer := NewDNAAnalyzer(dna)
    
    // 查找特定基序
    motif := "ATCG"
    positions := analyzer.FindMotif(motif)
    fmt.Printf("基序 '%s' 出现位置：%v\n", motif, positions)
    fmt.Printf("出现次数：%d\n\n", analyzer.CountMotif(motif))
    
    // 查找重复模式
    fmt.Println("重复模式（长度>=4，出现>=3 次）:")
    patterns := analyzer.FindRepeatedPatterns(4, 3)
    for _, p := range patterns {
        fmt.Printf("模式：%s, 长度：%d, 出现：%d次\n",
            p.Pattern, p.Length, p.Occurrences)
    }
}

示例 3：日志文件索引

package main

import (
    "fmt"
    "index/suffixarray"
    "os"
    "strings"
)

// LogIndex 日志索引
type LogIndex struct {
    content string
    index   *suffixarray.Index
    lines   []int // 每行的起始位置
}

// NewLogIndex 创建日志索引
func NewLogIndex(filename string) (*LogIndex, error) {
    // 读取文件
    data, err := os.ReadFile(filename)
    if err != nil {
        return nil, err
    }
    
    content := string(data)
    
    // 创建后缀数组
    index := suffixarray.New([]byte(content))
    
    // 记录每行的起始位置
    lines := []int{0}
    for i := 0; i < len(content); i++ {
        if content[i] == '\n' {
            lines = append(lines, i+1)
        }
    }
    
    return &LogIndex{
        content: content,
        index:   index,
        lines:   lines,
    }, nil
}

// Search 搜索日志
func (li *LogIndex) Search(keyword string) []LogMatch {
    positions := li.index.Lookup([]byte(keyword), -1)
    
    matches := make([]LogMatch, len(positions))
    for i, pos := range positions {
        lineNum := li.getLineNumber(pos)
        line := li.getLine(lineNum)
        
        matches[i] = LogMatch{
            LineNumber: lineNum,
            Line:       line,
            Position:   pos,
        }
    }
    
    return matches
}

// getLineNumber 获取行号
func (li *LogIndex) getLineNumber(pos int) int {
    // 二分查找确定行号
    for i := len(li.lines) - 1; i >= 0; i-- {
        if pos >= li.lines[i] {
            return i + 1
        }
    }
    return 1
}

// getLine 获取行内容
func (li *LogIndex) getLine(lineNum int) string {
    if lineNum < 1 || lineNum > len(li.lines) {
        return ""
    }
    
    start := li.lines[lineNum-1]
    end := len(li.content)
    
    if lineNum < len(li.lines) {
        end = li.lines[lineNum] - 1
    }
    
    return strings.TrimSpace(li.content[start:end])
}

// LogMatch 日志匹配
type LogMatch struct {
    LineNumber int
    Line       string
    Position   int
}

func main() {
    // 创建日志索引
    logIndex, err := NewLogIndex("app.log")
    if err != nil {
        panic(err)
    }
    
    // 搜索错误
    keyword := "ERROR"
    matches := logIndex.Search(keyword)
    
    fmt.Printf("搜索 '%s' 找到 %d 处匹配:\n\n", keyword, len(matches))
    for _, match := range matches {
        fmt.Printf("第 %d 行：%s\n", match.LineNumber, match.Line)
    }
}

示例 4：代码片段搜索工具

package main

import (
    "fmt"
    "index/suffixarray"
    "io/fs"
    "os"
    "path/filepath"
)

// CodeSearcher 代码搜索器
type CodeSearcher struct {
    files map[string]*suffixarray.Index
}

// NewCodeSearcher 创建代码搜索器
func NewCodeSearcher() *CodeSearcher {
    return &CodeSearcher{
        files: make(map[string]*suffixarray.Index),
    }
}

// IndexFile 索引单个文件
func (cs *CodeSearcher) IndexFile(filename string) error {
    data, err := os.ReadFile(filename)
    if err != nil {
        return err
    }
    
    cs.files[filename] = suffixarray.New(data)
    return nil
}

// IndexDirectory 索引目录
func (cs *CodeSearcher) IndexDirectory(dir string, extensions []string) error {
    return filepath.WalkDir(dir, func(path string, d fs.DirEntry, err error) error {
        if err != nil {
            return err
        }
        
        if d.IsDir() {
            return nil
        }
        
        // 检查文件扩展名
        ext := filepath.Ext(path)
        for _, e := range extensions {
            if ext == e {
                return cs.IndexFile(path)
            }
        }
        
        return nil
    })
}

// Search 搜索代码
func (cs *CodeSearcher) Search(pattern string) []FileMatch {
    var results []FileMatch
    
    for filename, index := range cs.files {
        positions := index.Lookup([]byte(pattern), -1)
        
        if len(positions) > 0 {
            results = append(results, FileMatch{
                Filename:  filename,
                Positions: positions,
                Count:     len(positions),
            })
        }
    }
    
    return results
}

// FileMatch 文件匹配
type FileMatch struct {
    Filename  string
    Positions []int
    Count     int
}

func main() {
    // 创建搜索器
    searcher := NewCodeSearcher()
    
    // 索引 Go 文件
    err := searcher.IndexDirectory(".", []string{".go"})
    if err != nil {
        panic(err)
    }
    
    // 搜索模式
    pattern := "func main"
    matches := searcher.Search(pattern)
    
    fmt.Printf("搜索 '%s':\n", pattern)
    for _, match := range matches {
        fmt.Printf("  %s: %d 处匹配\n", match.Filename, match.Count)
    }
}

示例 5：性能对比测试

package main

import (
    "fmt"
    "index/suffixarray"
    "strings"
    "time"
)

func main() {
    // 创建测试文本
    text := strings.Repeat("The quick brown fox jumps over the lazy dog. ", 10000)
    pattern := "fox"
    
    // 方法 1：使用 strings.Index
    start := time.Now()
    count1 := 0
    pos := 0
    for {
        idx := strings.Index(text[pos:], pattern)
        if idx == -1 {
            break
        }
        pos += idx + 1
        count1++
    }
    time1 := time.Since(start)
    
    // 方法 2：使用 suffixarray
    start = time.Now()
    index := suffixarray.New([]byte(text))
    positions := index.Lookup([]byte(pattern), -1)
    count2 := len(positions)
    time2 := time.Since(start)
    
    // 输出结果
    fmt.Println("性能对比:")
    fmt.Printf("文本长度：%d 字符\n", len(text))
    fmt.Printf("模式：'%s'\n", pattern)
    fmt.Printf("\nstrings.Index 方法:\n")
    fmt.Printf("  找到：%d 次\n", count1)
    fmt.Printf("  耗时：%v\n", time1)
    fmt.Printf("\nsuffixarray 方法:\n")
    fmt.Printf("  找到：%d 次\n", count2)
    fmt.Printf("  耗时：%v\n", time2)
    fmt.Printf("\n构建索引时间：%v\n", time2)
    fmt.Printf("加速比（多次搜索时）: %.2fx\n", float64(time1)/float64(time2))
}

五、最佳实践

1. 选择合适的搜索方法

// 场景 1：单次搜索 -> 使用 strings.Index
pos := strings.Index(text, pattern)

// 场景 2：多次搜索同一文本 -> 使用 suffixarray
index := suffixarray.New([]byte(text))
pos1 := index.Lookup(pattern1, -1)
pos2 := index.Lookup(pattern2, -1)
pos3 := index.Lookup(pattern3, -1)

// 场景 3：非常大的文本 -> 考虑分块处理
chunkSize := 1024 * 1024 // 1MB
for i := 0; i < len(text); i += chunkSize {
    end := i + chunkSize
    if end > len(text) {
        end = len(text)
    }
    chunk := text[i:end]
    index := suffixarray.New([]byte(chunk))
    // ...
}

2. 内存优化

// 技巧 1：及时释放不需要的索引
index := suffixarray.New(data)
// 使用索引
results := index.Lookup(pattern, -1)
// 不再需要时，让 GC 回收
index = nil

// 技巧 2：使用 limit 限制结果数量
// 如果只需要前 N 个结果
positions := index.Lookup(pattern, 10) // 只返回 10 个

// 技巧 3：保存和加载索引
// 避免重复构建
index.Save(writer)
// 后续使用
loadedIndex, _ := suffixarray.Load(reader)

3. 错误处理

func safeLoad(filename string) (*suffixarray.Index, error) {
    file, err := os.Open(filename)
    if err != nil {
        return nil, fmt.Errorf("打开文件失败：%w", err)
    }
    defer file.Close()
    
    index, err := suffixarray.Load(file)
    if err != nil {
        return nil, fmt.Errorf("加载索引失败：%w", err)
    }
    
    return index, nil
}

4. 性能优化

// 技巧 1：批量构建索引
// 对于多个文件，批量构建比单独构建更高效
searcher := NewCodeSearcher()
for _, file := range files {
    searcher.IndexFile(file)
}

// 技巧 2：并行搜索
var wg sync.WaitGroup
results := make([][]int, len(patterns))

for i, pattern := range patterns {
    wg.Add(1)
    go func(i int, p string) {
        defer wg.Done()
        results[i] = index.Lookup([]byte(p), -1)
    }(i, pattern)
}
wg.Wait()

// 技巧 3：缓存常用搜索结果
cache := make(map[string][]int)
func searchWithCache(pattern string) []int {
    if results, ok := cache[pattern]; ok {
        return results
    }
    results := index.Lookup([]byte(pattern), -1)
    cache[pattern] = results
    return results
}

5. 大数据处理

// 对于超大文本，考虑以下策略：

// 1. 分块处理
func searchLargeFile(filename, pattern string) error {
    file, _ := os.Open(filename)
    defer file.Close()
    
    reader := bufio.NewReader(file)
    chunkSize := 10 * 1024 * 1024 // 10MB
    buffer := make([]byte, chunkSize)
    
    for {
        n, err := reader.Read(buffer)
        if n == 0 {
            break
        }
        
        chunk := buffer[:n]
        index := suffixarray.New(chunk)
        positions := index.Lookup([]byte(pattern), -1)
        
        // 处理结果...
        
        if err != nil {
            break
        }
    }
    
    return nil
}

// 2. 使用 mmap（需要第三方库）
// 3. 分布式处理

六、与其他包配合

1. 与 bufio 配合

package main

import (
    "bufio"
    "fmt"
    "index/suffixarray"
    "os"
)

func processLargeFile(filename string) error {
    file, err := os.Open(filename)
    if err != nil {
        return err
    }
    defer file.Close()
    
    // 使用缓冲读取
    reader := bufio.NewReader(file)
    
    // 读取全部内容
    content, err := io.ReadAll(reader)
    if err != nil {
        return err
    }
    
    // 创建索引
    index := suffixarray.New(content)
    
    // 搜索
    positions := index.Lookup([]byte("pattern"), -1)
    fmt.Printf("找到：%v\n", positions)
    
    return nil
}

2. 与 bytes 配合

package main

import (
    "bytes"
    "fmt"
    "index/suffixarray"
)

func searchInBuffer(data []byte, pattern string) []int {
    // 使用 bytes.Buffer 处理
    var buf bytes.Buffer
    buf.Write(data)
    
    // 创建索引
    index := suffixarray.New(buf.Bytes())
    
    // 搜索
    return index.Lookup([]byte(pattern), -1)
}

func saveAndLoad() {
    data := []byte("test data")
    index := suffixarray.New(data)
    
    // 保存到 bytes.Buffer
    var buf bytes.Buffer
    index.Save(&buf)
    
    // 从 bytes.Buffer 加载
    loadedIndex, _ := suffixarray.Load(&buf)
    
    // 使用加载的索引
    positions := loadedIndex.Lookup([]byte("test"), -1)
    fmt.Printf("位置：%v\n", positions)
}

3. 与 os 配合

package main

import (
    "fmt"
    "index/suffixarray"
    "os"
)

func main() {
    // 读取文件
    content, err := os.ReadFile("input.txt")
    if err != nil {
        panic(err)
    }
    
    // 创建索引
    index := suffixarray.New(content)
    
    // 保存索引到文件
    indexFile, _ := os.Create("index.dat")
    defer indexFile.Close()
    index.Save(indexFile)
    
    // 从文件加载索引
    loadedFile, _ := os.Open("index.dat")
    defer loadedFile.Close()
    loadedIndex, _ := suffixarray.Load(loadedFile)
    
    // 使用加载的索引
    positions := loadedIndex.Lookup([]byte("search"), -1)
    fmt.Printf("找到位置：%v\n", positions)
}

4. 与 regexp 配合

package main

import (
    "fmt"
    "index/suffixarray"
    "regexp"
)

func hybridSearch(text string, pattern string) []int {
    // 对于简单字符串，使用 suffixarray
    if !regexp.MustCompile(`[\^\$\.\*\+\?\{\}\[\]\\]`).MatchString(pattern) {
        index := suffixarray.New([]byte(text))
        return index.Lookup([]byte(pattern), -1)
    }
    
    // 对于正则表达式，使用 regexp
    re := regexp.MustCompile(pattern)
    matches := re.FindAllStringIndex(text, -1)
    
    positions := make([]int, len(matches))
    for i, match := range matches {
        positions[i] = match[0]
    }
    
    return positions
}

func main() {
    text := "The quick brown fox jumps over the lazy dog"
    
    // 简单字符串搜索（使用 suffixarray）
    pos1 := hybridSearch(text, "fox")
    fmt.Printf("'fox' 的位置：%v\n", pos1)
    
    // 正则表达式搜索（使用 regexp）
    pos2 := hybridSearch(text, `\b\w+ox\b`)
    fmt.Printf("匹配 '\\w+ox' 的位置：%v\n", pos2)
}

七、快速参考

函数总览

结构体总览

方法总览

复杂度分析

符号说明：

• n：文本长度
• m：模式长度

使用场景对比

常见问题

八、注意事项

1. UTF-8 编码问题

// 注意：suffixarray 操作的是字节，不是字符
// 对于 UTF-8 编码的多字节字符，需要特别小心

text := "你好世界"
index := suffixarray.New([]byte(text))

// 正确：搜索完整的 UTF-8 序列
pos1 := index.Lookup([]byte("你好"), -1) // ✓

// 错误：搜索部分字节序列
pos2 := index.Lookup([]byte{0xe4}, -1)  // ✗ 可能得到意外结果

// 建议：始终使用完整的 UTF-8 字符或字符串

2. 内存使用

// 后缀数组需要 O(n) 空间
// 对于大文本，注意内存限制

// 估算内存使用：
// 索引大小 ≈ 文本大小 × (1-2) 倍

// 建议：
// 1. 对于 >100MB 的文本，考虑分块
// 2. 使用持久化存储
// 3. 及时释放不需要的索引

3. 性能特征

// 后缀数组适合：
// ✓ 同一文本的多次搜索
// ✓ 精确字符串匹配
// ✓ 需要所有匹配位置

// 不适合：
// ✗ 单次搜索（使用 strings.Index）
// ✗ 正则表达式（使用 regexp）
// ✗ 模糊匹配（需要其他算法）

4. 空模式处理

// 空模式会匹配所有位置
text := "hello"
index := suffixarray.New([]byte(text))

positions := index.Lookup([]byte(""), -1)
fmt.Printf("空模式的位置：%v\n", positions)
// 输出：[0 1 2 3 4 5]
// 注意：包括文本末尾

5. 边界情况

// 空文本
index := suffixarray.New([]byte(""))
positions := index.Lookup([]byte("pattern"), -1)
fmt.Printf("空文本的搜索：%v\n", positions)
// 输出：[]

// 模式长于文本
text := "hi"
index := suffixarray.New([]byte(text))
positions := index.Lookup([]byte("hello"), -1)
fmt.Printf("模式过长：%v\n", positions)
// 输出：[]

6. 持久化格式

// Save/Load 使用二进制格式
// 不保证版本兼容性

// 建议：
// 1. 在同一 Go 版本中使用
// 2. 保存时记录版本信息
// 3. 提供重新构建的选项

// 示例：带版本检查的保存
func saveWithVersion(filename string, index *suffixarray.Index) error {
    file, _ := os.Create(filename)
    defer file.Close()
    
    // 先写入版本信息
    file.Write([]byte("v1"))
    
    // 再写入索引
    return index.Save(file)
}

九、完整示例：文本分析工具

package main

import (
    "flag"
    "fmt"
    "index/suffixarray"
    "os"
    "sort"
    "strings"
)

// TextAnalyzer 文本分析器
type TextAnalyzer struct {
    text  string
    index *suffixarray.Index
}

// NewTextAnalyzer 创建文本分析器
func NewTextAnalyzer(filename string) (*TextAnalyzer, error) {
    data, err := os.ReadFile(filename)
    if err != nil {
        return nil, err
    }
    
    text := string(data)
    index := suffixarray.New([]byte(text))
    
    return &TextAnalyzer{
        text:  text,
        index: index,
    }, nil
}

// Search 搜索文本
func (ta *TextAnalyzer) Search(pattern string, limit int) []int {
    return ta.index.Lookup([]byte(pattern), limit)
}

// Count 统计出现次数
func (ta *TextAnalyzer) Count(pattern string) int {
    return len(ta.Search(pattern, -1))
}

// FindFrequentWords 查找高频词
func (ta *TextAnalyzer) FindFrequentWords(minLength, minCount int) []WordInfo {
    wordCount := make(map[string]int)
    
    // 提取所有单词
    words := strings.Fields(ta.text)
    for _, word := range words {
        // 清理标点
        word = strings.Trim(word, ".,!?;:\"'()[]{}")
        
        if len(word) >= minLength {
            wordCount[word]++
        }
    }
    
    // 转换为切片并排序
    var results []WordInfo
    for word, count := range wordCount {
        if count >= minCount {
            results = append(results, WordInfo{
                Word:  word,
                Count: count,
            })
        }
    }
    
    // 按出现次数排序
    sort.Slice(results, func(i, j int) bool {
        return results[i].Count > results[j].Count
    })
    
    return results
}

// WordInfo 单词信息
type WordInfo struct {
    Word  string
    Count int
}

// ShowContext 显示上下文
func (ta *TextAnalyzer) ShowContext(position int, contextSize int) {
    start := position - contextSize
    end := position + contextSize
    
    if start < 0 {
        start = 0
    }
    if end > len(ta.text) {
        end = len(ta.text)
    }
    
    context := ta.text[start:end]
    context = strings.ReplaceAll(context, "\n", " ")
    
    fmt.Printf("位置 %d: ...%s...\n", position, context)
}

func main() {
    // 命令行参数
    filename := flag.String("f", "", "输入文件")
    pattern := flag.String("p", "", "搜索模式")
    limit := flag.Int("n", -1, "最大结果数")
    frequent := flag.Bool("frequent", false, "查找高频词")
    minLength := flag.Int("min-len", 5, "最小单词长度")
    minCount := flag.Int("min-count", 10, "最小出现次数")
    
    flag.Parse()
    
    if *filename == "" {
        fmt.Println("用法：textanalyzer -f <文件> [选项]")
        os.Exit(1)
    }
    
    // 创建分析器
    analyzer, err := NewTextAnalyzer(*filename)
    if err != nil {
        fmt.Printf("错误：%v\n", err)
        os.Exit(1)
    }
    
    // 搜索模式
    if *pattern != "" {
        positions := analyzer.Search(*pattern, *limit)
        
        fmt.Printf("搜索 '%s' 找到 %d 处匹配:\n", *pattern, len(positions))
        for i, pos := range positions {
            if i >= 10 { // 只显示前 10 个
                fmt.Println("...")
                break
            }
            analyzer.ShowContext(pos, 20)
        }
    }
    
    // 查找高频词
    if *frequent {
        fmt.Printf("\n高频词（长度>=%d, 出现>=%d次）:\n", *minLength, *minCount)
        words := analyzer.FindFrequentWords(*minLength, *minCount)
        
        for i, word := range words {
            if i >= 20 { // 只显示前 20 个
                break
            }
            fmt.Printf("%s: %d次\n", word.Word, word.Count)
        }
    }
}

最后更新: 2026-04-04
Go 版本: 1.21+
包文档: https://pkg.go.dev/index/suffixarray