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

في علم الحاسوب ، مصفوفة اللواحق (Suffix Array) هي مصفوفة مرتبة من جميع لواحق السلسلة النصيّة. هو عبارة عن مبنى معطيات يُستخدم في عدة مجالات مثل ألغورتمات ضغط البيانات وغيرها..
تم اقتراح مصفوفة اللواحق بواسطة Manber & Myers (1990) كبديل بسيط وموفر للمساحة لأشجار اللواحق. وقد تم اكتشافها بشكل مستقل من قبل جاستون جونيت في عام 1987 تحت اسم مجموعة PAT (Gonnet, Baeza-Yates & Snider 1992) .
قدم Li, Li & Huo (2016) أول خوارزمية لبناء مصفوفة لاحقات زمنية في تعقيد وقت ${\mathcal {O}}(n)$ وهي الخوارزمية المثالية في كل من الزمان والمكان، حيث تعني في المكان أن الخوارزمية تحتاج فقط إلى مساحة إضافية ${\mathcal {O}}(n)$ تتجاوز سلسلة الإدخال ومصفوفة لاحقات الإخراج.
مصفوفة لواحق مُحسّنة/مُعزّزة (Enhanced suffix arrays - ESA) هي عبارة عن مصفوفة لاواحق تحتوي على جداول إضافية تعيد إنتاج الوظائف الكاملة لأشجار اللاحقة مع الحفاظ على نفس تعقيد الوقت والذاكرة. تُسمى مجموعة اللواحق لمجموعة فرعية من جميع لواحق السلسلة بمصفوفة اللواحق المتفرقة . تم تطوير خوارزميات احتمالية متعددة لتقليل استخدام الذاكرة الإضافية بما في ذلك خوارزمية الوقت والذاكرة المثلى.

## تعريف

لتكن $S=S[1]S[2]...S[n]$ وكذلك n{\textstyle n} -سلسلة و دع $S[i,j]$ تشير إلى السلسلة الفرعية من $S$ تتراوح من $i$ ل $j$ شامل.
مجموعة اللواحق $A$ ل $S$ يتم الآن تعريفه على أنه عبارة عن مجموعة من الأعداد الصحيحة التي توفر مواضع البداية لللاحقات $S$ حسب الترتيب الأبجدي . وهذا يعني دخول $A[i]$ يحتوي على موضع البداية لـ $i$ - أصغر لاحقة في $S$ وهكذا للجميع $1\leq i\leq n$ : $S[A[i-1],n]<S[A[i],n]$ .
كل لاحقة من $S$ يظهر في $A$ مرة واحدة بالضبط. اللواحق هي سلاسل بسيطة. يتم ترتيب هذه السلاسل النصية، قبل حفظ مواضعها الأولية (مؤشرات الأعداد الصحيحة) في $A$ .

## مثال

لنتطلع على النص $S$=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 |
مصفوفة اللواحق $A$ يحتوي على مواضع البداية لهذه اللواحق المرتبة:
مصفوفة اللواخق مع اللاحقات المكتوبة عموديًا في الأسفل من أجل الوضوح:
على سبيل المثال، $A[3]$ يحتوي على القيمة 4، وبالتالي يشير إلى اللاحقة التي تبدأ في الموضع 4 داخل $S$ ، وهي اللاحقة ana$ .

## علاقة مصفوفة اللواحق بـأشجار اللواحق

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

## الغوريتمات بناء مبنى المعطيات

يمكن بناء شجرة لاحقة في ${\mathcal {O}}(n)$ ويمكن تحويلها إلى مجموعة لاحقة من خلال عبور عمق الشجرة أولاً أيضًا ${\mathcal {O}}(n)$ لذا، توجد خوارزميات يمكنها بناء مجموعة لاحقة في ${\mathcal {O}}(n)$ .
الطريقة الساذجة لإنشاء مجموعة لاحقة هي استخدام خوارزمية ترتيب تعتمد على المقارنة. تتطلب هذه الخوارزميات ${\mathcal {O}}(n\log n)$ مقارنات اللواحق، ولكن تتم مقارنة اللواحق في ${\mathcal {O}}(n)$ الوقت، لذا فإن وقت التشغيل الإجمالي لهذا النهج هو ${\mathcal {O}}(n^{2}\log n)$ .

## مصفوفة لاحقة معممة

يمكن توسيع مفهوم مجموعة اللواحق إلى أكثر من سلسلة واحدة. يُطلق على هذا اسم مصفوفة لاحقات معممة (أو GSA)، وهي مصفوفة لاحقات تحتوي على جميع اللاحقات لمجموعة من السلاسل (على سبيل المثال، $S=S_{1},S_{2},S_{3},...,S_{k}$ ويتم ترتيبها معجميًا مع جميع لاحقات كل سلسلة.

## مراجع

* Manber، Udi؛ Myers، Gene (1990). "Suffix arrays: a new method for on-line string searches". First Annual ACM-SIAM Symposium on Discrete Algorithms. ص. 319–327. مؤرشف من الأصل في 2019-02-14.
* Manber، Udi؛ Myers، Gene (1993). "Suffix arrays: a new method for on-line string searches". SIAM Journal on Computing. ج. 22 ع. 5: 935–948. DOI:10.1137/0222058. S2CID:5074629. مؤرشف من الأصل في 2019-02-14.
* Gawrychowski، Paweł؛ Kociumaka، Tomasz (يناير 2017). "Sparse Suffix Tree Construction in Optimal Time and Space". Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms. Philadelphia, PA: Society for Industrial and Applied Mathematics: 425–439. arXiv:1608.00865. DOI:10.1137/1.9781611974782.27. ISBN:9781611974782. S2CID:6608776.
* Li، Zhize؛ Li، Jian؛ Huo، Hongwei (2016). "Optimal In-Place Suffix Sorting". Proceedings of the 25th International Symposium on String Processing and Information Retrieval (SPIRE). Lecture Notes in Computer Science. Springer. ج. 11147. ص. 268–284. arXiv:1610.08305. DOI:10.1007/978-3-030-00479-8_22. ISBN:978-3-030-00478-1.
* Shi، Fei (1996). "Suffix arrays for multiple strings: A method for on-line multiple string searches". Concurrency and Parallelism, Programming, Networking, and Security. Lecture Notes in Computer Science. Springer Berlin Heidelberg. ج. 1179. ص. 11–22. DOI:10.1007/BFb0027775. ISBN:978-3-540-62031-0.
* Abouelhoda، Mohamed Ibrahim؛ Kurtz، Stefan؛ Ohlebusch، Enno (2002). "The Enhanced Suffix Array and Its Applications to Genome Analysis". Algorithms in Bioinformatics. مذكرات محاضرة في علم الحاسوب $^{[لغاتأخرى]}$‏. ج. 2452. DOI:10.1007/3-540-45784-4_35. ISBN:978-3-540-44211-0.{{استشهاد بمنشورات مؤتمر}}: صيانة الاستشهاد: علامات ترقيم زائدة (link)
* Abouelhoda، Mohamed Ibrahim؛ Kurtz، Stefan؛ Ohlebusch، Enno (مارس 2004). "Replacing suffix trees with enhanced suffix arrays". Journal of Discrete Algorithms. ج. 2 ع. 1: 53–86. DOI:10.1016/S1570-8667(03)00065-0. ISSN:1570-8667.
* Gonnet، G.H.؛ Baeza-Yates، R.A.؛ Snider، T. (1992). "New indices for text: PAT trees and PAT arrays". Information Retrieval: Data Structures and Algorithms. مؤرشف من الأصل في 2021-12-07.
* Kurtz، S (1999). "Reducing the space requirement of suffix trees". Software: Practice and Experience. ج. 29 ع. 13: 1149–1171. DOI:10.1002/(SICI)1097-024X(199911)29:13<1149::AID-SPE274>3.0.CO;2-O. hdl:10338.dmlcz/135448.
* Puglisi، Simon J.؛ Smyth، W. F.؛ Turpin، Andrew H. (2007). "A taxonomy of suffix array construction algorithms". ACM Computing Surveys. ج. 39 ع. 2: 4. DOI:10.1145/1242471.1242472. S2CID:2653529. مؤرشف من الأصل في 2022-05-27.
* Nong، Ge؛ Zhang، Sen؛ Chan، Wai Hong (2009). "Linear Suffix Array Construction by Almost Pure Induced-Sorting". 2009 Data Compression Conference. ص. 193. DOI:10.1109/DCC.2009.42. ISBN:978-0-7695-3592-0.
* Fischer، Johannes (2011). "Inducing the LCP-Array". Algorithms and Data Structures. Lecture Notes in Computer Science. ج. 6844. ص. 374–385. arXiv:1101.3448. DOI:10.1007/978-3-642-22300-6_32. ISBN:978-3-642-22299-3.
* Salson، M.؛ Lecroq، T.؛ Léonard، M.؛ Mouchard، L. (2010). "Dynamic extended suffix arrays". Journal of Discrete Algorithms. ج. 8 ع. 2: 241. DOI:10.1016/j.jda.2009.02.007.
* Burkhardt، Stefan؛ Kärkkäinen، Juha (2003). "Fast Lightweight Suffix Array Construction and Checking". Combinatorial Pattern Matching. Lecture Notes in Computer Science. ج. 2676. ص. 55–69. DOI:10.1007/3-540-44888-8_5. ISBN:978-3-540-40311-1.
* Karp، Richard M.؛ Miller، Raymond E.؛ Rosenberg، Arnold L. (1972). "Rapid identification of repeated patterns in strings, trees and arrays". Proceedings of the fourth annual ACM symposium on Theory of computing - STOC '72. ص. 125–136. DOI:10.1145/800152.804905.
* Farach، M. (1997). "Optimal suffix tree construction with large alphabets". Proceedings 38th Annual Symposium on Foundations of Computer Science. DOI:10.1109/SFCS.1997.646102. ISBN:0-8186-8197-7.
* I، Tomohiro؛ Kärkkäinen، Juha؛ Kempa، Dominik (2014). Faster Sparse Suffix Sorting. Leibniz International Proceedings in Informatics (LIPIcs). Schloss Dagstuhl – Leibniz-Zentrum fuer Informatik. ج. 25. ص. 386–396. DOI:10.4230/LIPIcs.STACS.2014.386. ISBN:978-3-939897-65-1.
* Kärkkäinen، Juha؛ Sanders، Peter (2003). "Simple Linear Work Suffix Array Construction". Automata, Languages and Programming. Lecture Notes in Computer Science. ج. 2719. DOI:10.1007/3-540-45061-0_73. ISBN:978-3-540-40493-4.
* Dementiev، Roman؛ Kärkkäinen، Juha؛ Mehnert، Jens؛ Sanders، Peter (2008). "Better external memory suffix array construction". Journal of Experimental Algorithmics. ج. 12: 1–24. DOI:10.1145/1227161.1402296. S2CID:12296500. مؤرشف من الأصل في 2024-08-29.
* Kulla، Fabian؛ Sanders، Peter (2007). "Scalable parallel suffix array construction". Parallel Computing. ج. 33 ع. 9: 605–612. DOI:10.1016/j.parco.2007.06.004.
* 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.