什么是倒排索引
定义
- 倒排索引（Inverted Index）是一种索引数据结构，它是文档检索系统中最常用的数据结构之一。在信息检索领域，它用于快速地定位包含给定查询词的文档。与正向索引（Forward Index）相对，正向索引是从文档到词汇的映射，而倒排索引是从词汇到文档的映射。
基本结构和原理
倒排索引主要由两部分组成：词汇表（Vocabulary）和倒排记录表（Postings List）。
词汇表：包含了文档集合中出现的所有不同的词汇（或词条）。每个词汇都有一个指向其对应的倒排记录表的指针。例如，在一个包含多篇新闻文章的文档集合中，词汇表可能包含 “经济”“政治”“科技” 等词汇。
倒排记录表：对于词汇表中的每个词汇，倒排记录表记录了包含该词汇的所有文档的标识符（Document ID）以及可能的其他相关信息，如词汇在文档中的位置、出现的频率等。比如，对于词汇 “科技”，其倒排记录表可能包含文档 ID 为 1、3、5 的记录，表示这三篇文档中都出现了 “科技” 这个词汇。
- 假如现在有三份数据文档，内容分别是：
Doc 1:Java is the best programming language
Doc 2:PHP is the best programming language
Doc 3:Javascript is the best programming language 为了创建索引，通过分词器将每个文档的内容拆成单独的词，再将这些词条创建成不含重复词条的排序列表，然后列出每个词条出现在哪个文档，结果如下：
| term | Doc 1 | Doc 2 | Doc 3 |
| Java | √ | ||
| is | √ | √ | √ |
| the | √ | √ | √ |
| best | √ | √ | √ |
| programming | √ | √ | √ |
| language | √ | √ | √ |
| PHP | √ | √ | |
| Javascript | √ | √ |
这种结构由文档中所有不重复的词的列表构成，对于其中每个词都有至少一个文档与与之关联。这种由属性值来确定记录的位置的结构就是倒排索引，带有倒排索引的文件被称为倒排文件。
将上表转为更直观的图片来展示倒排索引：
分词在倒排索引中的重要性
- 建立索引基础：倒排索引是一种用于快速检索的数据结构。它的核心是将文档中的关键词提取出来，建立关键词到文档的映射关系。分词就是这个提取关键词的过程，只有通过分词，才能将文本内容分解为一个个有意义的词汇单元，为建立倒排索引提供基础。例如，对于一篇文档 “我爱自然语言处理技术”，如果不分词，这个文档就会被当作一个整体，很难进行有效的关键词检索；而通过分词得到 “我”“爱”“自然语言处理”“技术” 这些词汇后，就可以分别建立它们与该文档的索引关系。
- 提高检索效率和准确性：当用户进行查询时，倒排索引会根据用户输入的关键词来查找相关文档。精确的分词可以确保查询词和索引中的词汇准确匹配，提高检索的准确性。例如，在搜索引擎中，如果用户输入 “自然语言处理”，经过良好分词的倒排索引能够快速定位到包含这个词汇的文档，而不会因为没有正确分词而错过相关文档。同时，合理的分词还可以减少索引的大小，提高检索效率。如果将一些无意义的组合词也作为索引词，会增加索引的复杂度和存储量，而通过分词去除不必要的组合，只保留有意义的词汇，可以使索引更加紧凑，检索速度更快。
"中文分词面临的挑战:"
简单倒排索引的实现
接口定义
定义三个接口，分别是 数据库，正排索引，倒排索引；规定都要实现Get和Add功能
// DB接口定义了数据库的基本操作，用于获取和添加数据。
type DB interface {
Get(string) []string
Add(string)
}
// ForwardIndexer 用于根据给定的文档ID列表获取对应的原始字符串内容。
type ForwardIndexer interface {
Get([]int64) []string
Add(int64, string)
}
// InvertedIndexer 用于根据给定的字符串获取对应的文档ID列表以及添加倒排索引数据。
type InvertedIndexer interface {
Get(string) []int64
Add(string, int64)
}简单数据库的实现
定义简单数据库结构体，由id，正排索引和倒排索引组成。
Get方法是先通过倒排索引由字符串找出id，然后在通过正排索引由id找出匹配的字符串
Add方法把字符串存入倒排和正排
// SimpleDatabase结构体实现了DB接口，内部整合了正向索引和倒排索引来管理数据。
type SimpleDatabase struct {
id int64
fi ForwardIndexer
ii InvertedIndexer
}
// NewSimpleDatabase创建一个新的SimpleDatabase实例，初始化其正向索引和倒排索引相关组件。
func NewSimpleDatabase() DB {
return &SimpleDatabase{
id: 0, // 递增文档ID
fi: NewForwardIndex(),
ii: NewSimpleInverted(),
}
}
func (sd *SimpleDatabase) Get(s string) []string {
// 先通过倒排索引根据输入字符串获取对应的文档ID列表
ids := sd.ii.Get(s)
// 再通过正排索引根据获取到的文档ID列表查找对应的原字符串
return sd.fi.Get(ids)
}
func (sd *SimpleDatabase) Add(s string) {
atomic.AddInt64(&sd.id, 1)
id := sd.id
addToIndexes(sd.fi, sd.ii, id, s)
}
func addToIndexes(fi ForwardIndexer, ii InvertedIndexer, id int64, s string) {
// 倒排存入
ii.Add(s, id)
// 正排存入
fi.Add(id, s)
}倒排索引
倒排索引结构由读写锁，分词器和map组成
Get方法查找data返回id数组
Add先分词，然后把分词后的结构以及对应id存入map，ES中的分词器一般会大写转小写，但是这里我偷个懒就直接存了
// SimpleInverted结构体实现了InvertedIndexer接口，用于管理倒排索引数据。
type SimpleInverted struct {
sync.RWMutex
data map[string][]int64
analyzer Analyzer
}
// NewSimpleInverted创建一个新的SimpleInverted实例，初始化倒排索引数据存储结构和分析器。
func NewSimpleInverted() InvertedIndexer {
return &SimpleInverted{
data: make(map[string][]int64),
analyzer: NewSimpleAnalyzer(),
}
}
func (si *SimpleInverted) Get(s string) []int64 {
si.RLock()
result := si.data[s]
si.RUnlock()
return result
}
func (si *SimpleInverted) Add(s string, id int64) {
words := si.analyzer.Analyze(s)
si.Lock()
for _, word := range words {
si.data[word] = append(si.data[word], id)
}
si.Unlock()
}分词器
这里分词器的实现比较简单，直接逐个拆开来存了，在实际中分词器比这更加复杂和优雅，往往伴随着一些分词的算法
这里用使用了两层嵌套的 for 循环来生成输入字符串的所有可能子串，并将这些子串作为键存入一个 map 类型的变量 word 中。外层循环控制起始位置 i，内层循环控制结束位置 j，通过切片操作 su[i:j] 取出从位置 i 到位置 j（不包含 j）的子串，然后将其转换为字符串作为 map 的键，对应的值使用了空结构体 struct{}{}。
这样做虽然能实现分词，但是非常暴力而且浪费空间。因为中文分词不像英文，可以使用空格或者,进行简单切分，一般的中文分词器都会采用词典分词，因为我们是简单实现，所以这里就采用了这种暴力写法(其实是太菜了不会更好的分词方法)
// Analyzer接口定义了文本分析（例如分词等操作）的基本操作方法。
type Analyzer interface {
Analyze(s string) []string
}
// SimpleAnalyzer结构体实现了Analyzer接口，简单地进行字符串分析（示例中较简单的逻辑，可优化）。
type SimpleAnalyzer struct{}
// NewSimpleAnalyzer创建一个新的SimpleAnalyzer实例。
func NewSimpleAnalyzer() Analyzer {
return &SimpleAnalyzer{}
}
func (l *SimpleAnalyzer) Analyze(s string) (re []string) {
// 转为rune可以有效处理中英文字符的字节大小问题
su := []rune(s)
sl := len(su)
word := make(map[string]struct{})
for i := 0; i < sl; i++ {
for j := i + 1; j <= sl; j++ {
word[string(su[i:j])] = struct{}{}
}
}
re = make([]string, len(word))
num := 0
for index := range word {
re[num] = index
num++
}
return
}正排索引
这个比起倒排简单很多，没啥好讲的
// forwardIndex结构体实现了ForwardIndexer接口，用于管理正向索引数据。
type forwardIndex struct {
sync.RWMutex
data map[int64]string
}
// NewForwardIndex创建一个新的forwardIndex实例，初始化正向索引数据存储结构。
func NewForwardIndex() ForwardIndexer {
return &forwardIndex{
data: make(map[int64]string),
}
}
func (fi *forwardIndex) Get(ids []int64) (re []string) {
re = make([]string, len(ids))
fi.RLock()
for k, v := range ids {
re[k] = fi.data[v]
}
fi.RUnlock()
return
}
func (fi *forwardIndex) Add(id int64, s string) {
fi.Lock()
fi.data[id] = s
fi.Unlock()
}测试
单元测试代码如下，一首《春江花月夜》来试试效果
func TestSimpleDatabaseWithChunJiangHuaYueYe(t *testing.T) {
// 创建数据库实例
db := NewSimpleDatabase()
// 添加《春江花月夜》的诗句（假设逐句添加）
lines := []string{
"春江潮水连海平，海上明月共潮生。",
"江流宛转绕芳甸，月照花林皆似霰。",
"空里流霜不觉飞，汀上白沙看不见。",
"江天一色无纤尘，皎皎空中孤月轮。",
"江畔何人初见月？江月何年初照人？",
"人生代代无穷已，江月年年望相似。",
"不知江月待何人，但见长江送流水。",
"白云一片去悠悠，青枫浦上不胜愁。",
"谁家今夜扁舟子？何处相思明月楼？",
"可怜楼上月徘徊，应照离人妆镜台。",
"玉户帘中卷不去，捣衣砧上拂还来。",
"此时相望不相闻，愿逐月华流照君。",
"鸿雁长飞光不度，鱼龙潜跃水成文。",
"昨夜闲潭梦落花，可怜春半不还家。",
"江水流春去欲尽，江潭落月复西斜。",
"斜月沉沉藏海雾，碣石潇湘无限路。",
"不知乘月几人归，落月摇情满江树。",
}
for _, line := range lines {
db.Add(line)
}
// 测试获取包含“江”字的字符串
expectedJiang := []string{
"春江潮水连海平，海上明月共潮生。",
"江流宛转绕芳甸，月照花林皆似霰。",
"江天一色无纤尘，皎皎空中孤月轮。",
"江畔何人初见月？江月何年初照人？",
"人生代代无穷已，江月年年望相似。",
"不知江月待何人，但见长江送流水。",
"江水流春去欲尽，江潭落月复西斜。",
"不知乘月几人归，落月摇情满江树。",
}
actualJiang := db.Get("江")
if !reflect.DeepEqual(actualJiang, expectedJiang) {
t.Errorf("Get for '江' failed. Expected: %v, Got: %v", expectedJiang, actualJiang)
} else {
fmt.Println("========江=========")
for _, s := range actualJiang {
fmt.Println(s)
}
}
// 测试获取包含“月”字的字符串
expectedYue := []string{
"春江潮水连海平，海上明月共潮生。",
"江流宛转绕芳甸，月照花林皆似霰。",
"江天一色无纤尘，皎皎空中孤月轮。",
"江畔何人初见月？江月何年初照人？",
"人生代代无穷已，江月年年望相似。",
"不知江月待何人，但见长江送流水。",
"谁家今夜扁舟子？何处相思明月楼？",
"可怜楼上月徘徊，应照离人妆镜台。",
"此时相望不相闻，愿逐月华流照君。",
"江水流春去欲尽，江潭落月复西斜。",
"斜月沉沉藏海雾，碣石潇湘无限路。",
"不知乘月几人归，落月摇情满江树。",
}
actualYue := db.Get("月")
if !reflect.DeepEqual(actualYue, expectedYue) {
t.Errorf("Get for '月' failed. Expected: %v, Got: %v", expectedYue, actualYue)
} else {
fmt.Println("========月=========")
for _, s := range actualYue {
fmt.Println(s)
}
}
// 测试获取包含“花”字的字符串
expectedHua := []string{
"江流宛转绕芳甸，月照花林皆似霰。",
"昨夜闲潭梦落花，可怜春半不还家。",
}
actualHua := db.Get("花")
if !reflect.DeepEqual(actualHua, expectedHua) {
t.Errorf("Get for '花' failed. Expected: %v, Got: %v", expectedHua, actualHua)
} else {
fmt.Println("========花=========")
for _, s := range actualHua {
fmt.Println(s)
}
}
// 测试获取包含“海”字的字符串
expectedHai := []string{
"春江潮水连海平，海上明月共潮生。",
"斜月沉沉藏海雾，碣石潇湘无限路。",
}
actualHai := db.Get("海")
if !reflect.DeepEqual(actualHai, expectedHai) {
t.Errorf("Get for '海' failed. Expected: %v, Got: %v", expectedHai, actualHai)
} else {
fmt.Println("========海=========")
for _, s := range actualHai {
fmt.Println(s)
}
}
}测试结果通过，可喜可贺
总结
Go简单实现了一下倒排索引，感觉分词还是很重要的，直接决定了整个倒排索引的表现，还是要多学习一些厉害的分词器是怎么实现的~
Comments NOTHING