倒排索引
根据属性的值来查找记录。索引表中的每一项都包括一个属性值和具有该属性值的各记录的抵地址
由于不是由记录来确定属性值, 而是由属性值来确定记录的位置, 因此被被称为倒排索引(invertedindex)
# import（输入）
1.Alex works in Facebook for three years.
2.John is a professional data-science analyzer.
3.Ronnie is just a noob in data-excavating field.
4.IceFrog works in valve for serveral years.
# split (分词)
Alex, works, in, Facebook, for, three, years
John, is, a, professional, data-science, analyzer
Ronnie, is, just, a, noob, in, data-excavating, field
IceFrog, works, in, valve, for, serveral, years
# statistic (处理后的统计结果)
KeyWords(关键词) Article Number[Frequency]{position}（文章号[出现频率]{位置})
Alex 1[1]{0}
Facebook 1[1]{3}
IceFrog 4[1]{0}
John 2[1]{0}
Ronnie 3[1]{0}
a 2[1]{2}, 3[1]{3}
analyzer 2[1]{5}
data-excavating 3[1]{6}
data-science 2[1]{4}
three 1[1]{5}
field 3[1]{7}
for 1[1]{4}, 4[1]{4}
in 1[1]{2}, 3[1]{4}, 4[1]{2}
is 2[1]{1}, 3[1]{1}
just 3[1]{2}
noob 3[1]{4}
professional 2[1]{3}
serveral 4[1]{5}
works 1[1]{1}, 4[1]{1}
valve 4[1]{3}
years 1[1]{6}, 4[1]{6}
Lucene整体使用图:
压缩算法
为了节省空间，lucene在行存储和列存储中存放的都是压缩数据。对于行存储，lucene提供了两种压缩选项：BEST_SPEED和BEST_COMPRESSION，对应速度优先和空间优先的不同策略。
Cardinality:
Cardinality是指集合中不同值的个数。按照一般的做法，我们需要遍历集合，将不同的值保存到一个Map中，完成遍历后，map的size就是cardinality。可是这种处理方法不适合大集合，会消耗太多内存。Lucene采用了另外的方法来统计cardinality，该方法不能够得到精确计算结果，但是能够得到一个近似值。方法的名称为:HyperLogLog++，计算过程如下：
计算字段的hash值；
统计hash值末尾开始的连续0的个数，记为m；
记录m的最大值；
$$
Cardinality = 2^m
$$
我们来看个例子：
| 原始值 | hash值 | 末尾连续0的个数 |
|---|---|---|
| 12345 | 11001011111101011010 | 1 |
| 3456 | 10001101001100111000 | 3 |
| 948 | 01000111110100110100 | 2 |
在上面的3个值中，我们观察到末尾连续0的个数最大为3，根据公式，cadinality等于
$$
2^3 = 8
$$
二元搜索： 即二分查找算法
原文：https://www.cnblogs.com/ronnieyuan/p/11670956.html