مصفوفة اللواحق لسلسلة نصية
المحتويات
بدايةً، في علم الحاسوب ، مصفوفة اللواحق (Suffix Array) هي مصفوفة مرتبة من جميع لواحق السلسلة النصيّة. هو عبارة عن مبنى معطيات يُستعمل في عدة مجالات مثل ألغورتمات ضغط البيانات وغيرها.. ونتناول فيما يلي مزيدًا من التفاصيل.
وعلى صعيد آخر، قدم أول خوارزمية لبناء مصفوفة لاحقات زمنية في تعقيد وقت وهي الخوارزمية المثالية في كل من الزمان والمكان، حيث تعني في المكان أن الخوارزمية تحتاج فقط إلى مساحة إضافية تتجاوز سلسلة الإدخال ومصفوفة لاحقات الإخراج.
من جهة ثانية، تم اقتراح مصفوفة اللواحق بواسطة كبديل بسيط وموفر للمساحة لأشجار اللواحق. وقد تم اكتشافها بشكل مستقل من قبل جاستون جونيت في سنة 1987 تحت اسم مجموعة PAT .
إضافةً إلى ذلك، مصفوفة لواحق مُحسّنة/مُعزّزة (Enhanced suffix arrays - ESA) هي عبارة عن مصفوفة لاواحق تحتوي على جداول إضافية تعيد إنتاج الوظائف الكاملة لأشجار اللاحقة مع الحفاظ على نفس تعقيد الوقت والذاكرة. تُسمى مجموعة اللواحق لمجموعة فرعية من جميع لواحق السلسلة بمصفوفة اللواحق المتفرقة . تم تطوير خوارزميات احتمالية متعددة لتقليل استخدام الذاكرة الإضافية بما في ذلك خوارزمية الوقت والذاكرة المثلى.
علاقة مصفوفة اللواحق بـأشجار اللواحق
إضافةً إلى ذلك، يمكن إنشاء شجرة لاحقة في وقت خطي باستخدام مزيج من مصفوفة اللاحقة ومصفوفة LCP . للحصول على وصف للخوارزمية، راجع القسم المقابل في مقالة مجموعة LCP .
من جانب آخر، يمكن إنشاء مصفوفات اللواحق من خلال تنفيذ عملية عبور العمق أولاً (DFS) لشجرة اللواحق. تتوافق مجموعة اللواحق مع تسميات الأوراق المعطاة بالترتيب الذي تتم زيارتها به أثناء المسح، إذا تمت زيارة الحواف بالترتيب المعجمي لحرفها الأول.
ترتبط مصفوفات اللواحق ارتباطًا وثيقًا بأشجار اللواحق :
الغوريتمات بناء مبنى المعطيات
وفي هذا الصدد، يمكن بناء شجرة لاحقة في ويمكن تحويلها إلى مجموعة لاحقة من خلال عبور عمق الشجرة أولاً كذلك لذا، توجد خوارزميات يمكنها بناء مجموعة لاحقة في .
وفي السياق ذاته، الطريقة الساذجة لإنشاء مجموعة لاحقة هي استخدام خوارزمية ترتيب تعتمد على المقارنة. تتطلب هذه الخوارزميات مقارنات اللواحق، ولكن تتم مقارنة اللواحق في الوقت، لذا فإن وقت التشغيل الإجمالي لهذا النهج هو .
مصفوفة اللواحق في جافا
تنفيذ مصفوفة اللواحق في روبي
وحدة ترتيب اللاحقات لـ BWT في كود C
مثال
لنتطلع على النص =banana$ :
ومن جهة أخرى، مثلًا، يحتوي على القيمة 4، وبالتالي يشير إلى اللاحقة التي تبدأ في الموضع 4 داخل ، وهي اللاحقة ana$ .
- يمكن ترتيب هذه اللواحق بترتيب تصاعدي:
- مصفوفة اللواحق يحتوي على مواضع البداية لهذه اللواحق المرتبة:
- مصفوفة اللواخق مع اللاحقات المكتوبة عموديًا في الأسفل من أجل الوضوح:
إضافةً إلى ذلك، وينتهي النص بالرمز الخاص $ الذي يعتبر فريدًا من نوعه وأصغر معجميًا من أي حرف آخر. يحتوي النص على اللواحق التالية:
تعريف
وعلى صعيد آخر، كل لاحقة من يظهر في مرة واحدة بالضبط. اللواحق هي سلاسل بسيطة. يتم ترتيب هذه السلاسل النصية، قبل حفظ مواضعها الأولية (مؤشرات الأعداد الصحيحة) في .
ومن جهة أخرى، لتكن وكذلك -سلسلة و دع تشير إلى السلسلة الفرعية من تتراوح من ل شامل.
وفي السياق ذاته، مجموعة اللواحق ل يتم الآن تعريفه على أنه عبارة عن مجموعة من الأعداد الصحيحة التي توفر مواضع البداية لللاحقات حسب الترتيب الأبجدي . وهذا يعني دخول يحتوي على موضع البداية لـ - أصغر لاحقة في وهكذا للجميع : .
مصفوفة لاحقة معممة
إضافةً إلى ذلك، يمكن توسيع مفهوم مجموعة اللواحق إلى أكثر من سلسلة واحدة. يُطلق على هذا اسم مصفوفة لاحقات معممة (أو GSA)، وهي مصفوفة لاحقات تحتوي على جميع اللاحقات لمجموعة من السلاسل (مثلًا، ويتم ترتيبها معجميًا مع جميع لاحقات كل سلسلة.
تنفيذ مصفوفة اللواحق في بايثون
ومن ناحية أخرى، تنفيذ مصفوفة اللاحقات الزمنية الخطية في لغة C باستخدام شجرة اللاحقات
مكتبة أدوات مجموعة اللواحق
مكتبة API C سريعة وخفيفة الوزن وقوية لإنشاء مجموعة اللاحقات
ومن جهة أخرى، مشروع يحتوي على تطبيقات Suffix Array c/c++ المختلفة مع واجهة موحدة
📝 هل في هذه المقالة خطأ؟
إذا وجدت معلومة تحتاج تصحيحاً أو إضافة، أو أردت حذف المقالة، أرسل لنا طلباً وسنراجعه.
ما رأيك في هذه المقالة؟