Suffix array

---- เทคนิค Suffix array
เป็นเทคนิคที่ใช้กันอย่างแพร่หลายเพื่อพิรณาความสัมพันธ์ของชุดข้อมูล เราใช้เทคนิคนี้ในการหากลุ่มของตัวอักษรที่ยาวที่สุดที่ปรากฎซ้ำๆอยู่ในชุดข้อมูล ซึ่งก็คือวลีที่เราต้องการ
---- ให้ A แทน String ใดๆ (ซึ่งถ้ามองอีกรูปหนึ่ง A ก็คือ array of characters นั่นเอง) เราจะได้ S แทน Suffix array ของ A โดยที่ S คือ Array of pointer ที่ชี้ไปที่ตำแหน่งในหน่วยความจำของสมาชิกใน A แต่ละตัว ฉะนั้นสมาชิกของ S แต่ละตัวก็คือ Substring ที่เริ่มต้นด้วยตัวอักษรตำแหน่งต่างๆของ A
เช่น
A = banana
เราจะได้
S[0]=banana
S[1]=anana
S[2]=nana
S[3]=ana
S[4]=na
S[5]=a

จาก S ที่ได้ เราจะนำสมาชิกทั้งหมดของ S มาจัดเรียงลำดับจากน้อยไปมาก ซึ่งจะได้ผลดังต่อไปนี้
S[5]=a
S[3]=ana
S[1]=anana
S[0]=banana
S[4]=na
S[2]=nana
จาก S ที่ได้ผ่านการเรียงลำดับแล้ว จะทำให้เราสามารถหากลุ่มของตัวอักษรที่ยาวที่สุดที่ซ้ำกันในชุดของข้อมูลที่ติดกัน ซึ่งก็คือ anaที่ปรากฏอยู่ที่ S[3] และ S[1] นั่นเอง

จะได้ อัลกอริทึมของโปรแกรมการหา วลี จาก ชุด string ที่ผ่านการเรียงข้อมูลแล้วดังนี้

For m=1 To count(S)-FNUM Do
-----s1=999;
-----For i=m To m+FNUM Do
----------For c=1 To Length(Si) Do
---------------If Si[c] <> Si+1[c] Then
--------------------If c '<' s1= Then s1=c
-------------------break;
---------------End if
----------End for
-----End for
-----If s1 > Then LNUM Then ReturnPhase(S1..s1)
End for

S : คือ จำนวนชุดตัวอักษรย่อยที่ผ่านการจัดเรียงลำดับแล้ว
LNUM คือ จำนวนตัวอักษรน้อยที่สุดของชุดตัวอักษร ที่จะถูกเลือกเป็นวลี
FNUM คือ จำวนวนความถี่น้อยที่สุดในการเกิดชุดตัวอักษร ซ้ำๆกัน ที่จะถูกเลือกเป็นวลี
s1 คือ ตัวแปรสำหรับนับจำนวนตัวอักษรที่เกิดซ้ำกันในชุดข้อมูลย่อยทั้ง 2 ชุด


โปรแกรมจะวนรอบเป็นจำนวนครั้ง เท่ากับ จำนวนชุดตัวอักษรย่อย Count(S) ลบด้วยค่า FNUM ในแต่ละรอบ โปรแกรมจะเริ่มต้นด้วยการให้ค่าเริ่มต้นตัวแปร S1 มีค่าสูงสุดซึ่งคือ 999 ถัดมาจะวนรอบเพื่อเทียบชุดตัวอักษรเป็นจำนวนครั้งเท่ากับค่า FNUM ในรอบเปรียบเทียบตัวอักษรนี้โปรแกรมจะเปรียบเทียบตัวอักษรทีละตัวเป็นจำนวนครั้งเท่ากับจำนวนตัวอักษรในชุดตัวอักษรนั้น หรือเมื่อพบตัวอักษรที่ต่างกันของ 2 ชุดตัวอักษร (บรรทัดที่ 5-8) ทุกครั้งที่พบตัวอักษรที่ต่างกัน โปรแกรมจะตรวจสอบค่า s1 กับตำแหน่งตัวอักษรที่เริ่มต่างกันนี้(บรรทัดที่ 6) ถ้าหากว่าตำแหน่งตัวอักษรนี้น้อยกว่าค่า s1 ก็จะ กำหนดให้ s1 เท่ากับตำแหน่งตัวอักษรนั้น ด้วยวิธีนี้เมื่อโปรแกรมทำงานผ่านไปครบจำนวน FNUM รอบ จะได้ค่า s1 เป็นค่าของจำนวนตัวอักษรของชุดตัวอักษรที่เกิดซ้ำกันในชุดตัวอักษรทั้ง FNUM ชุด ซึ่งถ้าหากว่าค่า s1 นี้ไม่น้อยกว่าค่า LNUM ที่กำหนดไว้โปรแกรมก็จะเลือกให้ตัวอักษรตัวที่ 1 ถึง s1 เป็นวลี(บรรทัดที่ 11)