文档章节

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

wxwei100
 wxwei100
发布于 2014/06/06 16:37
字数 2085
阅读 229
收藏 3
点赞 0
评论 0

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

 

          // 归并查找各个搜索键出现文档的交集
	// 从后向前查保证先输出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
开源企业搜索起点R3发布新版官网

国内第一家开源企业级搜索厂商起点软件近日发布其5.1新版产品,引入实时搜索功能,源码现已可以下载,并启用新版官方网站和多个商用支持服务,同时面向全国诚招OEM合作伙伴和行业合作伙伴,详...

R3商业智能
2011/03/30
1K
2
当大数据遇见 Hadoop

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

超人学院
2016/07/21
28
0
对搜索引擎开源项目的代码分析——索引(1)

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

wxwei100
2014/05/08
0
0
一共81个,开源大数据处理工具汇总(下),包括日志收集系统/集群管理/RPC等

作者:大数据女神-诺蓝(微信公号:dashujunvshen)。本文是36大数据专稿,转载必须标明来源36大数据。 接上一部分:一共81个,开源大数据处理工具汇总(上),第二部分主要收集整理的内容主...

片刻
2016/04/28
370
0
81个开源大数据处理工具汇总(下),包括日志收集系统/集群管理/RPC等

上一部分:http://my.oschina.net/u/2391658/blog/711016 第二部分主要收集整理的内容主要有日志收集系统、消息系统、分布式服务、集群管理、RPC、基础设施、搜索引擎、Iaas和监控管理等大数...

孟飞阳
2016/07/13
86
0
开源大数据处理工具汇总(下)

作者:大数据女神-诺蓝(微信公号:dashujunvshen)。本文是36大数据专稿,转载必须标明来源36大数据。 接上一部分:一共81个,开源大数据处理工具汇总(上),第二部分主要收集整理的内容主...

openthings
2016/01/05
258
0
NUTCH公开课:从搜索引擎到网络爬虫

课程背景:Nutch诞生于2002年8月,是Apache旗下的一个用Java实现的开源搜索引擎项目,自Nutch1.2版本之后,Nutch已经从搜索引擎演化为网络爬虫,接着Nutch进一步演化为两大分支版本:1.X和2...

杨尚川
2013/09/12
3.3K
1
Apache Solr:基于Lucene的可扩展集群搜索服务器

Solr Solr是一个独立的企业级搜索应用服务器,它对外提供类似于Web-service的API接口。用户可以通过http请求,向搜索引擎服务器提交一定格式的XML文件,生成索引;也可以通过Http Get操作提出...

长平狐
2013/01/06
206
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

Win10专业版安装GIT后使用Git Bash闪退解决办法

百度后把过程和最终解决办法记录下来: 百度首先出来的解决办法如下: 来自:https://segmentfault.com/q/1010000012722511?sort=created 重启电脑 重新安装 安装到C盘 尝试网上的教程 \Git...

特拉仔
14分钟前
0
0
设计模式

1.装饰器模式 概念 允许向一个现有的对象添加新的功能,同时又不改变其结构。装饰者可以在所委托被装饰者的行为之前或之后加上自己的行为,以达到特定的目的。 实现 增加一个修饰类包裹原来的...

EasyProgramming
28分钟前
1
0
用python2和opencv进行人脸识别

一、安装cv2 sudo apt-get install python-opencv opencv-data 二、 Haar特征分类器 Haar特征分类器就是一个XML文件,该文件中会描述人体各个部位的Haar特征值。包括人脸、眼睛、嘴唇等等。 ...

wangxuwei
28分钟前
0
0
python模板中循环字典

{% for k,v in user.items %} {{ k}} {{ v}} {% endfor %}

南桥北木
57分钟前
0
0
Java8系列之重新认识HashMap

简介 Java为数据结构中的映射定义了一个接口java.util.Map,此接口主要有四个常用的实现类,分别是HashMap、Hashtable、LinkedHashMap和TreeMap,类继承关系如下图所示: 下面针对各个实现类...

HOT_POT
今天
0
0
获取调用方的className

/** * 获取调用方的class * @return */private static String getInvoke() { StackTraceElement[] stackTrace = Thread.currentThread().getStackTrace(); S......

iborder
今天
0
0
深入了解一下Redis的内存模型!

一前言 Redis是目前最火爆的内存数据库之一,通过在内存中读写数据,大大提高了读写速度,可以说Redis是实现网站高并发不可或缺的一部分。 我们使用Redis时,会接触Redis的5种对象类型(字符...

Java填坑之路
今天
1
0
从实践出发:微服务布道师告诉你Spring Cloud与Spring Boot他如何选择

背景 随着公司业务量的飞速发展,平台面临的挑战已经远远大于业务,需求量不断增加,技术人员数量增加,面临的复杂度也大大增加。在这个背景下,平台的技术架构也完成了从传统的单体应用到微...

老道士
今天
1
0
大数据学习的各个阶段

第一阶段:Linux课程讲解Linux基础操作,讲的是在命令行下进行文件系统的操作,这是Hadoop学习的基础,后面的所有视频都是基于linux操作的。鉴于很多学员没有linux基础,特增加该内容,保证零linux...

董黎明
今天
0
0
CVE-2013-0077 堆溢出分析

找了很久才发现这个环境比较容易搭建分析... 环境: 系统---Win XP SP3 漏洞程序:QQPlayer 3.7.892.400 出错DLL:quartz.dll 6.5.2600.5512 调试工具:x32db+gflag.exe 过程: 首先gflag设置...

Explorer0
今天
7
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部