基于.NET的分词软件设计与实现V4.0--使用SortedList提高分词效率

　　隔了一段时间，忙其他的去了，下面继续偶之前的分词软件。

　　在之前的3个版本里，我们已经实现了分词的基本功能，并对其合理性等作了大量的测试评估工作，但是性能的提升还很不如意，所以这里我提出了使用SortedList提高分词效率的方案。

　　C#中提供了众多集合类的数据结构，如大家常用的List<T>，Dictionary<T>等，这里我将着重介绍一下SortedList，并实现其在偶的分词软件中的应用。

一、SortedList简介

引自MSDN：

SortedList 元素可通过其键来访问 （如任意 IDictionary 实现中的元素），或通过其索引来访问（如任意 IList 实现中的元素）。

SortedList 在内部维护两个数组以存储列表中的元素；即，一个数组用于键，另一个数组用于相关联的值。每个元素都是一个可作为 DictionaryEntry 对象进行访问的键/值对，

键不能为空引用（在 Visual Basic 中为 Nothing），但值可以。

SortedList 的容量是 SortedList 可以保存的元素数。SortedList 的默认初始容量为 0。随着元素添加到 SortedList 中，在需要时可以通过重新分配自动增加容量。可通过调用

TrimToSize 或通过显式设置 Capacity 属性减少容量。

　　SortedList 的元素将按照特定的 IComparer 实现（在创建 SortedList 时指定）或按照键本身提供的 IComparable 实现并依据键来进行排序。不论在哪种情况下，

SortedList 都不允许重复键。 索引顺序基于排序顺序。当添加元素时，元素将按正确的排序顺序插入 SortedList，同时索引会相应地进行调整。当移除元素时，索引也会相应地进行调整

。因此，当在SortedList 中添加或移除元素时，特定键/值对的索引可能会更改。

由于要进行排序，所以在 SortedList 上操作比在 Hashtable 上操作要慢。但是，SortedList 允许通过相关联键或通过索引对值进行访问，可提供更大的灵活性。

可使用一个整数索引访问此集合中的元素。此集合中的索引从零开始。 C# 语言中的 foreach 语句（在 Visual Basic 中为 for each）需要集合中每个元素的类型。

由于 SortedList 的每个元素都是一个键/值对，因此元素类型既不是键的类型，也不是值的类型。而是 DictionaryEntry 类型。

二、SortedList介绍——个人整理

　　我们知道对于List<T>等集合，在查找某个元素是否存在时使用的是顺序遍历查找法，这样查询的偶然性比较大，效率低，而SortedList则采用了二分查找法，显著提高了查找效率（二分查找的介绍就略了吧）。

　　SortedList保存数据时和哈希表一样用Key-Value的方式进行存储，但不同的是，它把Key和Value分别保存在两个object[]数组中，每次插入删除操作都会保持这两个object[]大小的同步性。

　　SortedList在初始化时如果不指定大小，则会给一个默认的十六进制值0x10（16），在添加操作中，如果容量不足则会自动扩充为2倍容量，这些与ArrayList和Hashtable相同。

　　SortedList的独特之处在于它保证数据的有序性，这点是如何保证呢？

　　原来，在Add（key，value）方法中，SortedList会首先用二分查找插入的key值，如果有重复项，则报错，如果没有重复项，则根据key值大小，比较得出在集合中的位置，然后插入到该位置中，反编译查看源代码如下：

　　由于要进行排序，所以在 SortedList 上操作比在 Hashtable 上操作要慢。

　　但是，SortedList 允许通过相关联键或通过索引对值进行访问，可提供更大的灵活性，因为SortedList 兼容了 Hashtable 和 Array 的特征，当使用 Item 索引器属性按照元素的键访问元素时，其行为类似于 Hashtable，当使用 GetByIndex 或 SetByIndex 按照元素的索引访问元素时，其行为又类似于 Array。所以对于Hashtable来说，用object型的Key值来匹配，而对于ArrayList来说，则用int型的下标序号来获取，而SortedList由于兼有二者的特征，所以既可以用object型的key获取，也可以用int型的序号来获取，从而提高了数据访问的灵活性。

　　示例如下：　　

public static void Main()
{
   ArrayList arrList = new ArrayList();
   arrList.Add("rocky");
   Console.WriteLine(arrList[0]);
   
   Hashtable ht = new Hashtable();
   ht.Add("name", "rocky");
   Console.WriteLine(hash["name"]);

   SortedList sortedList = new SortedList();
   sortedList.Add("name", "rocky");
   sortedList.Add("hobby", "coding");
   Console.WriteLine(sortedList["name"]);
   Console.WriteLine(sortedList.GetByIndex(1));
}

　　此外，SortedList还有泛型版本：SortedList<TKey,TValue>，为了减少装箱拆箱带来的困扰，肯定优先使用泛型版本。

总结：

　　优点： 1、SortedList在添加元素时保证了集合中数据的有序性，并通过二分查找，显著提高了元素的查找效率。

　　　　　 2、SortedList兼容了ArrayList和Hashtable的数据访问方式，提高了数据访问的灵活性。

　　缺点： SortedList为了保证数据的有序性，所以构建时间较为耗时。

三、SortedList<TKey,TValue>在个人分词软件中的应用

　　首先，相对于第三个版本来说，这里将List<string> _dict = new List<string>();的词典构造方式改为：

SortedList<string, string> _dict = new SortedList<string, string>();

　　随后调用_dict的Add方法进行词典构造即可。

四、SortedList<TKey,TValue>在个人分词软件中的应用效果

　　其实，说了上面一大通，就是为了看选择SortedList这样的数据结构后能不能使分词性能得到显著的提升，还记得之前对1000字左右的文本进行分词，时间大概在8、9秒的样子，那下面就看一下SortedList的表现。

　　下面是之前的测试文本：

　　下面进行分词：

　　简直毫无压力。随后来点狠的，直接上之前2.0版中提到的完整的测试文本，看下分词效果：

　　依然毫无压力，可以看到每1000字的分词效率从之前的8、9秒一下提到了100毫秒左右，可以说是质的飞跃，也可以很好地看到SortedList在数据查找方面的优势。

　　下篇将使用上面提到的另一种数据结构——Hashtable进行测试。

上篇使用了SortedList，对分词的性能有了显著的改进，但是有一点偶没有提，那就是构造词典的时间，由于SortedList需要保证元素的有序性，所以对于我使用的20+万的词典来说，构造时间也达到了10秒左右，因此与之前的三个版本相比，虽然分词的性能大幅提升，但总的时间并没有什么改进，所以使用SortedList的方案自然也不可行，那让我们看看之前提到的Hashtable表现如何。

一、Hashtable的优势——高效的查找

　　时间复杂度：

　　这无疑是Hashtable最大的优势所在，对于之前提到的数据结构：ArrayList采用顺序查找，时间复杂度为O(n)，而SortedList采用二分查找，时间复杂度为O(logN)，而Hashtable则是O(1)。

　 原理：

　　当Hashtable添加数据时，(例如:hash.Add(key)) 首先调用当前键值key的GetHashCode()方法，得到哈希值（该值为Int32），取该哈希值的绝对值跟内部数组（上面代码的buckets）的总容量进行余运算(就是'%'操作)，得到一个小于总容量的值，把该值当做数组序号，存在对应的位置。

　　Hashtable之所以查找高效，是因为其存储的元素都是通过键值对的形式进行存储的，需要某个元素的值时，可通过映射Key值，找到数组中对应的索引位置，然后取出元素，整个过程无需循环。

　 代价：

　　哈希表高效的查找是有代价的，那就是内存，不过，介于现在硬件的发展速度，这种用空间换时间的做法显然没有任何压力。

二、Hashtable的不足

　　1、哈希表不能有重复键值

　　这意味着我们在进行哈希表构造时，需要在添加元素时进行判断，若其Key值不存在，则不用重复添加，否则报错。

　　2、哈希表会占用更多内存

　　之前提到哈希表高效的查找是以内存为代价的，而原理又是怎样的呢？

　　首先，我们实例化ArrayList或List<T>的时候,如果不指定容量,则其内部是赋值为一个静态的空数组。当有添加操作时，会实例化为一个长度为4的数组，如果容量满了以后，再添加，就会自动扩充为两倍的容量。所以使用ArrayList和List <T>的时候，建议在实例化方法里指定容量。

　　哈希表也有一个类似的情况，new Hashtable()如果不指定长度，则会将内置bucket数组的长度默认指定为11。如果给定一个值如new Hashtable(20)，也并不会将bucket数组长度设置为20，而是循环内部一个素数数组,设置为刚好大于20的素数（此处是23，由此可知，哈希表内部存取数组长度总是一个素数）。

　　此外，哈希表在未存满的情况下就要扩充： Hashtable有一个加载因子为0.72f。实际能存储的数据量等于内部长度* 0.72f。也就是说在Hashtable中，假如初始化了100个位置，只有72个可用，其他28个不能用，但仍然要占着地方。由于哈希算法本身的特点，哈希表内部存取数组长度总是一个素数，所以当需要扩充时，新的数组长度是刚好大于原数组二倍长度的素数，也就是说略大于二倍。

三、Hashtable——Q&A

　　其实，在刚接触Hashtable的时候，就看到一句话，也是上文提到的——哈希表内部存取数组长度总是一个素数，比较不解，如果你和我当时一样有着相同的疑问，那么下面的话希望能够解答。

　　哈希表大小为素数在理论上是有依据的，针对不同的哈希算法有不同的证明。例如，对于平方探测法，有如下定理：如果使用平方探测，且表大小是素数，那么当表至少有一半是空的时候，总能够插入一个新的元素。

　　hash函数用质数来做模运算(%)，分析发现,如果不是用质数来做模运算的话，很多生活中的数据分布会集中在某些点上，所以需要采用质数做模的除数。

因为用质数做了模的除数，自然存储空间的大小也用质数了，因为模完之后,数据是在[0-所选质数]之间。

四、HashSet<T>对于Hashtable的改进

　　之前提到的一个Hashtable不允许添加重复值，所以我们构造词典的时候代码会是这样：

　　可以看到Hashtable是使用键-值方式进行存储的，但有些时候，我们只需要其中一个值，比如上图所示的情况，我只需要词典中的词，对于value我们不需要进行设置，所以这样就造成了内存浪费。

　　不过其实有一种数据结构可以改变这样的情况，那就是HashSet<T>，HashSet<T>只保存一个值，所以更加适合处理这种情况。

　　HashSet<T>每条数据只保存一项，并不采用Key-Value的方式，换句话说，HashSet<T>中的Key就是Value，假如已经知道了Key，也没必要再查询去获取Value，需要做的只是检查值是否已存在。

　　HashSet<T>的Add方法返回bool值，在添加数据时，如果发现集合中已经存在，则忽略这次操作，并返回false值。而Hashtable和Dictionary<TKey,TValue>碰到重复添加的情况会直接抛出错误。

　　但HashSet<T>不能使用下标来访问元素，如：hs[1]。

　　所以上面的代码就可以写作：

　　看着舒心了些吧。。。

五、HashSet<T>在个人分词软件中的应用效果

　　好了，介绍的差不多，来看下最终的效果吧，以之前的那个完整的测试文本进行测试：

　　启动毫无压力，运行结果也灰常满意。

　　到此为此，介绍了个人在分词软件上对于算法、数据结构等方面的研究、测试与改进，最后的这个HashSet<T>的词典版本，也是个人的最终版本。

　　不过之前的所有测试使用的词典都是以文本形式存储的，下篇将介绍使用数据库进行词典存储后，分词软件的性能表现及相关改进。

　　本文部分内容参考了园子里面的文章，在此附上友情链接：http://www.cnblogs.com/hkncd/archive/2011/05/06/2035684.html

忙了一阵子，今天用空下来的一点时间来总结一下之前未完成的分词系列吧。。

　　上篇提到了使用HashSet<T>作为词典存储数据结构的方法，这也是在不使用数据库的情况下，自己在能力范围之内找到的最佳的解决方案。

　　但是，如果使用数据库呢，好吧，下面就让我们来看在使用数据库的情况下，本分词软件的表现。

　一、建立数据库

　　在之前的版本中，分词的词典都以文本的形式直接保存在txt文件中，这里自然要将其全部转存到数据库的表中，介于词典采用的是每行存取一个词的方法，我采用的方法是循环读取文本文档的每一行，随后使用insert语句将其录入数据库的表中。

　　随后我们不作任何优化措施，直接开始简单的测试，首先开启SQL中显示统计信息和分析、编译、执行各语句耗时的功能：

SET STATISTICS IO ON
SET STATISTICS TIME ON

　　来看一下查询“他们”这个简单的词，select * from Vocabulary where item = '他们'

　　SQL中的执行结果：

　　注意下面几个数据：逻辑读取871次，CPU时间=62毫秒，占用时间=59毫秒。

　　随后，我们将程序中判断某个词是否存在的程序改为：

  /// <summary>
  /// Updated：判断是否在词典中出现
  /// </summary>
  /// <param name="str"></param>
  /// <returns></returns>
  bool isExist(string str)
  {
         DBHelper db = new DBHelper();
         return Convert.ToInt32(db.ExecuteScalar("select count(*) from Vocabulary where item = '" + str + "'")) > 0;
   }

　　起初我计划以1000字的文本测试，但最后发现这个想法很不现实，为什么？让我们看下100字文本的分词结果就知道了：

　　没错，100字的文本分词时间居然达到了20+秒，无法忍受的一个结果。

　二、优化第一步——建立索引

　　索引的文章园子里面有很多，从原理到实例都有些经典的，这里自不必多说，这里主要看一下索引在本分词软件中的应用。

　　首先，我们频繁使用item字段，也就是保存词的字段进行查询，且其是表的主键，很适合建立聚集索引：

USE [Splitter]
GO
/****** 对象:  Index [PK_Vocabulary]    脚本日期: 05/06/2011 23:56:26 ******/
CREATE CLUSTERED INDEX [PK_Vocabulary] ON [dbo].[Vocabulary] 
(
    [item] ASC
)
WITH 
(
    SORT_IN_TEMPDB = OFF, 
    DROP_EXISTING = OFF, 
    IGNORE_DUP_KEY = OFF, 
    ONLINE = OFF
) 
ON [PRIMARY]

　　好了，建立完成后来看一下最终的结果：

　　是不是看着顺眼多了（附加一句：py和len两个字段是我为了方便某些特殊查询，比如看有多少个拼音简写是ab的词等，在程序中木有用处）。

　　下面以相同的语句查询“他们”这个词，看下结果：

　　
　　注意下面几个数据：逻辑读取2次，CPU时间=0毫秒，占用时间=11毫秒。耗时明显大幅度降低了。

　三、优化第二步——使用填充因子

　填充因子百分比指首次创建索引时索引页的叶级别充满程序，若没有显示设置，则默认为0。

　　当最初生成索引时，SQL Server 将索引 B 树结构放置在连续的物理页上，以便通过连续 I/O 扫描索引页获取最佳 I/O 性能。当由于发生页拆分，需要将新的页插入索引的逻辑 B 树结构时，SQL Server 必须分配新的 8 KB 索引页。这种插入发生在硬盘上的其它位置，从而打断了索引页的物理连续特性。使 I/O 操作从连续变为不连续，从而使得性能减低一半。可以通过重建索引页以恢复索引页的物理连续顺序来解决过多的页拆分。聚集索引的叶级也会遇到相同的问题，从而影响表的数据页。

　　100%填充因子可以提升读取的性能，但会减缓写活动的功能，引发频繁的页拆分，因为数据库引擎为了在数据页中得到空间必须持续地交换行的位置。

　　填充因子太低会给插入带来便利，但读取较慢，因为如果填充因子太小,就需要使用更多的页来保存数据，而更多页就意味着每个查询要读取的物理数据页读操作的数量也变得更多，此时，读和写操作的机能都会降低。

　　最佳实践：在没有修改活动的表中使用100%的填充因子，中低活动的使用70-90%，高活动的使用50%甚至更低的填充因子。

USE [Splitter]
GO
/****** 对象:  Index [PK_Vocabulary]    脚本日期: 05/06/2011 23:56:26 ******/
CREATE CLUSTERED INDEX [PK_Vocabulary] ON [dbo].[Vocabulary] 
(
    [item] ASC
)
WITH 
(
    PAD_INDEX = ON,
    FILLFACTOR = 100,  --填充因子100%
    SORT_IN_TEMPDB = OFF, 
    DROP_EXISTING = OFF, 
    IGNORE_DUP_KEY = OFF, 
    ONLINE = OFF
) 
ON [PRIMARY]

　　上面的代码演示了创建聚集索引并指定100%的填充因子。

　　继续看一下数据库中查询“他们”的效果：

　　注意下面几个数据：逻辑读取3次，CPU时间=0毫秒，占用时间=1毫秒。

　　可以看到较建立索引并使用默认填充因子的表现又更进了一步。

　　下面可以看一下1000字文本的测试结果了：

　　可以看到，1000字的文本仅仅花了1.7秒左右，较之前没有使用索引的惨不忍睹有了不少好转。

　四、优化第三步——使用存储过程

　首先，列举一下公认的存储过程的几个优点：

　　•高效：

–存储过程只在建立时编译，以后每次执行就不需要重新编译，而一般SQL语句每执行一次都需要先分析，然后再执行，所以使用存储过程可提高SQL语句的执行效率。

–存储过程代码直接存储于数据库中，不会产生大量T-sql语句的代码流量，显著降低了网络流量。

　　•安全：存储过程执行时，使用的是参数化的SQL语句，防止了常见的如SQL注入攻击等。

　　•可复用，可维护性高：更新存储过程通常比更改、测试以及重新部署程序集需要较少的时间和精力。

　由于分词过程中需要大量重复的执行SQL语句，那到底使用存储过程对于执行效率有没有提高呢，那我们一试：

    USE [Splitter]
GO
/****** 对象:  StoredProcedure [dbo].[IsExist]    脚本日期: 05/07/2011 01:34:56 ******/
SET ANSI_NULLS ON
GO
SET QUOTED_IDENTIFIER ON
GO

CREATE PROCEDURE [dbo].[IsExist]
(
  @item varchar(50),
  @result int output
)
AS
BEGIN
    SET NOCOUNT ON;

    SELECT @result = count(*) from Vocabulary WHERE item = @item
END

程序中详细调用步骤：

     bool isExist(string str)
{
      SqlConnection con = new SqlConnection(ConfigurationManager.ConnectionStrings["ConnectionString"].ToString());
      con.Open();
      SqlCommand cmd = new SqlCommand("IsExist", con);
      cmd.CommandType = CommandType.StoredProcedure;
      cmd.Parameters.Add(new SqlParameter("@item",   SqlDbType.VarChar, 50));
      cmd.Parameters["@item"].Value = str;
      cmd.Parameters.Add(new SqlParameter("@result",   SqlDbType.Int));
      cmd.Parameters["@result"].Direction = ParameterDirection.Output;
      int result = cmd.ExecuteNonQuery();
      con.Close();
      return Convert.ToBoolean(result); 
}