آلة الحالة المحدودة غير الدورية الحتمية

📅 آخر تحديث: ٢٨ يوليو ٢٠٢٦
✍️ نُشر في: ٢٨ يوليو ٢٠٢٦
📷 يحتوي على 1 صور
الموسوعة الحرة
يتم تخزين السلاسل "tap" و "taps" و "top" و "tops" في شجرة بحث (يسار) و DAFSA (يمين)، EOW تعني نهاية الكلمة.

في علم الحاسوب ، تُعرف آلة الحالة المحدودة غير الدورية الحتمية ( DAFSA ) [ 1 ] بأنها بنية بيانات تمثل مجموعة من السلاسل النصية ، وتتيح إجراء عملية استعلام لاختبار ما إذا كانت سلسلة نصية معينة تنتمي إلى المجموعة في وقت يتناسب مع طولها. توجد خوارزميات لإنشاء وصيانة هذه الآلات [ 1 ] مع الحفاظ على بساطتها . تُعد DAFSA إعادة اكتشاف لبنية بيانات تُسمى الرسم البياني للكلمات غير الدورية الموجهة (DAWG) [ 2 ] ، على الرغم من أن الاسم نفسه قد أُطلق سابقًا على بنية بيانات أخرى مرتبطة بآلة اللواحق [ 3 ] .

آلة الحالة المحدودة الموجهة غير الدورية (DAFSA) هي حالة خاصة من آلات التعرف على الحالات المحدودة ، وتتخذ شكل رسم بياني موجه غير دوري ذي رأس مصدر واحد (رأس بدون حواف واردة)، حيث تُسمى كل حافة من حواف الرسم البياني بحرف أو رمز، ولكل رأس حافة صادرة واحدة على الأكثر لكل حرف أو رمز ممكن. تتكون السلاسل التي تمثلها آلة الحالة المحدودة الموجهة غير الدورية من الرموز الموجودة على المسارات في الرسم البياني من رأس المصدر إلى أي رأس مصب (رأس بدون حواف صادرة). في الواقع، تكون آلة الحالة المحدودة المحددة غير دورية إذا وفقط إذا كانت تتعرف على مجموعة محدودة من السلاسل . [ 1 ]

تاريخ

قام بلومر وآخرون [ 3 ] بتعريف مصطلح الرسم البياني للكلمات غير الدورية الموجهة (DAWG) لأول مرة في عام 1983. استخدم أبيل وجاكوبسن [ 2 ] نفس التسمية لهيكل بيانات مختلف في عام 1988. وبشكل مستقل عن العمل السابق، أعاد داتشيوك وآخرون [ 1 ] اكتشاف هيكل البيانات الأخير في عام 2000 لكنهم أطلقوا عليه اسم DAFSA.

مقارنة بالمحاولات

بفضل إمكانية الوصول إلى الرؤوس نفسها عبر مسارات متعددة، قد تستخدم DAFSA عددًا أقل بكثير من الرؤوس مقارنةً ببنية بيانات الشجرة ذات الصلة القوية . على سبيل المثال، لنأخذ الكلمات الإنجليزية الأربع "tap" و"taps" و"top" و"tops". ستحتوي شجرة هذه الكلمات الأربع على 12 رأسًا، رأس واحد لكل سلسلة من السلاسل المكونة كبادئة لإحدى هذه الكلمات، أو لإحدى الكلمات متبوعة بعلامة نهاية السلسلة. مع ذلك، يمكن لـ DAFSA تمثيل هذه الكلمات الأربع نفسها باستخدام ستة رؤوس فقط vᵢ حيث 0 ≤ i ≤ 5، والحواف التالية: حافة من v₀ إلى v₁ تحمل علامة "t"، وحافتان من v₁ إلى v₂ تحملان علامتي "  a " و " o " ، وحافة من v₂ إلى v₃ تحمل علامة " p " ، وحافة من v₃ إلى v₄ تحمل علامة " s "، وحواف من v₃ و v₄ إلى v₅ تحمل علامة نهاية السلسلة. هناك مقايضة بين الذاكرة والوظائف، لأن DAFSA القياسي يمكنه إخبارك ما إذا كانت كلمة ما موجودة بداخله، لكنه لا يستطيع أن يشير إلى معلومات إضافية حول تلك الكلمة، بينما يمكن لشجرة البحث أن تفعل ذلك.   

يتمثل الفرق الرئيسي بين DAFSA وشجرة البحث (Trie) في التخلص من تكرار اللواحق والزوائد في تخزين السلاسل النصية. تتخلص شجرة البحث من تكرار البادئات لأن جميع البادئات المشتركة بين السلاسل النصية، مثل البادئة "doctor" المشتركة بين كلمتي "doctors " و "doctorate" . في DAFSA، تُشارك اللواحق المشتركة أيضًا، وذلك للكلمات التي لها نفس مجموعة اللواحق الممكنة. بالنسبة لمجموعات القواميس من الكلمات الإنجليزية الشائعة، يُترجم هذا إلى تقليل كبير في استخدام الذاكرة.

نظرًا لإمكانية الوصول إلى العقد الطرفية في DAFSA عبر مسارات متعددة، لا يمكن لـ DAFSA تخزين معلومات إضافية تتعلق بكل مسار بشكل مباشر، مثل تردد كلمة ما في اللغة الإنجليزية. مع ذلك، إذا قمنا بتخزين عدد المسارات الفريدة التي تمر عبر كل عقدة في البنية، فيمكننا استخدام هذه المعلومات لاسترجاع فهرس كلمة ما، أو كلمة معينة بمعرفة فهرسها. [ 4 ] ويمكن بعد ذلك تخزين المعلومات الإضافية في مصفوفة.

مراجع

  1. 1 2 3 4 جان داتشيوك، ستويان ميهوف، بروس واتسون وريتشارد واتسون (2000). البناء التدريجي لآلات الحالة المحدودة غير الدورية الدنيا. اللغويات الحاسوبية 26 (1):3-16.
  2. 1 2 أبيل، أندرو؛ جاكوبسن، جاي (1988). أسرع برنامج سكرابل في العالم. اتصالات رابطة آلات الحوسبة، 31 (5): 572-578
  3. 1 2 أنسيلم بلومر، جانيت بلومر، أندريه إهرنفويشت، ديفيد هاوسلر، روس م. ماكونيل (1983). آلات الحالة المحدودة ذات الحجم الخطي لمجموعة جميع الكلمات الفرعية لكلمة ما - ملخص النتائج. نشرة الجمعية الأوروبية لعلوم الحاسوب النظرية، 21 : 12-20
  4. ↑ كوالتوفسكي، ت.؛ سي إل لوتشيسي (1993). "تطبيقات الأوتوماتا المحدودة التي تمثل مفردات كبيرة". البرمجيات - الممارسة والخبرة . 1993 : 15-30 . CiteSeerX 10.1.1.56.5272 . 
  • بلومر، أ.؛ بلومر، ج.؛ هاوسلر، د.؛ إهرنفويشت، أ.؛ تشين، م. ت.؛ سيفراس، ج. (1985)، "أصغر آلة تتعرف على الكلمات الفرعية للنص"، علوم الحاسوب النظرية ، 40 : 31-55 ، doi : 10.1016/0304-3975(85)90157-4
  • أبيل، أندرو؛ جاكوبسن، جاي (1988)، "أسرع برنامج سكرابل في العالم" (ملف PDF) ، اتصالات رابطة آلات الحوسبة ، 31 (5): 572-578 ، doi : 10.1145/42411.42420. أحد أوائل الإشارات إلى بنية البيانات.
  • يانسن، سيس جيه إيه؛ بوكي، ديك إي. (1990)، "حول أهمية الرسم البياني للكلمات غير الدورية الموجهة في علم التشفير"، التقدم في علم التشفير - AUSCRYPT '90 ، سلسلة محاضرات في علوم الحاسوب ، المجلد  453، سبرينغر-فيرلاغ ، الصفحات 318-326 ، doi : 10.1007/BFb0030372 ، ISBN  3-540-53000-2.
  • إبيفانيو، كيارا؛ مينوسي، فيليبو؛ شاليط، جيفري. Venturini، Ilaria (2004)، “الرسوم البيانية Sturmian وتخمين موسر”، في Calude، Cristian S .؛ كالود، إيلينا؛ دينين، مايكل ج. (محرران)، التطورات في نظرية اللغة. وقائع المؤتمر الدولي الثامن (DLT 2004)، أوكلاند، نيوزيلندا، ديسمبر 2004 ، ملاحظات محاضرة في علوم الكمبيوتر، المجلد.  3340، سبرينغر فيرلاغ ، الصفحات من 175 إلى 187، ISBN  3-540-24014-4، Zbl 1117.68454 
  • تريسولدي، تياجو (2020)، "DAFSA: مكتبة بايثون لأتمتة الحالات المحدودة غير الدورية الحتمية"، مجلة البرمجيات مفتوحة المصدر ، 5 (46): 1986، Bibcode : 2020JOSS....5.1986T ، doi : 10.21105/joss.01986 ، hdl : 21.11116/0000-0005-AD0D-Bتطبيق مفتوح المصدر بلغة بايثون .