DawgSharp
1.0.0
[NuGet包] [获取商业许可证]
DAWG（有向非循环词图）是一种用于存储和搜索大型单词列表和词典的数据结构。对于某些类型的数据，它的效率比 .NET Dictionary类高 40 倍。
举个例子，我的网站托管着一个 200 万单词的字典，该字典过去占用磁盘上 56 兆，加载时间为 7 秒（使用 Dictionary 和 BinarySerializer 时）。切换到 DAWG 后，现在磁盘上需要 1.4 兆，加载时间为 0.3 秒。
这怎么可能？为什么标准词典不如 DAWG 聪明？问题是，DAWG 可以很好地处理自然语言字符串，但可能不适用于生成的字符串，例如许可证密钥 (OIN1r4Be2su+UXSeOj0TaQ)。人类语言单词往往有许多常见的字母序列，例如能力、可能性、敏捷性等，算法通过查找这些序列并为多个单词仅存储一次来利用这一点。事实证明，DAWG 在表示 DNA 数据（基因序列）方面也很有用。 DAWG 的历史可以追溯到 1985 年。有关更多背景信息，请谷歌 DAWG 或 DAFSA（确定性非循环有限状态自动机）。
DawgSharp 是 DAWG 的一个实现，是众多实现之一。它有何特别之处？
Load/Save将数据写入磁盘并将其读回。在此示例中，我们将模拟涉及两个程序的使用场景，一个程序生成字典并将其写入磁盘，另一个程序加载该文件并使用只读字典进行查找。
首先通过克隆此存储库或安装 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. " ) ;
} 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”的长度。
DawgBuilder类不是线程安全的，在任何特定时间只能由一个线程访问。
Dawg类是不可变的，因此是线程安全的。
MultiDawg 类可以以非常节省内存的方式针对单个字符串键存储多个值。
API 旨在适应特定的使用场景（见上文），并且可以扩展以支持其他场景，例如能够在压缩后向字典添加新单词。我只是不需要这个，所以它没有实现。你不会有任何例外。 Dawg类中没有Insert方法。
在 DawgBuilder 和 Dawg 上实现 IDictionary 接口 (#5)。
DawgSharp 根据 GPLv3 获得许可，这意味着它可以在开源项目中免费使用。阅读完整的许可证
如果您想在专有项目中使用 DawgSharp，请在 http://morpher.co.uk 购买商业许可证。
