Trie Tree（字典樹）服務(wù)（已開源）

作者：Tony Qu

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

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

TrieTree之所以快速，和它樹形存儲結(jié)構(gòu)很有關(guān)系，由于所有的查找都是走結(jié)點(diǎn)的，所以速度會比普通字符串匹配快很多，傳統(tǒng)匹配的問題在于即使匹配不成功，每次還是要去匹配前面這些字符，而且要與每一個(gè)字典項(xiàng)去匹配。

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

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

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

Trie Tree服務(wù)支持POS (Part of Speech)枚舉，說通俗點(diǎn)就是某個(gè)詞的詞性，如名詞、動詞、代詞等。目前的POSType采用了盤古分詞的類型，以后會考慮擴(kuò)充，目前足夠了。（話說清華和北大都有一套自己的POS分類，比盤古要詳細(xì)，以后會考慮支持這兩個(gè)標(biāo)準(zhǔn)，因?yàn)镻OS的細(xì)粒度決定了最終的分詞結(jié)果。）

[Flags]
public enum POSType : int
{
    /// <summary>
    /// 形容詞 形語素
    /// </summary>
    D_A = 0x40000000,    
    /// <summary>
    /// 區(qū)別詞 區(qū)別語素
    /// </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>
    /// 習(xí)語
    /// </summary>
    D_L = 0x00800000,    
    /// <summary>
    /// 數(shù)詞 數(shù)語素
    /// </summary>
    A_M = 0x00400000,    
    /// <summary>
    /// 數(shù)量詞
    /// </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>
    /// 時(shí)間詞
    /// </summary>
    D_T = 0x00004000,    
    /// <summary>
    /// 助詞 助語素
    /// </summary>
    D_U = 0x00002000,    
    /// <summary>
    /// 動詞 動語素
    /// </summary>
    D_V = 0x00001000,    
    /// <summary>
    /// 標(biāo)點(diǎn)符號
    /// </summary>
    D_W = 0x00000800,    
    /// <summary>
    /// 非語素字
    /// </summary>
    D_X = 0x00000400,
    /// <summary>
    /// 語氣詞 語氣語素
    /// </summary>
    D_Y = 0x00000200,    
    /// <summary>
    /// 狀態(tài)詞
    /// </summary>
    D_Z = 0x00000100,    
    /// <summary>
    /// 人名
    /// </summary>
    A_NR = 0x00000080,    
    /// <summary>
    /// 地名
    /// </summary>
    A_NS = 0x00000040,    
    /// <summary>
    /// 機(jī)構(gòu)團(tuán)體
    /// </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,   
}

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

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

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

由于定義了IDataProvider接口，你可以根據(jù)需要定制自己的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代表導(dǎo)入的一條條詞條，當(dāng)然你必須先實(shí)現(xiàn)這個(gè)接口。其中的POS是之前提到的詞性，F(xiàn)requency是頻率，Word是詞本身。對于沒有詞性和沒有頻率的導(dǎo)入項(xiàng)，直接忽略這兩項(xiàng)就行了。

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

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

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