نظرة عامة شاملة حول مصفوفة اللواحق لسلسلة نصية

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

تم اقتراح مصفوفة اللواحق بواسطة Manber & Myers (1990) كبديل بسيط وموفر للمساحة لأشجار اللواحق. وقد تم اكتشافها بشكل مستقل من قبل جاستون جونيت في عام 1987 تحت اسم مجموعة PAT (Gonnet, Baeza-Yates & Snider 1992) .

قدم Li, Li & Huo (2016) أول خوارزمية لبناء مصفوفة لاحقات زمنية في تعقيد وقت











O





(

n

)





{\displaystyle {\mathcal {O}}(n)}



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











O





(

n

)





{\displaystyle {\mathcal {O}}(n)}



تتجاوز سلسلة الإدخال ومصفوفة لاحقات الإخراج.

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