[207]海量数据相似性检测:文档的抽块处理(Shingling) — ScalersTalk成长会 – 持续行动,刻意学习 – ScalersTalk Wonderland

[207]海量数据相似性检测:文档的抽块处理(Shingling)

雕虫小技 scalers 浏览 0条评论

 

欢迎关注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=9Hash4字节,相当于省了一半多的存储空间。

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 查看历史文章。

 

发表评论