DawgSharp下載 - DawgSharp原始碼下載

DawgSharp

其他源碼

1.0.0

下載

[NuGet套件] [取得商業許可證]

DawgSharp，C# 中的巧妙字串字典

DAWG（有向非循環詞圖）是一種用於儲存和搜尋大型單字清單和字典的資料結構。對於某些類型的數據，它的效率比 .NET Dictionary類別高 40 倍。

舉個例子，我的網站託管著一個 200 萬個單字的字典，該字典過去佔用磁碟上 56 兆，載入時間為 7 秒（使用 Dictionary 和 BinarySerializer 時）。切換到 DAWG 後，現在磁碟上需要 1.4 兆，載入時間為 0.3 秒。

這怎麼可能？為什麼標準字典不如 DAWG 聰明？問題是，DAWG 可以很好地處理自然語言字串，但可能不適用於產生的字串，例如許可證金鑰 (OIN1r4Be2su+UXSeOj0TaQ)。人類語言單字往往有許多常見的字母序列，例如能力、可能性、敏捷性等，演算法透過尋找這些序列並為多個單字僅儲存一次來利用這一點。事實證明，DAWG 在表示 DNA 數據（基因序列）方面也很有用。 DAWG 的歷史可以追溯到 1985 年。

DawgSharp 是 DAWG 的一個實現，也是眾多實現之一。它有何特別之處？

它是用純 C# 編寫的，編譯為 MSIL (AnyCPU) 並在 .NET 3.5 及更高版本上運行。
它沒有依賴性。
它對鍵中的字元沒有限制。一些競爭實現僅允許 26 個英文字母。此實作處理任何 Unicode 字元。
壓縮演算法僅訪問每個節點一次，這使得它非常快（對於我的 200 萬個單字列表，只需 5 秒）。
它提供開箱即用的持久性：呼叫Load/Save將資料寫入磁碟並將其讀回。
它有單元測試（使用 Visual Studio 測試框架）。
它已經接受了幾個工時的效能分析會話，因此它的速度幾乎是盡可能快的。加快速度的下一步是用 IL 重寫相關程式碼。
它是 GC 友好的：垃圾收集器只看到 3 個大的整數數組，其中字典將存儲數百萬個字串。

用法

在此範例中，我們將模擬涉及兩個程式的使用場景，一個程式產生字典並將其寫入磁碟，另一個程式會載入該檔案並使用唯讀字典進行查找。

首先透過複製此儲存庫或安裝 NuGet 套件來取得程式碼。

建立並填入DawgBuilder物件：

 var words = new [ ] { " Aaron " , " abacus " , " abashed " } ;

var dawgBuilder = new DawgBuilder < bool > ( ) ; // <bool> is the value type.
                                             // Key type is always string.
foreach ( string key in words )
{
    dawgBuilder . Insert ( key , true ) ;
}

（或者，執行var dawgBuilder = words.ToDawgBuilder(key => key, _ => true); ）

呼叫BuildDawg來取得壓縮版本並將其儲存到磁碟：

 Dawg < bool > dawg = dawgBuilder . BuildDawg ( ) ; 
// Computer is working.  Please wait ...

using ( var file = File . Create ( " DAWG.bin " ) ) 
    dawg . SaveTo ( file ) ;

現在讀回檔案並檢查字典中是否存在特定單字：

 var dawg = Dawg < bool > . Load ( File . Open ( " DAWG.bin " ) ) ;

if ( dawg [ " chihuahua " ] )
{
    Console . WriteLine ( " Word is found. " ) ;
}

值類型，<TPayload>

Dawg和DawgBuilder類別採用名為<TPayload>的範本參數。它可以是您想要的任何類型。只是為了能夠測試一個單字是否在字典中，一個 bool 就足夠了。您也可以將其設為int或string或自訂類別。但要注意一個重要的限制。只有當 TPayload 可以採用的值集相對較小時，DAWG 才能正常運作。越小越好。例如，如果您為每個單字添加定義，它將使每個條目都是唯一的，並且您的圖表將成為一棵樹（這可能還不錯！）。

匹配前綴()

DAWG 的另一個吸引人的方面是它能夠有效地檢索以特定子字串開頭的所有單字：

dawg . MatchPrefix ( " awe " )

上面的查詢將傳回一個IEnumerable<KeyValuePair> ，其中可能包含awe、aweful和Awesome等鍵。呼叫dawg.MatchPrefix("")將傳回字典中的所有項目。

如果您需要按後綴查找，則沒有 MatchSuffix 方法。但是可以透過新增反轉鍵然後在反轉鍵上使用 MatchPrefix() 來實現所需的效果：

dawgBuilder . Insert ( " ability " . Reverse ( ) , true ) ;
.. .
dawg . MatchPrefix ( " ility " . Reverse ( ) )

取得前綴()

GetPrefixes() 傳回其鍵是給定字串的子字串的所有字典項目。例如：

dawg . GetPrefixes ( " awesomenesses " )

可能會傳回諸如awe、awesome、awesomeness和最後Awesomeness之類的鍵。

取得最長公共前綴長度()

另一個巧妙的功能是int GetLongestCommonPrefixLength(IEnumerable<char> word)方法。如果在字典中找到word ，則返回其長度；如果不是，它將返回字典中找到的最長單字的長度，這也是給定單字的開頭。例如，如果prepare在字典中但preempt不在字典中，則dawg.GetLongestCommonPrefixLength("preempt")將傳回3，即“pre”的長度。