谷歌4亿英镑收购人工智能公司DeepMind,百度目前正推进“百度大脑”项目,腾讯、阿里等各大巨头布局深度学习。随着社会化数据大量产生,硬件速度上升、成本降低,大数据技术的落地实现,让冷冰冰的数据具有智慧逐渐成为新的热点。要从数据中发现有用的信息就要用到数据挖掘技术,不过买来的数据挖掘书籍一打开全是大量的数学公式,而课本知识早已还给老师了,难以下手、非常头大!

我们可以跳过数学公式,先看看我们了解数据挖掘的目的:发现数据中价值。这个才是关键,如何发现数据中的价值。那什么是数据呢?比如大家要上网首先需要输入网址,打开网页后会自动判断哪些是图片、哪些是新闻、哪些是用户名称、游戏图标等。人大脑可以存储大量的信息,包括文字、声音、视频、图片等,每一个都可以转换数据存储在电脑。人的大脑可以根据输入自动进行判断,电脑可以通过输入判断吗?答案是肯定的! 不过需要我们编写程序来判断每一种信息,就拿文字识别来说吧,怎么从一个人在社交网络的言论判断他今天的心情是高兴还是愤怒!比如:“你假如上午没给我吃冰淇淋,我绝对会不happy的。” 信息发布时间为下午2点。对于我们人类一看这个句子就知道他是吃过冰淇淋了,心情肯定不会是愤怒。那计算机怎么知道呢?

这就是今天的主题,要让计算机理解句子的语义,必须要有个程序,上面的句子和发布时间是输入,输出就是 “高兴”。要得到“高兴”就要建立 “高兴”的规则,可以建一个感情色彩词库,比如 高兴(识别词是高兴、happy),愤怒(识别词是愤怒、生气)。这里的识别词就是输入中出现的词语,比如上面的句子中的“happy”就识别出了“高兴”这个感情色彩词。但是光识别出“happy”肯定是不行的,前面的“假如。。。没。。。,我。。。不。。。”等关键词都需要识别出来,才能完整判断一个句子的意思。为了达到这个效果,就必须要用分词技术了。

我们先人工对上面的句子来进行一下切词,使用斜线分割:“你/假如/上午/没/给/我/吃/冰淇淋/,/我/绝对/会/不/happy/的/。/”。但是程序如何做到自动切分?这个其实中国的前辈们已经做了很多中文分词的研究,常见的分词算法有:

1、基于词典的分词,需要先预设一个分词词典,比如上面句子切分出来的“假如、上午”这些词先存放在词典,然后把句子切分成单字组合成词语去词典里查找,匹配上了就挑选出来一个词。没有匹配上的就切分成单字。

2、基于统计的分词,需要先获取大量的文本语料库(比如新闻、微博等),然后统计文本里相邻的字同时出现的次数,次数越多就越可能构成一个词。当达到一定次数时就构成了一个词即可形成语料概率库。再对上面句子进行单字切分,把字与字结合后在语料概率库里查找对应的概率,如果概率大于一定值就挑选出来形成一个词。这个是大概描述,实际生产环境中还需要对句子的上下文进行结合才能更准确的分词。

3、基于语义的分词,简而言之就是模拟人类对句子的理解来进行分词。需要先整理出中文语句的句法、语义信息作为知识库,然后结合句子的上下文,对句子进行单字切分后组合成词逐个带入知识库进行识别,识别出来就挑选出一个词。目前还没有特别成熟的基于语义的分词系统。

为了让大家快速的了解分词技术,我们采用第一个方式来做测试:基于词典的分词,这种方式简单暴力可以解决百分之七八十的问题。基于词典的分词大概分为以下几种方式:

1、正向最大匹配,沿着我们看到的句子逐字拆分后组合成词语到词典里去匹配,直到匹配不到词语为止。举个实际的例子:“人民大会堂真雄伟”,我们先拆分为单字“人”去词典里去查找,发现有“人”这个词,继续组合句子里的单字组合“人民”去词典里查找,发现有“人民”这个词,以此类推发现到“人民大会堂”,然后会结合“人民大会堂真”去词典里查找没有找到这个词,第一个词“人民大会堂”查找结束。最终分词的结果为:“人民大会堂/真/雄伟”。

segment

2、逆向最大匹配,这个和上面相反,就是倒着推理。比如“沿海南方向”,我们按正向最大匹配来做就会切分成 “沿海/南方/向”,这样就明显不对。采用逆向最大匹配法则来解决这个问题,从句子的最后取得“方向”这两个字查找词典找到“方向”这个词。再加上“南方向”组成三字组合查找词典没有这个词,查找结束,找到“方向”这个词。以此类推,最终分出“沿/海南/方向”。

3、双向最大匹配,顾名思义就是结合正向最大匹配和逆向最大匹配,最终取其中合理的结果。最早由哈工大王晓龙博士理论化的取最小切分词数,比如“我在中华人民共和国家的院子里看书”,正向最大匹配切分出来为“我/在/中华人民共和国/家/的/院子/里/看书”工8个词语,逆向最大匹配切分出来为“我/在/中华/人民/共/和/国家/的/院子/里/看书”共11个词语。取正向最大匹配切出来的结果就是正确的。但是如果把上面那个例子“沿海南方向”双向切分,都是3个词语,改如何选择?看第4个《最佳匹配法则》。

4、最佳匹配法则,先准备一堆文本语料库、一个词库,统计词库里的每一个词在语料库里出现的次数记录下来。最后按照词频高的优先选出,比如“沿海南方向”,正向切分为:“沿海/南方/向”,逆向切分为:“沿/海南/方向”。其中“海南”的频度最高,优先取出来。剩下“沿”、“方向”也就正常切分了。是不是这就是基于词典分词的最佳方案?比如数学之美中提到的:“把手抬起来” 和 “这扇门的把手”,可以分为“把”、“手”、“把手”,不管怎么分总有一句话的意思不对。后续再介绍如何通过统计的分词处理这些问题。

说了这么多,我们来实战一下如何基于词典的分词:

public class TestPositiveMatch {
    public static void main(String[] args) {
        String str = "我爱这个中华人民共和国大家庭";
        List<String> normalDict = new ArrayList<String>();

        normalDict.add("");
        normalDict.add("爱");
        normalDict.add("中华");   //测试词库里有中华和中华人民共和国,按照最大匹配应该匹配出中华人民共和国
        normalDict.add("中华人民共和国");

        int strLen = str.length();  //传入字符串的长度
        int j = 0;
        String matchWord = ""; //根据词库里识别出来的词
        int matchPos = 0; //根据词库里识别出来词后当前句子中的位置
        while (j < strLen) {      //从0字符匹配到字符串结束
            int matchPosTmp = 0;   //截取字符串的位置
            int i = 1;
            while (matchPosTmp < strLen) {   //从当前位置直到整句结束,匹配最大长度
                matchPosTmp = i + j;
                String keyTmp = str.substring(j, matchPosTmp);//切出最大字符串
                if (normalDict.contains(keyTmp)) { //判断当前字符串是否在词典中
                    matchWord = keyTmp;  //如果在词典中匹配上了就赋值
                    matchPos = matchPosTmp; //同时保存好匹配位置
                }
                i++;
            }
            if (!matchWord.isEmpty()) {
                //有匹配结果就输出最大长度匹配字符串
                j = matchPos;
                //保存位置,下次从当前位置继续往后截取
                System.out.print(matchWord + " ");
            } else {
                //从当前词开始往后都没有能够匹配上的词,则按照单字切分的原则切分
                System.out.print(str.substring(j, ++j) + " ");
            }
            matchWord = "";
        }
    }
}

输出结果为: 我 爱 这 个 中华人民共和国 大 家 庭

按照这样我们一个基本的分词程序开发完成。

对于文章一开始提到的问题还没解决,如何让程序识别文本中的感情色彩。现在我们先要构建一个感情色彩词库“高兴”,修饰词库“没”、”不”。再完善一下我们的程序:

public class TestSentimentPositiveMatch {
    public static void main(String[] args) {
        String str = "你假如上午没给我吃冰淇淋,我绝对会不happy的。";

        //语义映射
        Map<String, String> sentimentMap = new HashMap<String, String>();
        sentimentMap.put("happy", "高兴");

        //情感词库
        List<String> sentimentDict = new ArrayList<String>();
        sentimentDict.add("happy");

        //修饰词
        List<String> decorativeDict = new ArrayList<String>();
        decorativeDict.add("不");
        decorativeDict.add("没");

        //修饰词衡量分数
        Map<String, Double> decorativeScoreMap = new HashMap<String, Double>();
        decorativeScoreMap.put("不", -0.5);
        decorativeScoreMap.put("没", -0.5);

        List<String> decorativeWordList = new ArrayList<String>();  //修饰词
        String sentimentResult = ""; //情感结果

        int strLen = str.length();  //传入字符串的长度
        int j = 0;
        String matchSentimentWord = ""; //根据词库里识别出来的情感词
        String matchDecorativeWord = ""; //根据词库里识别出来的修饰词
        int matchPos = 0; //根据词库里识别出来词后当前句子中的位置
        while (j < strLen) {      //从0字符匹配到字符串结束
            int matchPosTmp = 0;   //截取字符串的位置
            int i = 1;
            while (matchPosTmp < strLen) {   //从当前位置直到整句结束,匹配最大长度
                matchPosTmp = i + j;
                String keyTmp = str.substring(j, matchPosTmp);//切出最大字符串
                if (sentimentDict.contains(keyTmp)) { //判断当前字符串是否在词典中
                    matchSentimentWord = keyTmp;  //如果在词典中匹配上了就赋值
                    matchPos = matchPosTmp; //同时保存好匹配位置
                }
                if (decorativeDict.contains(keyTmp)) { //判断当前字符串是否在词典中
                    matchDecorativeWord = keyTmp;  //如果在词典中匹配上了就赋值
                    matchPos = matchPosTmp; //同时保存好匹配位置
                }
                i++;
            }
            if (!matchSentimentWord.isEmpty()) {
                //有匹配结果就输出最大长度匹配字符串
                j = matchPos;
                //保存位置,下次从当前位置继续往后截取
                System.out.print(matchSentimentWord + " ");
                sentimentResult = sentimentMap.get(matchSentimentWord);
            }
            if (!matchDecorativeWord.isEmpty()) {
                //有匹配结果就输出最大长度匹配字符串
                j = matchPos;
                //保存位置,下次从当前位置继续往后截取
                System.out.print(matchDecorativeWord + " ");
                decorativeWordList.add(matchDecorativeWord);
            } else {
                //从当前词开始往后都没有能够匹配上的词,则按照单字切分的原则切分
                System.out.print(str.substring(j, ++j) + " ");
            }
            matchSentimentWord = "";
            matchDecorativeWord = "";
        }

        double totalScore = 1;
        for (String decorativeWord : decorativeWordList) {
            Double scoreTmp = decorativeScoreMap.get(decorativeWord);
            totalScore *= scoreTmp;
        }

        System.out.print("\r\n");
        if (totalScore > 0) {
            System.out.println("当前心情是:" + sentimentResult);
        } else {
            System.out.println("当前心情是:不" + sentimentResult);
        }
    }
}

通过传入“你假如上午没给我吃冰淇淋,我绝对会不happy的。”,结果输出为:“当前心情是:高兴”。当然你也可以改变其中的修饰词,比如改为:“你假如上午没给我吃冰淇淋,我绝对会happy的。”,结果输出为:“当前心情是:不高兴”。

机器再也不是冷冰冰的,看起来他能读懂你的意思了。不过这只是一个开始,抛出几个问题:

1、如何让程序识别句子中的时间?比如“上午”、“下午2点”。
2、如何处理“把手抬起来” 和 “这扇门的把手”中的“把”与“手”的问题?
3、如何构建海量的知识库,让程序从“婴儿”变成“成年人”?
4、如何使用有限的存储空间海量的知识库?
5、如何提高程序在海量知识库中查找定位信息的效率?
6、如何识别新词、人名、新鲜事物等未知领域?

univers_brain

这是《纽约时报》刊登的2张照片,一张是老鼠的脑细胞(左),一张是宇宙(右)。早期宇宙中星系互连关系,和大脑神经元相互连接,几乎无法分辨两张图之间的不同,大脑细胞与整个宇宙拥有一样的结构。

宇宙芸芸众生都是相通的,大脑也许就是一个小宇宙,在这个小宇宙又有很多星球、住着很多生物。而电脑也是宇宙中地球上的一个产物,只要存储计算速度发展到足够强大一定可以构建成一个强大的大脑。

你看这个单词 “testaword” 认识吗?可能不认识,因为我们五官先获取到的信息,然后根据大脑以往学习的经验做出判断。但是你看这个短语 ” test a word” 认识吗?再看看开始那个单词“testaword”是不是就亲切多了?

原创文章,转载请注明: 转载自LANCEYAN.COM

本文链接地址: 数据挖掘-分词入门

在前一篇文章 《海量数据相似度计算之simhash和海明距离》 介绍了simhash的原理,大家应该感觉到了算法的魅力。但是随着业务的增长 simhash的数据也会暴增,如果一天100w,10天就1000w了。我们如果插入一条数据就要去比较1000w次的simhash,计算量还是蛮大,普通PC 比较1000w次海明距离需要 300ms ,和5000w数据比较需要1.8 s。看起来相似度计算不是很慢,还在秒级别。给大家算一笔账就知道了:

随着业务增长需要一个小时处理100w次,一个小时为3600 *1000 = 360w毫秒,计算一下一次相似度比较最多只能消耗 360w / 100w = 3.6毫秒。300ms慢吗,慢!1.8S慢吗,太慢了!很多情况大家想的就是升级、增加机器,但有些时候光是增加机器已经解决不了问题了,就算增加机器也不是短时间能够解决的,需要考虑分布式、客户预算、问题解决的容忍时间?头大时候要相信人类的智慧是无穷的,泡杯茶,听下轻音乐:)畅想下宇宙有多大,宇宙外面还有什么东西,程序员有什么问题能够难倒呢?

加上客户还提出的几个,汇总一下技术问题:

  • 1、一个小时需要比较100w次,也就是每条数据和simhash库里的数据比较需要做到3.6毫秒。
  • 2、两条同一时刻发出的文本如果重复也只能保留一条。
  • 3、希望保留2天的数据进行比较去重,按照目前的量级和未来的增长,2天大概在2000w — 5000w 中间。
  • 4、短文本和长文本都要去重,经过测试长文本使用simhash效果很好,短文本使用simhash 准备度不高。

目前我们估算一下存储空间的大小,就以JAVA 来说,存储一个simhash 需要一个原生态 lang 类型是64位 = 8 byte,如果是 Object 对象还需要额外的 8 byte,所以我们尽量节约空间使用原生态的lang类型。假设增长到最大的5000w数据, 5000w * 8byte = 400000000byte = 400000000/( 1024 * 1024) = 382 Mb,所以按照这个大小普通PC服务器就可以支持,这样第三个问题就解决了。

比较5000w次怎么减少时间呢?其实这也是一个查找的过程,我们想想以前学过的查找算法: 顺序查找、二分查找、二叉排序树查找、索引查找、哈希查找。不过我们这个不是比较数字是否相同,而是比较海明距离,以前的算法并不怎么通用,不过解决问题的过程都是通用的。还是和以前一样,不使用数学公式,使用程序猿大家都理解的方式。还记得JAVA里有个HashMap吗?我们要查找一个key值时,通过传入一个key就可以很快的返回一个value,这个号称查找速度最快的数据结构是如何实现的呢?看下hashmap的内部结构:

java hashmap内部结构

如果我们需要得到key对应的value,需要经过这些计算,传入key,计算key的hashcode,得到7的位置;发现7位置对应的value还有好几个,就通过链表查找,直到找到v72。其实通过这么分析,如果我们的hashcode设置的不够好,hashmap的效率也不见得高。借鉴这个算法,来设计我们的simhash查找。通过顺序查找肯定是不行的,能否像hashmap一样先通过键值对的方式减少顺序比较的次数。看下图:

大规模simhash算法优化

存储
1、将一个64位的simhash code拆分成4个16位的二进制码。(图上红色的16位)
2、分别拿着4个16位二进制码查找当前对应位置上是否有元素。(放大后的16位)
3、对应位置没有元素,直接追加到链表上;对应位置有则直接追加到链表尾端。(图上的 S1 — SN)

查找
1、将需要比较的simhash code拆分成4个16位的二进制码。
2、分别拿着4个16位二进制码每一个去查找simhash集合对应位置上是否有元素。
2、如果有元素,则把链表拿出来顺序查找比较,直到simhash小于一定大小的值,整个过程完成。

原理
借鉴hashmap算法找出可以hash的key值,因为我们使用的simhash是局部敏感哈希,这个算法的特点是只要相似的字符串只有个别的位数是有差别变化。那这样我们可以推断两个相似的文本,至少有16位的simhash是一样的。具体选择16位、8位、4位,大家根据自己的数据测试选择,虽然比较的位数越小越精准,但是空间会变大。分为4个16位段的存储空间是单独simhash存储空间的4倍。之前算出5000w数据是 382 Mb,扩大4倍1.5G左右,还可以接受:)

通过这样计算,我们的simhash查找过程全部降到了1毫秒以下。就加了一个hash效果这么厉害?我们可以算一下,原来是5000w次顺序比较,现在是少了2的16次方比较,前面16位变成了hash查找。后面的顺序比较的个数是多少? 2^16 = 65536, 5000w/65536 = 763 次。。。。实际最后链表比较的数据也才 763次!所以效率大大提高!

到目前第一点降到3.6毫秒、支持5000w数据相似度比较做完了。还有第二点同一时刻发出的文本如果重复也只能保留一条和短文本相识度比较怎么解决。其实上面的问题解决了,这两个就不是什么问题了。

  • 之前的评估一直都是按照线性计算来估计的,就算有多线程提交相似度计算比较,我们提供相似度计算服务器也需要线性计算。比如同时客户端发送过来两条需要比较相似度的请求,在服务器这边都进行了一个排队处理,一个接着一个,第一个处理完了在处理第二个,等到第一个处理完了也就加入了simhash库。所以只要服务端加了队列,就不存在同时请求不能判断的情况。
  • simhash如何处理短文本?换一种思路,simhash可以作为局部敏感哈希第一次计算缩小整个比较的范围,等到我们只有比较700多次比较时,就算使用我们之前精准度高计算很慢的编辑距离也可以搞定。当然如果觉得慢了,也可以使用余弦夹角等效率稍微高点的相似度算法。

参考:
我的数学之美系列二 —— simhash与重复信息识别

原创文章,转载请注明: 转载自LANCEYAN.COM

本文链接地址: 海量数据相似度计算之simhash短文本查找

通过 采集系统 我们采集了大量文本数据,但是文本中有很多重复数据影响我们对于结果的分析。分析前我们需要对这些数据去除重复,如何选择和设计文本的去重算法?常见的有余弦夹角算法、欧式距离、Jaccard相似度、最长公共子串、编辑距离等。这些算法对于待比较的文本数据不多时还比较好用,如果我们的爬虫每天采集的数据以千万计算,我们如何对于这些海量千万级的数据进行高效的合并去重。最简单的做法是拿着待比较的文本和数据库中所有的文本比较一遍如果是重复的数据就标示为重复。看起来很简单,我们来做个测试,就拿最简单的两个数据使用Apache提供的 Levenshtein for 循环100w次计算这两个数据的相似度。代码结果如下:

            String s1 = "你妈妈喊你回家吃饭哦,回家罗回家罗" ;
            String s2 = "你妈妈叫你回家吃饭啦,回家罗回家罗" ;

            long t1 = System.currentTimeMillis();

            for (int i = 0; i < 1000000; i++) {
                   int dis = StringUtils .getLevenshteinDistance(s1, s2);
            }

            long t2 = System.currentTimeMillis();

            System. out .println(" 耗费时间: " + (t2 - t1) + "  ms ");

耗费时间: 4266 ms

大跌眼镜,居然计算耗费4秒。假设我们一天需要比较100w次,光是比较100w次的数据是否重复就需要4s,就算4s一个文档,单线程一分钟才处理15个文档,一个小时才900个,一天也才21600个文档,这个数字和一天100w相差甚远,需要多少机器和资源才能解决。

为此我们需要一种应对于海量数据场景的去重方案,经过研究发现有种叫 local sensitive hash 局部敏感哈希 的东西,据说这玩意可以把文档降维到hash数字,数字两两计算运算量要小很多。查找很多文档后看到google对于网页去重使用的是simhash,他们每天需要处理的文档在亿级别,大大超过了我们现在文档的水平。既然老大哥也有类似的应用,我们也赶紧尝试下。simhash是由 Charikar 在2002年提出来的,参考 《Similarity estimation techniques from rounding algorithms》 。 介绍下这个算法主要原理,为了便于理解尽量不使用数学公式,分为这几步:

  • 1、分词,把需要判断文本分词形成这个文章的特征单词。最后形成去掉噪音词的单词序列并为每个词加上权重,我们假设权重分为5个级别(1~5)。比如:“ 美国“51区”雇员称内部有9架飞碟,曾看见灰色外星人 ” ==> 分词后为 “ 美国(4) 51区(5) 雇员(3) 称(1) 内部(2) 有(1) 9架(3) 飞碟(5) 曾(1) 看见(3) 灰色(4) 外星人(5)”,括号里是代表单词在整个句子里重要程度,数字越大越重要。

  • 2、hash,通过hash算法把每个词变成hash值,比如“美国”通过hash算法计算为 100101,“51区”通过hash算法计算为 101011。这样我们的字符串就变成了一串串数字,还记得文章开头说过的吗,要把文章变为数字计算才能提高相似度计算性能,现在是降维过程进行时。

  • 3、加权,通过 2步骤的hash生成结果,需要按照单词的权重形成加权数字串,比如“美国”的hash值为“100101”,通过加权计算为“4 -4 -4 4 -4 4”;“51区”的hash值为“101011”,通过加权计算为 “ 5 -5 5 -5 5 5”。

  • 4、合并,把上面各个单词算出来的序列值累加,变成只有一个序列串。比如 “美国”的 “4 -4 -4 4 -4 4”,“51区”的 “ 5 -5 5 -5 5 5”, 把每一位进行累加, “4+5 -4+-5 -4+5 4+-5 -4+5 4+5” ==》 “9 -9 1 -1 1 9”。这里作为示例只算了两个单词的,真实计算需要把所有单词的序列串累加。

  • 5、降维,把4步算出来的 “9 -9 1 -1 1 9” 变成 0 1 串,形成我们最终的simhash签名。 如果每一位大于0 记为 1,小于0 记为 0。最后算出结果为:“1 0 1 0 1 1”。

整个过程图为:

simhash计算过程图

大家可能会有疑问,经过这么多步骤搞这么麻烦,不就是为了得到个 0 1 字符串吗?我直接把这个文本作为字符串输入,用hash函数生成 0 1 值更简单。其实不是这样的,传统hash函数解决的是生成唯一值,比如 md5、hashmap等。md5是用于生成唯一签名串,只要稍微多加一个字符md5的两个数字看起来相差甚远;hashmap也是用于键值对查找,便于快速插入和查找的数据结构。不过我们主要解决的是文本相似度计算,要比较的是两个文章是否相识,当然我们降维生成了hashcode也是用于这个目的。看到这里估计大家就明白了,我们使用的simhash就算把文章中的字符串变成 01 串也还是可以用于计算相似度的,而传统的hashcode却不行。我们可以来做个测试,两个相差只有一个字符的文本串,“你妈妈喊你回家吃饭哦,回家罗回家罗” 和 “你妈妈叫你回家吃饭啦,回家罗回家罗”。

通过simhash计算结果为:

1000010010101101111111100000101011010001001111100001001011001011

1000010010101101011111100000101011010001001111100001101010001011

通过 hashcode计算为:

1111111111111111111111111111111110001000001100110100111011011110

1010010001111111110010110011101

大家可以看得出来,相似的文本只有部分 01 串变化了,而普通的hashcode却不能做到,这个就是局部敏感哈希的魅力。目前Broder提出的shingling算法和Charikar的simhash算法应该算是业界公认比较好的算法。在simhash的发明人Charikar的论文中并没有给出具体的simhash算法和证明,“量子图灵”得出的证明simhash是由随机超平面hash算法演变而来的

现在通过这样的转换,我们把库里的文本都转换为simhash 代码,并转换为long类型存储,空间大大减少。现在我们虽然解决了空间,但是如何计算两个simhash的相似度呢?难道是比较两个simhash的01有多少个不同吗?对的,其实也就是这样,我们通过海明距离(Hamming distance)就可以计算出两个simhash到底相似不相似。两个simhash对应二进制(01串)取值不同的数量称为这两个simhash的海明距离。举例如下: 1010100110 从第一位开始依次有第一位、第四、第五位不同,则海明距离为3。对于二进制字符串的a和b,海明距离为等于在a XOR b运算结果中1的个数(普遍算法)。

为了高效比较,我们预先加载了库里存在文本并转换为simhash code 存储在内存空间。来一条文本先转换为 simhash code,然后和内存里的simhash code 进行比较,测试100w次计算在100ms。速度大大提升。

未完待续:

1、目前速度提升了但是数据是不断增量的,如果未来数据发展到一个小时100w,按现在一次100ms,一个线程处理一秒钟 10次,一分钟 60 * 10 次,一个小时 60*10 *60 次 = 36000次,一天 60*10*60*24 = 864000次。 我们目标是一天100w次,通过增加两个线程就可以完成。但是如果要一个小时100w次呢?则需要增加30个线程和相应的硬件资源保证速度能够达到,这样成本也上去了。能否有更好的办法,提高我们比较的效率?

2、通过大量测试,simhash用于比较大文本,比如500字以上效果都还蛮好,距离小于3的基本都是相似,误判率也比较低。但是如果我们处理的是微博信息,最多也就140个字,使用simhash的效果并不那么理想。看如下图,在距离为3时是一个比较折中的点,在距离为10时效果已经很差了,不过我们测试短文本很多看起来相似的距离确实为10。如果使用距离为3,短文本大量重复信息不会被过滤,如果使用距离为10,长文本的错误率也非常高,如何解决?

simhash_hammingdistance

参考:
Detecting near-duplicates for web crawling.

Similarity estimation techniques from rounding algorithms.

http://en.wikipedia.org/wiki/Locality_sensitive_hashing

http://en.wikipedia.org/wiki/Hamming_distance

simHash 简介以及 java 实现

simhash原理推导

原创文章,转载请注明: 转载自LANCEYAN.COM

本文链接地址: 海量数据相似度计算之simhash和海明距离