文档章节

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

wxwei100
 wxwei100
发布于 2014/06/06 16:37
字数 2085
阅读 240
收藏 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
3.2K
10
ES(elasticsearch)搜索引擎安装和使用(windows And Linux)

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

ZhangLG
2018/09/17
0
0
Elastic 今日在纽交所上市,股价最高暴涨122%。

10 月 6 日,Elastic 正式在纽约证券交易所上市,股票代码为"ESTC"。开盘之后股价直线拉升,最高点涨幅达122%,截止到收盘涨幅回落到94%,意味着上市第一天估值接近翻倍。 该公司最初位于阿姆...

纯洁的微笑
2018/10/08
0
0
当大数据遇见 Hadoop

一些组织将“人力资本”视为无形资产,这是其成功的关键因素,它们大多认为员工 是其最宝贵的财富。另一个通常不会在公司资产负债表上列出的关键资产就是公司所拥有 的信息。一些因素能够加强...

超人学院
2016/07/21
28
0

没有更多内容

加载失败,请刷新页面

加载更多

发布xxl-job executor dotnet core 执行器的实现

DotXxlJob [github][https://github.com/xuanye/DotXxlJob] xxl-job的dotnet core 执行器实现,支持XXL-JOB 2.0+ 1 XXL-JOB概述 [XXL-JOB][1]是一个轻量级分布式任务调度平台,其核心设计目标...

假正经哥哥
今天
2
0
mysql 查询当天、本周,本月,上一个月的数据

今天 select * from 表名 where to_days(时间字段名) = to_days(now()); 昨天 SELECT * FROM 表名 WHERE TO_DAYS( NOW( ) ) - TO_DAYS( 时间字段名) <= 1 近7天 SELECT * FROM 表名 wher......

BraveLN
今天
3
0
Spring 事务初始化源码分析

相关文章 Spring 事务使用详解 Spring AOP 创建代理的源码解析 Spring AOP 注解方式源码解析 Spring AOP 功能使用详解 Spring 的 getBean 方法源码解析 Spring bean 创建过程源码解析 Spring...

TSMYK
今天
1
0
Android Multimedia框架总结(六)C++中MediaPlayer的C/S架构

前面几节中,都是通过java层调用到jni中,jni向下到c++层并未介绍 看下Java层一个方法在c++层 MediaPlayer后续过程 frameworks/av/media/libmedia/MediaPlayer.cpp 找一个我们之前熟悉的setDa...

天王盖地虎626
今天
3
0
【Linux】【MySQL】CentOS7安装最新版MySQL8.0.13(最新版MySQL从安装到运行)

1、前言   框框博客在线报时:2018-11-07 19:31:06   当前MySQL最新版本:8.0.13 (听说比5.7快2倍)   官方之前表示:MySQL 8.0 正式版 8.0.11 已发布,MySQL 8 要比 MySQL 5.7 快 2 ...

Code辉
今天
5
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部