Trie Tree（字典樹）服務（已開源）

作者：Tony Qu

前言：在數據挖掘領域，.NET基本上是空白，除了分詞程序外，啥都沒有，大量的招聘顯示數據挖掘目前是Java, C++和Python的天下。作為微軟陣營的一份子，我始終認為我們不該坐以待斃，與其坐著被人看笑話，還不如勇敢的站出來，創造一個嶄新的.NET未來。（話說昨天的吐槽貼不知道大家玩的盡興不盡興，不是有人讓我給點實戰的玩意來證明.NET的牛X嘛，沒問題啊，我如約而至。）

Trie Tree（字典樹）對很多人顯得有些陌生，用一句話來概括，它可以有效加速字符串匹配速度，并且應用極其廣泛，如分詞、搜索、臟字過濾等。曾經寫過一篇介紹TrieTree的文章，不熟悉的同學可以看一下《Trie Tree介紹及其C#實現》。

TrieTree之所以快速，和它樹形存儲結構很有關系，由于所有的查找都是走結點的，所以速度會比普通字符串匹配快很多，傳統匹配的問題在于即使匹配不成功，每次還是要去匹配前面這些字符，而且要與每一個字典項去匹配。

舉個簡單的例子，假設字典里面有兩句整句，如“這里是我們的地盤”，“這里是你們的”，假設我現在要匹配
“這里是他們的”，傳統存儲會把字典保存在List<string>中，但這就意味著，“這里是”三個字每次都要匹配一遍，即使最終結果是沒找到“這里是他們的”。但如果是TrieTree結構，我們只需要匹配一次“這里是”就能知道存不存在，隨著字典中詞數的增加，這種性能提升愈加明顯。

這么好的東西怎么能沒有一個通用的框架，于是我便考慮設計了TrieTree Service。TrieTree Service是一個基于Windows Service的服務，采用socket與客戶端進行通訊，通訊部分使用了江大魚的SuperSocket。（這玩意確實好用，上手也很快，我大概用了2天就把通訊部分全搞定了。）之所以采用Windows Service，主要考慮了分布式部署、以及內存空間的需求。由于TrieTree Service采用內存作為緩存空間，所以對內存是有很大需求的，如果與其他應用共享空間，在32位系統上估計很快就3GB了，根本沒法用，但做成Windows Service以后，3GB至少是獨享的。而且理論上我可以部署n個service，加載不同的字典，比如Service 1我加載盤古分詞詞典、Service 2我加載MongoDB的字典，以此類推，客戶端會根據需要去訪問不同的Service，從而獲得足夠的數據支持。

Trie Tree服務還有一個很明顯的優勢那就是字典資源的整合，以往如果我們要調用第三方字典庫或者擴展字典庫，可能必須重新寫一個類來實現讀，然后調用不同的接口來加載不同的字典庫，現在有了Trie Tree服務，你就可以做到把幾個庫合并在一起，比如盤古分詞的庫可以和細胞詞庫混用，如果詞重復，Trie Tree服務不會重復添加，而是在現有結點上把頻率相加。例如，我本地的TrieTree服務就把盤古分詞、IKAnalyzer詞典、還有我自己的多個MongoDB的字典庫一起加載起來運行，那效果絕對是只可意會不可言傳啊，哈哈。我看了下，內存占用也不高，只有400M左右。

Trie Tree服務支持POS (Part of Speech)枚舉，說通俗點就是某個詞的詞性，如名詞、動詞、代詞等。目前的POSType采用了盤古分詞的類型，以后會考慮擴充，目前足夠了。（話說清華和北大都有一套自己的POS分類，比盤古要詳細，以后會考慮支持這兩個標準，因為POS的細粒度決定了最終的分詞結果。）

[Flags]
public enum POSType : int
{
    /// <summary>
    /// 形容詞 形語素
    /// </summary>
    D_A = 0x40000000,    
    /// <summary>
    /// 區別詞 區別語素
    /// </summary>
    D_B = 0x20000000,    
    /// <summary>
    /// 連詞 連語素
    /// </summary>
    D_C = 0x10000000,    
    /// <summary>
    /// 副詞 副語素
    /// </summary>
    D_D = 0x08000000,    
    /// <summary>
    /// 嘆詞 嘆語素
    /// </summary>
    D_E = 0x04000000,    
    /// <summary>
    /// 方位詞 方位語素
    /// </summary>
    D_F = 0x02000000,    
    /// <summary>
    /// 成語
    /// </summary>
    D_I = 0x01000000,    
    /// <summary>
    /// 習語
    /// </summary>
    D_L = 0x00800000,    
    /// <summary>
    /// 數詞 數語素
    /// </summary>
    A_M = 0x00400000,    
    /// <summary>
    /// 數量詞
    /// </summary>
    D_MQ = 0x00200000,    
    /// <summary>
    /// 名詞 名語素
    /// </summary>
    D_N = 0x00100000,    
    /// <summary>
    /// 擬聲詞
    /// </summary>
    D_O = 0x00080000,    
    /// <summary>
    /// 介詞
    /// </summary>
    D_P = 0x00040000,    
    /// <summary>
    /// 量詞 量語素
    /// </summary>
    A_Q = 0x00020000,    
    /// <summary>
    /// 代詞 代語素
    /// </summary>
    D_R = 0x00010000,    
    /// <summary>
    /// 處所詞
    /// </summary>
    D_S = 0x00008000,    
    /// <summary>
    /// 時間詞
    /// </summary>
    D_T = 0x00004000,    
    /// <summary>
    /// 助詞 助語素
    /// </summary>
    D_U = 0x00002000,    
    /// <summary>
    /// 動詞 動語素
    /// </summary>
    D_V = 0x00001000,    
    /// <summary>
    /// 標點符號
    /// </summary>
    D_W = 0x00000800,    
    /// <summary>
    /// 非語素字
    /// </summary>
    D_X = 0x00000400,
    /// <summary>
    /// 語氣詞 語氣語素
    /// </summary>
    D_Y = 0x00000200,    
    /// <summary>
    /// 狀態詞
    /// </summary>
    D_Z = 0x00000100,    
    /// <summary>
    /// 人名
    /// </summary>
    A_NR = 0x00000080,    
    /// <summary>
    /// 地名
    /// </summary>
    A_NS = 0x00000040,    
    /// <summary>
    /// 機構團體
    /// </summary>
    A_NT = 0x00000020,    
    /// <summary>
    /// 外文字符
    /// </summary>
    A_NX = 0x00000010,    
    /// <summary>
    /// 其他專名
    /// </summary>
    [Description("其他專名")]
    A_NZ = 0x00000008,    
    /// <summary>
    /// 前接成分
    /// </summary>
    D_H = 0x00000004,    
    /// <summary>
    /// 后接成分
    /// </summary>
    D_K = 0x00000002,    
    /// <summary>
    /// 未知詞性
    /// </summary>
    UNKNOWN = 0x00000000,   
}

同時TrieTree還支持POS并集查詢，如D_N|D_V，表示查詞性是名詞或者動詞的詞。、

目前TrieTree支持三種匹配命令，它們是MMFetch（Maximum Match，正向最大匹配）、 RMMFetch（Reverse Maximum Match, 反向最大匹配）、 ExactMatch（全字匹配）。

例如你要使用MMFetch命令搜索“我們”，直接通過socket向TrieTree Service發送“MMFetch 我們”即可。如果你想搜索詞性，可以發送“MMFetch 我們<SOH>512”，這表示搜索詞性為語氣詞D_Y（0x200=512）的“我們”，其中<SOH>是一個自定義字符0x01，用作分隔符。其他兩個命令的用法類似。

由于定義了IDataProvider接口，你可以根據需要定制自己的DataProvider。目前TrieTree Service自帶了PanguDictProvider, TxtDictProvider, IKAnaylzerDictProvider。以下是IDataProvider的定義

public interface IDataNode
{
    /// <summary>
    /// word text
    /// </summary>
    string Word 
    { 
        get; set; 
    }
    /// <summary>
    /// Part of Speech Tag Value
    /// </summary>
    POSType POS 
    { 
        get; set; 
    }
    /// <summary>
    /// frequency of the word
    /// </summary>
    double Frequency
    { 
        get; set; 
    }
}

public interface IDataProvider
{
    List<IDataNode> Load();
}

這里的IDataNode代表導入的一條條詞條，當然你必須先實現這個接口。其中的POS是之前提到的詞性，Frequency是頻率，Word是詞本身。對于沒有詞性和沒有頻率的導入項，直接忽略這兩項就行了。

在BluePrint.Dictionary命名空間下面定義了一個客戶端封裝類DictionaryServiceClient，提供了對命令的基本封裝，這樣你就不用直接去和SendCommand打交道了。

public TrieTreeResult ExactMatch(string word){...}
public TrieTreeResult MaximumMatch(string word){...}
public TrieTreeResult ReverseMaximumMatch(string word){...}

下載地址：https://github.com/tonyqus/TrieTreeService