一个有意思的需求——中文匹配度

发布时间:2014-07-13 15:01:00作者:左潇龙阅读(2229 )评论(18)

    引言

     

      最近LZ带头在做一个互联网项目,互联网的东西总是那么新鲜,这也难怪大部分猿友都喜欢互联网。这个互联网项目不仅让LZ开发了一个HBase大数据应用,近期的一次需求讨论会上,又出来一个小需求,蛮有意思的。这些需求在之前枯燥的企业内部应用开发中,还是很难见到的,毕竟内部应用更多的是业务流程的体现。

      具体的需求这里不方便透露,但简单的描述一下需求,就是如何判断两个公司名是一个。这其实就是Java当中字符串的相等判断,最简单的当然是用equals来判断。但是由于实际情况是,公司名是由客户手动输出的,难免有小小的偏差,因此equals自然就不适用了。比如“博客园科技发展有限公司”和“博客园科技发展(北京)有限公司”,这两个显然应该是一个公司,但是如果用equals,自然结果会是false。

      

    方案提出

     

      会议上,LZ简单提出了一个解决方案,就是利用分词来计算两者的匹配度,如果匹配度达到一定数值,我们就认为两个字符串是相等的。不过不论算法如何高明,准确率都不可能达到100%,这点也是LZ一再给业务同事强调的,否则到时候匹配错了,他们找LZ的茬可咋办。不过好在业务同事只是希望有一个提示功能,并不做严格的判断标准,所以系统需要做的只是初步的判断,因此准确率要求并不是特别的高,只能说越高越好。

      由于这个项目是LZ以PM介入开发的,而且LZ一直都兼任SM,所以技术方案自然是LZ说了算了。没有讨论,没有异议,方案就这么在会议上定了。

     

    小研究

     

      由于LZ最近负责的事情比较多,所以上班的时候自然是没有时间研究这些东西,只能趁着周末小小研究一下。其实LZ对于分词并不是特别了解,这些东西与算法的关联度比较高,而LZ的算法基础只能说“呵呵”。不过不管怎样,作为一个项目的领头人,总得向前冲。如果到时候算法的时间、空间成本太高,或者准确率太低,等着后续寻找大神优化也不晚。

      这件事的思路比较清晰,LZ需要做的就是两件事,第一件事就是“分词”,第二件事就是“匹配”。

     

    分词

     

      分词是比较简单的一步,有很多现成的类库可以使用,只要选择一个使用就可以了。Lucene是LZ第一个想到的,毕竟LZ也算是Apache的脑残粉,因此话不多说,第一时间就下载Lucene,开始了探究之旅。

      以下是LZ在网络上找到的示例,稍微进行了一点修改。

    package com.creditease.borrow.lucene;
    
    import java.io.IOException;
    
    import org.apache.lucene.analysis.TokenStream;
    import org.apache.lucene.analysis.cn.smart.SmartChineseAnalyzer;
    import org.apache.lucene.analysis.tokenattributes.CharTermAttribute;
    import org.apache.lucene.util.Version;
    
    public class App 
    {
        public static void main( String[] args ) throws IOException
        {
            String text = "博客园科技发展(北京)有限公司";
            SmartChineseAnalyzer smartChineseAnalyzer = new SmartChineseAnalyzer(Version.LUCENE_47);
            TokenStream tokenStream = smartChineseAnalyzer.tokenStream("field", text);
            CharTermAttribute charTermAttribute = tokenStream.getAttribute(CharTermAttribute.class);
            tokenStream.reset();
            while (tokenStream.incrementToken()) {
                System.out.print(charTermAttribute.toString() + "  ");
            }
            tokenStream.end();
            tokenStream.close();
            smartChineseAnalyzer.close();
        }
        
    }

      输出结果为以下内容。

    博  客  园  科技  发展  北京  有限公司  

      这种分词结果勉强可以接受了,最理想的应该是将“博客”放在一起,不过看来Lucene的字典里没有这个词。没关系,这对我们的计划并不影响,我们接下来开始着手匹配的事。

     

    匹配

     

      有了分词,我们要做的,就是匹配两个字符串数组,并得到一个匹配度。既然是匹配度,那么肯定就有分母和分子。我们可以挑其中一个数组的长度为分母,以另外一个数组中的元素找到匹配分词的个数作为分子。为了减少程序的复杂度,我们采用Set集合的去重特点来进行计算。就像以下程序这样。

    package com.creditease.borrow.lucene;
    
    import java.io.IOException;
    import java.util.HashSet;
    import java.util.Set;
    
    import org.apache.lucene.analysis.TokenStream;
    import org.apache.lucene.analysis.cn.smart.SmartChineseAnalyzer;
    import org.apache.lucene.analysis.tokenattributes.CharTermAttribute;
    import org.apache.lucene.util.Version;
    
    public class App 
    {
        
        private static SmartChineseAnalyzer smartChineseAnalyzer = new SmartChineseAnalyzer(Version.LUCENE_47);
        
        public static void main( String[] args ) throws IOException
        {
            String text1 = "博客园科技发展(北京)有限公司";
            String text2 = "博客园科技发展有限公司";
            System.out.println(oneWayMatch(text1, text2));
        }
        
        public static double oneWayMatch(String text1,String text2) {
            try {
                Set<String> set = new HashSet<String>(10);
                TokenStream tokenStream = smartChineseAnalyzer.tokenStream("field", text1);
                CharTermAttribute charTermAttribute = tokenStream.getAttribute(CharTermAttribute.class);
                tokenStream.reset();
                while (tokenStream.incrementToken()) {
                    set.add(charTermAttribute.toString());
                }
                int denominator = set.size();
                tokenStream.end();
                tokenStream.close();
                tokenStream = smartChineseAnalyzer.tokenStream("field", text2);
                charTermAttribute = tokenStream.getAttribute(CharTermAttribute.class);
                tokenStream.reset();
                while (tokenStream.incrementToken()) {
                    set.add(charTermAttribute.toString());
                }
                int numerator = set.size() - denominator;
                double unmatchRate = ((double)numerator)/denominator;
                tokenStream.end();
                tokenStream.close();
                return unmatchRate;
            } catch (IOException e) {
                return 1D;
            }
            
        }
        
    }

      输出的结果为0,也就是说匹配度为100%。这显然是不对的,两个字符串很明显不是一模一样,得到匹配度为100%说明我们的算法还是有问题。

      仔细分析一下,问题就出在我们是拿text2中不匹配的分词作为分子,而text2中的分词在text1中全部都包含,因此分子最终会是0,那么不匹配度自然就是0(unmatchRate)。为了弥补这一缺陷,LZ想来想去最终还是决定采取“双向”(twoWay)的办法解决这个问题,可以看到LZ给上面那个方法取的名字为“单向”匹配(oneWay)。

      双向匹配其实就是将两者顺序颠倒,再进行一次匹配而已,因此我们的程序可以简单的更改为以下形式。

    package com.creditease.borrow.lucene;
    
    import java.io.IOException;
    import java.util.HashSet;
    import java.util.Set;
    
    import org.apache.lucene.analysis.TokenStream;
    import org.apache.lucene.analysis.cn.smart.SmartChineseAnalyzer;
    import org.apache.lucene.analysis.tokenattributes.CharTermAttribute;
    import org.apache.lucene.util.Version;
    
    public class App 
    {
        
        private static SmartChineseAnalyzer smartChineseAnalyzer = new SmartChineseAnalyzer(Version.LUCENE_47);
        
        public static void main( String[] args ) throws IOException
        {
            String text1 = "博客园科技发展(北京)有限公司";
            String text2 = "博客园科技发展有限公司";
            System.out.println(twoWayMatch(text1, text2));
        }
        
        public static double twoWayMatch(String text1,String text2) {
            return (oneWayMatch(text1, text2) + oneWayMatch(text2, text1));
        }
        
        public static double oneWayMatch(String text1,String text2) {
            try {
                Set<String> set = new HashSet<String>(10);
                TokenStream tokenStream = smartChineseAnalyzer.tokenStream("field", text1);
                CharTermAttribute charTermAttribute = tokenStream.getAttribute(CharTermAttribute.class);
                tokenStream.reset();
                while (tokenStream.incrementToken()) {
                    set.add(charTermAttribute.toString());
                }
                int denominator = set.size();
                tokenStream.end();
                tokenStream.close();
                tokenStream = smartChineseAnalyzer.tokenStream("field", text2);
                charTermAttribute = tokenStream.getAttribute(CharTermAttribute.class);
                tokenStream.reset();
                while (tokenStream.incrementToken()) {
                    set.add(charTermAttribute.toString());
                }
                int numerator = set.size() - denominator;
                double unmatchRate = ((double)numerator)/denominator;
                tokenStream.end();
                tokenStream.close();
                return unmatchRate;
            } catch (IOException e) {
                return 1D;
            }
            
        }
        
    }

      该程序的输出结果为0.1666666666...,也就是0.17,也就是说两者的匹配度为83%。这个值显然更加接近实际的情况。可以看到,双向匹配以单向匹配为基础,将顺序颠倒的结果相加,就能得到不匹配度。

      事情原本到此就可以结束了,但是还有一个更大的难点没有处理。那就是匹配度到底设置为多少合适。这个问题到目前为止,LZ还没有更好的办法。按照上面的小例子来讲,自然是设为80%就可以。

      但是看下下面这个例子,就会发现这个数值很不正确,或者说匹配算法还是有问题。

    public static void main( String[] args ) throws IOException
        {
            String text1 = "博客园科技发展(北京)有限公司";
            String text2 = "博客园有限公司";
            System.out.println(twoWayMatch(text1, text2));
        }

      运行的结果为0.75,也就是说匹配度大约只有25%。但是很明显,上面两个公司实际上匹配度是很高的,因为最重要的三个字是匹配的。

      再仔细分析一下,问题就变成权重了。也就是说,每个词的权重应该是不一样的,这样的话,匹配的准确度可能会更高一点。我们稍微改善一下程序。(以下统一使用后面加双斜线的方式表示程序主要改变的地方)

    package com.creditease.borrow.lucene;
    
    import java.io.IOException;
    import java.util.Arrays;
    import java.util.HashSet;
    import java.util.List;
    import java.util.Set;
    
    import org.apache.lucene.analysis.TokenStream;
    import org.apache.lucene.analysis.cn.smart.SmartChineseAnalyzer;
    import org.apache.lucene.analysis.tokenattributes.CharTermAttribute;
    import org.apache.lucene.util.Version;
    
    public class App 
    {
        
        private static SmartChineseAnalyzer smartChineseAnalyzer = new SmartChineseAnalyzer(Version.LUCENE_47);
        
        private static List<String> smallWeightWords = Arrays.asList("公司","有限公司","科技","发展","股份");
        
        private static double smallWeight = 0.3D;
        
        public static void main( String[] args ) throws IOException
        {
            String text1 = "博客园科技发展(北京)有限公司";
            String text2 = "博客园有限公司";
            System.out.println(twoWayMatch(text1, text2));
        }
        
        public static double twoWayMatch(String text1,String text2) {
            return (oneWayMatch(text1, text2) + oneWayMatch(text2, text1));
        }
        
        public static double oneWayMatch(String text1,String text2) {
            try {
                Set<String> set = new HashSet<String>(10);
                TokenStream tokenStream = smartChineseAnalyzer.tokenStream("field", text1);
                CharTermAttribute charTermAttribute = tokenStream.getAttribute(CharTermAttribute.class);
                tokenStream.reset();
                while (tokenStream.incrementToken()) {
                    set.add(charTermAttribute.toString());
                }
                int denominator = set.size();
                tokenStream.end();
                tokenStream.close();
                tokenStream = smartChineseAnalyzer.tokenStream("field", text2);
                charTermAttribute = tokenStream.getAttribute(CharTermAttribute.class);
                tokenStream.reset();
                int smallWeightWordsCount = 0;//
                while (tokenStream.incrementToken()) {
                    String word = charTermAttribute.toString();//
                    int tempSize = set.size();//
                    set.add(word);//
                    if (tempSize + 1 == set.size() && smallWeightWords.contains(word)) {//
                        smallWeightWordsCount++;//
                    }//
                }
                int numerator = set.size() - denominator;
                double unmatchRate = (smallWeightWordsCount * smallWeight + numerator - ((double)smallWeightWordsCount))/denominator;//
                tokenStream.end();
                tokenStream.close();
                return unmatchRate;
            } catch (IOException e) {
                return 1D;
            }
            
        }
        
    }

      现在程序的输出结果为0.4,匹配度为60%。从结果来看,依然有点不尽人意。仔细分析一下程序,会发现,我们计算不匹配度的时候,是交叉计算的。也就是说,我们使用一个数组中不匹配的数目去除以另外一个数组的大小,这可能会造成“极端”数值。

      我们需要调整程序,让数组自己与自己计算,这样就不会出现那种情况。如下。

    package com.creditease.borrow.lucene;
    
    import java.io.IOException;
    import java.util.Arrays;
    import java.util.HashSet;
    import java.util.List;
    import java.util.Set;
    
    import org.apache.lucene.analysis.TokenStream;
    import org.apache.lucene.analysis.cn.smart.SmartChineseAnalyzer;
    import org.apache.lucene.analysis.tokenattributes.CharTermAttribute;
    import org.apache.lucene.util.Version;
    
    public class App 
    {
        
        private static SmartChineseAnalyzer smartChineseAnalyzer = new SmartChineseAnalyzer(Version.LUCENE_47);
        
        private static List<String> smallWeightWords = Arrays.asList("公司","有限公司","科技","发展","股份");
        
        private static double smallWeight = 0.3D;
        
        public static void main( String[] args ) throws IOException
        {
            String text1 = "博客园科技发展(北京)有限公司";
            String text2 = "博客园有限公司";
            System.out.println(twoWayMatch(text1, text2));
        }
        
        public static double twoWayMatch(String text1,String text2) {
            return (oneWayMatch(text1, text2) + oneWayMatch(text2, text1));
        }
        
        public static double oneWayMatch(String text1,String text2) {
            try {
                Set<String> set = new HashSet<String>(10);
                TokenStream tokenStream = smartChineseAnalyzer.tokenStream("field", text1);
                CharTermAttribute charTermAttribute = tokenStream.getAttribute(CharTermAttribute.class);
                tokenStream.reset();
                while (tokenStream.incrementToken()) {
                    set.add(charTermAttribute.toString());
                }
                int originalCount = set.size();//
                tokenStream.end();
                tokenStream.close();
                tokenStream = smartChineseAnalyzer.tokenStream("field", text2);
                charTermAttribute = tokenStream.getAttribute(CharTermAttribute.class);
                tokenStream.reset();
                int smallWeightWordsCount = 0;
                int denominator = 0;//
                while (tokenStream.incrementToken()) {
                    denominator++;//
                    String word = charTermAttribute.toString();
                    int tempSize = set.size();
                    set.add(word);
                    if (tempSize + 1 == set.size() && smallWeightWords.contains(word)) {
                        smallWeightWordsCount++;
                    }
                }
                int numerator = set.size() - originalCount;
                double unmatchRate = (smallWeightWordsCount * smallWeight + numerator - ((double)smallWeightWordsCount))/denominator;//
                tokenStream.end();
                tokenStream.close();
                return unmatchRate;
            } catch (IOException e) {
                return 1D;
            }
            
        }
        
    }

      程序的输出结果为0.2285714285714286,也就是匹配度大约为77%,这个数值还是比较科学的。这次我们主要调整了分母,将分母调整为不匹配元素自己的数组大小。

      现在我们需要做的就很简单了,就是把有可能改变的地方都在程序当中做成可配置的,比如从数据库读取。需要做成可配置项的内容有以下几个。

      1、低权重的词语,也就是smallWeightWords。

      2、低权重的数值,也就是smallWeight。

      3、匹配度的最小值,也就是说匹配度大于等于多少的时候,我们就认为是一个公司。

      具体如何做成可配置项,这里LZ就不再赘述了,真实的web项目当中有无数种办法可以达到这个目的,最常用的当然是存储到数据库。但第一项更适合放入数据库,后面两项更适合存放在配置文件当中。无论放在哪里,这些配置都要支持动态刷新,这样应用在运行的时候就可以动态调整判断规则了。

      

    小结

     

      LZ的算法不一定是最好的,或者说一定不是最好的。但是有时候慢慢解决一个问题,让答案逐渐靠近自己的判断也是一种乐趣不是吗?


    版权声明:本文版权归作者(左潇龙)所有,欢迎转载。但未经作者同意必须保留此段声明,且在文章页面明显位置给出原文连接,否则保留追究法律责任的权利。

    8
    精彩
    0
    感动
    0
    搞笑
    0
    开心
    0
    愤怒
    0
    无聊
    0
    灌水
    0
    惊讶
#1楼     时间:2014-07-13 15:24:00      来源:rocketball
词的权重可以用TD*IDF,中文分词Apache的不一定好的,IK或者复旦的库都比lucene好
#2楼     时间:2014-07-13 16:18:00      来源:天天
我以前在项目里也用过类似功能,另有二点(1)当时做一个计划任务定时扫描表的中文分词到另一个表中,以提高查询速度。(2)当用户查找时,关键词会写到search表中,我们会定期查看系统匹配结果,如果不准,会人工调整
#3楼     时间:2014-07-13 16:57:00      来源:左潇龙
@ rocketball
分词工具可以随时替换,这个倒不打紧,不过我很想知道TD和IDF是什么,能具体解释一下吗?或者最好直接把这种思想的java代码拿出来也可以。
#4楼     时间:2014-07-13 16:58:00      来源:左潇龙
@ 天天
抱歉,没太看明白,意思是定时批量处理提高速度吗?
#5楼     时间:2014-07-13 18:11:00      来源:海神解说
刚刚开始软件行业,还没遇到这种需求,互联网的技术果然比公司erp什么的更有意思啊。请问楼主,。net中有这种类似的类库可以用么?
#6楼     时间:2014-07-13 18:14:00      来源:passer.net
博主想要的应该是字符串相似度判断的算法
简单的来说就是通过 “插入 删除 修改”一个字符 从字符串A搭配字符串B一共需要多少个步骤。
这里有一个算法实现 http://www.cnblogs.com/stone_w/archive/2012/08/16/2642679.html

分词处理有可能让匹配的更准确也有可能让匹配的结果偏差更大。


实际情况我一般不建议分词后判断相似度。
#7楼     时间:2014-07-13 20:04:00      来源:__虚竹__
@左潇龙
DF和IDF,我知道是词频与反文档频率,分别代表某个词在所有文档中出现的次数与某个词在多少个文档中出现过的倒数。
#8楼     时间:2014-07-13 20:08:00      来源:左潇龙
@ 海神解说
嗯,互联网毕竟是服务于更多客户的,所谓林子大了什么鸟都有,需求也就是千奇百怪了。但这或许也正是互联网的魅力所在吧。
#9楼     时间:2014-07-13 20:11:00      来源:左潇龙
@ passer.net
大约看了下,好像思路大概是拆成一个一个的字,然后计算匹配度,其实与文中相比,就是去掉了第一步的过程。这确实也不失为一个办法。多谢提醒,后续真正上线后可以看看效果,进行适当的调整,如果分词效果不好,我就把分词的步骤去掉再观察一下。
#10楼     时间:2014-07-13 20:15:00      来源:左潇龙
@ __虚竹__
嗯,是这个意思。我还是忍不住百度了,0.0。不过好像场景与我的不太一样,那个更多的是基于大量的数据进行分析,类似于百度吧,主要是给搜索引擎用的,有点高端。这里的需求比较简单,似乎没有那么复杂。或许我对这个领域太陌生,还没悟出来吧。
#11楼     时间:2014-07-13 21:20:00      来源:Aimeast
别的不说了,我曾经一片关于字符串相似度的文章也许也有借鉴意义:

《【算法】字符串近似搜索》
http://www.cnblogs.com/Aimeast/archive/2011/09/05/2167844.html
#12楼     时间:2014-07-13 22:13:00      来源:StanZhai
#13楼     时间:2014-07-14 00:11:00      来源:寻风问雨
mark,写的不错。
不过总感觉匹配没有基准的感觉,感觉只是相对比较。有没有引入第三方绝对比较的方式?
#14楼     时间:2014-07-14 00:51:00      来源:左潇龙
@ Aimeast
非常感谢。不过这个好像和那个TD,IDF有点类似。场景都是类似于数据库里已经有一大把文章,然后用户输入一句话或者几个词语的时候,进行匹配,貌似还是搜索引擎的概念哦。
这里最大的不同是,文中是一个字符串和一个字符串比较,不论什么算法,最终的结果就是true或者false。而搜索引擎,则是一个字符串与一堆文章(假设是一堆文章吧,其余的类似),然后得出的结果是一个list,这个list里面的内容是根据最像、次像、次次像以此类推的内容。两者的区别在于一个是1对1比较,结果是布尔值,一个是1对多比较,结果是个按照相似度排过序的list集合。
两者感觉场景还是有点不太一样。可能我才疏学浅,对这些不太了解吧。
#15楼     时间:2014-07-14 00:52:00      来源:左潇龙
@ 寻风问雨
第三方绝对比较是什么意思,能否请您解释一下。说不定我听了后有什么启发呢。
#16楼     时间:2014-07-14 12:00:00      来源:无证临时程序员
公司名字这种特定场景里面包含了太多的“垃圾”成分,比如开头的省市名称,结尾的“有限责任公司”、“有限公司”、“公司”,中间还有“集团”、”XX研究所“、“XX设计院”,还有表明分公司的括号内省市名称,等等。去掉这些干扰项,剩下的干货作为输入再来匹配更有意义。
#17楼     时间:2014-07-14 14:26:00      来源:Zux
@ 无证临时程序员
省市是很重要的关键字,集团和有限公司也是很重要的关键字
xx集团和xx有限公司,事实上他们的关系一般来说是母子关系,但从企业来说他们是两家企业
1市xx公司和2市xx公司,更是有可能完全搭不上关系的两家企业
#18楼     时间:2017-11-02 16:21:00      来源:剑神西门吹雪
好文章,学习了。
发表评论

站内搜索

最新评论