1

func New(data []byte) *Index

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

package main

import (
	"fmt"
	"index/suffixarray"
)

// 这是一个展示 suffixarray.New 用法的示例
func main() {

	// 待索引的文本——选一首诗，方便观察
	text := []byte("春眠不觉晓，处处闻啼鸟。夜来风雨声，花落知多少。")

	// 使用 suffixarray.New 创建后缀数组索引
	// 这一行代码背后做了很多事情：
	// 1. 分析文本所有后缀
	// 2. 对后缀进行字典序排序
	// 3. 构建加速查找的数据结构
	idx := suffixarray.New(text)

	// 打印一下文本内容
	fmt.Printf("索引的文本: %s\n", text)
	// 输出: 索引的文本: 春眠不觉晓，处处闻啼鸟。夜来风雨声，花落知多少。

	// 打印一下后缀数组的长度（应该等于文本字节数）
	fmt.Printf("后缀数组长度: %d (等于文本字节数)\n", len(idx))
	// 输出: 后缀数组长度: 65 (等于文本字节数)
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

package main

import (
	"fmt"
	"index/suffixarray"
)

// 模拟大规模文本索引场景
func main() {

	// 假设这是从文件加载的大量文本
	// 真实场景中可以是日志、小说、代码库、DNA序列等
	var largeText []byte

	// 模拟生成100万个字符
	for i := 0; i < 1000000; i++ {
		largeText = append(largeText, byte('a'+i%26))
	}

	fmt.Printf("文本长度: %d 字符\n", len(largeText))
	// 输出: 文本长度: 1000000 字符

	// 构建后缀数组索引
	// 注意：New 操作对于大文本可能耗时较长，但只需执行一次
	idx := suffixarray.New(largeText)

	fmt.Println("后缀数组索引构建完成！")
	// 输出: 后缀数组索引构建完成！

	// 后续查找将非常快速
	fmt.Printf("索引结构类型: %T\n", idx)
	// 输出: 索引结构类型: *index/suffixarray.Index
}

1

func (x *Index) Lookup(s []byte, n int) []int

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50

package main

import (
	"fmt"
	"index/suffixarray"
)

// 演示 Lookup 的基本用法
func main() {

	// 一段经典的中文文本
	text := []byte("锄禾日当午，汗滴禾下土。谁知盘中餐，粒粒皆辛苦。")

	// 构建后缀数组索引
	idx := suffixarray.New(text)

	// 查找子串 "禾"
	fmt.Println("=== 查找子串 '禾' ===")
	locations := idx.Lookup([]byte("禾"), -1) // -1 表示返回所有匹配
	fmt.Printf("找到 %d 处匹配，位置分别是: %v\n", len(locations), locations)
	// 输出: 找到 2 处匹配，位置分别是: [1 13]

	// 打印匹配位置对应的上下文
	for _, pos := range locations {
		start := pos
		if start > 10 {
			start = 10
		}
		end := pos + 10
		if end > len(text) {
			end = len(text)
		}
		fmt.Printf("  位置 %d 附近: ...%s...\n", pos, text[start:end])
	}
	// 输出:
	//   位置 1 附近: ...锄禾日当午...
	//   位置 13 附近: ...汗滴禾下土...

	// 查找子串 "盘中餐"
	fmt.Println("\n=== 查找子串 '盘中餐' ===")
	locations = idx.Lookup([]byte("盘中餐"), -1)
	fmt.Printf("找到 %d 处匹配，位置分别是: %v\n", len(locations), locations)
	// 输出: 找到 1 处匹配，位置分别是: [18]

	// 只返回前1个匹配
	fmt.Println("\n=== 查找 '粒'，只返回前1个 ===")
	locations = idx.Lookup([]byte("粒"), 1)
	fmt.Printf("找到（最多1个）: %v\n", locations)
	// 输出: 找到（最多1个）: [30]
}

1

func (x *Index) FindAllIndex(re *regexp.Regexp, n int) [][]int

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79

package main

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

// 演示 FindAllIndex 的正则表达式查找功能
func main() {

	// 一段包含各种模式的文本
	text := []byte(`
	联系方式：
	邮箱: alice@example.com
	邮箱: bob@test.org
	电话: 138-1234-5678
	电话: 139-9876-5432
	网址: https://golang.org
	网址: http://go.dev
	IP地址: 192.168.1.1
	IP地址: 10.0.0.1
	`)

	// 构建后缀数组索引
	idx := suffixarray.New(text)

	// 查找所有邮箱地址（简化版）
	fmt.Println("=== 查找所有邮箱 ===")
	emailRegex := regexp.MustCompile(`[\w]+@[\w]+\.[\w]+`)
	emails := idx.FindAllIndex(emailRegex, -1)
	fmt.Printf("找到 %d 个邮箱地址:\n", len(emails))
	for _, match := range emails {
		fmt.Printf("  [%d:%d] %s\n", match[0], match[1], text[match[0]:match[1]])
	}
	// 输出:
	// 找到 2 个邮箱地址:
	//   [31:47] alice@example.com
	//   [56:68] bob@test.org

	// 查找所有电话号码
	fmt.Println("\n=== 查找所有电话号码 ===")
	phoneRegex := regexp.MustCompile(`\d{3}-\d{4}-\d{4}`)
	phones := idx.FindAllIndex(phoneRegex, -1)
	fmt.Printf("找到 %d 个电话号码:\n", len(phones))
	for _, match := range phones {
		fmt.Printf("  [%d:%d] %s\n", match[0], match[1], text[match[0]:match[1]])
	}
	// 输出:
	// 找到 2 个电话号码:
	//   [88:100] 138-1234-5678
	//   [109:121] 139-9876-5432

	// 查找所有URL（只返回前3个）
	fmt.Println("\n=== 查找URL（最多3个）===")
	urlRegex := regexp.MustCompile(`https?://[^\s]+`)
	urls := idx.FindAllIndex(urlRegex, 3)
	fmt.Printf("找到（最多3个）:\n")
	for _, match := range urls {
		fmt.Printf("  [%d:%d] %s\n", match[0], match[1], text[match[0]:match[1]])
	}
	// 输出:
	// 找到（最多3个）:
	//   [139:158] https://golang.org
	//   [167:180] http://go.dev

	// 查找所有IP地址
	fmt.Println("\n=== 查找所有IP地址 ===")
	ipRegex := regexp.MustCompile(`\d{1,3}\.\d{1,3}\.\d{1,3}\.\d{1,3}`)
	ips := idx.FindAllIndex(ipRegex, -1)
	fmt.Printf("找到 %d 个IP地址:\n", len(ips))
	for _, match := range ips {
		fmt.Printf("  [%d:%d] %s\n", match[0], match[1], text[match[0]:match[1]])
	}
	// 输出:
	// 找到 2 个IP地址:
	//   [203:213] 192.168.1.1
	//   [232:241] 10.0.0.1
}

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116

package main

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

// 性能对比：线性扫描 vs 后缀数组
func main() {

	// 生成测试数据：100万个字符的文本
	text := generateText(1_000_000)
	searchTerm := "patternXYZ"

	// 先在文本中加入我们要找的串
	textWithMatch := []byte(string(text) + searchTerm)

	fmt.Printf("测试文本长度: %d 字符\n", len(textWithMatch))
	// 输出: 测试文本长度: 1000009 字符

	// 构建后缀数组
	fmt.Println("\n正在构建后缀数组索引...")
	start := time.Now()
	idx := suffixarray.New(textWithMatch)
	buildTime := time.Since(start)
	fmt.Printf("后缀数组构建耗时: %v\n", buildTime)
	// 输出类似: 后缀数组构建耗时: 152.3ms

	// 方法1：使用 suffixarray 查找（对数时间）
	fmt.Println("\n=== 使用后缀数组查找 ===")
	start = time.Now()
	results := idx.Lookup([]byte(searchTerm), -1)
	lookupTime := time.Since(start)
	fmt.Printf("查找耗时: %v\n", lookupTime)
	fmt.Printf("找到匹配: %d 处\n", len(results))
	// 输出类似:
	// 查找耗时: 1.2ms
	// 找到匹配: 1 处

	// 方法2：使用 strings.Index 查找（线性扫描）
	fmt.Println("\n=== 使用 strings.Index 线性扫描 ===")
	start = time.Now()
	linearResults := linearSearch(string(textWithMatch), searchTerm)
	linearTime := time.Since(start)
	fmt.Printf("查找耗时: %v\n", linearTime)
	fmt.Printf("找到匹配: %d 处\n", len(linearResults))
	// 输出类似:
	// 查找耗时: 4.2ms
	// 找到匹配: 1 处

	// 对比
	fmt.Println("\n=== 性能对比 ===")
	if linearTime > 0 && lookupTime > 0 {
		speedup := float64(linearTime) / float64(lookupTime)
		fmt.Printf("后缀数组快 %.1f 倍\n", speedup)
	}

	// 测试多次查找的场景——后缀数组的优势更明显
	fmt.Println("\n=== 多次查找场景（查找1000次）===")

	// 多次使用后缀数组
	start = time.Now()
	for i := 0; i < 1000; i++ {
		idx.Lookup([]byte(searchTerm), -1)
	}
	multiLookupTime := time.Since(start)
	fmt.Printf("后缀数组 1000次查找耗时: %v\n", multiLookupTime)
	// 输出类似: 后缀数组 1000次查找耗时: 1.2s

	// 多次使用线性扫描
	start = time.Now()
	for i := 0; i < 1000; i++ {
		linearSearch(string(textWithMatch), searchTerm)
	}
	multiLinearTime := time.Since(start)
	fmt.Printf("线性扫描 1000次查找耗时: %v\n", multiLinearTime)
	// 输出类似: 线性扫描 1000次查找耗时: 4.5s

	speedup := float64(multiLinearTime) / float64(multiLookupTime)
	fmt.Printf("后缀数组在多次查找场景快 %.1f 倍\n", speedup)
}

// 生成指定长度的测试文本
func generateText(n int) []byte {
	patterns := []string{
		"hello world",
		"pattern match",
		"binary search",
		"data structure",
		"algorithm",
		"complexity analysis",
		"performance optimization",
	}
	var sb strings.Builder
	sb.Grow(n)
	for sb.Len() < n {
		for _, p := range patterns {
			sb.WriteString(p)
		}
	}
	result := sb.String()
	return []byte(result[:n])
}

// 线性搜索：逐字符扫描
func linearSearch(text, pattern string) []int {
	var results []int
	for i := 0; i <= len(text)-len(pattern); i++ {
		if text[i:i+len(pattern)] == pattern {
			results = append(results, i)
		}
	}
	return results
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61

package main

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

// 场景1：日志分析 - 快速定位错误
func logAnalysisDemo() {

	// 模拟日志文件内容
	logData := []byte(`
2024/01/15 10:23:45 INFO: Server started on port 8080
2024/01/15 10:23:46 INFO: Database connected successfully
2024/01/15 10:24:12 ERROR: Connection timeout to external API
2024/01/15 10:24:13 ERROR: Failed to process request #1234
2024/01/15 10:24:15 WARN: Retry attempt 1/3
2024/01/15 10:24:16 ERROR: Connection timeout to external API
2024/01/15 10:24:17 ERROR: Retry failed, giving up
2024/01/15 10:25:00 INFO: Request processed successfully
2024/01/15 10:26:00 ERROR: NullPointerException in thread pool
2024/01/15 10:26:01 ERROR: Stack trace: at com.example.Service.process
2024/01/15 10:26:02 ERROR: Stack trace: at com.example.Controller.handle
`)

	// 构建后缀数组索引
	idx := suffixarray.New(logData)

	fmt.Println("=== 日志分析示例 ===\n")

	// 查找所有 ERROR 日志
	fmt.Println("【所有错误日志】")
	errors := idx.FindAllIndex(
		strings.NewReplacer(
			"\n", "",
		).NewReader(nil), // 简化：用普通方式
		-1,
	)

	// 实际上我们用 Lookup 来演示
	errorLogs := idx.Lookup([]byte("ERROR"), -1)
	for _, pos := range errorLogs {
		// 找到该 ERROR 所在的行
		start := pos
		end := pos
		for start > 0 && logData[start-1] != '\n' {
			start--
		}
		for end < len(logData) && logData[end] != '\n' {
			end++
		}
		line := strings.TrimSpace(string(logData[start:end]))
		fmt.Printf("  位置 %d: %s\n", pos, line)
	}

	fmt.Printf("\n共发现 %d 条错误日志\n", len(errorLogs))
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72

package main

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

// 场景2：简单的文本搜索引擎
func textSearchDemo() {

	// 文档集合（简化为一个大字符串，用换行分隔）
	documents := []byte(`
Go语言是Google开发的编译型编程语言。
Go语言以简洁、高效著称。
Python是一种解释型脚本语言。
Python以可读性高著称。
Java是一种面向对象的编程语言。
Java有丰富的生态系统。
Go语言的并发模型非常强大。
Python在数据科学领域应用广泛。
JavaScript是Web开发的核心语言。
JavaScript最初只能在浏览器中运行。
Go语言的语法与C语言相似。
Python有丰富的第三方库。
Java可以运行在JVM上。
Go语言适合构建高性能服务。
`)

	// 构建索引
	idx := suffixarray.New(documents)

	fmt.Println("=== 文本搜索引擎 ===\n")

	// 搜索函数
	search := func(keyword string) {
		fmt.Printf("搜索关键词: \"%s\"\n", keyword)

		matches := idx.Lookup([]byte(keyword), -1)

		seen := make(map[int]bool)
		for _, pos := range matches {
			// 找到所属行
			lineStart := pos
			lineEnd := pos
			for lineStart > 0 && documents[lineStart-1] != '\n' {
				lineStart--
			}
			for lineEnd < len(documents) && documents[lineEnd] != '\n' {
				lineEnd++
			}
			lineNum := 1
			for i := 0; i < lineStart; i++ {
				if documents[i] == '\n' {
					lineNum++
				}
			}
			if !seen[lineStart] {
				seen[lineStart] = true
				line := documents[lineStart:lineEnd]
				fmt.Printf("  第 %d 行: %s\n", lineNum, line)
			}
		}
		fmt.Printf("  共找到 %d 处匹配\n\n", len(matches))
	}

	// 执行搜索
	search("Go语言")
	search("Python")
	search("Java")
	search("高性能")
}

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113

package main

import (
	"fmt"
	"index/suffixarray"
)

// 场景3：代码补全（简化版IDE功能）
func codeCompletionDemo() {

	// 模拟一个代码库的代码
	code := []byte(`
func calculateSum(numbers []int) int {
    sum := 0
    for _, n := range numbers {
        sum += n
    }
    return sum
}

func calculateAverage(numbers []int) float64 {
    sum := calculateSum(numbers)
    return float64(sum) / float64(len(numbers))
}

func calculateMedian(numbers []int) float64 {
    sorted := make([]int, len(numbers))
    copy(sorted, numbers)
    sort.Ints(sorted)
    n := len(sorted)
    if n%2 == 0 {
        return float64(sorted[n/2-1]+sorted[n/2]) / 2
    }
    return float64(sorted[n/2])
}

func calculateVariance(numbers []int) float64 {
    avg := calculateAverage(numbers)
    sum := 0
    for _, n := range numbers {
        diff := float64(n) - avg
        sum += int(diff * diff)
    }
    return float64(sum) / float64(len(numbers))
}
`)

	// 构建索引
	idx := suffixarray.New(code)

	fmt.Println("=== 代码补全示例 ===\n")

	// 模拟用户输入 "calc"
	partial := "calc"
	fmt.Printf("用户输入（触发补全）: \"%s\"\n\n", partial)

	// 查找所有以 "calc" 开头的函数
	matches := idx.Lookup([]byte(partial), -1)

	// 收集所有可能的补全
	type completion struct {
		name    string
		lineNum int
	}
	var completions []completion
	seen := make(map[string]bool)

	for _, pos := range matches {
		// 找到该匹配所在的行
		lineStart := pos
		for lineStart > 0 && code[lineStart-1] != '\n' {
			lineStart--
		}
		lineEnd := pos
		for lineEnd < len(code) && code[lineEnd] != '\n' {
			lineEnd++
		}

		line := string(code[lineStart:lineEnd])

		// 提取函数名（简化匹配）
		var funcName string
		for _, name := range []string{
			"calculateSum",
			"calculateAverage",
			"calculateMedian",
			"calculateVariance",
		} {
			if len(line) > 9 && line[9:9+len(name)] == name {
				funcName = name
				break
			}
		}

		if funcName != "" && !seen[funcName] {
			seen[funcName] = true
			lineNum := 1
			for i := 0; i < lineStart; i++ {
				if code[i] == '\n' {
					lineNum++
				}
			}
			completions = append(completions, completion{funcName, lineNum})
		}
	}

	fmt.Println("推荐补全：")
	for _, c := range completions {
		fmt.Printf("  📝 %s (第 %d 行)\n", c.name, c.lineNum)
	}

	fmt.Printf("\n找到 %d 个可能的补全\n", len(completions))
}