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

ในวิทยาการคอมพิวเตอร์ แถวลำดับซัฟฟิกซ์ (อังกฤษ: suffix array) คือการจัดเรียง อาร์เรย์ ของ ข้อความทั้งหมดจากท้ายข้อความ เป็นโครงสร้างข้อมูลที่ใช้ในดัชนีข้อความแบบเต็ม อัลกอริทึมการบีบอัดข้อมูลและภายในเขตข้อมูลของ bibliometrics

Suffix array
Type	Array
Invented by	Manber & Myers (1990)
Time complexity in big O notation
Average	Worst case
Space	${\displaystyle {\mathcal {O}}(n)}$	${\displaystyle {\mathcal {O}}(n)}$
Construction	${\displaystyle {\mathcal {O}}(n)}$	${\displaystyle {\mathcal {O}}(n)}$

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

นิยาม

ให้ ${\displaystyle S=S[1]S[2]...S[n]}$  เป็นข้อความและให้ ${\displaystyle S[i,j]}$  หมายถึงสตริงย่อยของ ${\displaystyle S}$  ตั้งแต่ ${\displaystyle i}$  ถึง ${\displaystyle j}$ 

${\displaystyle A}$  ของ ${\displaystyle S}$  ถูกกำหนดให้เป็นอาร์เรย์ของจำนวนเต็ม ให้ตำแหน่งเริ่มต้นของส่วนต่อท้าย ${\displaystyle S}$  ใน lexicographical order ซึ่งหมายความว่า รายการ ${\displaystyle A[i]}$  มีตำแหน่งเริ่มต้นของ ${\displaystyle i}$ -คำต่อท้ายที่เล็กที่สุดใน ${\displaystyle S}$  และสำหรับทั้งหมด ${\displaystyle {\displaystyle 1<i\leq n}}$ : ${\displaystyle {\displaystyle S[A[i-1],n]<S[A[i],n]}}$ 

ตัวอย่างเช่น

พิจารณาข้อความ ${\displaystyle S}$ =banana$ เพื่อสร้างดัชนี:

i	1	2	3	4	5	6	7
${\displaystyle S[i]}$	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

อาร์เรย์ ${\displaystyle A}$  มีตำแหน่งเริ่มต้นของส่วนต่อท้ายที่เรียงลำดับเหล่านี้:

i	1	2	3	4	5	6	7
${\displaystyle A[i]}$	7	6	4	2	1	5	3

suffix array เขียนไว้ในแนวตั้งเพื่อความชัดเจน:

i	1	2	3	4	5	6	7
${\displaystyle A[i]}$	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					$

ตัวอย่างเช่น ${\displaystyle A[3]}$  มีค่า 4 ดังนั้นจึงหมายถึงส่วนต่อท้ายที่เริ่มต้นที่ตำแหน่งที่ 4 ภายใน ${\displaystyle S}$  ana$