تنزيل DawgSharp - تنزيل كود مصدر DawgSharp

DawgSharp

شفرة المصدر الأخرى

1.0.0

تنزيل

[حزمة NuGet] [الحصول على رخصة تجارية]

DawgSharp، قاموس سلسلة ذكي في C#

DAWG (الرسم البياني للكلمات الحلقية الموجهة) عبارة عن بنية بيانات لتخزين قوائم الكلمات والقواميس الكبيرة والبحث فيها. ويمكن أن تكون أكثر كفاءة بمقدار 40 مرة من فئة Dictionary .NET لأنواع معينة من البيانات.

على سبيل المثال، يستضيف موقع الويب الخاص بي قاموسًا يضم 2 مليون كلمة والذي كان يستهلك 56 ميجا على القرص ويستغرق تحميله 7 ثوانٍ (عند استخدام Dictionary وBinarySerializer). بعد التبديل إلى DAWG، يستغرق التحميل الآن 1.4 ميجا على القرص و0.3 ثانية.

كيف يكون هذا ممكنا؟ لماذا لا يكون القاموس القياسي ذكيًا مثل DAWG؟ الأمر هو أن DAWG يعمل بشكل جيد مع سلاسل اللغة الطبيعية وقد لا يعمل أيضًا مع السلاسل التي تم إنشاؤها مثل مفاتيح الترخيص (OIN1r4Be2su+UXSeOj0TaQ). تميل كلمات اللغة البشرية إلى أن تحتوي على الكثير من تسلسلات الحروف الشائعة، على سبيل المثال - القدرة والإمكانية وخفة الحركة وما إلى ذلك وتستفيد الخوارزمية من ذلك من خلال العثور على تلك التسلسلات وتخزينها مرة واحدة فقط لكلمات متعددة. أثبت DAWG أيضًا فائدته في تمثيل بيانات الحمض النووي (تسلسل الجينات). يعود تاريخ DAWG إلى عام 1985. لمزيد من المعلومات الخلفية، ابحث في Google DAWG أو DAFSA (Automaton Acyclic Finite State Automaton).

DawgSharp هو أحد تطبيقات DAWG، وهو واحد من العديد من التطبيقات. ما الذي يجعلها مميزة؟

إنه مكتوب بلغة C# النقية، ويتم تجميعه إلى MSIL (AnyCPU) ويعمل على .NET 3.5 وما فوق.
ليس لديها تبعيات.
لا يقدم أي قيود على الأحرف في المفاتيح. تسمح بعض التطبيقات المنافسة بـ 26 حرفًا إنجليزيًا فقط. يعالج هذا التطبيق أي أحرف Unicode.
تقوم خوارزمية الضغط بزيارة كل عقدة مرة واحدة فقط مما يجعلها سريعة جدًا (5 ثوانٍ لقائمة الكلمات التي تحتوي على 2 مليون كلمة).
إنه يوفر استمرارية خارج الصندوق: اتصل بـ Load/Save لكتابة البيانات على القرص وقراءتها مرة أخرى.
يحتوي على اختبارات الوحدة (باستخدام إطار اختبار Visual Studio).
لقد تلقت عدة ساعات من جلسات تحديد الأداء، لذا فهي سريعة قدر الإمكان. الخطوة التالية لتسريع الأمر هي إعادة كتابة الكود ذي الصلة في IL.
إنها صديقة لـ GC: لا يرى Garbage Collector سوى 3 مصفوفات كبيرة من ints حيث يمكن للقاموس تخزين ملايين السلاسل.

الاستخدام

في هذا المثال، سنقوم بمحاكاة سيناريو استخدام يشتمل على برنامجين، أحدهما لإنشاء القاموس وكتابته على القرص والآخر لتحميل هذا الملف واستخدام قاموس القراءة فقط لعمليات البحث.

احصل أولاً على الكود عن طريق استنساخ هذا المستودع أو تثبيت حزمة 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> . يمكن أن يكون أي نوع تريده. فقط لتكون قادرًا على اختبار ما إذا كانت هناك كلمة في القاموس، فإن المنطق يكفي. يمكنك أيضًا جعله int أو string أو فئة مخصصة. ولكن حذار من أحد القيود الهامة. يعمل DAWG بشكل جيد فقط عندما تكون مجموعة القيم التي يمكن أن يأخذها TPayload صغيرة نسبيًا. أصغر كلما كان ذلك أفضل. على سبيل المثال، إذا قمت بإضافة تعريف لكل كلمة، فسوف يجعل كل إدخال فريدًا وسيصبح الرسم البياني الخاص بك شجرة (وهو ما قد لا يكون سيئًا للغاية!).

بادئة المباراة()

أحد الجوانب الجذابة الأخرى في 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 " )

قد يُرجع مفاتيح مثل الرهبة والرهبة والذهول وأخيرًا الذهول .

GetLongestCommonPrefixLength()

إحدى الميزات الرائعة الأخرى هي الطريقة int GetLongestCommonPrefixLength(IEnumerable<char> word) . إذا تم العثور على word في القاموس، فسيتم إرجاع طولها؛ إذا لم يكن الأمر كذلك، فسوف يُرجع طول أطول كلمة موجودة في القاموس والتي تعد أيضًا بداية الكلمة المحددة. على سبيل المثال، إذا كان التحضير موجودًا في القاموس ولكن الإجراء الاستباقي غير موجود، فسيُرجع dawg.GetLongestCommonPrefixLength("preempt") 3 وهو طول "pre".