مصفوفة اللواحق لسلسلة نصية

في علم الحاسوب ، مصفوفة اللواحق (Suffix Array) هي مصفوفة مرتبة من جميع لواحق السلسلة النصيّة. هو عبارة عن مبنى معطيات يُستخدم في عدة مجالات مثل ألغورتمات ضغط البيانات وغيرها..

تم اقتراح مصفوفة اللواحق بواسطة  كبديل بسيط وموفر للمساحة لأشجار اللواحق. وقد تم اكتشافها بشكل مستقل من قبل جاستون جونيت في عام 1987 تحت اسم مجموعة PAT  .

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

مصفوفة لواحق مُحسّنة/مُعزّزة (Enhanced suffix arrays - ESA) هي عبارة عن مصفوفة لاواحق تحتوي على جداول إضافية تعيد إنتاج الوظائف الكاملة لأشجار اللاحقة مع الحفاظ على نفس تعقيد الوقت والذاكرة.  تُسمى مجموعة اللواحق لمجموعة فرعية من جميع لواحق السلسلة بمصفوفة اللواحق المتفرقة .  تم تطوير خوارزميات احتمالية متعددة لتقليل استخدام الذاكرة الإضافية بما في ذلك خوارزمية الوقت والذاكرة المثلى. 

 تعريف 
لتكن  وكذلك  -سلسلة و دع  تشير إلى السلسلة الفرعية من  تتراوح من  ل  شامل.

مجموعة اللواحق  ل  يتم الآن تعريفه على أنه عبارة عن مجموعة من الأعداد الصحيحة التي توفر مواضع البداية لللاحقات  حسب الترتيب الأبجدي . وهذا يعني دخول  يحتوي على موضع البداية لـ  - أصغر لاحقة في  وهكذا للجميع  :  .

كل لاحقة من  يظهر في  مرة واحدة بالضبط. اللواحق هي سلاسل بسيطة. يتم ترتيب هذه السلاسل النصية، قبل حفظ مواضعها الأولية (مؤشرات الأعداد الصحيحة) في  .

 مثال 
لنتطلع على النص =banana$ :

وينتهي النص بالرمز الخاص $ الذي يعتبر فريدًا من نوعه وأصغر معجميًا من أي حرف آخر. يحتوي النص على اللواحق التالية:
اللاحقة i banana$ 1 anana$ 2 nana$ 3 ana$ 4 na$ 5 a$ 6 $ 7
يمكن ترتيب هذه اللواحق بترتيب تصاعدي:
اللاحقة i $ 7 a$ 6 ana$ 4 anana$ 2 banana$ 1 na$ 5 nana$ 3
مصفوفة اللواحق  يحتوي على مواضع البداية لهذه اللواحق المرتبة:

مصفوفة اللواخق مع اللاحقات المكتوبة عموديًا في الأسفل من أجل الوضوح:

على سبيل المثال،  يحتوي على القيمة 4، وبالتالي يشير إلى اللاحقة التي تبدأ في الموضع 4 داخل  ، وهي اللاحقة ana$ .

 علاقة مصفوفة اللواحق بـأشجار اللواحق 
ترتبط مصفوفات اللواحق ارتباطًا وثيقًا بأشجار اللواحق :

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

 الغوريتمات بناء مبنى المعطيات 
يمكن بناء شجرة لاحقة في  ويمكن تحويلها إلى مجموعة لاحقة من خلال عبور عمق الشجرة أولاً أيضًا  لذا، توجد خوارزميات يمكنها بناء مجموعة لاحقة في  .

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

 مصفوفة لاحقة معممة 
يمكن توسيع مفهوم مجموعة اللواحق إلى أكثر من سلسلة واحدة. يُطلق على هذا اسم مصفوفة لاحقات معممة (أو GSA)، وهي مصفوفة لاحقات تحتوي على جميع اللاحقات لمجموعة من السلاسل (على سبيل المثال،  ويتم ترتيبها معجميًا مع جميع لاحقات كل سلسلة. 

 مراجع 





















 Mohamed Ibrahim Abouelhoda, Stefan Kurtz, and Enno Ohlebusch. "Replacing suffix trees with enhanced suffix arrays." Journal of Discrete Algorithms, 2(1):53–86, 2004.
 Dong Kyue Kim, Jeong Eun Jeon, and Heejin Park. "An efficient index data structure with the capabilities of suffix trees and suffix arrays for alphabets of non-negligible size." String Processing and Information Retrieval Lecture Notes in Computer Science, page138–149, 2004.

 روابط خارجية 

 مصفوفة اللواحق في جافا
 وحدة ترتيب اللاحقات لـ BWT في كود C
 تنفيذ مصفوفة اللواحق في روبي
 مكتبة أدوات مجموعة اللواحق
 مشروع يحتوي على تطبيقات Suffix Array c/c++ المختلفة مع واجهة موحدة
 مكتبة API C سريعة وخفيفة الوزن وقوية لإنشاء مجموعة اللاحقات
 تنفيذ مصفوفة اللواحق في بايثون
 تنفيذ مصفوفة اللاحقات الزمنية الخطية في لغة C باستخدام شجرة اللاحقات

تصنيف:علم الحاسوب النظري
تصنيف:بنى البيانات
تصنيف:سلسلة (علم الحاسوب)
تصنيف:مصفوفات