966,690 十二月 独立访问用户
语言 & 开发
架构 & 设计
文化 & 方法
您目前处于：
基于Lucene的分布式搜索引擎: Elasticsearch 1.3.0发布
基于Lucene的分布式搜索引擎: Elasticsearch 1.3.0发布
欲知区块链、VR、TensorFlow等潮流技术和框架，请锁定
Author Contacted
相关厂商内容
告诉我们您的想法
允许的HTML标签: a,b,br,blockquote,i,li,pre,u,ul,p
当有人回复此评论时请E-mail通知我
允许的HTML标签: a,b,br,blockquote,i,li,pre,u,ul,p
当有人回复此评论时请E-mail通知我
允许的HTML标签: a,b,br,blockquote,i,li,pre,u,ul,p
当有人回复此评论时请E-mail通知我
赞助商链接
架构 & 设计
文化 & 方法
<及所有内容，版权所有 &#169;
C4Media Inc.
服务器由 提供, 我们最信赖的ISP伙伴。
北京创新网媒广告有限公司
京ICP备号-7
注意：如果要修改您的邮箱，我们将会发送确认邮件到您原来的邮箱。
使用现有的公司名称
修改公司名称为：
公司性质：
使用现有的公司性质
修改公司性质为:
使用现有的公司规模
修改公司规模为：
使用现在的国家
使用现在的省份
Subscribe to our newsletter?
Subscribe to our industry email notices?
我们发现您在使用ad blocker。
我们理解您使用ad blocker的初衷，但为了保证InfoQ能够继续以免费方式为您服务，我们需要您的支持。InfoQ绝不会在未经您许可的情况下将您的数据提供给第三方。我们仅将其用于向读者发送相关广告内容。请您将InfoQ添加至白名单，感谢您的理解与支持。Elasticsearch最新版本2.20特性及如何安装-爱编程
Elasticsearch最新版本2.20特性及如何安装
版本选择：Elasticsearch最新版本2.20
&&&&Elasticsearch的更新速度实在太快了，16年2月2日更新到了2.2版本，首先看一下这个版本增加了哪些新的特性。首先是基于Lucene 5.4.1，修复了Elasticsearch 2.1.2和Elasticsearch 1.7.5版本中存在的很多bug，同时Elasticsearch 2.2.0增加了两个很棒的新功能：查询分析器和增强地理位置字段。这个版本增加了更加严格的安全性和修复了2.1的一个重大bug，就是在分片恢复的时候会非常缓慢。以及许多其他的错误修复和改进。官方鼓励所有用户升级到此版本。
&&&&分析器(Profile API)
& & 利用分析器可以得到查询的详细分析信息，它可以让你了解和调试查询性能。查询的每一部分都独立的记录了统计时间，如多长时间重写查询，找到匹配的文档以及他们的得分情况。这个当查询慢的时候就不需要进行猜测为什么这么慢：只要设置profile这个参数为true，你就可以得到最直接的深入的查询分析。
&&&&增强地理位置字段
&&&&地理位置字段在2.20版本中几乎进行了从写，它利用一个新的紧凑型数据结构存储在Lucene的索引中，可以增加50%的入库效率，&20-50%的查询效率，一半的存储空间和内存的占用以及更简单的映射参数。
&&&&对插件和脚本进行更严格的安全性检查
&&&&作为安全增强的一部分，Groovy和Lucene的表达式脚本语言已经移出了核心层，现在把他们作为默认的分布式模块的插件。这样的调整可以控制这些模块的权限，已减少黑客的攻击，Elasticsearch的核心模块在未来将会更多的进行模块化处理。脚本语言，现在预定义提供一个白名单列表，这些脚本不能读写文件，不能打开远程的连接。默认情况下，都不准许插件有特殊权限，否则必须事先声明这些权限。同时在插件安装时将会被警告有特殊权限的要求，这个时候你可以根据需要确认是否移除这些插件。
&&&&本文由赛克蓝德(secisland)原创，转载请标明作者和出处。
&&&&Elasticsearch安装至少需要Java 7的支持。最新的版本建议使用Oracle的JDK版本1.8.0_72。如需了解Java的情况，可以到oracle的官网找相关的资料。在你安装Elasticsearch前，请检查您的Java版本运行：
&&&&java -version
&&&&当我们设置好Java后，我们可以下载最新的版本。下载地址：https://www.elastic.co/downloads/past-releases/elasticsearch-2-2-0。
&&&&下载完成后直接解压。然后到cd elasticsearch-2.2.0/bin目录。
&&在windows下执行elasticsearch.bat，在linux下运行./elasticsearch。
& 如果一切顺利的话，你应该看到一堆像下面这样的信息：
[&16:53:31,122][INFO&][node&&&&&&&&&&&&&&&&&&&&&]&[Rintrah]&version[2.2.0],&pid[6840],&build[8ff36d1/T13:32:39Z]
[&16:53:31,122][INFO&][node&&&&&&&&&&&&&&&&&&&&&]&[Rintrah]&initializing&...
[&16:53:31,668][INFO&][plugins&&&&&&&&&&&&&&&&&&]&[Rintrah]&modules&[lang-groovy,&lang-expression],&plugins&[],&sites&[]
[&16:53:31,684][INFO&][env&&&&&&&&&&&&&&&&&&&&&&]&[Rintrah]&using&[1]&data&paths,&mounts&[[work&(D:)]],&net&usable_space&[67.2gb],&net&total_space&[99.9gb],&spins?&[unknown],&types&[NTFS]
[&16:53:31,684][INFO&][env&&&&&&&&&&&&&&&&&&&&&&]&[Rintrah]&heap&size&[910.5mb],&compressed&ordinary&object&pointers&[true]
[&16:53:33,637][INFO&][node&&&&&&&&&&&&&&&&&&&&&]&[Rintrah]&initialized
[&16:53:33,637][INFO&][node&&&&&&&&&&&&&&&&&&&&&]&[Rintrah]&starting&...
[&16:53:33,918][INFO&][transport&&&&&&&&&&&&&&&&]&[Rintrah]&publish_address&{127.0.0.1:9300},&bound_addresses&{[::1]:9300},&{127.0.0.1:9300}
[&16:53:33,934][INFO&][discovery&&&&&&&&&&&&&&&&]&[Rintrah]&elasticsearch/1oo5dtelT8ax-3LmnTrs8g
[&16:53:37,982][INFO&][cluster.service&&&&&&&&&&]&[Rintrah]&new_master&{Rintrah}{1oo5dtelT8ax-3LmnTrs8g}{127.0.0.1}{127.0.0.1:9300},&reason:&zen-disco-join(elected_as_master,&[0]&joins&received)
[&16:53:40,363][INFO&][gateway&&&&&&&&&&&&&&&&&&]&[Rintrah]&recovered&[0]&indices&into&cluster_state
[&16:53:40,567][INFO&][http&&&&&&&&&&&&&&&&&&&&&]&[Rintrah]&publish_address&{127.0.0.1:9200},&bound_addresses&{[::1]:9200},&{127.0.0.1:9200}
[&16:53:40,567][INFO&][node&&&&&&&&&&&&&&&&&&&&&]&[Rintrah]&started
&&&&这样我们就已经启动了Elasticsearch，当然我们也可以在启动的时候修改集群的名称和节点的名称。例如：
./elasticsearch --cluster.name my_cluster_name --node.name my_node_name
& 默认情况下，Elasticsearch使用9200端口提供的REST API。该端口是可配置的。
&&&&在本机访问http://127.0.0.1:9200/
&&&&将会得到一下内容：
&&"name"&:&"Rintrah",
&&"cluster_name"&:&"elasticsearch",
&&"version"&:&{
&&&&"number"&:&"2.2.0",
&&&&"build_hash"&:&"8ff36d139e16fef62cfe",
&&&&"build_timestamp"&:&"T13:32:39Z",
&&&&"build_snapshot"&:&false,
&&&&"lucene_version"&:&"5.4.1"
&&"tagline"&:&"You&Know,&for&Search"
&&&&现在，我们有我们的节点（和集群）将争取的运行，下一步就是要了解如何进行使用。Elasticsearch提供了非常全面和强大的REST API，通过这些API，我们可以了解集群的信息。这些API可以做如下事情：
1、检查群集，节点和索引的情况，状态和统计
2、管理群集、节点和索引数据和文档数据
3、执行CRUD（创建，读取，更新和删除）操作，可以对索引进行操作
4、执行高级搜索操作如分页、排序、过滤、脚本、聚合及其他操作。
赛克蓝德(secisland)后续会逐步对Elasticsearch的最新版本的各项功能进行分析，近请期待。
版权所有 爱编程 (C) Copyright 2012. . All Rights Reserved.
闽ICP备号-3
微信扫一扫关注爱编程，每天为您推送一篇经典技术文章。本帖最后由 yr123 于
15:47 编辑
1、了解定长编码、差值编码、一元编码、Elias Gamma编码、Elias Delta编码、哈夫曼编码、Golomb编码、 插值编码。
1. 定长编码
最容易想到的方式就是常用的普通二进制编码，每个数值占用的长度相同，都占用最大的数值所占用的位数，如图所示。
1.png (11.92 KB, 下载次数: 2)
15:16 上传
这里有一个文档ID列表，254,507,756,1007，如果按照二进制定长编码，需要按照最大值1007所占用的位数10位进行编码，每个数字都占用10位。
和词典的格式设计中顺序列表方式遇到的问题一样，首先的问题就是空间的浪费，本来254这个数值8位就能表示，非得也用上10位。另外一个问题是随着索引文档的增多，谁也不知道最长需要多少位才够用。
2. 差值(D-gap)编码
看过前面前端编码的读者可能会想到一个类似的方法，就是我们可以保存和前一个数值的差值，如果Term在文档中分布比较均匀(差不多每隔几篇就会包含某个Term)，文档ID之间的差别都不是很大，这样每个数值都会小很多，所用的位数也就节省了，如图所示。
2.png (14.79 KB, 下载次数: 2)
15:16 上传
还是上面的例子中，我们可以看到，这个Term在文档中的分布还是比较均匀的，每隔差不多250篇文档就会出现一次这个Term，所以计算差值的结果比较理想，得到下面的列表254,253,249,251，每个都占用8位，的确比定长编码节省了空间。
然而Term在文档中均匀分布的假设往往不成立，很多词汇很可能是聚集出现的，比如奥运会，世界杯等相关的词汇，在一段时间里密集出现，然后会有很长时间不被提起，然后又出现，如果索引的新闻网页是安装抓取先后来编排文档ID的情况下，很可能出现图所示的情况。
3.png (20.79 KB, 下载次数: 2)
15:16 上传
在很早时间第10篇文档出现过这个Term，然后相关的文档沉寂了一段时间，然后在第1000篇的时候密集出现。如果使用差值编码，得到序列10,990,21,1，虽然很多值已经被减小了，但是由于前两篇文档的差值为990，还是需要10位进行编码，并没有节省空间。
3. 一元编码(unary)
有人可能会问了，为什么要用最大的数值所占用的位数啊，有几位咱们就用几位嘛。这种思想就是变长编码，也即每个数值所占用的位数不同。然而说的容易做起来难，定长编码模式下，每读取b个bit就是一个数值，某个数值从哪里开始，读取到哪里结束，都一清二楚，然而对于变长编码来说就不是了，每个数值的长度都不同，那一连串二进制读出来，读到哪里算一个数值呢？比如上面的例子中，10和990的二进制连起来就是10，那到底1010是一个数值，是另一个数值呢，还是1010111是一个数值，剩下的1011110算另一个数值呢？另外就是会不会产生歧义呢？比如一个数值A=0011是另一个数值B=00111的前缀，那么当二进制中出现00111的时候，到底是一个数值A，最后一个1属于下一个数值呢，还是整个算作数值B呢？这都是变长编码所面临的问题。当然还有错了一位，多了一位，丢掉一位导致整个编码都混乱的问题，可以通过各种校验方法来保证，不在本文的讨论范围内，本文仅仅讨论假设完全正确的前提下，如何编码和解码。
最简单的变长编码就是一元编码，它的规则是这样的：对于正整数x，用x-1个1和末尾一个0来表示。比如5，用11110表示。这种编码方式对于小数值来讲尚可，对于大数值来讲比较恐怖，比如1000需要用999个1外加一个0来表示，这哪里是压缩啊，分明是有钱没处使啊。但是不要紧，火车刚发明出来的时候还比马车慢呢。这种编码方式虽然初级，但是很好的解决了上面两个问题。读到哪里结束呢？读到出现0了，一个数值就结束了。会不会出现歧义呢？没有一个数值是另一个数值的前缀，当然没有歧义了。所以一元编码成为很多变长编码的基础。
4. Elias Gamma编码
Gamma编码的规则是这样的：对于正整数x，首先对于
1.1.png (510 Bytes, 下载次数: 2)
15:38 上传
进行一元编码，然后
1.2.png (451 Bytes, 下载次数: 2)
15:38 上传
1.3.png (502 Bytes, 下载次数: 2)
15:38 上传
进行二进制编码。
比如对于正整数10，
1.4.png (578 Bytes, 下载次数: 2)
15:38 上传
，对于4进行一元编码1110，计算
1.5.png (622 Bytes, 下载次数: 2)
15:38 上传
，用3个bit进行编码010，所以最后编码为1110010。
可以看出，Gamma编码综合了一元编码和二进制编码，对于第一部分一元编码的部分，可以知道何时结束并且无歧义编码，对于二进制编码的部分，由于一元编码部分指定了二进制部分的长度，因而也可以知道何时结束并无歧义解码。
比如读取上述编码，先读取一系列1，到0结束，得到1110，是一元编码部分，值为4，所以后面3个bit是二进制部分，读取下面的3个bit(即便这3个bit后面还有些0和1，都不是这个数值的编码了)，010，值为2，最后
1.6.png (459 Bytes, 下载次数: 2)
15:38 上传
，解码成功。
Gamma编码比单纯的一元编码好的多，对于小的数值也是很有效的，但是当数值增大的情况下，就暴露出其中一元编码部分的弱势，比如1000经过编码需要19个bit。
5. Elias Delta编码
我们在Gamma编码的基础上，进一步减少一元编码的影响，形成Delta编码，它的规则：对于正整数x，首先对于
2.1.png (510 Bytes, 下载次数: 2)
15:41 上传
进行Gamma编码，然后用
2.2.png (451 Bytes, 下载次数: 2)
15:41 上传
2.3.png (502 Bytes, 下载次数: 2)
15:41 上传
进行二进制编码。
比如对于正整数10，
2.4.png (578 Bytes, 下载次数: 2)
15:41 上传
，首先对于4进行Gamma编码，
2.5.png (529 Bytes, 下载次数: 2)
15:41 上传
，对于3进行一元编码110，然后用2个bit对
2.6.png (600 Bytes, 下载次数: 2)
15:41 上传
进行二进制编码00，所以4的Gamma编码为11000，然后计算
2.7.png (622 Bytes, 下载次数: 2)
15:41 上传
，用3个bit进行编码010，所以最后编码为。
Delta是Gamma编码和二进制编码的整合，也是符合变长编码要求的。
如果读取上述编码，先读入一元编码110，为数值3，接着读取3-1=2个bit为00，为数值0，所以Gamma编码为
2.8.png (451 Bytes, 下载次数: 2)
15:41 上传
，然后读取三个bit位010，二进制编码数值为2，所以
2.9.png (459 Bytes, 下载次数: 2)
15:41 上传
，解码成功。
尽管从数值10的编码中，我们发现Delta比Gamma使用的bit数还多，然而当数值比较大的时候，Delta就相对比较好了。比如1000经过Delta编码需要16个bit，要优于Gamma编码。
6. 哈夫曼编码
前面所说的编码方式都有这样一个特点，“任尔几路来 ，我只一路去”，也即无论要压缩的倒排表是什么样子的，都是一个方式进行编码，这种方法显然不能满足日益增长的多样物质文化的需要。接下来介绍的这种编码方式，就是一种看人下菜碟的编码方式。
前面也说到变长编码无歧义，要求任何一个编码都不是其他编码的前缀。学过数据结构的同学很可能会想到——哈夫曼编码。
哈夫曼编码是如何看人下菜碟的呢？哈夫曼编码根据数值出现的频率不同而采用不同长度进行编码，出现的次数多的编码长度短一些，出现次数少的编码长度长一些。
这种方法从直觉上显然是正确的，如果一个数值出现的频率高，就表示出现的次数多，如果采用较短的bit数进行编码，少一位就能节约不少空间，而对于出现频率低的数值，比如就出现一次，我们就用最奢侈的方法编码，也占用不了多少空间。
当然这种方法也是符合信息论的，信息论中的香农定理给出了数据压缩的下限。也即用来表示某个数值的bit的数值的下限和数值出现的概率是有关的：。看起来很抽象，举一个例子，如果抛硬币正面朝上概率是0.5，则至少使用1位来表示，0表示正面朝上，1表示没有正面朝上。当然很对实际运用中，由于对于数值出现的概率估计的没有那么准确，则编码达不到这个最低的值，比如用2位表示，00表示正面朝上，11表示没有正面朝上，那么01和10两种编码就是浪费的。对于整个数值集合s，每个数值所占用的平均bit数目，即所有的平均值，称为墒。
要对一些数值进行哈夫曼编码，首先要通过扫描统计每个数值出现的次数，假设统计的结果如图所示。
4.png (12.58 KB, 下载次数: 2)
15:16 上传
其次，根据统计的数据构建哈夫曼树，构建过程是这样的，如图：
1) 按照次数进行排序，每个文档ID构成一棵仅包含根节点的树，根节点的值即次数。
2) 将具有最小值的两棵树合并成一棵树，根节点的值为左右子树根节点的值之和。
3) 将这棵新树根据根节点的值，插入到队列中相应的位置，保持队列排序。
4) 重复第二步和第三步，直到合并成一棵树为止，这棵树就是哈夫曼树。
5.png (91.27 KB, 下载次数: 2)
15:16 上传
最终，根据最后形成的哈夫曼树，给每个边编号，左为0，右为1，然后从根节点到叶子节点的路径上的字符组成的二进制串就是编码，如图所示。
6.png (45.33 KB, 下载次数: 2)
15:16 上传
最终形成的编码，我们通过观察可以发现，没有一个文档ID的编码是另外一个的前缀，所以不存在歧义，对于二进制序列1001110，唯一的解码是文档ID “123”和文档ID “689”，不可能有其他的解码方式，对于Gamma和Delta编码，如果要保存二进制，则需要通过一元编码或者Gamma编码保存一个长度，才能知道这个二进制到底有多长，然而在这里连保存一个长度的空间都省了。
当然这样原始的哈夫曼编码也是有一定的缺点的：
1) 如果需要编码的数值有N个，则哈夫曼树的叶子节点有N个，每个都需要一个指向数值的指针，内部节点个数是N-1个，每个内部节点包含两个指针，如将整棵哈夫曼树保存在内存中，假设数值和指针都需要占用M个byte，则需要(N+N+2(N-1))*M=(4N-2)*M的空间，耗费还是比较大的。
2) 哈夫曼树的形成是有一定的不稳定性的，在构造哈夫曼树的第3步中，将一棵新树插入到排好序的队列中的时候，如果遇到了两个相同的值，谁排在前面？不同的排列方法会产生不同的哈夫曼树，最终影响最后的编码，如图。
7.png (42.96 KB, 下载次数: 2)
15:16 上传
为了解决上面两个问题，大牛Schwartz在论文《Generating a canonical prefix encoding》中，对哈夫曼编码做了一定的规范(canonical)，所以又称为规范哈夫曼编码或者范式哈夫曼编码。
当然哈夫曼树还是需要建立的，但是不做保存，仅仅用来确定每个数值所应该占用的bit的数目，因为出现次数多的数值占用bit少，出现次数少的数值占用bit多，这个灵魂不能丢。但是如果占用相同的bit，到底你是001，我是010，还是倒过来，这倒不必遵循左为0，右为1，而是指定一定的规范，来消除不稳定性，并在占用内存较少的情况下也能解码。
规范具体描述如下：
1) 所有要编码的数值或者字符排好队，占用bit少的在前，占用bit多的在后，对于相同的bit按照数值大小排序，或者按照字典顺序排序。
2) 先从占用bit最少的数值开始编码，对于第一个数值，如果占用i个bit，则应该是i个0。
3) 对于相同bit的其他数值，则为上一个数值加1后的二进制编码
4) 当占用i个bit的数值编码完毕，接下来开始对占用j个bit的数值进行编码，i & j。则j的第一个数值的编码应该是i个bit的最后一个数值的编码加1，然后后面再追加j-i个0
5) 充分3和4完成对所有数值的编码。
按照这个规范，图中的编码应该如图：
8.png (50.26 KB, 下载次数: 2)
15:16 上传
根据这些规则，不稳定性首先得到了解决，无论同一个层次的节点排序如何，都会按照数值或字符的排序来决定编码。
然后就是占用内存的问题，如果使用范式哈夫曼编码，则只需要存储下面的数据结构，如图:
9.png (23.65 KB, 下载次数: 2)
15:16 上传
当然原本数值的列表还是需要保存的，只不过顺序是安装占用bit从小到大，相同bit数按照数值排序的，需要N*M个byte。
另外三个数组就比较小了，它们的下标表示占用的bit的数目，也即最长的编码需要多少个bit，则这三个数组最长就那么长，在这个例子中，最长的编码占用5个bit，所以，它们仅仅占用3*5*M个byte。
第一个数组保存的是占用i个bit的编码中，起始编码是什么，由于相同bit数的编码是递增的，因而知道了起始，后面的都能够推出来。
第二个数组保存的是占用i个bit的编码有几个，比如5个bit的编码有5个，所以Number[5]=5。
第三个数组保存的是占用i个bit的编码中，起始编码在数值列表中的位置，为了解码的时候快速找到被解码的数值。
如果让我们来解析二进制序列1110110，首先读入第一个1，首先判断是否能构成一个1bit的编码，Number[1]=0，占用1个bit的编码不存在；所以读入第二个1，形成11，判断是否能构成一个2bit的编码，Number[2]=3，然后检查FirstCode[2]=00 & 11，然而11 – 00 + 1 = 4 & Number[2]，超过了2bit编码的范围；于是读入第三个1，形成111，判断是否能构成一个3bit的，Number[3]=1，然后检查FirstCode[3]=110&111，然而111 – 110 + 1 = 2& Number[3]，超过了3bit的编码范围；于是读入第四个0，Number[4]=0，再读入第五个1，判断是否能构成一个5bit的编码，Number[5]=4，然后检查FirstCode[5]=11100 & 1 – 11100 + 1 = 2&4，所以是一个5bit编码，而且是5bit编码中的第二个，5bit编码的第二个在位置Position[5]=5，所以此5bit编码是数值列表中的第6项，解码为value[6]=345。然后读入1，不能构成1bit编码，11不能构成2bit编码，110，Number[3]=1，然后检查FirstCode[3]=110=110，所以构成3bit编码的第一个Position[3]=4，解码为value[4]=789。
如果真能像理想中的那样，在压缩所有的倒排表之前，都能够事先通过全局的观测来统计每个文档ID出现的概率，则能够实现比较好的压缩效果。
在这个例子中，我们编码后使用的bit的数目为：
123.png (1.63 KB, 下载次数: 2)
15:21 上传
我们再来算一下墒：
234.png (2.95 KB, 下载次数: 2)
15:22 上传
按照香农定理最低占用的bit数为
345.png (1.11 KB, 下载次数: 2)
15:23 上传
可以看出哈夫曼编码的压缩效果相当不错。然而在真正的搜索引擎系统中，文档是不断的添加的，很难事先做全局的统计。
对于每一个倒排表进行局部的统计和编码是另一个选择，然而付出的代价就是需要为每一个倒排表保存一份上述的结构来进行解码。很不幸上述的结构中包含了数值的列表，如果一个倒排表中数值重复率很高，比如100万的长的倒排表只有10种数值，为100万保存10个数值的列表还可以接受，如果重复率不高，那么数值列表本身就和要压缩的倒排表差不多大了，根本起不到压缩作用。
7. Golomb编码
如果我们将倒排表中文档ID的概率分布假设的简单一些，就没必要统计出现的所有的数值的概率。比如一个简单的假设就是：Term在文档集集合中是独立随机出现的。
既然是随机出现的，那么就有一个概率问题，也即某个Term在某篇文档中出现的概率是多少？假设我们把整个倒排结构呈现如图的矩阵的样子，左面是n个Term，横着是N篇文档，如果某个Term在某篇文档中出现，则那一位设为1，假设里面1的个数为f，那么概率
456.png (472 Bytes, 下载次数: 2)
15:23 上传
10.png (23.82 KB, 下载次数: 2)
15:16 上传
正如在差值编码一节中论述的那样，我们在某个Term的倒排表里面保存的不是文档ID，而是文档ID的间隔的数值，我们想要做的事情就是用最少的bit数来表示这些间隔数值。
如果所有的间隔组成的集合是已知的，则可用上一节所述的哈夫曼编码。
我们在这里想要模拟的情况是：间隔组成的集合是不确定的，甚至是无限的，随着新的文档的不断到来进行不断的编码。
可以形象的想象成下面的情形，一个Term坐在那里等着文档一篇篇的到来，如果文档包含自己，就挂在倒排表上。
如果文档间隔是x，则表示的情形就是，来一篇文档不包含自己，再来一篇还是不包含自己，x-1篇都过去了，终于到了第x篇，包含了自己。如果对于一篇文档是否包含自己的概率为p，则文档间隔x出现的概率就是
131.png (522 Bytes, 下载次数: 2)
15:25 上传
假设编码当前的文档间隔x用了n个bit，这个Term接着等下一篇文档的到来，结果这次更不幸，等了x篇还包含自己，直到等到x+b篇文档才包含自己，于是要对x+b进行编码，x+b出现的概率为，显然比x的概率要低，根据信息论，如果x用n个bit，则x+b要使用更多的bit，假设，则最优的情况应该多用1个bit。
这样我们就形成了一个递推的情况，假设已知文档间隔x用了n个bit，对于来说，x+b就应该只用n+1个bit，这样如果有了初始的文档间隔并且进行了最优的编码，后面的都能达到最优。
于是Golomb编码就产生了，对于参数b(当然是根据文档集合计算出的概率产生的)，对于数值x的编码分为两部分，第一部分计算，然后将q+1用一元编码，第二部分是余数，r=x-1-qb，由于余数一定在0到b-1之间，则可以用或者进行无前缀编码(哈夫曼编码)。
用上面的理论来看Golomb编码就容易理解了，第一部分是用来保持上面的递推性质的，一元编码的性质可以保证，数值增加1，编码就多用1位，递推性质要求数值x增加b，编码增加1位，于是有了用数值x除以b，这样。第二部分的长度对于每个编码都是一样的，最多不过差一位，与数值x无关，仅仅与参数b有关，其实第二部分是用来保证初始的文档间隔是最优的，所以哈夫曼编码进行无前缀编码。
例如x=9，b=6，则，对q+1用一元编码为10，余数r=2，首先对于所有的余数进行哈夫曼编码，形成如图的哈夫曼树，从最小的余数开始进行范式哈夫曼编码，0为00，1为01，2占用三个bit，为01 + 1补充一位，为100，3为101，4为110，5为111。所以x=9的编码为10100。
接下来我们试图编码x=9+6=15，b=6，则，对q+1用一元编码为110，余数r=2，编码为100，最后编码为110100，果真x增大b，编码多了1位。
接下来要解决的问题就是如何确定b的值，按照咱们的理论推导，计算起来有些麻烦，我们先来计算分母部分，当p接近于0的时候，由著名的极限公式，所以分母约为p，于是公式最后为
由于Golomb编码仅仅需要另外保存一个参数b，所以既可以基于整个文档集合的概率进行编码，这个时候，也可以应用于某一个倒排表中，对于一个倒排表进行局部编码，以达到更好的效果，对于某一个倒排表，term的数量n=1，f=词频Term Freqency，，这样不同的倒排表使用不同的参数b，达到这样一个效果，对于词频高的Term，文档出现的相对紧密，用较小的b值来编码，对于词频低的Term，文档出现的相对比较松散，用较大的b来进行编码。
8. 插值编码(Binary Interpolative Coding)
前面讲到的Golomb编码表现不凡，实现了较高的压缩效果。然而一个前提条件是，假设Term在文档中出现是独立随机的，在倒排表中，文档ID的插值相对比较均匀的情况下，Golomb编码表现较好。
然而Term在文档中却往往出现的不那么随机，而往往是相关的话题聚集在一起的出现的。于是倒排表往往形成如下的情况，如图.
12.jpg (14.54 KB, 下载次数: 2)
15:17 上传
我们可以看到，从文档ID 8到文档ID 13之间，文档是相对比较聚集的。对于聚集的文档，我们可以利用这个特性实现更好的压缩。
如果我们已知第1篇文档的ID为8，第3篇文档的ID为11，那么第2篇文档只有两种选择9或者10，所以可以只用1位进行编码。还有更好的情况，比如如果我们已知第3篇文档ID为11，第5篇文档ID为13，则第6篇文档别无选择，只有12，可以不用编码就会知道。
这种方法可以形象的想象成为，我们从1到20共20个坑，我们要将文档ID作为标杆插到相应的坑里面，我们总是采用限制两头在中间找坑的方式，还是上面的例子，如果我们已经将第1篇文档插到第8个坑里，已经将第3篇文档插到第11个坑里，下面你要将第2篇文档插到他们两个中间，只有两个坑，所以1个bit就够了。当然一开始一个标杆还没有插的时候，选择的范围会比较的大，所以需要较多的bit来表示，当已经有很多的标杆插进去了以后，选择的范围会越来越小，需要的bit数也越来越小。
下面详细叙述一下编码的整个过程，如图所示。
13.png (25.06 KB, 下载次数: 2)
15:17 上传
最初的时候，我们要处理的是整个倒排表，长度Length为7，面对的从Low=1到High=20总共有20个坑。还是采取限制两头中间插入的思路，我们先找到中间数值11，然后找一坑插入它，那两头如何限制呢？是不是从1到20都可以插入呢？当然不是，因为数值11的左面有三个数值Left=3，一个数值一个坑的话，至少要留三个坑，数值11的右面也有三个数值Right=3，则右面也要留三个坑，所以11这根标杆只能插到从4到17共14个坑里面，也就是说共有14中选择，用二进制表示的话，需要bit来存储，我们用4位来编码11-4=7为0111。
第一根标杆的插入将倒排表和坑都分成了两部分，我们可以分而治之。左面一部分我们称之&Length=3, Low=1, High=10&，因为它要处理的倒排表长度为3，而且一定是放在从1到10这10个坑里面的。同理，右面一部分我们称之&Length=3, Low=12, High=20&，表示另外3个数值组成的倒排表要放在从12到20这些坑里。
先来处理&Length=3, Low=1, High=10&这一部分，如图。
14.png (23.16 KB, 下载次数: 2)
15:17 上传
同样选取中间的数值8，然后左面需要留一个坑Left=1，右面需要留一个坑Right=1，所以8所能插入的坑从2到9共8个坑，也就是8中选择，用二进制表示，需要bit来存储，于是编码8-2=6为110。
标杆8的插入将倒排表和坑又分为两部分，还是用上面的表示方法，左面一部分为&Length=1,Low=1,High=7&，表示只有一个值的倒排表要插入从1到7这七个坑中，右面一部分为&Length=1,Low=9,High=10&，表示只有一个值的倒排表要插入从9到10这两个坑中。
我们来处理&Length=1,Low=1,High=7&部分，如图。
15.png (17.65 KB, 下载次数: 2)
15:17 上传
只有一个数值3，左右也不用留坑，所以可以插入从1到7任何一个坑，共7中选择，需要3bit，编码3-1=2为010。
对于&Length=1,Low=9,High=10&部分，如图。
16.png (18.54 KB, 下载次数: 2)
15:17 上传
只有一个数值9，可以选择的坑从9到10两个坑，共两种选择，需要1bit，编码9-9=0为0。
再来处理&Length=3, Low=12, High=20&部分，如图。
17.png (25.63 KB, 下载次数: 2)
15:17 上传
选择插入中间数值13，左面需要留一个坑Left=1，右面需要留一个坑Right=1，所以13可以插入在从13到19这7个坑里，共7种选择，需要3bit，编码13-13=0为000。
数值13的插入将倒排表和坑分为两部分，左面&Length=1, Low=12, High=12&，只有一个数值的倒排表要插入唯一的一个坑，右面&Length=1,Low=14,High=20&，只有一个数值的倒排表插入从14到20的坑。
对于&Length=1, Low=12, High=12&，如图，一个数一个坑，不用占用任何bit就可以。
18.png (18.36 KB, 下载次数: 2)
15:17 上传
对于&Length=1,Low=14,High=20&，如图，只有一个值17，放在14到20之间7个坑中，有7中选择，需要3bit，编码17-14=3为011。
19.png (19.09 KB, 下载次数: 2)
15:17 上传
综上所述，最终的编码为 0 000 011，共17位。如果用Golomb编码差值&3，5，1，2，1，1，4&，经计算b=2，则编码共18位。差值编码表现更好。
那么解码过程应该如何呢？初始我们知道&Length=7，Low = 1，High=20&，首先解码的是中间的也即第3个数值，由于Left=3，Right=3，则可这个数值必定在从4到17，表示这14种选择需要4位，因而读取最初的4位0111为7，加上Low + Left = 4，第3个数值解码为11。
已知第3个数值为11后，则左面应该有三个数值，而且一定是从1到10，表示为&Length=3, Low=1, High=10&，右面的也应该有三个数值，而且一定是从12到20，表示为&Length=3, low=12, high=20&。
先解码左面&Length=3, Low=1, High=10&，解码中间的数值，也即第1个数值，由于Left=1，Right=1，则这个数值必定从2到9，表示8种选择需要3位，因而读出3位110，为6，加上Low+Left=2，第1个数值解码为8。
数值8左面还有一个数值，在1到7之间，表示7种选择需要3位，读出3位010，为2，加上Low=1，第0个数值解码为3。
数值8右面还有一个数值，在9到10之间，表示2种选择需要1位，读出1位0，为0，加上Low=9，第2个数值解码为9。
然后解码&Length=3, low=12, high=20&，解码中间的数值，也即第5个数值，由于Left=1，Right=1，则这个数值必定从13到19，表示7中选择需要3位，读出3位000，为0，加上low=13，第5个数值解码为13。
数值13左面还有一个数值，在12到12之间，必定是12，无需读取，第4个数值解码为12。
数值13右面还有一个数值，在14到20之间，表示7种选择需要3位，读出3位011，为3，加上low=14，则第6个数值解码为17。
解码完毕。
(18.6 KB, 下载次数: 2)
15:17 上传
(882 Bytes, 下载次数: 2)
15:25 上传
站长推荐 /6
about云|新出视频，openstack零基础入门，解决你ping不通外网难题
云计算hadoop视频大全(新增 yarn、flume|storm、hadoop一套视频
视频资料大优惠
大数据零基础由入门到实战
阶段1：hadoop零基础入门基础篇
阶段2：hadoop2入门
阶段3：大数据非hadoop系列课程
阶段4：项目实战篇
阶段5：大数据高级系列应用课程
阶段6：工作实用系列教程
等待验证会员请验证邮箱
新手获取积分方法
Powered by}