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

จากวิกิพีเดีย สารานุกรมเสรี
ไบยังการนำทาง ไปยังการค้นหา
Suffix array
Type Array
Invented by Manber & Myers (1990)
Time complexity
in big O notation
Average Worst case
Space
Construction

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