文档章节

对搜索引擎开源项目的代码分析——索引(2)

wxwei100
 wxwei100
发布于 2014/06/06 16:37
字数 2085
阅读 232
收藏 3

上文中已经分析了索引的一部分,接下来将继续学习索引的部分;

 

          // 归并查找各个搜索键出现文档的交集
	// 从后向前查保证先输出DocId较大文档
	indexPointers := make([]int, len(table))
	for iTable := 0; iTable < len(table); iTable++ {
		indexPointers[iTable] = indexer.getIndexLength(table[iTable]) - 1
	}
	// 平均文本关键词长度,用于计算BM25
	avgDocLength := indexer.totalTokenLength / float32(indexer.numDocuments)
	for ; indexPointers[0] >= 0; indexPointers[0]-- {
		// 以第一个搜索键出现的文档作为基准,并遍历其他搜索键搜索同一文档
		baseDocId := indexer.getDocId(table[0], indexPointers[0])
		if docIds != nil {
			_, found := (*docIds)[baseDocId]
			if !found {
				continue
			}
		}

本段代码中indexPointers类似指针并指向某个搜索键的对应文档索引项,同时在后续搜索引擎的搜索环节的排序自评分阶段将用到BM25(用于评比关键词和文档的相关情况),所以BM25将在搜索排序阶段给予详细的公式讲解;

        iTable := 1        found := true
        for ; iTable < len(table); iTable++ {
            // 二分法比简单的顺序归并效率高,也有更高效率的算法,
            // 但顺序归并也许是更好的选择,考虑到将来需要用链表重新实现
            // 以避免反向表添加新文档时的写锁。
            // TODO: 进一步研究不同求交集算法的速度和可扩展性。
            position, foundBaseDocId := indexer.searchIndex(table[iTable],
                0, indexPointers[iTable], baseDocId)
            if foundBaseDocId {
                indexPointers[iTable] = position
            } else {
                if position == 0 {
                    // 该搜索键中所有的文档ID都比baseDocId大,因此已经没有
                    // 继续查找的必要。
                    return
                } else {
                    // 继续下一indexPointers[0]的查找
                    indexPointers[iTable] = position - 1
                    found = false
                    break
                }
            }

 本段代码没有采用二分法算法进行查找DocId,就如注释说的那样,将来如采用链表实现,所以用顺序归并进行查找,相关网上有这方面的关于索引的二分法的查找,有兴趣的学习者,可以自行进行尝试实现;这里是以baseDocId为首选项进行查找的;

        if found {            indexedDoc := types.IndexedDocument{}
            // 当为LocationsIndex时计算关键词紧邻距离
            if indexer.initOptions.IndexType == types.LocationsIndex {
                // 计算有多少关键词是带有距离信息的
                numTokensWithLocations := 0
                for i, t := range table[:len(tokens)] {
                    if len(t.locations[indexPointers[i]]) > 0 {
                        numTokensWithLocations++
                    }
                }
                if numTokensWithLocations != len(tokens) {
                    docs = append(docs, types.IndexedDocument{
                        DocId: baseDocId,
                    })
                    break
                }
                // 计算搜索键在文档中的紧邻距离
                tokenProximity, tokenLocations := computeTokenProximity(table[:len(tokens)], indexPointers, tokens)
                indexedDoc.TokenProximity = int32(tokenProximity)
                indexedDoc.TokenSnippetLocations = tokenLocations
                // 添加TokenLocations
                indexedDoc.TokenLocations = make([][]int, len(tokens))
                for i, t := range table[:len(tokens)] {
                    indexedDoc.TokenLocations[i] = t.locations[indexPointers[i]]
                }
            }

所谓关键词紧邻距离是一种衡量文档和多个关键词相关度的方法。紧邻距离不能作为给文档排序的唯一指标,但是可以通过阀值可以过滤掉一部分的无关的结果;运用computeTokenProximity函数进行紧邻距离的计算;

            // 当为LocationsIndex或者FrequenciesIndex时计算BM25            if indexer.initOptions.IndexType == types.LocationsIndex ||
                indexer.initOptions.IndexType == types.FrequenciesIndex {
                bm25 := float32(0)
                d := indexer.docTokenLengths[baseDocId]
                for i, t := range table[:len(tokens)] {
                    var frequency float32
                    if indexer.initOptions.IndexType == types.LocationsIndex {
                        frequency = float32(len(t.locations[indexPointers[i]]))
                    } else {
                        frequency = t.frequencies[indexPointers[i]]
                    }
                    // 计算BM25
                    if len(t.docIds) > 0 && frequency > 0 && indexer.initOptions.BM25Parameters != nil && avgDocLength != 0 {
                        // 带平滑的idf
                        idf := float32(math.Log2(float64(indexer.numDocuments)/float64(len(t.docIds)) + 1))
                        k1 := indexer.initOptions.BM25Parameters.K1
                        b := indexer.initOptions.BM25Parameters.B
                        bm25 += idf * frequency * (k1 + 1) / (frequency + k1*(1-b+b*d/avgDocLength))
                    }
                }
                indexedDoc.BM25 = float32(bm25)
            }
            indexedDoc.DocId = baseDocId
            docs = append(docs, indexedDoc)
        }
    }
    return

计算BM25需要indexer.initOptions.IndexType = LocationsIndex或者FrequenciesIndex类型,同时本段代码运用BM25计算公式:

                IDF * TF * (k1 + 1)
BM25 = sum ----------------------------
           TF + k1 * (1 - b + b * D / L)

其中sum对所有关键词求和TFterm frequency为某关键词在该文档中出现的词频,D为该文档的词数L为所有文档的平均词数,k1和b为常数在悟空里默认值为2.0和0.75,不过可以在引擎初始化的时候IDFinverse document frequency衡量关键词是否常见悟空引擎使用带平滑的IDF公式

                   总文档数目
IDF = log2( ------------------------  + 1 )
              出现该关键词的文档数目
// 二分法查找indices中某文档的索引项// 第一个返回参数为找到的位置或需要插入的位置
// 第二个返回参数标明是否找到
func (indexer *Indexer) searchIndex(
    indices *KeywordIndices, start int, end int, docId uint64) (int, bool) {
    // 特殊情况
    if indexer.getIndexLength(indices) == start {
        return start, false
    }
    if docId < indexer.getDocId(indices, start) {
        return start, false
    } else if docId == indexer.getDocId(indices, start) {
        return start, true
    }
    if docId > indexer.getDocId(indices, end) {
        return end + 1, false
    } else if docId == indexer.getDocId(indices, end) {
        return end, true
    }
    // 二分
    var middle int
    for end-start > 1 {
        middle = (start + end) / 2
        if docId == indexer.getDocId(indices, middle) {
            return middle, true
        } else if docId > indexer.getDocId(indices, middle) {
            start = middle
        } else {
            end = middle
        }
    }
    return end, false
}

本段代码中使用了二分法进行索引项的查找,上面我们讲述了用顺序归并法的例子,在索引器type Indexer struct {}定义中,为了反向索引读写的安全,加了读写锁sync.RWMutex; 

// 假定第 i 个搜索键首字节出现在文本中的位置为 P_i,长度 L_i// 紧邻距离计算公式为
//
//     ArgMin(Sum(Abs(P_(i+1) - P_i - L_i)))
//
// 具体由动态规划实现,依次计算前 i 个 token 在每个出现位置的最优值。
// 选定的 P_i 通过 tokenLocations 参数传回。
func computeTokenProximity(table []*KeywordIndices, indexPointers []int, tokens []string) (
    minTokenProximity int, tokenLocations []int) {
    minTokenProximity = -1
    tokenLocations = make([]int, len(tokens))
    var (
        currentLocations, nextLocations []int
        currentMinValues, nextMinValues []int
        path                            [][]int
    )
    // 初始化路径数组
    path = make([][]int, len(tokens))
    for i := 1; i < len(path); i++ {
        path[i] = make([]int, len(table[i].locations[indexPointers[i]]))
    }
    // 动态规划
    currentLocations = table[0].locations[indexPointers[0]]
    currentMinValues = make([]int, len(currentLocations))
    for i := 1; i < len(tokens); i++ {
        nextLocations = table[i].locations[indexPointers[i]]
        nextMinValues = make([]int, len(nextLocations))
        for j, _ := range nextMinValues {
            nextMinValues[j] = -1
        }
        var iNext int
        for iCurrent, currentLocation := range currentLocations {
            if currentMinValues[iCurrent] == -1 {
                continue
            }
            for iNext+1 < len(nextLocations) && nextLocations[iNext+1] < currentLocation {
                iNext++
            }
            update := func(from int, to int) {
                if to >= len(nextLocations) {
                    return
                }
                value := currentMinValues[from] + utils.AbsInt(nextLocations[to]-currentLocations[from]-len(tokens[i-1]))
                if nextMinValues[to] == -1 || value < nextMinValues[to] {
                    nextMinValues[to] = value
                    path[i][to] = from
                }
            }
            // 最优解的状态转移只发生在左右最接近的位置
            update(iCurrent, iNext)
            update(iCurrent, iNext+1)
        }
        currentLocations = nextLocations
        currentMinValues = nextMinValues
    }
    // 找出最优解
    var cursor int
    for i, value := range currentMinValues {
        if value == -1 {
            continue
        }
        if minTokenProximity == -1 || value < minTokenProximity {
            minTokenProximity = value
            cursor = i
        }
    }
    // 从路径倒推出最优解的位置
    for i := len(tokens) - 1; i >= 0; i-- {
        if i != len(tokens)-1 {
            cursor = path[i+1][cursor]
        }
        tokenLocations[i] = table[i].locations[indexPointers[i]][cursor]
    }
    return
}

 本段代码中关于minTokenProximity = -1nextMinValues[j] = -1 对这个赋值,我难

以理解,同时难以理解的是为什么要进行update?功能没有理解明白;

            update := func(from int, to int) {                if to >= len(nextLocations) {
                    return
                }
                value := currentMinValues[from] + utils.AbsInt(nextLocations[to]-currentLocations[from]-len(tokens[i-1]))
                if nextMinValues[to] == -1 || value < nextMinValues[to] {
                    nextMinValues[to] = value
                    path[i][to] = from
                }
            }

  没看懂这个路径组在推出最有路径组方面的有何联系?

    // 初始化路径数组    path = make([][]int, len(tokens))
    for i := 1; i < len(path); i++ {
        path[i] = make([]int, len(table[i].locations[indexPointers[i]]))
    }

 根据公式,可以比较理解,就是计算文本中多个搜索键之间的最小离,特别是首先以其中一个搜索键为基准前提,逐次计算进行求和;

// 从KeywordIndices中得到第i个文档的DocIdfunc (indexer *Indexer) getDocId(ti *KeywordIndices, i int) uint64 {
    return ti.docIds[i]
}
// 得到KeywordIndices中文档总数
func (indexer *Indexer) getIndexLength(ti *KeywordIndices) int {
    return len(ti.docIds)
}

这段代码是进行的函数定义,是得到索引器里面的文档参数;

 

总结
     
    本文是后续的索引部分,相对而言比较难以理解,需要结合搜索排序部分,用到的索引方法比较多,索引的分词部分,将在单独的sego项目讲解到,利用了分词字典环节,索引部分还允许用户绕过悟空内置的分词器直接进行输入文档关键词,从而使得引擎外部分词成为可能;本文中出现一些比较重要和使用频繁的概念,比如:table数组,keyWordIndices,searchIndex等等,所以了解索引部分,了解概念内涵及其之间的联系是至关重要的;同时本文用到的公式比较多,这主要为后续的搜索的排序打分做铺垫的,在后面的学习中将要提及;
         本文最后提及的不理解的部分,暂时先进行搁置,在分析后面的部分再继续跟踪,也许也找到联系进而会有所悟;如果有了解的和懂的,可以在评论中给予指出;

 

 

 

 

 

© 著作权归作者所有

共有 人打赏支持
wxwei100
粉丝 7
博文 3
码字总数 4342
作品 0
浦东
全文检索——Lucene

简单介绍: 全文检索是一种将文件中所有文本与检索项匹配的文字资料检索方法。全文检索系统是按照全文检索理论建立起来的用于提供全文检索服务的软件系统。 像我们平时用的百度谷歌搜索引擎,...

邵鸿鑫
2016/06/24
0
0
【开源访谈】蚁坊软件平台部何小成:一个超大规模搜索引擎背后的故事

湖南蚁坊软件股份有限公司是一家高新技术企业,专业从事互联网大数据分析,专注于大数据信息的挖掘和价值传递。蚁坊软件拥有自主品牌的大数据服务云——蚁工厂(Antfact),日处理10亿多条实...

局长
2017/05/17
2.9K
10
ES(elasticsearch)搜索引擎安装和使用(windows And Linux)

大数据时代,搜索无处不在。搜索技术是全栈工程师必备技术之一,如今是开源时代,数不尽的资源供我们利用,如果要自己写一套搜索引擎无疑是浪费绳命。本节主要介绍搜索引擎开源项目elasticSe...

ZhangLG
09/17
0
0
ES(elasticsearch)搜索引擎安装和使用(windows And Linux)

大数据时代,搜索无处不在。搜索技术是全栈工程师必备技术之一,如今是开源时代,数不尽的资源供我们利用,如果要自己写一套搜索引擎无疑是浪费绳命。本节主要介绍搜索引擎开源项目elasticSe...

ZhangLG
09/17
0
0
对搜索引擎开源项目的代码分析——索引(1)

首先,需要对基本概念进行简单的介绍:Keywords:搜索键; tokens:关键词; 关键词(tokens)和标签(labels)组成了索引器中的搜索键(keywords) 1. 上文中,已经从微博上,抓取了相应的微博信...

wxwei100
2014/05/08
0
0

没有更多内容

加载失败,请刷新页面

加载更多

多线程

1. 多线程概念。并发和并行的概念。 多线程指的是一段时间内cpu同时执行多个线程。一个程序至少运行>=1个进程,进程就是运行中的程序,而一个进程至少运行>=1个线程,线程是操作系统能调度的...

鱼想吃肉
今天
0
0
HBase 表修复在线方式和离线方式

一、在线修复 1.1 使用检查命令 $ ./bin/hbase hbck 该命令可完整修复 HBase 元数据信息;存在有错误信息会进行输出; 也可以通过如下命令查看详细信息: $ ./bin/hbase hbck -details 1.2 ...

Ryan-瑞恩
今天
3
0
redis 系列二 -- 常用命令

1.基础命令 info ping quit save dbsize select flushdb flushall 2.键命令 2.1 set 直接赋值 set a a 2.2 get 取值 get a 2.3 exists 是否存在 exists a 2.4 expire 设置剩余时间 秒 expire......

imbiao
今天
2
0
php foreach

<?php// 数组的引用$a=array(1,2,3,4,5);foreach($a as $key=>&$value){$value=$value*2;}print_r($a);echo " $key -------------------$value\r\n";/** * ...

小张525
今天
3
0
12-利用思维导图梳理JavaSE-多线程

12-利用思维导图梳理JavaSE-多线程 主要内容 1.线程概念 2.线程开发 3.线程的状态 4.线程的同步和死锁 5.Java5.0并发库类 QQ/知识星球/个人WeChat/公众号二维码 本文为原创文章,如果对你有一...

飞鱼说编程
今天
2
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部