Unduh DawgSharp - Unduh kode sumber DawgSharp

DawgSharp

Kode sumber lainnya

1.0.0

Unduh

[Paket NuGet] [Dapatkan Lisensi Komersial]

DawgSharp, kamus string pintar di C#

DAWG (Directed Acyclic Word Graph) adalah struktur data untuk menyimpan dan mencari daftar kata dan kamus berukuran besar. Ini bisa 40x lebih efisien daripada kelas Dictionary .NET untuk tipe data tertentu.

Sebagai contoh, situs web saya menampung kamus 2 juta kata yang biasanya memakan 56 MB pada disk dan memerlukan waktu 7 detik untuk memuat (saat menggunakan Kamus dan BinarySerializer). Setelah beralih ke DAWG, sekarang dibutuhkan 1,4 MB pada disk dan 0,3 detik untuk memuat.

Bagaimana ini mungkin? Mengapa Kamus standar tidak secerdas DAWG? Masalahnya adalah, DAWG bekerja dengan baik dengan string bahasa alami dan mungkin tidak berfungsi dengan baik untuk string yang dihasilkan seperti kunci lisensi (OIN1r4Be2su+UXSeOj0TaQ). Kata-kata dalam bahasa manusia cenderung memiliki banyak rangkaian huruf yang sama, misalnya -ility dalam ability , kemungkinan , agility , dll. Dan algoritma mengambil keuntungan dari hal tersebut dengan menemukan rangkaian tersebut dan menyimpannya hanya sekali untuk beberapa kata. DAWG juga terbukti berguna dalam merepresentasikan data DNA (urutan gen). Sejarah DAWG dimulai pada tahun 1985. Untuk latar belakang lebih lanjut, google DAWG atau DAFSA (Deterministic Acyclic Finite State Automaton).

DawgSharp adalah implementasi DAWG, salah satu dari banyak implementasi. Apa yang membuatnya istimewa?

Itu ditulis dalam C# murni, dikompilasi ke MSIL (AnyCPU) dan berjalan di .NET 3.5 dan yang lebih baru.
Ia tidak memiliki ketergantungan.
Ini tidak memperkenalkan batasan pada karakter dalam kunci. Beberapa implementasi yang bersaing hanya mengizinkan 26 huruf bahasa Inggris. Implementasi ini menangani semua karakter Unicode.
Algoritme pemadatan mengunjungi setiap node hanya sekali sehingga membuatnya sangat cepat (5 detik untuk daftar 2 juta kata saya).
Ia menawarkan persistensi yang unik: panggil Load/Save untuk menulis data ke disk dan membacanya kembali.
Ini memiliki pengujian unit (menggunakan kerangka pengujian Visual Studio).
Ini telah menerima beberapa jam sesi pembuatan profil kinerja sehingga dapat dilakukan secepat mungkin. Langkah selanjutnya untuk membuatnya lebih cepat adalah menulis ulang kode yang relevan di IL.
Ramah GC: Pengumpul Sampah hanya melihat 3 array besar int tempat Kamus akan menyimpan jutaan string.

Penggunaan

Dalam contoh ini kita akan menyimulasikan skenario penggunaan yang melibatkan dua program, satu untuk menghasilkan kamus dan menuliskannya ke disk dan yang lainnya untuk memuat file tersebut dan menggunakan kamus read-only untuk pencarian.

Pertama dapatkan kodenya dengan mengkloning repositori ini atau menginstal paket NuGet.

Membuat dan mengisi objek 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 ) ;
}

(Atau, lakukan var dawgBuilder = words.ToDawgBuilder(key => key, _ => true); )

Panggil BuildDawg untuk mendapatkan versi terkompresi dan menyimpannya ke disk:

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

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

Sekarang baca kembali file tersebut dan periksa apakah ada kata tertentu di kamus:

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

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

Jenis Nilai, <TPayload>

Kelas Dawg dan DawgBuilder mengambil parameter templat yang disebut <TPayload> . Itu bisa jenis apa pun yang Anda inginkan. Hanya untuk dapat menguji apakah suatu kata ada dalam kamus, bool saja sudah cukup. Anda juga dapat menjadikannya int atau string atau kelas khusus. Namun waspadalah terhadap satu batasan penting. DAWG bekerja dengan baik hanya ketika kumpulan nilai yang dapat diambil oleh TPayload relatif kecil. Semakin kecil semakin baik. Misalnya, jika Anda menambahkan definisi untuk setiap kata, setiap entri akan menjadi unik dan grafik Anda akan menjadi pohon (yang mungkin tidak terlalu buruk!).

Awalan Pertandingan()

Salah satu sisi menarik lainnya dari DAWG adalah kemampuannya mengambil semua kata yang dimulai dengan substring tertentu secara efisien:

dawg . MatchPrefix ( " awe " )

Kueri di atas akan mengembalikan IEnumerable<KeyValuePair> yang mungkin berisi kunci seperti awe, aweful , dan awesome . Panggilan dawg.MatchPrefix("") akan mengembalikan semua item dalam kamus.

Jika Anda perlu mencari berdasarkan sufiks, tidak ada metode MatchSuffix. Namun efek yang diinginkan dapat dicapai dengan menambahkan kunci terbalik dan kemudian menggunakan MatchPrefix() pada kunci terbalik:

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

DapatkanAwalan()

GetPrefixes() mengembalikan semua item kamus yang kuncinya merupakan substring dari string tertentu. Misalnya:

dawg . GetPrefixes ( " awesomenesses " )

Mungkin mengembalikan kunci seperti kekaguman, kedahsyatan, kedahsyatan, dan akhirnya kedahsyatan .

DapatkanPanjangAwalanUmumTerpanjang()

Salah satu fitur menarik lainnya adalah metode int GetLongestCommonPrefixLength(IEnumerable<char> word) . Jika word ditemukan di kamus, panjangnya akan dikembalikan; jika tidak, ia akan mengembalikan panjang kata terpanjang yang ditemukan dalam kamus dan itu juga merupakan awal dari kata yang diberikan. Misalnya, jika persiapan ada dalam kamus tetapi preempt tidak, maka dawg.GetLongestCommonPrefixLength("preempt") akan mengembalikan 3 yang merupakan panjang dari "pre".

Keamanan Benang

Kelas DawgBuilder tidak aman untuk thread dan harus diakses hanya oleh satu thread pada waktu tertentu.

Kelas Dawg tidak dapat diubah dan karenanya aman untuk thread.

MultiDawg

Kelas MultiDawg dapat menyimpan banyak nilai terhadap satu kunci string dengan cara yang sangat hemat memori.

Rencana masa depan

Skenario penggunaan lainnya

API dirancang agar sesuai dengan skenario penggunaan tertentu (lihat di atas) dan dapat diperluas untuk mendukung skenario lain, misalnya kemampuan untuk menambahkan kata-kata baru ke kamus setelah dipadatkan. Saya hanya tidak membutuhkan ini sehingga tidak diterapkan. Anda tidak akan mendapatkan pengecualian apa pun. Tidak ada metode Insert di kelas Dawg .