哈希函数的套路 | 文本分析：大规模文本处理（1）
这个系列打算以文本相似度为切入点，逐步介绍一些文本分析的干货。
第一篇中，介绍了文本相似度是干什么的；
第二篇，介绍了如何量化两个文本，如何计算余弦相似度，穿插介绍了分词、词频、向量夹角余弦的概念。
第三篇中，介绍了目前常用的相似度，以及相关 Python 包。
其中具体如何计算，在这里复习：
假如我现在有 5 条文本数据，想计算两两之间的相似度，找出最相似的文本对（比如cosine相似度>0.9），在本地 Python 中 不到一毫秒就跑出来了：
但是同样的问题，我把数据扩大500倍，耗时就提高了一个量级。我尝试过在1500条英文短文本中进行聚类，把相似度 >0.9 的文本聚在一起，使用 DBSCAN 密度聚类，耗时大概2分钟。
我再把数据扩大到 2W 的级别呢？2W条数据，同样进行DBSCAN聚类，我的经验是大概需要4个小时的时间。
实际上，业界处理数据的量级动辄就是百万甚至千万。在这样量级的茫茫数据中，进行两两比对，进而找出相似的文本对，耗时是非常可怕的。我们需要考虑对方法进行优化，甚至引入新的方法。
局部敏感性性哈希（Locality Sensitive Hashing, LSH），就是一个神奇的方法。
不过我们首先得了解 Hash 这个东西。Hash function，哈希函数，又叫散列函数。
1、它是干嘛的？一个套路函数
本质上，它对原始内容做一个映射，并且能把任意长度的内容，映射到成固定维度。你可以理解为它是一个”套路函数“，不管原始内容什么样的，都要按照它的套路走。
比如，有一个hash function：f(x) = x*3 mod 7，即套路是，取任意一个数的3倍再除以 7 的余：
- x=234, f(234)=2
- x=235, f(235)=5
2、它有哪些特点？套路险而深
听起来，Hash function 不就是一个函数嘛！呵呵，我只能说，城市套路深，我想回农村，农村道路远，套路更加险。
哈希函数，可以认为是一种特殊的函数。为了满足某些场景的使用需求，我们期望它能满足一些性质，这些成为了 Hash function 的独有套路。
但是这些套路远比你想象的要深。我们来认识一下：
为方便说明，我把原始信息叫做 X，hash后的信息叫做 TLL（TaoLuLe）
（1）输入 X 可以是任意长度，哪怕是一部100万字的长篇小说，输出 TLL 都要是固定长度。这个性质，对于我们本系列要讲的大规模文本分析来说，有非常重要的作用。
（2）Hash function 是一种单向密码体制，即从X到TLL是一个不可逆的过程。比如，我们上面取余的例子，X=234 → TLL=2，是没办法反过来寻找的。
（3）当 X 改变，哪怕概念一个字节，TLL就会发生变化。之前取余的例子中，234 与 235 很相似，但哈希之后的值一个是2，一个是5，出现了很大的差别。这是一种类似“防篡改”的性质，这个性质也很重要，是区块链的核心技术。同时，在我们做大规模文本比对的时候，这个性质能直接帮我们减少计算耗时。
但是，哈希之后能取到的值，范围总是有限的，而 X 的取值却可以是无限的，因此一定存在两个不同的 X，hash之后取到相同的 TLL，比如仍以取余为例，当X=3 时，f(3)=2，这与 x=234 是一样的，这就叫“冲突”或“碰撞”。
冲突是我们不愿看到但又不可避免的，因此，如果一个 Hash function 能再满足下面两个性质：
（4）抗弱碰撞性：已经给定了 X1，其哈希值 H(X1)，想找一个 X2，使得 H(X1)=H(X2) 在计算上几乎是不可行的。
（5）抗强碰撞性：在计算上，几乎不可能找不到一对 (X1, X2)，使得 H(X1)=H(X2)。
就说这个 hash function 是安全的。
3、它有什么用？唯有套路得人心
hash function 在现代密码学中有很重要的应用，比如消息认证，消息认证是用来验证消息完整性的一种机制或服务。
如下图所示，一份原始消息，我们可以把它理解为一份文件、或一份在线网页，我们down下来，求一个哈希值 TLL_1。之后我们通过了某个未知安全通道，你可以理解为这份文件或网页传输了、或者在线放置了N天，之后我们再求一个哈希值 TLL_2。
现在比对这两个哈希值是否相等，如果不相等，那说明这份文件/网页被篡改过，也就是消息不完整了。
同时，哈希函数的这个防篡改性质，也是区块链的核心技术之一。这里安利一下，《Python量化投资入门》课程（公众号主页—菜单栏“量化入门”查看）的主讲老师邢不行，最近在上海交通大学安泰经管学院做了一次关于区块链技术的演讲视频，感兴趣可以了解一下，文末有链接）
本系列最主要想要说的，是 hash function 在大规模文本处理中的应用。
在本系列的前面几篇文章中，我们介绍了文本相似的计算方法，以 cosine 相似度为例，算法的复杂度是O(n2)。如果处理的是海量文本，计算耗时将相当可怕。而hash function 的特点，可以很好的帮我们进行降维。
但是降维最大的问题是信息的损失，这意味着准确度的下降。比如上面的例子中，234 和 235 无论当做数值型还是当做字符型，都是很相似的一组信息，但用取余的方法 hash 之后，相似度就大相径庭。因此，在文本处理这个场景，我们对 hash function 的要求很直接：
（1）能够降维，减少文本相似比对的计算成本。这个要求不难，hash funtion 的基本性质就能够满足。
（2）原始文本信息 hash 之后，能保持原有的相似性。这就要求我们挑选一个很好的 hash function，满足这个要求的哈希，称之为“局部敏感性哈希”。
关于这点，我们后来再接着说。总结一下，在大规模文本比对的时候，我们不能直接用原始信息去计算相似度，这样的计算耗时是相当可怕的，我们需要用一种特殊的 hash funtion 套路一下，再去计算。
腾讯云开发者
