DawgSharpダウンロード - DawgSharpソースコードのダウンロード

DawgSharp

その他のソースコード

1.0.0

ダウンロード

[NuGet パッケージ] [商用ライセンスを取得]

DawgSharp、C# の賢い文字列辞書

DAWG (Directed Acyclic Word Graph) は、大規模な単語リストと辞書を保存および検索するためのデータ構造です。特定の種類のデータについては、.NET Dictionaryクラスよりも 40 倍効率的です。

例として、私の Web サイトは 200 万語の辞書をホストしていますが、以前はディスク上で 56 MB を占有し、読み込みに 7 秒かかりました (Dictionary と BinarySerializer を使用する場合)。 DAWG に切り替えた後は、ディスク上で 1.4 メガ、ロードに 0.3 秒かかります。

これはどのようにして可能でしょうか?標準の辞書が DAWG ほど賢くないのはなぜですか?実際のところ、DAWG は自然言語文字列ではうまく機能しますが、ライセンスキー (OIN1r4Be2su+UXSeOj0TaQ) などの生成された文字列ではうまく機能しない可能性があります。人間の言語の単語には、「能力」、 「可能性」、 「敏捷性」などの一般的な文字シーケンスがたくさんある傾向があり、アルゴリズムはそれらのシーケンスを見つけて複数の単語に対して 1 回だけ保存することでそれを利用します。 DAWG は、DNA データ (遺伝子配列) を表現するのにも役立つことが証明されています。 DAWG の歴史は 1985 年にまで遡ります。詳しい背景については、Google DAWG または DAFSA (Deterministic Acyclic Finite State Automaton) をご覧ください。

DawgSharp は、数多くある DAWG の実装の 1 つです。何が特別なのでしょうか？

これは純粋な C# で書かれており、MSIL (AnyCPU) にコンパイルされ、.NET 3.5 以降で実行されます。
依存関係はありません。
キー内の文字に制限はありません。競合する実装の中には、26 文字のみを許可するものもあります。この実装は、あらゆる Unicode 文字を処理します。
圧縮アルゴリズムはすべてのノードに 1 回だけアクセスするため、非常に高速になります (私の 200 万語のリストの場合は 5 秒)。
これはすぐに使用できる永続性を提供します。Load Load/Save呼び出してデータをディスクに書き込み、それを再度読み取ります。
単体テストがあります (Visual Studio テストフレームワークを使用)。
数人時間のパフォーマンスプロファイリングセッションを受けているため、可能な限り高速です。高速化の次のステップは、IL 内の関連コードを書き直すことです。
これは GC に適しています。ガベージコレクターは、ディクショナリが数百万の文字列を格納する 3 つの大きな int 配列のみを認識します。

使用法

この例では、2 つのプログラムを含む使用シナリオをシミュレートします。1 つは辞書を生成してディスクに書き込み、もう 1 つはそのファイルをロードして検索に読み取り専用辞書を使用します。

まず、このリポジトリを複製するか、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 、またはカスタムクラスにすることもできます。ただし、重要な制限が 1 つあるので注意してください。 DAWG は、TPayload が取り得る値のセットが比較的小さい場合にのみ適切に機能します。小さいほど良いです。たとえば、各単語の定義を追加すると、各エントリが一意になり、グラフがツリーになります (これはそれほど悪いことではないかもしれません!)。

MatchPrefix()

DAWG のもう 1 つの魅力的な側面は、特定の部分文字列で始まるすべての単語を効率的に取得できることです。

dawg . MatchPrefix ( " awe " )

上記のクエリは、 awe、aweful 、 awesomeなどのキーを含むIEnumerable<KeyValuePair>を返します。 dawg.MatchPrefix("")を呼び出すと、辞書内のすべての項目が返されます。

代わりにサフィックスで検索する必要がある場合、MatchSuffix メソッドはありません。ただし、反転されたキーを追加し、反転されたキーに対して MatchPrefix() を使用することで、目的の効果を実現できます。

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

GetPrefixes()

GetPrefixes() は、キーが指定された文字列の部分文字列であるすべての辞書項目を返します。例えば：

dawg . GetPrefixes ( " awesomenesses " )

awe、awesome、awesomeness 、finally awesomenessなどのキーを返す場合があります。

GetLongestCommonPrefixLength()

もう 1 つの優れた機能は、メソッドint GetLongestCommonPrefixLength(IEnumerable<char> word)です。辞書内でwordが見つかった場合は、その長さを返します。そうでない場合は、辞書内で見つかった最長の単語の長さを返し、それが指定された単語の先頭でもあります。たとえば、 preempt が辞書に含まれていてもpreemptが含まれていない場合、 dawg.GetLongestCommonPrefixLength("preempt") 「pre」の長さである 3 を返します。

スレッドの安全性

DawgBuilderクラスはスレッドセーフではないため、常に 1 つのスレッドのみがアクセスする必要があります。

Dawgクラスは不変であるため、スレッドセーフです。

マルチドーグ

MultiDawg クラスは、非常にメモリ効率の高い方法で、単一の文字列キーに対して複数の値を格納できます。

今後の予定

さらなる使用シナリオ

API は、特定の使用シナリオ (上記を参照) に適合するように設計されており、他のシナリオをサポートするように拡張することができます。たとえば、辞書が圧縮された後に辞書に新しい単語を追加できるようになります。これは必要なかったので実装されていません。例外はありません。 DawgクラスにはInsertメソッドがありません。