专栏首页数说工作室哈希函数的套路 | 文本分析:大规模文本处理(1)

哈希函数的套路 | 文本分析:大规模文本处理(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 套路一下,再去计算。

本文分享自微信公众号 - 数说工作室(shushuojun),作者:最接地气最懂你的

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2017-11-02

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 文本分析 | 常用距离/相似度 一览

    这个系列打算以文本相似度为切入点,逐步介绍一些文本分析的干货,包括分词、词频、词频向量、TF-IDF、文本匹配等等。 第一篇中,介绍了文本相似度是干什么的; 第...

    数说君
  • 海量文本用 Simhash, 2小时变4秒! | 文本分析:大规模文本处理(2)

    这是一个相似匹配的问题(文本相似匹配基础→ 词频与余弦相似度)。但是,亿级数据库,用传统的相似度计算方法太慢了,我们需要一个文本查询方法,可以快速的把一段文本的...

    数说君
  • 【数说•大数据公司】德强农场

    我们在微博中每天播报大数据风控、精准医疗、精准农业、关联营销、推荐系统等等......可以发现,大数据将各行各业的生产和营销能力提高了不止一个倍数。 从今天开...

    数说君
  • 一个关于Angular Directive selector里的中括号使用问题

    其实对于Angular指令的selector,我一直搞得不是太清楚,看下面的例子:selector的定义里,包含了中括号。

    Jerry Wang
  • 使用Fiori elements技术开发的ui5应用,方便大家参考

    版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。 ...

    Jerry Wang
  • JavaScript获取默认时间的上一个月

    王小婷
  • 全网最易懂的正则表达式教程(6)- 分组

    那到底啥是不保存分组呢?可以理解成,括号只用于归组,把某些表达式当做一个单独的整体,不分配编号,后面不会再进行这部分的引用

    小菠萝测试笔记
  • 【通信专栏】STM32单片机/SPI通信

    SPI 接口主要应用在 EEPROM, FLASH,实时时钟, AD 转换器,还有数字信号处理器和数字信号解码器之间。SPI,是一种高速的,全双工,同步的通信总...

    周旋
  • Python 面向对象静态方法、类方法、属性方法知识点小结

    本文实例讲述了Python 面向对象静态方法、类方法、属性方法知识点。分享给大家供大家参考,具体如下:

    砸漏
  • 只需几十元,就可以学会比特币交易的全过程

    大概在9个月前,我与同事们谈起我刚刚买了一个比特币,绝大多数同事们投来不可思议的眼神,当时1BTC的价格为4000元。今天我再次与他们谈起比特币,眼神还是没变。...

    申龙斌

扫码关注云+社区

领取腾讯云代金券