Algorithm：C++语言实现之SimHash和倒排索引算法相关(抽屉原理、倒排索、建立查找树、处理Hash冲突、Hash查找)

Algorithm：C++语言实现之SimHash和倒排索引算法相关(抽屉原理、倒排索、建立查找树、处理Hash冲突、Hash查找)

---

一、SimHash算法

1、SimHash算法五个步骤

2、抽屉原理

抽屉原理：桌上有十个苹果，要把这十个苹果放到九个抽屉里，无论怎样放，我们会发现至少会有一个抽屉里面至少放两个苹果。这一现象就是我们所说的“抽屉原理”。 抽屉原理的一般含义为：“如果每个抽屉代表一个集合，每一个苹果就可以代表一个元素，假如有n+1个元素放到n个集合中去，其中必定有一个集合里至少有两个元素。” 抽屉原理有时也被称为鸽巢原理。它是组合数学中一个重要的原理。

1、抽屉原理应用
       二维坐标系oXY中，坐标(x,y)都是整数的点叫做“格点”。试证明：任取平面上5个格点，它们的连接线段的中点至少有1个是格点。
分析问题：要想中点为格点，那么该线段的首尾坐标的中点

，即两个元素一定是偶数。
分析条件：
(1)、图中，明显可知，每个点的坐标x、y，不是奇数就是偶数。分析可知，一共可分为四大类(偶数，偶数)、(偶数，奇数)、(奇数，奇数)、(奇数，偶数)。
(2)、而图中随机选取5个点，那么图中第5个点，一定是四类中的一类，即可知5个点一定有2个点是同类的。那么，既然存在同类的点，说明可形成一个中点，因为不管是(奇数+奇数)还是(偶数+偶数)一定存在中点。
(3)、考虑连线非格点情况：只有当x1、x2(或y1、y2)属于不同类型的时候，比如(奇数+偶数)不能够除以2。
结论：所以取>4的坐标点，肯定存在类型相同的两个点。

二、倒排索引

1、倒排索引的应用

2、建立查找树

3、处理Hash冲突

4、Hash查找