เมนูนำทาง
แถวลำดับซัฟฟิกซ์
พิจารณาข้อความ S {\displaystyle S} =banana$ เพื่อสร้างดัชนี:
| i | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|---|
| S [ i ] {\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 |
อาร์เรย์ A {\displaystyle A} มีตำแหน่งเริ่มต้นของส่วนต่อท้ายที่เรียงลำดับเหล่านี้:
| i | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|---|
| A [ i ] {\displaystyle A[i]} | 7 | 6 | 4 | 2 | 1 | 5 | 3 |
suffix array เขียนไว้ในแนวตั้งเพื่อความชัดเจน:
| i | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|---|
| A [ i ] {\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 | $ |
ตัวอย่างเช่น A [ 3 ] {\displaystyle A[3]} มีค่า 4 ดังนั้นจึงหมายถึงส่วนต่อท้ายที่เริ่มต้นที่ตำแหน่งที่ 4 ภายใน S {\displaystyle S} ana$
เมนูนำทาง
แถวลำดับซัฟฟิกซ์ใกล้เคียง
แหล่งที่มา
WikiPedia: แถวลำดับซัฟฟิกซ์