1链表应用分词.docx
《1链表应用分词.docx》由会员分享,可在线阅读,更多相关《1链表应用分词.docx(10页珍藏版)》请在冰点文库上搜索。
1链表应用分词
实验内容:
根据下面文章的知识,编写程序实现基于词典的分词中的正向最大匹配算法,实现分词。
严澜:
数据挖掘入门——分词
谷歌4亿英镑收购人工智能公司DeepMind,XX目前正推进“XX大脑”项目,腾讯、阿里等各大巨头也在积极布局深度学习。
随着社会化数据大量产生,硬件速度上升、成本降低,大数据技术的落地实现,让冷冰冰的数据具有智慧逐渐成为新的热点。
要从数据中发现有用的信息就要用到数据挖掘技术,不过买来的数据挖掘书籍一打开全是大量的数学公式,而课本知识早已还给老师了,着实难以下手、非常头大!
我们不妨先跳过数学公式,看看我们了解数据挖掘的目的——发现数据中价值。
这个才是关键,如何发现数据中的价值。
那什么是数据呢?
比如大家要上网首先需要输入网址,打开网页后会自动判断哪些是图片、哪些是新闻、哪些是用户名称、游戏图标等。
大脑可以存储大量的信息,包括文字、声音、视频、图片等,这些同样可以转换成数据存储在电脑。
人的大脑可以根据输入自动进行判断,电脑可以通过输入判断吗?
答案是肯定的!
不过需要我们编写程序来判断每一种信息,就拿文字识别来说吧,怎么从一个人在社交网络的言论判断他今天的心情是高兴还是愤怒!
比如:
“你假如上午没给我吃冰淇淋,我绝对会不happy的。
” 信息发布时间为下午2点。
对于我们人类一看这个句子就知道他是吃过冰淇淋了,心情肯定不会是愤怒。
那计算机怎么知道呢?
这就是今天的主题,要让计算机理解句子的语义,必须要有个程序,上面的句子和发布时间是输入,输出就是“高兴”。
要得到“高兴”就要建立“高兴”的规则,可以建一个感情色彩词库,比如高兴(识别词是高兴、happy),愤怒(识别词是愤怒、生气)。
这里的识别词就是输入中出现的词语,比如上面的句子中的“happy”就识别出了“高兴”这个感情色彩词。
但是光识别出“happy”肯定是不行的,前面的“假如……没……,我……不……”等关键词都需要识别出来,才能完整判断一个句子的意思。
为了达到这个效果,就必须要用分词技术了。
分词
我们先人工对上面的句子来进行一下切词,使用斜线分割:
“你/假如/上午/没/给/我/吃/冰淇淋/,/我/绝对/会/不/happy/的/。
/”。
但是程序如何做到自动切分?
这个其实中国的前辈们已经做了很多中文分词的研究,常见的分词算法有:
1.基于词典的分词,需要先预设一个分词词典,比如上面句子切分出来的“假如、上午”这些词先存放在词典,然后把句子切分成单字组合成词语去词典里查找,匹配上了就挑选出来一个词。
没有匹配上的就切分成单字。
2.基于统计的分词,需要先获取大量的文本语料库(比如新闻、微博等),然后统计文本里相邻的字同时出现的次数,次数越多就越可能构成一个词。
当达到一定次数时就构成了一个词,即可形成语料概率库。
再对上面句子进行单字切分,把字与字结合后在语料概率库里查找对应的概率,如果概率大于一定值就挑选出来形成一个词。
这个是大概描述,实际生产环境中还需要对句子的上下文进行结合才能更准确的分词。
3.基于语义的分词,简而言之就是模拟人类对句子的理解来进行分词。
需要先整理出中文语句的句法、语义信息作为知识库,然后结合句子的上下文,对句子进行单字切分后组合成词逐个带入知识库进行识别,识别出来就挑选出一个词。
目前还没有特别成熟的基于语义的分词系统。
基于词典的分词
为了让大家快速的了解分词技术,我们采用第一个方式来做测试:
基于词典的分词,这种方式简单暴力可以解决百分之七八十的问题。
基于词典的分词大概分为以下几种方式:
1.正向最大匹配,沿着我们看到的句子逐字拆分后组合成词语到词典里去匹配,直到匹配不到词语为止。
举个实际的例子:
“人民大会堂真雄伟”,我们先拆分为单字“人”去词典里去查找,发现有“人”这个词,继续组合句子里的单字组合“人民”去词典里查找,发现有“人民”这个词,以此类推发现到“人民大会堂”,然后会结合“人民大会堂真”去词典里查找没有找到这个词,第一个词“人民大会堂”查找结束。
最终分词的结果为:
“人民大会堂/真/雄伟”。
如下图演示了用正向最大匹配算法识别人民大会堂的过程,“真”,“雄伟”的识别类似。
2.逆向最大匹配,这个和上面相反,就是倒着推理。
比如“沿海南方向”,我们按正向最大匹配来做就会切分成“沿海/南方/向”,这样就明显不对。
采用逆向最大匹配法则来解决这个问题,从句子的最后取得“方向”这两个字查找词典找到“方向”这个词。
再加上“南方向”组成三字组合查找词典没有这个词,查找结束,找到“方向”这个词。
以此类推,最终分出“沿/海南/方向”。
3.双向最大匹配,顾名思义就是结合正向最大匹配和逆向最大匹配,最终取其中合理的结果。
最早由哈工大王晓龙博士理论化的取最小切分词数,比如“我在中华人民共和国家的院子里看书”,正向最大匹配切分出来为“我/在/中华人民共和国/家/的/院子/里/看书”工8个词语,逆向最大匹配切分出来为“我/在/中华/人民/共/和/国家/的/院子/里/看书”共11个词语。
取正向最大匹配切出来的结果就是正确的。
但是如果把上面那个例子“沿海南方向”双向切分,都是3个词语,改如何选择?
看第4个《最佳匹配法则》。
4.最佳匹配法则,先准备一堆文本语料库、一个词库,统计词库里的每一个词在语料库里出现的次数记录下来。
最后按照词频高的优先选出,比如“沿海南方向”,正向切分为:
“沿海/南方/向”,逆向切分为:
“沿/海南/方向”。
其中“海南”的频度最高,优先取出来。
剩下“沿”、“方向”也就正常切分了。
是不是这就是基于词典分词的最佳方案?
比如数学之美中提到的:
“把手抬起来”和“这扇门的把手”,可以分为“把”、“手”、“把手”,不管怎么分总有一句话的意思不对。
后续再介绍如何通过统计的分词处理这些问题。
说了这么多,我们来实战一下如何基于词典的分词:
publicclassTestPositiveMatch{
publicstaticvoidmain(String[]args){
Stringstr="我爱这个中华人民共和国大家庭";
ListnormalDict=newArrayList();
normalDict.add("");
normalDict.add("爱");
normalDict.add("中华");//测试词库里有中华和中华人民共和国,按照最大匹配应该匹配出中华人民共和国
normalDict.add("中华人民共和国");
intstrLen=str.length();//传入字符串的长度
intj=0;
StringmatchWord="";//根据词库里识别出来的词
intmatchPos=0;//根据词库里识别出来词后当前句子中的位置
while(jintmatchPosTmp=0;//截取字符串的位置
inti=1;
while(matchPosTmpmatchPosTmp=i+j;
StringkeyTmp=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="";
}
}
}
输出结果为:
我爱这个中华人民共和国大家庭
按照这样我们一个基本的分词程序开发完成。
对于文章一开始提到的问题还没解决,如何让程序识别文本中的感情色彩。
现在我们先要构建一个感情色彩词库“高兴”,修饰词库“没”、"不”。
再完善一下我们的程序:
publicclassTestSentimentPositiveMatch{
publicstaticvoidmain(String[]args){
Stringstr="你假如上午没给我吃冰淇淋,我绝对会不happy的。
";
//语义映射
MapsentimentMap=newHashMap();
sentimentMap.put("happy","高兴");
//情感词库
ListsentimentDict=newArrayList();
sentimentDict.add("happy");
//修饰词
ListdecorativeDict=newArrayList();
decorativeDict.add("不");
decorativeDict.add("没");
//修饰词衡量分数
MapdecorativeScoreMap=newHashMap();
decorativeScoreMap.put("不",-0.5);
decorativeScoreMap.put("没",-0.5);
ListdecorativeWordList=newArrayList();//修饰词
StringsentimentResult="";//情感结果
intstrLen=str.length();//传入字符串的长度
intj=0;
StringmatchSentimentWord="";//根据词库里识别出来的情感词
StringmatchDecorativeWord="";//根据词库里识别出来的修饰词
intmatchPos=0;//根据词库里识别出来词后当前句子中的位置
while(jintmatchPosTmp=0;//截取字符串的位置
inti=1;
while(matchPosTmpmatchPosTmp=i+j;
StringkeyTmp=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="";
}
doubletotalScore=1;
for(StringdecorativeWord:
decorativeWordList){
DoublescoreTmp=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.如何识别新词、人名、新鲜事物等未知领域?
宇宙芸芸众生都是相通的,大脑也许就是一个小宇宙,在这个小宇宙又有很多星球、住着很多生物。
而电脑也是宇宙中地球上的一个产物,只要存储计算速度发展到足够强大一定可以构建成一个强大的大脑。
你看这个单词"testaword"认识吗?
可能不认识,因为我们五官先获取到的信息,然后根据大脑以往学习的经验做出判断。
但是你看这个短语"testaword"认识吗?
再看看开始那个单词“testaword”是不是就亲切多了?