搜索引擎倒排索引表压缩:gamma编码、Golomb编码

2023-12-04 11:08

本文主要是介绍搜索引擎倒排索引表压缩:gamma编码、Golomb编码,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

搜索引擎的倒排索引表所占的空间很大,对倒排索引表进行压缩显得非常必要。由于倒排索引表中存储的全部都是数字,对其进行压缩有着专门的方法,Gamma编码就是其中之一。

当你每天打开电脑,在百度搜索框中输入你要搜索的内容,按下回车之后,你可能不会意识到,有无数台主机在飞速运转,对比了数百万条记录,经过初步结果集生成、相关度打分、结果排序、摘要生成之后,才最终在你的屏幕上打出了你想要的结果。这一切仅仅发生在几毫秒之间。
是什么保证了如此迅速的检索速度呢?良好的索引构建是其中的要素之一。通常情况下,搜索引擎内部会为每个网页或文章分配一个数字id,用这个id代表这个网页或者文章。构建索引的时候,采用分词工具将这些网页或者文章分成一个个词,并网页id存储在称为倒排索引表的数据结构中。

由于网络空间巨大,对应的倒排索引表所占的空间也很大,对倒排索引表进行压缩显得非常必要。由于倒排索引表中存储的全部都是数字,对其进行压缩有着专门的方法,Gamma和Golomb编码就是其中的两种。
1、Gamma编码
Gamma编码是一种基于位的变长编码,介绍它之前先说一下一元编码。
一元编码:将 n 表示成 n 个1和最后一个0,,
比如: 3的一元码是 1110
40的一元码是 11111111111111111111111111111111111111110

Gamma将数G字表示成长度(length)和偏移(offset)两部分;
offset部分对应G的二进制编码,只不过将首部的1去掉。
例如 13 → 1101 → 101 = 偏移;
length部分采用一元编码,表示偏移部分的位数。
例如G=13(偏移101),偏移长度为3,一元编码1110
G的编码就是将长度部分和偏移部分两者联接起来得到的结果。

2、Golomb编码
使用Golomb编码对整数x(x≥0)进行编码时,通过参数m(m≥1)将x分解为:

x=q*m+r

其中,q为x除以m的商,r为余数。Golomb编码即有q和r两部分组成,q用上面提到的一元编码表示,如,3表示为1110;如果用b=log2(m),对b向上取整;t=2^b-m,r的表示分两种情况:
(1)当0≤ r< t时,用b-1位二进制编码表示r;
(2)当t≤ r< m时,用b位二进制编码表示r+t;
例如:取整数18,m=5,18=3*5+3;q=3,r=3
b=log2(5),向上取整为3,t=2^3-m=3=r,选第二种情况编码r,
故x可编码为1110:110.

这篇关于搜索引擎倒排索引表压缩:gamma编码、Golomb编码的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/453235

相关文章

一文详解SpringBoot响应压缩功能的配置与优化

《一文详解SpringBoot响应压缩功能的配置与优化》SpringBoot的响应压缩功能基于智能协商机制,需同时满足很多条件,本文主要为大家详细介绍了SpringBoot响应压缩功能的配置与优化,需... 目录一、核心工作机制1.1 自动协商触发条件1.2 压缩处理流程二、配置方案详解2.1 基础YAML

Python实现将MySQL中所有表的数据都导出为CSV文件并压缩

《Python实现将MySQL中所有表的数据都导出为CSV文件并压缩》这篇文章主要为大家详细介绍了如何使用Python将MySQL数据库中所有表的数据都导出为CSV文件到一个目录,并压缩为zip文件到... python将mysql数据库中所有表的数据都导出为CSV文件到一个目录,并压缩为zip文件到另一个

VSCode中C/C++编码乱码问题的两种解决方法

《VSCode中C/C++编码乱码问题的两种解决方法》在中国地区,Windows系统中的cmd和PowerShell默认编码是GBK,但VSCode默认使用UTF-8编码,这种编码不一致会导致在VSC... 目录问题方法一:通过 Code Runner 插件调整编码配置步骤方法二:在 PowerShell

Mysql中InnoDB与MyISAM索引差异详解(最新整理)

《Mysql中InnoDB与MyISAM索引差异详解(最新整理)》InnoDB和MyISAM在索引实现和特性上有差异,包括聚集索引、非聚集索引、事务支持、并发控制、覆盖索引、主键约束、外键支持和物理存... 目录1. 索引类型与数据存储方式InnoDBMyISAM2. 事务与并发控制InnoDBMyISAM

StarRocks索引详解(最新整理)

《StarRocks索引详解(最新整理)》StarRocks支持多种索引类型,包括主键索引、前缀索引、Bitmap索引和Bloomfilter索引,这些索引类型适用于不同场景,如唯一性约束、减少索引空... 目录1. 主键索引(Primary Key Index)2. 前缀索引(Prefix Index /

Python如何实现读取csv文件时忽略文件的编码格式

《Python如何实现读取csv文件时忽略文件的编码格式》我们再日常读取csv文件的时候经常会发现csv文件的格式有多种,所以这篇文章为大家介绍了Python如何实现读取csv文件时忽略文件的编码格式... 目录1、背景介绍2、库的安装3、核心代码4、完整代码1、背景介绍我们再日常读取csv文件的时候经常

MySQL进阶之路索引失效的11种情况详析

《MySQL进阶之路索引失效的11种情况详析》:本文主要介绍MySQL查询优化中的11种常见情况,包括索引的使用和优化策略,通过这些策略,开发者可以显著提升查询性能,需要的朋友可以参考下... 目录前言图示1. 使用不等式操作符(!=, <, >)2. 使用 OR 连接多个条件3. 对索引字段进行计算操作4

Python利用PIL进行图片压缩

《Python利用PIL进行图片压缩》有时在发送一些文件如PPT、Word时,由于文件中的图片太大,导致文件也太大,无法发送,所以本文为大家介绍了Python中图片压缩的方法,需要的可以参考下... 有时在发送一些文件如PPT、Word时,由于文件中的图片太大,导致文件也太大,无法发送,所有可以对文件中的图

Java实现Elasticsearch查询当前索引全部数据的完整代码

《Java实现Elasticsearch查询当前索引全部数据的完整代码》:本文主要介绍如何在Java中实现查询Elasticsearch索引中指定条件下的全部数据,通过设置滚动查询参数(scrol... 目录需求背景通常情况Java 实现查询 Elasticsearch 全部数据写在最后需求背景通常情况下

Pandas中多重索引技巧的实现

《Pandas中多重索引技巧的实现》Pandas中的多重索引功能强大,适用于处理多维数据,本文就来介绍一下多重索引技巧,具有一定的参考价值,感兴趣的可以了解一下... 目录1.多重索引概述2.多重索引的基本操作2.1 选择和切片多重索引2.2 交换层级与重设索引3.多重索引的高级操作3.1 多重索引的分组聚