devbox
知新_RL
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

对搜索引擎开源项目的代码分析——索引（1）

作者：知新_RL | 2024-02-29 20:58:44

赞

踩

tokens和labels

2019独角兽企业重金招聘Python工程师标准>>> hot3.png

首先，需要对基本概念进行简单的介绍：Keywords:搜索键; tokens:关键词; 关键词（tokens）和标签（labels）组成了索引器中的搜索键（keywords）

 

1.       上文中，已经从微博上，抓取了相应的微博信息，下面将对其进行搜索引擎的下一步骤：“索引”

  // 读入微博数据file, err := os.Open("../../testdata/weibo_data.txt")

2.       使用悟空引擎你需要import两个包;第一个包定义了引擎功能，第二个包定了结构体，同时需要对引擎使用之前进行初始化；

  1. import(
  2. "github.com/huichen/wukong/engine"
  3. "github.com/huichen/wukong/types"
  4. )

 

3.       再索引之前，需要了解下需要注意的基本概念：

 IndexerInitOptions.IndexType的类型选择，共有三种不同类型的索引表进行选择；
    1） DocIdsIndex，提供了最基本的索引，仅仅记录搜索键出现的文档docid；
    2） FrequenciesIndex，除了记录docid外，还保存了搜索键在每个文档中出现的频率；
    3.）LocationsIndex，这个不仅包括上两种索引的内容，还额外存储了关键词在文档中的具体位置
这三种索引由上到下在提供更多计算能力的同时也消耗了更多的内存，特别是LocationsIndex，当文档很长时会占用大量内存。请根据需要平衡选择。如果没有选择，那么系统会默认选择FrequenciesIndex

4.       悟空引擎允许你加入三种索引数据：
    1）文档的正文（content），会被分词为关键词（tokens）加入索引。
    2）文档的关键词（tokens）。当正文为空的时候，允许用户绕过悟空内置的分词器直接
           输入文档关键词，这使得在引擎外部进行文档分词成为可能。
    3）文档的属性标签（labels），比如微博的作者，类别等。标签并不出现在正文中。
需要注意的是：文档的正文是进行关键词的优先择；关键词（tokens）和标签（labels）组成了索引器中的搜索键（keywords），当然标签labels是不出现在正文中的；

5.       引擎采用了非同步的索引方式，也就是说当IndexDocument返回时索引可能还没有加入索引表中，从而方便的循环并发加入索引；如果你需要等待索引添加完毕后再进行后续操作，请用下面的函数：searcher.FlushIndex()

6.下面分析索引的代码功能，一些功能重叠部分将在后续的索引中进行分析；

下面定义了索引器的一些基本单位，其中添加了sync.RWMutex读写锁实现安全的map；但是了解到，自锁和解锁的相互过程，试想如果自锁一次，而在不知道自锁次数的情况下解锁超过自锁，那么将要报错，因此在此可以进行次数检查，防止自锁和解锁次数的不一致导致的错误；

  1. // 索引器
  2. type Indexer struct {
  3.     // 从搜索键到文档列表的反向索引
  4.     // 加了读写锁以保证读写安全
  5.     tableLock struct {
  6.         sync.RWMutex
  7.         table map[string]*KeywordIndices
  8.     }
  9.     initOptions types.IndexerInitOptions
  10.     initialized bool
  11.     // 这实际上是总文档数的一个近似
  12.     numDocuments uint64
  13.     // 所有被索引文本的总关键词数
  14.     totalTokenLength float32
  15.     // 每个文档的关键词长度
  16.     docTokenLengths map[uint64]float32
  17. }

 

本段代码定义了的功能已在上面的概念解析中进行了阐述；注意IndexType的选择符合业务的需求，内存的消耗承担情况；

  1. // 反向索引表的一行，收集了一个搜索键出现的所有文档，按照DocId从小到大排序。 
  2. type KeywordIndices struct { 
  3.     // 下面的切片是否为空，取决于初始化时IndexType的值
  4.     docIds      []uint64  // 全部类型都有 
  5.     frequencies []float32 // IndexType == FrequenciesIndex 
  6.     locations   [][]int   // IndexType == LocationsIndex}

 对索引器进行相应的初始化

  1. // 初始化索引器
  2. func (indexer *Indexer) Init(options types.IndexerInitOptions) {
  3.     if indexer.initialized == true {
  4.         log.Fatal("索引器不能初始化两次")
  5.     }
  6.     indexer.initialized = true
  7.     indexer.tableLock.table = make(map[string]*KeywordIndices)
  8.     indexer.initOptions = options
  9.     indexer.docTokenLengths = make(map[uint64]float32)
  10. }

 

下面将文档加入索引：提取文档的关键词，出现频率甚至是位置信息等等；

  1. // 向反向索引表中加入一个文档
  2. func (indexer *Indexer) AddDocument(document *types.DocumentIndex) {
  3.     if indexer.initialized == false {
  4.         log.Fatal("索引器尚未初始化")
  5.     }
  6.     indexer.tableLock.Lock()
  7.     defer indexer.tableLock.Unlock()
  8.     // 更新文档关键词总长度
  9.     if document.TokenLength != 0 {
  10.         originalLength, found := indexer.docTokenLengths[document.DocId]
  11.         indexer.docTokenLengths[document.DocId] = float32(document.TokenLength)
  12.         if found {
  13.             indexer.totalTokenLength += document.TokenLength - originalLength
  14.         } else {
  15.             indexer.totalTokenLength += document.TokenLength
  16.         }
  17.     } 
  18.     ...
  19.     ...
  20.     ...

 

查找新文档之后，进行搜索键的查找；

  1. docIdIsNew := true    for _, keyword := range document.Keywords {
  2.         indices, foundKeyword := indexer.tableLock.table[keyword.Text]
  3.         if !foundKeyword {
  4.             // 如果没找到该搜索键则加入
  5.             ti := KeywordIndices{}
  6.             switch indexer.initOptions.IndexType {
  7.             case types.LocationsIndex:
  8.                 ti.locations = [][]int{keyword.Starts}
  9.             case types.FrequenciesIndex:
  10.                 ti.frequencies = []float32{keyword.Frequency}
  11.             }
  12.             ti.docIds = []uint64{document.DocId}
  13.             indexer.tableLock.table[keyword.Text] = &ti
  14.             continue
  15.         }
  16.         // 查找应该插入的位置
  17.         position, found := indexer.searchIndex(
  18.             indices, 0, indexer.getIndexLength(indices)-1, document.DocId)
  19.         if found {
  20.             docIdIsNew = false
  21.             // 覆盖已有的索引项
  22.             switch indexer.initOptions.IndexType {
  23.             case types.LocationsIndex:
  24.                 indices.locations[position] = keyword.Starts
  25.             case types.FrequenciesIndex:
  26.                 indices.frequencies[position] = keyword.Frequency
  27.             }
  28.             continue
  29.         }

 

此处根据IndexType的选择进行代码的索引的插入项； 

  1. // 当索引不存在时，插入新索引项        
  2.        switch indexer.initOptions.IndexType {
  3.         case types.LocationsIndex:
  4.             indices.locations = append(indices.locations, []int{})
  5.             copy(indices.locations[position+1:], indices.locations[position:])
  6.             indices.locations[position] = keyword.Starts
  7.         case types.FrequenciesIndex:
  8.             indices.frequencies = append(indices.frequencies, float32(0))
  9.             copy(indices.frequencies[position+1:], indices.frequencies[position:])
  10.             indices.frequencies[position] = keyword.Frequency
  11.         }
  12.         indices.docIds = append(indices.docIds, 0)
  13.         copy(indices.docIds[position+1:], indices.docIds[position:])
  14.         indices.docIds[position] = document.DocId
  15.     }
  16.     // 更新文章总数
  17.     if docIdIsNew {
  18.         indexer.numDocuments++
  19.     }

 

其中，当搜索键是关键词和标签结合时，可以更加缩小搜寻范围；同时注意：标签并不在正文之中；其中以下代码中的copy(keywords[len(tokens):], labels)，我认为是否是copy(keywords[len(tokens)+1:], labels)？

  1. // 查找包含全部搜索键(AND操作)的文档// 当docIds不为nil时仅从docIds指定的文档中查找
  2. func (indexer *Indexer) Lookup(
  3.     tokens []string, labels []string, docIds *map[uint64]bool) (docs []types.IndexedDocument) {
  4.     if indexer.initialized == false {
  5.         log.Fatal("索引器尚未初始化")
  6.     }
  7.     if indexer.numDocuments == 0 {
  8.         return
  9.     }
  10.     // 合并关键词和标签为搜索键
  11.     keywords := make([]string, len(tokens)+len(labels))
  12.     copy(keywords, tokens)
  13.     copy(keywords[len(tokens):], labels)
  14.     indexer.tableLock.RLock()
  15.     defer indexer.tableLock.RUnlock()
  16.     table := make([]*KeywordIndices, len(keywords))
  17.     for i, keyword := range keywords {
  18.         indices, found := indexer.tableLock.table[keyword]
  19.         if !found {
  20.             // 当反向索引表中无此搜索键时直接返回
  21.             return
  22.         } else {
  23.             // 否则加入反向表中
  24.             table[i] = indices
  25.         }
  26.     }
  27.     // 当没有找到时直接返回
  28.     if len(table) == 0 {
  29.         return
  30.     }

 总结：

  • 以上代码的索引是为倒排索引的使用提供条件，倒排索引是根据单词à文档的模式即根据单词进行查  找包含单词的所有文档，同时映射了单词在相应的文档里的出现次数和位置信息；以上的代码功能简单的说明索引的前奏细节，接下来将要重点解析索引运用的方法；

  • 以上代码部分，个人理解是，在Golang语言中，为了避免代码编译时出现异常，应尽量采用err.Error()机制来进行避免，不知道是否妥当，以后在实践中需要注意；


 

 

转载于:https://my.oschina.net/u/1402946/blog/262391

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/知新_RL/article/detail/168352
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号