专栏首页数说工作室哈希函数的套路 | 文本分析:大规模文本处理(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 条评论
登录 后参与评论

相关文章

  • python日志按时间切分-----TimedRotatingFileHandler

    原生loggging类+ TimedRotatingFileHandler类 实现按day hour second 切分 原生loggging类+ Timed...

    财主刀刀
  • python的数学函数(1)-python组合函数模块itertools

    要解决的问题: 输出n个 ['A','T','C','G'] 所有的排列组合。 比如n=2 时,输出为 AA,AT,AC,AG,TA,TT,TC,TG,……...

    财主刀刀
  • python 应用thrift---- thrift的监控fb303 -

    2011-08-18 fb303 在thrift的源码包 contrib之中 * What does it provide? * A standard in...

    财主刀刀
  • Python NLP入门教程

    目录[-] 本文简要介绍Python自然语言处理(NLP),使用Python的NLTK库。NLTK是Python的自然语言处理工具包,在NLP领域中,最常使...

    jhao104
  • Python Webdriver 重新使用已经打开的浏览器实例

    目录[-] 因为Webdriver每次实例化都会新开一个全新的浏览器会话,在有些情况下需要复用之前打开未关闭的会话。比如爬虫,希望结束脚本时,让浏览器处于空...

    jhao104
  • Python 面试中8个必考问题

    ? 翻译 everfighting 原文链接:https://www.toptal.com/python/interview-questions Q1、下...

    CDA数据分析师
  • 项目管理工具 Trac入门

    trac是一个python写成的项目管理系统,集成wiki svn和bug跟踪子系统 官方介绍: “Trac是基于web的软件项目管理和缺陷/事务追踪系统. 强...

    财主刀刀
  • list comprehensions

    2011-10-07 列表解析 python很优雅的东西,今天从cookbook稍微深的理解下它,举例: >>> multi = [[0] * 5] * 3 ...

    财主刀刀
  • Python标准库笔记(6) — struct模块

    目录[-] 该模块作用是完成Python数值和C语言结构体的Python字符串形式间的转换。这可以用于处理存储在文件中或从网络连接中存储的二进制数据,以及其...

    jhao104
  • 使用captcha模块生成图形验证码

    目录[-] captcha模块是专门用于生成图形验证码和语音验证码的Python三方库。图形验证码支持数字和英文单词。 安装 安装 可以直接使用 pip 安...

    jhao104

扫码关注云+社区

领取腾讯云代金券