java使用Nagao算法实现新词发现、热门词的挖掘
采用nagao算法统计各个子字符串的频次,然后基于这些频次统计每个字符串的词频、左右邻个数、左右熵、交互信息(内部凝聚度)。
名词解释:
nagao算法:一种快速的统计文本里所有子字符串频次的算法。详细算法可见
词频:该字符串在文档中出现的次数。出现次数越多越重要。
左右邻个数:文档中该字符串的左边和右边出现的不同的字的个数。左右邻越多,说明字符串成词概率越高。
左右熵:文档中该字符串的左边和右边出现的不同的字的数量分布的熵。类似上面的指标,有一定区别。
交互信息:每次将某字符串分成两部分,左半部分字符串和右半部分字符串,计算其同时出现的概率除于其各自独立出现的概率,最后取所有的划分里面概率最小值。这个值越大,说明字符串内部凝聚度越高,越可能成词。
算法具体流程:
1. 将输入文件逐行读入,按照非汉字([^\u4e00-\u9fa5]+)以及停词“的很了么呢是嘛个都也比还这于不与才上用就好在和对挺去后没说”,
分成一个个字符串,代码如下:
string[] phrases = line.split("[^\u4e00-\u9fa5]+|["+stopwords+"]");
停用词可以修改。
2. 获取所有切分后的字符串的左子串和右子串,分别加入左、右ptable
3. 对ptable排序,并计算ltable。ltable记录的是,排序后的ptable中,下一个子串同上一个子串具有相同字符的数量
4. 遍历ptable和ltable,即可得到所有子字符串的词频、左右邻
5. 根据所有子字符串的词频、左右邻结果,输出字符串的词频、左右邻个数、左右熵、交互信息
1. nagaoalgorithm.java
package com.algo.word; import java.io.bufferedreader; import java.io.bufferedwriter; import java.io.filenotfoundexception; import java.io.filereader; import java.io.filewriter; import java.io.ioexception; import java.util.arraylist; import java.util.arrays; import java.util.collections; import java.util.hashmap; import java.util.hashset; import java.util.list; import java.util.map; import java.util.set; public class nagaoalgorithm { private int n; private list<string> leftptable; private int[] leftltable; private list<string> rightptable; private int[] rightltable; private double wordnumber; private map<string, tfneighbor> wordtfneighbor; private final static string stopwords = "的很了么呢是嘛个都也比还这于不与才上用就好在和对挺去后没说"; private nagaoalgorithm(){ //default n = 5 n = 5; leftptable = new arraylist<string>(); rightptable = new arraylist<string>(); wordtfneighbor = new hashmap<string, tfneighbor>(); } //reverse phrase private string reverse(string phrase) { stringbuilder reversephrase = new stringbuilder(); for (int i = phrase.length() - 1; i >= 0; i--) reversephrase.append(phrase.charat(i)); return reversephrase.tostring(); } //co-prefix length of s1 and s2 private int coprefixlength(string s1, string s2){ int coprefixlength = 0; for(int i = 0; i < math.min(s1.length(), s2.length()); i++){ if(s1.charat(i) == s2.charat(i)) coprefixlength++; else break; } return coprefixlength; } //add substring of line to ptable private void addtoptable(string line){ //split line according to consecutive none chinese character string[] phrases = line.split("[^\u4e00-\u9fa5]+|["+stopwords+"]"); for(string phrase : phrases){ for(int i = 0; i < phrase.length(); i++) rightptable.add(phrase.substring(i)); string reversephrase = reverse(phrase); for(int i = 0; i < reversephrase.length(); i++) leftptable.add(reversephrase.substring(i)); wordnumber += phrase.length(); } } //count ltable private void countltable(){ collections.sort(rightptable); rightltable = new int[rightptable.size()]; for(int i = 1; i < rightptable.size(); i++) rightltable[i] = coprefixlength(rightptable.get(i-1), rightptable.get(i)); collections.sort(leftptable); leftltable = new int[leftptable.size()]; for(int i = 1; i < leftptable.size(); i++) leftltable[i] = coprefixlength(leftptable.get(i-1), leftptable.get(i)); system.out.println("info: [nagao algorithm step 2]: having sorted ptable and counted left and right ltable"); } //according to ptable and ltable, count statistical result: tf, neighbor distribution private void counttfneighbor(){ //get tf and right neighbor for(int pindex = 0; pindex < rightptable.size(); pindex++){ string phrase = rightptable.get(pindex); for(int length = 1 + rightltable[pindex]; length <= n && length <= phrase.length(); length++){ string word = phrase.substring(0, length); tfneighbor tfneighbor = new tfneighbor(); tfneighbor.incrementtf(); if(phrase.length() > length) tfneighbor.addtorightneighbor(phrase.charat(length)); for(int lindex = pindex+1; lindex < rightltable.length; lindex++){ if(rightltable[lindex] >= length){ tfneighbor.incrementtf(); string cophrase = rightptable.get(lindex); if(cophrase.length() > length) tfneighbor.addtorightneighbor(cophrase.charat(length)); } else break; } wordtfneighbor.put(word, tfneighbor); } } //get left neighbor for(int pindex = 0; pindex < leftptable.size(); pindex++){ string phrase = leftptable.get(pindex); for(int length = 1 + leftltable[pindex]; length <= n && length <= phrase.length(); length++){ string word = reverse(phrase.substring(0, length)); tfneighbor tfneighbor = wordtfneighbor.get(word); if(phrase.length() > length) tfneighbor.addtoleftneighbor(phrase.charat(length)); for(int lindex = pindex + 1; lindex < leftltable.length; lindex++){ if(leftltable[lindex] >= length){ string cophrase = leftptable.get(lindex); if(cophrase.length() > length) tfneighbor.addtoleftneighbor(cophrase.charat(length)); } else break; } } } system.out.println("info: [nagao algorithm step 3]: having counted tf and neighbor"); } //according to wordtfneighbor, count mi of word private double countmi(string word){ if(word.length() <= 1) return 0; double coprobability = wordtfneighbor.get(word).gettf()/wordnumber; list<double> mi = new arraylist<double>(word.length()); for(int pos = 1; pos < word.length(); pos++){ string leftpart = word.substring(0, pos); string rightpart = word.substring(pos); double leftprobability = wordtfneighbor.get(leftpart).gettf()/wordnumber; double rightprobability = wordtfneighbor.get(rightpart).gettf()/wordnumber; mi.add(coprobability/(leftprobability*rightprobability)); } return collections.min(mi); } //save tf, (left and right) neighbor number, neighbor entropy, mutual information private void savetfneighborinfomi(string out, string stoplist, string[] threshold){ try { //read stop words file set<string> stopwords = new hashset<string>(); bufferedreader br = new bufferedreader(new filereader(stoplist)); string line; while((line = br.readline()) != null){ if(line.length() > 1) stopwords.add(line); } br.close(); //output words tf, neighbor info, mi bufferedwriter bw = new bufferedwriter(new filewriter(out)); for(map.entry<string, tfneighbor> entry : wordtfneighbor.entryset()){ if( entry.getkey().length() <= 1 || stopwords.contains(entry.getkey()) ) continue; tfneighbor tfneighbor = entry.getvalue(); int tf, leftneighbornumber, rightneighbornumber; double mi; tf = tfneighbor.gettf(); leftneighbornumber = tfneighbor.getleftneighbornumber(); rightneighbornumber = tfneighbor.getrightneighbornumber(); mi = countmi(entry.getkey()); if(tf > integer.parseint(threshold[0]) && leftneighbornumber > integer.parseint(threshold[1]) && rightneighbornumber > integer.parseint(threshold[2]) && mi > integer.parseint(threshold[3]) ){ stringbuilder sb = new stringbuilder(); sb.append(entry.getkey()); sb.append(",").append(tf); sb.append(",").append(leftneighbornumber); sb.append(",").append(rightneighbornumber); sb.append(",").append(tfneighbor.getleftneighborentropy()); sb.append(",").append(tfneighbor.getrightneighborentropy()); sb.append(",").append(mi).append("\n"); bw.write(sb.tostring()); } } bw.close(); } catch (ioexception e) { throw new runtimeexception(e); } system.out.println("info: [nagao algorithm step 4]: having saved to file"); } //apply nagao algorithm to input file public static void applynagao(string[] inputs, string out, string stoplist){ nagaoalgorithm nagao = new nagaoalgorithm(); //step 1: add phrases to ptable string line; for(string in : inputs){ try { bufferedreader br = new bufferedreader(new filereader(in)); while((line = br.readline()) != null){ nagao.addtoptable(line); } br.close(); } catch (ioexception e) { throw new runtimeexception(); } } system.out.println("info: [nagao algorithm step 1]: having added all left and right substrings to ptable"); //step 2: sort ptable and count ltable nagao.countltable(); //step3: count tf and neighbor nagao.counttfneighbor(); //step4: save tf neighborinfo and mi nagao.savetfneighborinfomi(out, stoplist, "20,3,3,5".split(",")); } public static void applynagao(string[] inputs, string out, string stoplist, int n, string filter){ nagaoalgorithm nagao = new nagaoalgorithm(); nagao.setn(n); string[] threshold = filter.split(","); if(threshold.length != 4){ system.out.println("error: filter must have 4 numbers, seperated with ',' "); return; } //step 1: add phrases to ptable string line; for(string in : inputs){ try { bufferedreader br = new bufferedreader(new filereader(in)); while((line = br.readline()) != null){ nagao.addtoptable(line); } br.close(); } catch (ioexception e) { throw new runtimeexception(); } } system.out.println("info: [nagao algorithm step 1]: having added all left and right substrings to ptable"); //step 2: sort ptable and count ltable nagao.countltable(); //step3: count tf and neighbor nagao.counttfneighbor(); //step4: save tf neighborinfo and mi nagao.savetfneighborinfomi(out, stoplist, threshold); } private void setn(int n){ n = n; } public static void main(string[] args) { string[] ins = {"e://test//ganfen.txt"}; applynagao(ins, "e://test//out.txt", "e://test//stoplist.txt"); } }
2. tfneighbor.java
package com.algo.word; import java.util.hashmap; import java.util.map; public class tfneighbor { private int tf; private map<character, integer> leftneighbor; private map<character, integer> rightneighbor; tfneighbor(){ leftneighbor = new hashmap<character, integer>(); rightneighbor = new hashmap<character, integer>(); } //add word to leftneighbor public void addtoleftneighbor(char word){ //leftneighbor.put(word, 1 + leftneighbor.getordefault(word, 0)); integer number = leftneighbor.get(word); leftneighbor.put(word, number == null? 1: 1+number); } //add word to rightneighbor public void addtorightneighbor(char word){ //rightneighbor.put(word, 1 + rightneighbor.getordefault(word, 0)); integer number = rightneighbor.get(word); rightneighbor.put(word, number == null? 1: 1+number); } //increment tf public void incrementtf(){ tf++; } public int getleftneighbornumber(){ return leftneighbor.size(); } public int getrightneighbornumber(){ return rightneighbor.size(); } public double getleftneighborentropy(){ double entropy = 0; int sum = 0; for(int number : leftneighbor.values()){ entropy += number*math.log(number); sum += number; } if(sum == 0) return 0; return math.log(sum) - entropy/sum; } public double getrightneighborentropy(){ double entropy = 0; int sum = 0; for(int number : rightneighbor.values()){ entropy += number*math.log(number); sum += number; } if(sum == 0) return 0; return math.log(sum) - entropy/sum; } public int gettf(){ return tf; } }
3. main.java
package com.algo.word; public class main { public static void main(string[] args) { //if 3 arguments, first argument is input files splitting with ',' //second argument is output file //output 7 columns split with ',' , like below: //word, term frequency, left neighbor number, right neighbor number, left neighbor entropy, right neighbor entropy, mutual information //third argument is stop words list if(args.length == 3) nagaoalgorithm.applynagao(args[0].split(","), args[1], args[2]); //if 4 arguments, forth argument is the ngram parameter n //5th argument is threshold of output words, default is "20,3,3,5" //output tf > 20 && (left | right) neighbor number > 3 && mi > 5 else if(args.length == 5) nagaoalgorithm.applynagao(args[0].split(","), args[1], args[2], integer.parseint(args[3]), args[4]); } }
以上所述就是本文的全部内容了,希望大家能够喜欢。
上一篇: java实现短地址服务的方法(附代码)