欢迎关注ScalersTalk。IT人，搞技术，聊英语，玩口译，话学术，谈生活。学习成长，笔耕不辍。回复m查看文章列表，或者访问S君小站ScalersTalk.com

今天起，陆陆续续发一些我的技术学习笔记，主要是自己在技术学习中的总结记录。由于是笔记，可能会有一定的跳跃性，比如有一些没有直接上下文，有一些基本的概念可能默认读者理解。今天是一个尝试，我将根据读者的反馈调整行文。

海量数据相似性检测主要是从大量数据中找出相似的内容，这里一般是文档或者文本等文字信息。今天从头开始梳理，在海量数据下，相似性检测的技术路线。先是从抽块开始，也就是Shingle

k-Shingles

k-Shingles被定义成为长度为k的字符串，是文档中一个连续的字符串，可以看成是一个大小为k的滑动窗口。

从文档中取块，取出的块定义出一个块集合k-ShingleSet，这是一个不重复的集合，一个元素出现一次。一个变形(variation)就是元素可以重复，于是定义其为bag

1.     空格（换行或者制表等）

对于英文文档，对空格可以采取不同的策略。比如无视所有空格，连在一起处理；或者每个空格都不同，连续N个也算N个；另外还有一种做法，出现多个空格，算一个空格。后者是主要的处理方式。

2. k大小的选取

k大小的选取主要由几方面因素来决定：

(1)对象文档的一般长度。即所处理的文档的一般长度，可以影响k的选取。如果文档是短文本，k的大小必然不能超过短文本的长度；如果是长文本，那k亦然可以放宽一些。

(2)语言的字符集的大小。比如英文如果单算字母加上空格，不考虑大小写一共27个。

(1)和(2)需要综合在一起，才能看出一个k-Shingles方案选取所具备的表达能力。如果一个语言字符集的大小是M，对于k长度的k-Shingles，共能支持$M^k$种不同表达。

但是微妙的一点是，字符集并非平均分布的，某些字条出现的概率会大一些，某些会小一些。所以比如英文字符可能最多算20个字符，其他语言比如中文，也有类似情况。

k如果太小，于是变得很平凡trivial，在每一个文档中都会出现这些k-Shingles，所以即使这些k-Shingles相似，也不代表文档的相似，价值不太。极端的情况就是，当k=1时，每个文档都会出现语言字符集的内容，但是这明明就是不同的文档。k如果太大了也不行，那就变成了一个文档的量身定制。

k的选取应该大小适中，以确保任何一个k-Shingles在每一个文档中出现的概率都要低。

3.对Shingle进行哈希

可以选用Hash对一个k-Shingle进行映射，生成一个数字。这可以实现信息的压缩，以及便于机器按字的长度进行操作。比如k=9时Hash到4字节，相当于省了一半多的存储空间。

Hash的一个原则就是从大空间向小空间映射。有关Hash函数其实和密码学里的安全性模型有关，择日再谈。

4.另一种基于词的k-Shingles处理方式

前面说的是直接滑动窗口的k-Shingle处理方法，对于文档类，有一个特点是可读性高，于是还有一个思路就是从词出发做k-Shingle。

这里以英文为例。英文中有一些停用词Stop Word，一般是一门语言中频繁出现的词，即它们到处出现，但是又不能提供一些信息。于是在数据处理中，往往需要剔除，是谓之停用词由来。

这种处理方式就是，找出文档中所有停用词，并从该词开始连续选k个词，包括后续可能的停用词。这是一种上下文紧密的处理方式，对于网页中存在正文与广告的情况，具有一定的适配效果。

回复“100小时”查看口译100小时训练计划；回复“十万字”查看十万字视译计划。

S君的口译100小时、十万字视译训练交流QQ群，欢迎加入（群号为231441722）

S君个人微信号，ScalersTalker欢迎添加。

如果你觉得S君的文章对你有用，欢迎捐助打赏 。支付宝账号是

scalerstalk [at] gmail [dot] com

想看更多相关文章，关注 ScalersTalk 回复任意小于标题括号中的三位数字查看。或者去我的站点 ScalersTalk.com 查看历史文章。