2006-12-26

原创中文分词代码分享（1.2）——词典接口

关键字: 中文分词
最后说一下双Hash结构的实现类DoubleHashDictionary类：
java 代码
 
  1. /* 
  2.  * @作者:Hades , 创建日期:2006-11-17 
  3.  * 
  4.  * 汕头大学03计算机本科 
  5.  *  
  6.  */  
  7. package edu.stu.cn.segment.matching.dictionary;  
  8.   
  9. import java.io.BufferedReader;  
  10. import java.io.FileReader;  
  11. import java.io.IOException;  
  12. import java.io.PrintStream;  
  13. import java.io.Serializable;  
  14. import java.util.ArrayList;  
  15. import java.util.Collections;  
  16. import java.util.Hashtable;  
  17. import java.util.LinkedList;  
  18.   
  19. /** 
  20.  * @author Hades Guan 基于词典分词方法中使用的词典实例 
  21.  */  
  22. public class DoubleHashDictionary implements Serializable, DictionaryImpl  
  23. {  
  24.     /** 
  25.      * serialVersionUID 的注释 
  26.      */  
  27.     private static final long serialVersionUID = -6085097706592874294L;  
  28.   
  29.     /** 
  30.      * 词典索引表 
  31.      */  
  32.     private Hashtablenull;  
  33.   
  34.     /** 
  35.      * 最大词长 
  36.      */  
  37.     private int maxWordLen = 0;  
  38.   
  39.     /** 
  40.      * 词典长度 
  41.      */  
  42.     private int wordCount = 0;  
  43.   
  44.     /** 
  45.      * 删除词典中的词word 
  46.      *  
  47.      * @param word 
  48.      *            待删除的词汇 
  49.      */  
  50.     public void deleteWord(String word)  
  51.     {  
  52.         if (word == null)  
  53.             return;  
  54.   
  55.         // 过滤多于空格  
  56.         word = word.trim();  
  57.         // 获取词长  
  58.         int len = word.length();  
  59.         // 判断词长为len的二级索引表（首字hash表）是否为空  
  60.         if (this.indexTable[len - 1] == null)  
  61.             return;  
  62.         // 获取词的首字  
  63.         String fch = word.substring(0, 1);  
  64.         // 首字对应的词汇列表  
  65.         ArrayList wal = null;  
  66.         if (this.indexTable[len - 1].containsKey(fch))  
  67.             wal = this.indexTable[len - 1].get(fch);  
  68.         else  
  69.             return;  
  70.   
  71.         // 判断是否包含该词汇  
  72.         String str = word.substring(1, len);  
  73.         if (Collections.binarySearch(wal, str) >= 0)  
  74.         {  
  75.             wal.remove(str);  
  76.             this.indexTable[len - 1].put(fch, wal);  
  77.         }  
  78.         else  
  79.             return;  
  80.     }  
  81.   
  82.     /** 
  83.      * @return 返回 maxWordLen。 
  84.      */  
  85.     public int getMaxWordLen()  
  86.     {  
  87.         return maxWordLen;  
  88.     }  
  89.   
  90.     /** 
  91.      * @return 返回 wordCount。 
  92.      */  
  93.     public int getWordCount()  
  94.     {  
  95.         return wordCount;  
  96.     }  
  97.   
  98.     /** 
  99.      * 将词汇word插入到词典文件中 
  100.      *  
  101.      * @param word 
  102.      *            待插入的词汇 
  103.      */  
  104.     public void insertWord(String word)  
  105.     {  
  106.         if (word == null)  
  107.             return;  
  108.   
  109.         // 过滤多于空格  
  110.         word = word.trim();  
  111.         // 获取词长  
  112.         int len = word.length();  
  113.         // 初始化二级索引表（首字hash表）  
  114.         if (this.indexTable[len - 1] == null)  
  115.             this.indexTable[len - 1] = new Hashtable
  116.         // 获取词的首字  
  117.         String fch = word.substring(0, 1);  
  118.         // 首字对应的词汇列表  
  119.         ArrayList wal = null;  
  120.         if (this.indexTable[len - 1].containsKey(fch))  
  121.             wal = this.indexTable[len - 1].get(fch);  
  122.         else  
  123.             wal = new ArrayList();  
  124.   
  125.         // 截取剩余部分  
  126.         String str = word.substring(1, len);  
  127.         // 当词汇表中不存在当前词汇时插入新词汇  
  128.         if (Collections.binarySearch(wal, str) < 0)  
  129.             wal.add(str);  
  130.   
  131.         Collections.sort(wal);  
  132.         this.indexTable[len - 1].put(fch, wal);  
  133.     }  
  134.   
  135.     /** 
  136.      * 载入以文本格式存储的词典 
  137.      *  
  138.      * @param fileName 
  139.      *            词典的文件名 
  140.      */  
  141.     @SuppressWarnings("unchecked")  
  142.     public void loadDictionary(String fileName)  
  143.     {  
  144.         try  
  145.         {  
  146.             // 初始化输入流  
  147.             BufferedReader in = new BufferedReader(new FileReader(fileName));  
  148.             String word = null;  
  149.             // 初始化记录链表  
  150.             LinkedList wordLink = new LinkedList();  
  151.             // 最大词长  
  152.             this.maxWordLen = 0;  
  153.   
  154.             // 读取词典  
  155.             while ((word = in.readLine()) != null)  
  156.             {  
  157.                 if (word.length() > this.maxWordLen)  
  158.                     this.maxWordLen = word.length();  
  159.                 wordLink.add(word);  
  160.                 this.wordCount++;  
  161.             }  
  162.   
  163.             // 初始化一级索引表（词长索引表）  
  164.             this.indexTable = new Hashtable[this.maxWordLen];  
  165.             // 重新遍历词典链表  
  166.             for (String w : wordLink)  
  167.             {  
  168.                 // 插入词汇  
  169.                 this.insertWord(w);  
  170.             }  
  171.             // 回收资源  
  172.             wordLink.clear();  
  173.         }  
  174.         catch (IOException e)  
  175.         {  
  176.             // TODO 自动生成 catch 块  
  177.             e.printStackTrace();  
  178.         }  
  179.     }  
  180.   
  181.     /** 
  182.      * 判断输入的字符串是否在词典中 
  183.      *  
  184.      * @param word 
  185.      *            待判断字符串 
  186.      * @return 判断结果 
  187.      */  
  188.     public boolean match(String word)  
  189.     {  
  190.         if (word == null)  
  191.             return false;  
  192.   
  193.         // 获取词长  
  194.         int len = word.length();  
  195.   
  196.         // 当词长大于当前词库中最大词长则返回false  
  197.         if (len > this.maxWordLen)  
  198.             return false;  
  199.   
  200.         // 当词长为len的hash索引表未被初始化时返回false  
  201.         if (this.indexTable[len - 1] == null)  
  202.             return false;  
  203.   
  204.         // 获取首字  
  205.         String fch = word.substring(0, 1);  
  206.         if (this.indexTable[len - 1].containsKey(fch))  
  207.         {  
  208.             if (len == 1)  
  209.                 return true;  
  210.             else  
  211.             {  
  212.                 // 获取以fch开头的词汇表  
  213.                 ArrayList wal = this.indexTable[len - 1].get(fch);  
  214.                 // 折半查找  
  215.                 if (Collections.binarySearch(wal, word.substring(1, len)) < 0)  
  216.                     return false;  
  217.                 else  
  218.                     return true;  
  219.             }  
  220.         }  
  221.         else  
  222.             return false;  
  223.     }  
  224.   
  225.     /** 
  226.      * 输出已载入内存中所有词汇 
  227.      *  
  228.      * @param out 
  229.      *            输出流 
  230.      */  
  231.     public void print(PrintStream out)  
  232.     {  
  233.         for (int i = 0; i < this.indexTable.length; i++)  
  234.         {  
  235.             out.println("词长：" + (i + 1));  
  236.             // 判断词典是否已初始化  
  237.             if (this.indexTable[i] != null)  
  238.             {  
  239.                 for (String fch : this.indexTable[i].keySet())  
  240.                 {  
  241.                     out.println("首字：" + fch);  
  242.                     for (String w : this.indexTable[i].get(fch))  
  243.                         out.println("\t" + w);  
  244.                 }  
  245.             }  
  246.         }  
  247.         out.flush();  
  248.     }  
  249. }  
为什么说是双Hash结构呢？因为在查询词汇时，先使用词汇的长度length作为第一次Hash的key取出Hashtable结构的value，接下来也就跟首字Hash查询的操作一样了：取首字作为key取出一维线性表的value后采用折半查找。当词典中词汇数目很大时，一维线性表过长，进行折半查找无疑会提高比较的次数从而降低了效率。而使用双Hash正是希望通过增加多一次Hash求值从而将长的词汇表剪短成为多段较短的一维线性表减低折半查找时的比较次数。

既然说道了序列化，当然少不了序列化操作类DictionaryUtil：
java 代码
 
  1. /* 
  2.  * @作者:Hades , 创建日期:2006-11-18 
  3.  * 
  4.  * 汕头大学03计算机本科 
  5.  *  
  6.  */  
  7. package edu.stu.cn.segment.matching.util;  
  8.   
  9. import java.io.BufferedInputStream;  
  10. import java.io.BufferedOutputStream;  
  11. import java.io.FileInputStream;  
  12. import java.io.FileOutputStream;  
  13. import java.io.IOException;  
  14. import java.io.ObjectInputStream;  
  15. import java.io.ObjectOutputStream;  
  16.   
  17. import edu.stu.cn.segment.matching.dictionary.DictionaryImpl;  
  18.   
  19. /** 
  20.  * @author Hades Guan 词典工具类 
  21.  *  
  22.  */  
  23. public class DictionaryUtilextends DictionaryImpl>  
  24. {  
  25.     /** 
  26.      * 从fileName文件中读入词典实例 
  27.      *  
  28.      * @param fileName 
  29.      *            存储文件 
  30.      * @return 词典实例 
  31.      */  
  32.     @SuppressWarnings("unchecked")  
  33.     public T readDictionary(String fileName)  
  34.     {  
  35.         try  
  36.         {  
  37.             ObjectInputStream in = new ObjectInputStream(  
  38.                     new BufferedInputStream(new FileInputStream(fileName)));  
  39.             T dic = (T) in.readObject();  
  40.             in.close();  
  41.             return dic;  
  42.         }  
  43.         catch (Exception e)  
  44.         {  
  45.             System.err.println(e.getMessage());  
  46.             return null;  
  47.         }  
  48.     }  
  49.   
  50.     /** 
  51.      * 将词典实例dic写入到fileName文件中 
  52.      *  
  53.      * @param dic 
  54.      *            词典实例 
  55.      * @param fileName 
  56.      *            存储文件 
  57.      * @return 操作成功与否 
  58.      */  
  59.     public boolean writeDictionary(T dic, String fileName)  
  60.     {  
  61.         try  
  62.         {  
  63.             ObjectOutputStream out = new ObjectOutputStream(  
  64.                     new BufferedOutputStream(new FileOutputStream(fileName)));  
  65.             out.writeObject(dic);  
  66.             out.flush();  
  67.             out.close();  
  68.             return true;  
  69.         }  
  70.         catch (IOException e)  
  71.         {  
  72.             System.err.println(e.getMessage());  
  73.             return false;  
  74.         }  
  75.   
  76.     }  
  77. }  
通过这个操作类可以把实现DictionaryImpl接口的词典实现类写入文件或者从文件中读出。
评论
发表评论

该博客是同时发布到论坛的，无法评论在论坛已被锁定的帖子

billgmh
  • 浏览: 31282 次
  • 性别: Icon_minigender_1
  • 来自: 广东广州
  • 详细资料
搜索本博客
我的相册
6024ce3a-b42c-451f-bf30-eba1a43b95b9-thumb
Inter
共 3 张
存档
最新评论