企业网站开发用什么语言写,网站建站基本要素,安卓小程序制作,属于网络营销的特点文章目录 #x1f4da;词项-文档关联矩阵#x1f407;相关名词#x1f407;词项-文档关联矩阵的布尔查询处理 #x1f4da;倒排索引#x1f407;关于索引#x1f407;建立索引#x1f407;基于倒排索引的布尔查询处理#x1f407;查询优化 #x1f4da;字典数据结构词项-文档关联矩阵相关名词词项-文档关联矩阵的布尔查询处理 倒排索引关于索引建立索引基于倒排索引的布尔查询处理查询优化 字典数据结构哈希表各种树B树 vs B树 短语查询及含位置信息的倒排记录二元词索引Biword indexes位置信息索引混合索引机制 基于跳表的倒排记录表快速合并算法 线性扫描是一种最简单的计算机文档检索方式这个过程通常称为grepping。在使用现代计算机的条件下对一个规模不大的文档集进行线性扫描非常简单根本不需要做额外的处理。但在1大规模文档集2更灵活的匹配方式3需要对结果进行排序的情况下就不能再用上边的线性扫描。一种非线性扫描的方式是事先给文档建立索引index。 词项-文档关联矩阵
相关名词
词项Term索引的单位通常用词来表示。文档Document检索系统的检索对象可以是单独的一条记录或者是一本书的各章。文档集/语料库collection/corpus所有文档的集合。词项-文档关联矩阵Term-document incidence matrices 从行看可以得到每个词项对应的文档向量表示词项在哪些文档出现或不出现。从列看可以得到每个文档对应的词项向量表示文档中哪些词项出现或不出现。 词项-文档关联矩阵的布尔查询处理
对于采用AND、OR及NOT等逻辑操作符连接起来的布尔表达式查询通过对文档向量间接逻辑操作来得到查询结果。例响应查询Brutus AND Caesar AND NOT Calpurnia结果向量中的第1和第4个元素为1这表明该查询对应的剧本是Antony and Cleo patra和Hamlet。 假设有50万个词项和100万篇文档所以其对应的词项-文档矩阵大概有5000亿个取布尔值的元素这远远大于一台计算机内存的容量。此外这个庞大的矩阵实际上具有高度的稀疏性即大部分元素都是0而只有极少部分元素为1。 也就是说对于词项个数和文档规模很大的情况构造出的关联矩阵是高度稀疏的。这时只记录原始矩阵中1的位置的表示方法比词项-文档关联矩阵更好。因此引出了倒排索引。
倒排索引
关于索引
索引Index由词项词典Dictionary和一个全体倒排记录表Postings组成。图 1-3 中的词典按照字母顺序进行排序而倒排记录表则按照文档ID号进行排序。
建立索引 预处理词语切分、词项归一化、词干还原与词形合并、去除停用词 构建倒排索引 给每篇文章的所有词项加上文档ID。 按照字母顺序排序。 将同一词项合并并将词项和文档ID分开存储。 在字典的每个词项中还可以存储其他信息如文档频率。 每个倒排记录表存储了词项出现的文档列表还可以存储词项频率、词项在文档中出现的位置。
基于倒排索引的布尔查询处理 求两个倒排记录表交集的合并算法
我们对每个有序列表都维护一个位置指针并让两个指针同时在两个列表中后移。该算法对于倒排记录表集即待合并的两个倒排记录表的大小而言是线性的。每一步我们都比较两个位置指针所指向的文档 ID如果两者一样则将该 ID 输出到结果表中然后同时将两个指针后移一位。如果两个文档 ID不同则将较小的 ID 所对应的指针后移。假设两个倒排记录表的大小分别是 x 和 y那么上述求交集的过程需要 O ( x y ) O(xy) O(xy)次操作也即查询的时间复杂度为 Θ ( N ) Θ(N) Θ(N)其中 N 是文档集合中文档的数目。 和线性扫描相比这种索引方法并没有带来Θ意义上时间复杂度的提高而最多只是一个常数级别的变化。但是实际当中这个常数很大。 查询优化
对每个词项我们必须取出其对应的倒排记录表然后将它们合并。一个启发式的想法是按照词项的文档频率也就是倒排记录表的长度从小到大依次进行处理如果我们先合并两个最短的倒排记录表那么所有中间结果的大小都不会超过最短的倒排记录表这是因为多个集合的交集元素个数肯定不大于其中任何一个集合的元素个数 这样处理所需要的工作量很可能最少。 布尔查询适合精确查询。
字典数据结构 Two main choices——Hashtables、Trees 哈希表
数据结构 | 第十章散列表 | 字典 | 线性探查 | 链式散列 | LZW编码
各种树
数据结构可视化网站
数据结构 | 第十一章二叉树和其他树 | 【前序遍历】【中序遍历】【后序遍历】【层次遍历】 | 并查集 数据结构 | 第十二章优先级队列 | 堆 | 左高树 | 堆排序 | 霍夫曼编码 数据结构 | 第十四章搜索树 | 二叉搜索树的查找、插入、删除 数据结构 | 第十五章平衡搜索树——AVL树 | AVL树的搜索、插入、删除 数据结构 | 第十五章平衡搜索树——B-树 | B-树的搜索、插入、删除 B树 vs B树 B树 B树 B树和B树相比的主要区别 B树所有关键码都在叶子节点B树的叶子节点是带有指针的且叶节点本身按关键码从小到大顺序连接在搜索过程中如果查询和内部节点的关键字一致那么搜索过程不停止而是继续向下搜索这个分支。因此在B树中不管查找成功与否每次查找都是走了一条从根到叶子结点的路径。 B树在文件系统、数据库系统当中更有优势更高效。 B树更有利于对数据库的扫描 因为所有元素都在叶子节点上。B树的查询效率更加稳定 B树最后就是要找到叶子节点每次查找都是走了一条从根到叶子结点的路径。B树没有像B树一样把一些关键码每层都放一部分之间存在互相之间的关系。在考虑指针指向内容上B树没有这些要存反而数据量大的情况的占的空间要比B树小。
短语查询及含位置信息的倒排记录
二元词索引Biword indexes
对文档中每个接续词对Biword看成词项这样马上就能处理两个词构成的短语查询。更长的查询可以分成多个短查询来处理。比如按照上面的方法可以将查询 stanford university palo alto分成如下的布尔查询“stanford university” AND “university palo” AND “palo alto”。可以期望该查询在实际中效果会不错但是偶尔也会有错误的返回例子。对于该布尔查询返回的文档我们并不知道其是否真正包含最原始的四词短语。
位置信息索引
在位置信息索引positional index中对于每个词项以如下方式存储倒排记录 短语查询处理 同样类似的方法可以用于 k 词近邻搜索当中employment /3 place 这里/k 意味着“ 从左边或右边相距在 k 个词之内” 。很显然位置索引能够用于邻近搜索而二元词索引则不能。 混合索引机制
二元词索引和位置索引这两种策略可以进行有效的合并。假如用户通常只查询特定的短语如Michael Jackson那么基于位置索引的倒排记录表合并方式效率很低。一个混合策略是对某些查询使用短语索引或只使用二元词索引而对其他短语查询则采用位置索引。短语索引所收录的那些较好的查询可以根据用户最近的访问行为日志统计得到也就是说它们往往是那些高频常见的查询。
基于跳表的倒排记录表快速合并算法
跳表skip list在构建索引的同时在倒排记录表上建立跳表。跳表指针能够提供捷径来跳过那些不可能出现在检索结果中的记录项。 在什么位置上放置跳表指针 跳表指针越多意味着跳跃的步长越短那么在合并过程中跳跃的可能性也更大但同时这也意味着需要更多的指针比较次数和更多的存储空间。跳表指针越少意味着更少的指针比较次数但同时也意味着更长的跳跃步长也就是说意味着更少的跳跃机会。 放置跳表指针位置的一个简单的启发式策略在每个 P \sqrt{P} P 处均匀放置跳表指针其中 P P P 是倒排记录表的长度。这个策略在实际中效果不错但是仍然有提高的余地因为它并没有考虑查询词项的任何分布细节。如果索引相对固定的话建立有效的跳表指针则比较容易。但是如果倒排记录表由于经常更新而发生变化那么跳表指针的建立就比较困难。恶意的删除策略可能会使跳表完全失效。 参考博客
B树和B树的区别
