# 3.1 index/suffixarray -- 后缀数组 其实后缀数组在 Golang 里面的应用还是比较简单的，从 API 文档中可以看到，只是用了一个查找 Index 的功能，此外，还提供了持久化和反持久化功能。OK，下面先以一个例子介绍一下功能。 ## Suffixarray 查找索引 ``` func main() { index := suffixarray.New([]byte("banana")) offsets := index.Lookup([]byte("ana"), -1) for idx, off := range offsets { fmt.Printf("suffixarryay%d: %d\n", idx, off) } fmt.Println("strings.Index1: ", strings.Index("banana", "ana")) fmt.Println("strings.Index2: ", strings.Index("banana", "ana")) } ``` 执行一下，结果应该是： ``` suffixarryay0: 3 suffixarryay1: 1 strings.Index1: 1 strings.Index2: 1 ``` 这效果还是比较明显的，这里我为了方便大家理解，特别得增加了 `strings.Index` 的调用用于对比效果。这基本上就是 suffixarray 的最直接的用法了。 ## 持久化反持久化 suffixarray 除了直接解析 bytes 之外，Golang 还支持持久化和反持久化，继续看个例子： ``` func main() { index := suffixarray.New([]byte("banana")) var b bytes.Buffer writer := bufio.NewWriter(&b) index.Write(writer) writer.Flush() rIndex := suffixarray.New(nil) rIndex.Read(bytes.NewReader(b.Bytes())) offsets := rIndex.Lookup([]byte("ana"), -1) for idx, off := range offsets { fmt.Printf("suffixarryay%d: %d\n", idx, off) } fmt.Println("strings.Index1: ", strings.Index("banana", "ana")) fmt.Println("strings.Index2: ", strings.Index("banana", "ana")) } ``` 这里我们先使用 `suffixarray` 构造了一个后缀数组并且持久化到 **bytes.Buffer** 中，然后再从这个 **bytes.Buffer** 中反持久化出一个 `suffixarray`，然后再使用它。非常得简单。 ## 后缀数组原理 所谓的后缀数组，其实就是讲一个 bytes 的所有后缀都罗列出来，然后再对他们进行排序，例如 “banana”，所有的后缀可能有：  然后根据后缀排序（字典序），排序之后我们会发现索引不同了：  然后假如我们要查找 `ana` 的 index，那么就遍历这个列表，如果这个列表的后缀包含 `ana` 那么就返回对应的 index，例如这个表里面有两个地方都有 `ana` 前缀：  对应的结果就是我们前面看到的 3 和 1 了。 # 导航 - [第三章 数据结构与算法](/chapter03/03.0.md) - 下一节：[container — 容器数据类型：heap、list和ring](/chapter03/03.3.md)