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

Suffix array
Type	Array
Invented by	แม่แบบ:Harvtxt
Time complexity in big O notation
Average	Worst case
Space	$𝒪(n)$	$𝒪(n)$
Construction	$𝒪(n)$	$𝒪(n)$

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

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

นิยาม

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

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

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

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

i	1	2	3	4	5	6	7
$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

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

i	1	2	3	4	5	6	7
$A[i]$	7	6	4	2	1	5	3

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

i	1	2	3	4	5	6	7
$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					$

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