中文分词程序

昨天在博客园看到一个朋友些的中文分词程序。net版，自我感觉不是很难，于是决定自己动手写一个java版的，那个朋友的分词程序是基于词典的，于是乎我就去找中文词库，经过一段时间我找到了大约有42万条词条的词库，这词库是我从网上东拼西凑的。说一下我的思路。

 我的思路是首先定义一个词典类，采用单例模式，代码如下：

/** 
 * black he 
 *天雅  www.itp1.cn 
 */ 
/** 
 *  
 */ 
package cn.itp1;  
 
import java.io.BufferedReader;  
import java.io.File;  
import java.io.FileReader;  
import java.util.HashMap;  
 
/** 
 * 词典类 
 *  
 * @author black he 天雅 www.itp1.cn 
 */ 
public class Dictionary {  
    /** 
     * hashMap用于词条的键值对，键为词条字符串，值为该词条出现在词典中各词条前端的次数 。 
     * 在本程序中都设置为1； 
     */ 
    private HashMap<String, Integer> hm;  
    private static Dictionary dictionary;  
 
    /** 
     *  
     */ 
    private Dictionary() {  
        hm = new HashMap<String, Integer>();  
    }  
 
    public static Dictionary getInstance() {  
        if (dictionary == null) {  
            dictionary = new Dictionary();  
        }  
        return dictionary;  
    }  
    /** 
     * 插入词条 
     * @param s 
     */ 
    public void insertWord(String s) {  
        if (s != null && !s.trim().equals("") && !hm.containsKey(s)) {  
            int count = 1;  
            //以下代码是计算该词条出现在词典中各词条前端的次数 。不过加载词典的效率将大大的降低  
            // for (String key : hm.keySet()) {  
            // if (((key.length() > s.length()) && (key.substring(0, s  
            // .length() - 1).equals(s)))) {  
            // count++;  
            // }  
            // if ((key.length() < s.length())  
            // && (s.substring(0, key.length() - 1).equals(key))) {  
            // int i = hm.get(key);  
            // i++;  
            // hm.remove(key);  
            // hm.put(key, i);  
            // }  
            // }  
            hm.put(s, count);  
        }  
    }  
 
    /** 
     * 字符串是否出现在词典中 
     *  
     * @param s 
     * @return 
     */ 
    public int getCount(String s) {  
        if (!hm.containsKey(s)) {  
            return 0;  
        } else {  
            return hm.get(s);  
        }  
    }  
 
    /** 
     * 初始化词典 
     *  
     * @param path 
     *            词典文件名或者文件夹名 
     */ 
    public void initDictionary(String path) {  
        readDictionary(new File(path));  
    }  
 
    /** 
     * 返回词典词条数目 
     *  
     * @return 
     */ 
    public int count() {  
        return hm.size();  
    }  
 
    /** 
     * 初始化词典词条 
     *  
     * @param path 
     *            词典文件名或者文件夹名 
     */ 
    private void readDictionary(File path) {  
        BufferedReader bReader = null;  
        if (path == null) {  
            return;  
        }  
        if (path.isDirectory()) {  
            File[] fs = path.listFiles();  
            for (File f : fs) {  
                readDictionary(f);  
            }  
        } else {  
            if (path.getName().endsWith("txt")  
                    || path.getName().endsWith("TXT")) {  
                try {  
                    bReader = new BufferedReader(new FileReader(path));  
                    String word = "";  
                    while ((word = bReader.readLine()) != null) {  
                        insertWord(word);  
                        // System.out.println(word);  
                    }  
                } catch (Exception e) {  
                    // TODO Auto-generated catch block  
                    e.printStackTrace();  
                }  
            }  
        }  
    }  
} 
/**
 * black he
 *天雅  www.itp1.cn
 */
/**
 *
 */
package cn.itp1;

import java.io.BufferedReader;
import java.io.File;
import java.io.FileReader;
import java.util.HashMap;

/**
 * 词典类
 *
 * @author black he 天雅 www.itp1.cn
 */
public class Dictionary {
 /**
  * hashMap用于词条的键值对，键为词条字符串，值为该词条出现在词典中各词条前端的次数 。
  * 在本程序中都设置为1；
  */
 private HashMap<String, Integer> hm;
 private static Dictionary dictionary;

 /**
  *
  */
 private Dictionary() {
  hm = new HashMap<String, Integer>();
 }

 public static Dictionary getInstance() {
  if (dictionary == null) {
   dictionary = new Dictionary();
  }
  return dictionary;
 }
 /**
  * 插入词条
  * @param s
  */
 public void insertWord(String s) {
  if (s != null && !s.trim().equals("") && !hm.containsKey(s)) {
   int count = 1;
   //以下代码是计算该词条出现在词典中各词条前端的次数 。不过加载词典的效率将大大的降低
   // for (String key : hm.keySet()) {
   // if (((key.length() > s.length()) && (key.substring(0, s
   // .length() - 1).equals(s)))) {
   // count++;
   // }
   // if ((key.length() < s.length())
   // && (s.substring(0, key.length() - 1).equals(key))) {
   // int i = hm.get(key);
   // i++;
   // hm.remove(key);
   // hm.put(key, i);
   // }
   // }
   hm.put(s, count);
  }
 }

 /**
  * 字符串是否出现在词典中
  *
  * @param s
  * @return
  */
 public int getCount(String s) {
  if (!hm.containsKey(s)) {
   return 0;
  } else {
   return hm.get(s);
  }
 }

 /**
  * 初始化词典
  *
  * @param path
  *            词典文件名或者文件夹名
  */
 public void initDictionary(String path) {
  readDictionary(new File(path));
 }

 /**
  * 返回词典词条数目
  *
  * @return
  */
 public int count() {
  return hm.size();
 }

 /**
  * 初始化词典词条
  *
  * @param path
  *            词典文件名或者文件夹名
  */
 private void readDictionary(File path) {
  BufferedReader bReader = null;
  if (path == null) {
   return;
  }
  if (path.isDirectory()) {
   File[] fs = path.listFiles();
   for (File f : fs) {
    readDictionary(f);
   }
  } else {
   if (path.getName().endsWith("txt")
     || path.getName().endsWith("TXT")) {
    try {
     bReader = new BufferedReader(new FileReader(path));
     String word = "";
     while ((word = bReader.readLine()) != null) {
      insertWord(word);
      // System.out.println(word);
     }
    } catch (Exception e) {
     // TODO Auto-generated catch block
     e.printStackTrace();
    }
   }
  }
 }
}
 

代码就不一一解释了，看代码就可以了。

然后定义一个分词器类。里面定义一个静态常量MAXLENGTH表示最大搜索长度和一个静态方法parse(String s,Dictionary d) s为待切割的字符串，d为词典类的实例，返回切割后的字符串列表，代码如下：

/** 
* black he 
*天雅  www.itp1.cn 
*/ 
/** 
 *  
 */ 
package cn.itp1;  
 
import java.util.ArrayList;  
import java.util.List;  
 
/** 
 * 分词器 
 * @author black he 
 *天雅 www.itp1.cn 
 */ 
public class Parse {  
    /** 
     * 最大搜索长度 
     */ 
    private static final int MAXLENGTH=8;  
    /** 
     * 切割字符串，返回字符串列表 
     * @param s 待切割的字符串 
     * @param d 依据的词典 
     * @return 切割后的字符串列表 
     */ 
    public static List<String> parse(String s,Dictionary d) {  
        List<String> list=new ArrayList<String>();  
        s=s.trim().replaceAll("<(\\S*?)[^>]*>|</\1>|<.*? />", "");//去除html标记  
        s=s.replaceAll("[，。？：；‘’！“”—……、,!?]", " ");//替换标点符号  
        int k=1;  
 
        for (int i = 0; i < s.length();) {  
            loop:  
            for (int j = i; j < ((s.length()<(i+MAXLENGTH)?s.length():(i+MAXLENGTH))); j++) {  
                String subString=s.substring(i, j+1);  
                //是否中文  
                if (subString.matches("^[\u4e00-\u9fa5]+")) {  
                    //是否在词典里  
                    if (d.getCount(subString)>0) {  
                        list.add(subString);  
                    }  
                }   
                //是否单词符号，.@  
                else if (subString.matches("^[\\w.@://]+")) {  
                    int n=0;  
                    //切割单词，数字，email，网址  
                    while (subString.matches("^[\\w.:@//]+$")) {  
                        if (i+subString.length()>=s.length()||s.substring(i+subString.length(), i+subString.length()+1).matches("\\s|[\u4e00-\u9fa5|，|。|！|!|?|？]")) {  
                            if (!subString.matches("[.:;/]*")) {  
                                list.add(subString);  
                                k = subString.length();  
                                i += k;  
                                break loop;  
                            }  
                        }  
                        n++;  
                        subString=s.substring(i, i+n);  
                    }  
                }  
            }  
            i++;  
        }  
        return list;  
          
    }  
} 
/**
* black he
*天雅  www.itp1.cn
*/
/**
 *
 */
package cn.itp1;

import java.util.ArrayList;
import java.util.List;

/**
 * 分词器
 * @author black he
 *天雅 www.itp1.cn
 */
public class Parse {
 /**
  * 最大搜索长度
  */
 private static final int MAXLENGTH=8;
 /**
  * 切割字符串，返回字符串列表
  * @param s 待切割的字符串
  * @param d 依据的词典
  * @return 切割后的字符串列表
  */
 public static List<String> parse(String s,Dictionary d) {
  List<String> list=new ArrayList<String>();
  s=s.trim().replaceAll("<(\\S*?)[^>]*>|</\1>|<.*? />", "");//去除html标记
  s=s.replaceAll("[，。？：；‘’！“”—……、,!?]", " ");//替换标点符号
  int k=1;

  for (int i = 0; i < s.length();) {
   loop:
   for (int j = i; j < ((s.length()<(i+MAXLENGTH)?s.length():(i+MAXLENGTH))); j++) {
    String subString=s.substring(i, j+1);
    //是否中文
    if (subString.matches("^[\u4e00-\u9fa5]+")) {
     //是否在词典里
     if (d.getCount(subString)>0) {
      list.add(subString);
     }
    }
    //是否单词符号，.@
    else if (subString.matches("^[\\w.@://]+")) {
     int n=0;
     //切割单词，数字，email，网址
     while (subString.matches("^[\\w.:@//]+$")) {
      if (i+subString.length()>=s.length()||s.substring(i+subString.length(), i+subString.length()+1).matches("\\s|[\u4e00-\u9fa5|，|。|！|!|?|？]")) {
       if (!subString.matches("[.:;/]*")) {
        list.add(subString);
        k = subString.length();
        i += k;
        break loop;
       }
      }
      n++;
      subString=s.substring(i, i+n);
     }
    }
   }
   i++;
  }
  return list;
  
 }
}
 

分词算法采用正向搜索算法，从左到右依次截取1到最大值字符组成新字符串，判断该字符串是否是中文，如果是中文，则和词典的词条比对，如果存在词典中则存入列表中，如果不是中文，则进入单词切割程序段，本人表达能力不好，有可能说不清楚，各位还是看代码吧。

测试数据为：

中南林业科技大学http://ajava.org/readbook/java/zixsc/9519.html，csdn我[e-mail]是http://www.itp1.cn丁力许文强wacth<li><a href="http://www.williamlong.info/google/" title="Google Earth" target="_blank">Google Earth观察</a></li><li><a href="http://www.williamlong.info/blog/" title="月光微博客" target="_blank">月光,我的微博新浪体育讯　在被尤文淘汰之后，皇马主帅博斯克拒绝接受媒体对球队后防线的批评，同时还为自己排出的首发阵容</a></li>&nbsp;</span>新浪体育讯　在被尤文淘汰之后，皇马主帅博斯克拒绝接受媒体对球队后防线的批评，同时还为自己排出的首发阵容进行了辩护。“失利是全队的责任，而 不仅仅是后防线该受指责，”博斯克说，“我并不认为我们踢得一塌糊涂。”“我们进入了半决赛，而且在晋级的道路上一路奋战。即使是今天的比赛我们也有几个 翻身的机会，但我们面对的对手非常强大，他们踢得非常好。”“我们的球迷应该为过去几个赛季里我们在冠军杯中的表现感到骄傲。”博斯克还说。对于博斯克在 首发中排出了久疏战阵的坎比亚索，赛后有记者提出了质疑，认为完全应该将队内的另一名球员帕文派遣上场以加强后卫线。对于这一疑议，博斯克拒绝承担所谓的 “责任”，认为球队的首发没有问题。“我们按照整个赛季以来的方式做了，对于人员上的变化我没有什么可说的。”对于球队在本赛季的前景，博斯克表示皇马还 有西甲联赛的冠军作为目标。“皇家马德里在冠军杯中战斗到了最后，我们在联赛中也将这么做。”oogle推出的这项服务对于早先的一个同类服务TwitterFeed是一个重大打击，FeedBurner无论从速度、功能还是稳定性上都领先一筹，根据我的测试，同一个Feed由FeedBurner同步到Twitter需要10分钟左右，而TwitterFeed则需要40分钟，足足慢了半小时。从细节上看，TwitterFeed发的消息没有留下RT的空间，让别人难以RT，在稳定性上看，TwitterFeed以前经常出现几小时故障情况，这个大概不会在FeedBurner上出现，预计未来几天将是TwitterFeed用户大逃亡的日子。

测试结果为：
中南 
中南林业科技大学  林业  科技  科技大学  大学  http://ajava.org/readbook/java/zixsc/9519.html  csdn  [e-mail]  http://www.itp1.cn  力  许文强  wacthGoogle  Earth  月光  光  我的  微博  新浪  新浪体育  体育 
尤文  淘汰  之后  皇马  主帅  拒绝  接受  媒体  球队  后防  防线  线的  批  批评  同时  还为  自己  排出  出的  首发 
首发阵容  阵容  新浪  新浪体育  体育  尤文  淘汰  之后  皇马  主帅  拒绝  接受  媒体  球队  后防  防线  线的  批  批评  同时 
还为  自己  排出  出的  首发  首发阵容  阵容  进行  行  行了  辩护  失利  利是  全队  责任  不仅  不仅仅  不仅仅是  仅仅  仅仅是 
仅是  后防  防线  该受  指责  我并  并  并不  并不认为  不认  不认为  认为  为我  为我们  我们  踢得  一塌糊涂  糊涂  我们  进入 
入了  半决赛  决赛  而且  而且在  晋级  道  道路  道路上  路上  一路  奋战  即使  即使是  今天  天的  比赛  我们  也有  几个 
翻身  机会  我们  面对  对的  对手  非常  强大  他们  踢得  非常  非常好  我们  我们的  们的  球迷  应该  该为  过去  几个 
赛季  里  我们  冠军  冠军杯  中的  表现  感到  骄傲  还说  对于  于博  首发  排出  出了  战阵  坎比亚索  赛后  后有  记者 
提出  出了  质疑  认为  完全  应该  内的  另一  一名  球员  帕文  派遣  上场  加强  后卫  后卫线  对于  这一  拒绝  承担  所谓  所谓的  责任  认为  球队  首发  没有  没有问题  有问题  问题  我们  按照  整个  赛季  以来  来的  方式  做了  对于  人员 
上的  变化  我没  我没有  没有  没有什么  有什么  什么  可说  说的  对于  球队  赛季  前景  表示  皇马  西甲  联赛  冠军  作为 
目标  皇家  皇家马德里  马德里  德里  里  冠军  冠军杯  战斗  斗  到了  最后  我们  联赛  也将  这么  这么做  oogle  出的  这项 
服务  对于  早先  先的  一个  同类  服务  TwitterFeed  一个  重大  大打  打击  FeedBurner  从速  速度  功  功能  还是  稳定  稳定性 
定性  领先  一筹  根据  据我  我的  测试  同一  同一个  一个  Feed  FeedBurner  Twitter  10  左右  TwitterFeed  需要  40  足足

 慢了  半小时  小时  细节  TwitterFeed  消息  没有  留下  RT  空间  别人  难以  RT  稳定  稳定性  定性  TwitterFeed  经  经常  出现  几小时  小时  故障  情况  这个  大概  概不  不会  不会在  会在  FeedBurner  出现  预计  未来  几天  将是  TwitterFeed  逃亡  日子 

 

 

从结果看出程序可以识别网址，email地址，单词，数字，但是不能识别词典里没有的词语和单字，另外分词效率低，我电脑cpu1.6M的，速度只有2-3万字每秒，如果哪位可以提高速度或者改进算法请不吝赐教，谢谢！