แถวลำดับซัฟฟิกซ์

Suffix array Type Array Invented by   Time complexityin big O notation Average Worst case Space   Construction  
ในวิทยาการคอมพิวเตอร์ แถวลำดับซัฟฟิกซ์ () คือการจัดเรียง อาร์เรย์ ของ ข้อความทั้งหมดจากท้ายข้อความ เป็นโครงสร้างข้อมูลที่ใช้ในดัชนีข้อความแบบเต็ม อัลกอริทึมการบีบอัดข้อมูลและภายในเขตข้อมูลของ  bibliometrics

แถวลำดับซัฟฟิกซ์  ถูกเป็นแนะนำโดย Manber & Myers (1990) เป็นเรื่องง่ายสำหรับ suffix trees

 นิยาม 
ให้  เป็นข้อความและให้  หมายถึงสตริงย่อยของ  ตั้งแต่  ถึง 

 ของ  ถูกกำหนดให้เป็นอาร์เรย์ของจำนวนเต็ม ให้ตำแหน่งเริ่มต้นของส่วนต่อท้าย  ใน lexicographical order ซึ่งหมายความว่า รายการ  มีตำแหน่งเริ่มต้นของ -คำต่อท้ายที่เล็กที่สุดใน  และสำหรับทั้งหมด : 

 ตัวอย่างเช่น 
พิจารณาข้อความ =banana$ เพื่อสร้างดัชนี:
 i 1  2  3  4  5  6  7  b  a  n  a  n  a  $
ข้อความสิ้นสุดให้ลงท้ายด้วยเครื่องหมายนพิเศษ $ ที่มีลักษณะเฉพาะและมีขนาดเล็กกว่าตัวอักษรอื่น ๆ ข้อความที่มีคำต่อท้ายดังต่อไปนี้:
 Suffix  i banana$  1 anana$  2 nana$  3 ana$  4 na$  5 a$  6 $  7
คำเหล่านี้สามารถจัดเรียงตามลำดับจากน้อยไปมาก:
 Suffix  i $  7 a$  6 ana$  4 anana$  2 banana$  1 na$  5 nana$  3
อาร์เรย์  มีตำแหน่งเริ่มต้นของส่วนต่อท้ายที่เรียงลำดับเหล่านี้:
 i 1  2  3  4  5  6  7  7  6  4  2  1  5  3
suffix array เขียนไว้ในแนวตั้งเพื่อความชัดเจน:
 i 1  2  3  4  5  6  7  7  6  4  2  1  5  3 1 $  a  a  a  b  n  n 2    $  n  n  a  a  a 3       a  a  n  $  n 4       $  n  a    a 5         a  n    $ 6         $  a     7           $    
ตัวอย่างเช่น  มีค่า 4 ดังนั้นจึงหมายถึงส่วนต่อท้ายที่เริ่มต้นที่ตำแหน่งที่ 4 ภายใน  ana$
หมวดหมู่:แถวลำดับ