在golang中创建后缀树

Question

我有一个字符串数组，需要在Golang中创建后缀树。因为SuffixArray仅接受字节数组（即单个字符串），所以它无法满足我的需求。请问是否有人能提供相关实现的指导？

谢谢！

- BigDataLearner

---

你是想创建一个由所有字符串组成的后缀树，还是想为数组中的每个元素创建一个后缀树？ - Ben Echols

@Ben Echols：一个后缀树，可以在所有字符串上进行搜索。我将用它来实现网站的自动完成功能。 - BigDataLearner

SuffixArray 在其实现中已经使用了指针。 :) - user1804599

Answer 1

这是一个使用后缀数组进行自动完成的示例。（playground）。

请注意，我将所有字符串都连接在一起，并带有一个前缀\x00，这个前缀不会出现在字符串中。

package main

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

func main() {
    words := []string{
        "aardvark",
        "happy",
        "hello",
        "hero",
        "he",
        "hotel",
    }
    // use \x00 to start each string
    joinedStrings := "\x00" + strings.Join(words, "\x00")
    sa := suffixarray.New([]byte(joinedStrings))

    // User has typed in "he"
    match, err := regexp.Compile("\x00he[^\x00]*")
    if err != nil {
        panic(err)
    }
    ms := sa.FindAllIndex(match, -1)

    for _, m := range ms {
        start, end := m[0], m[1]
        fmt.Printf("match = %q\n", joinedStrings[start+1:end])
    }
}

打印

match = "hello"
match = "hero"
match = "he"

- Nick Craig-Wood

---

谢谢你的实现。如果你能解释一下为什么在每个字符串中使用\x00，那就太好了。另外，如果我想处理两种情况，1)如果用户输入“ello”，则应匹配“hello”2)如果单词数组有“hello world”且用户输入“wor”，则应显示“hello world”，代码会如何改变。 - BigDataLearner

这个例子在将多个字符串合并为单个byte[]方面很好，但请注意您的正则表达式模式打败了后缀数组的目的，因为您只查看单词的开头。如果要查看前缀，您不需要像后缀数组那样强大的工具-只需对原始字符串进行排序并执行二进制搜索即可。后缀数组的真正威力在于查找单词内的匹配项，而不仅仅是开头。 - Eli Bendersky

Answer 2

你需要的是通用后缀树。构建这种树的简单方法是为每个字符串添加不同的结束标记（未在任何字符串中使用的符号），将它们连接起来并为连接后的字符串构建普通后缀树。因此，你只需要将“hello world”添加到字符串集合中，并使用以下代码：

match, err := regexp.Compile("[^\x00]*wor[^\x00]*")

获取包含“wor”的字符串。请注意，正确的字符串是joinedStrings[start:end]。

- Codeb Fan

Answer 3

我创建了一个后缀树的实现，其复杂度为O(n)，其中n是字符串的长度：https://github.com/twelvedata/searchindex 更多细节请参阅我的Medium文章https://medium.com/twelve-data/in-memory-text-search-index-for-quotes-on-go-5243adc62c26。

- Nick