ดัชนีเอฟเอ็ม

ดัชนีเอฟเอ็ม (FM-index) คือการนำเอาข้อความที่เกิดจากการสลับที่อย่างมีรูปแบบด้วย Burrows-Wheeler Transform (BWT) มาหาตำแหน่งของตัวอักษรที่เราต้องการ

ขั้นตอนการทำงาน

1.รับข้อมูลจากการสลับที่ของตัวอักษรจาก BWT ตัวอักษรที่ใส่เข้าไป เช่น abaaba จะได้ผลเป็น

 $abaaba a$abaab aaba$ab aba$aba abaaba$ ba$abaa baaba$a

2.ดูคอลัมน์แรกและคอลัมน์สุดท้ายเป็นหลัก ใช้ตัว $ ในการบอกตำแหน่ง

 0 $abaaba 6 $ 1 a$abaab 5 a$ 2 aaba$ab 2 aaba$ 3 aba$aba 3 aba$ 4 abaaba$ 0 abaaba$ 5 ba$abaa 4 ba$ 6 baaba$a 1 baaba$

3.ใส่ตัวอักษรที่ต้องการหาตำแหน่ง เช่น ตำแหน่งของ aba หาแถวที่ขึ้นต้นด้วยตัว a และมี b ต่อท้าย

 $abaaba → a$abaab← → aaba$ab← → aba$aba → abaaba$ ba$abaa baaba$a

4.ต้องการหาตำแหน่ง เช่น ตำแหน่งของ aba หาแถวที่ขึ้นต้นด้วยตัว ba และมี a ต่อท้าย

 $abaaba a$abaab aaba$ab aba$aba abaaba$ → ba$abaa← → baaba$a←

5.ตัดตำแหน่งอื่นออกจะเหลือตำแหน่งที่มีเฉพาะ aba อยู่ที่ [0,3]

 aba$aba 3 aba$ abaaba$ 0 abaaba$

ตัวอย่างการเขียนโปรแกรม

def FM_index(query):  def string_search (query, firstCol, bwtString,saArray,countTable,occTable):  hitSApositions = []  queryLength = len(query)  query = list(query)  initLetter = query.pop()  startOld = min(letter_range_in_string(initLetter,firstCol))  endOld = max(letter_range_in_string(initLetter,firstCol))  if queryLength ==1:  hitSApositions = letter_range_in_string(initLetter,firstCol)  else:  i = 2  while i <= queryLength:  letter = query.pop()  startOld = letter_LF(letter,startOld,bwtString,saArray,countTable,occTable)  endOld = letter_LF(letter,endOld,bwtString,saArray,countTable,occTable)  i+=1   hitSApositions= [startOld,endOld]   for i in range(len(hitSApositions)):  hitSApositions[i]=saArray[hitSApositions[i]]   return list(set(hitSApositions))   result = string_search(query, firstCol, bwtString,saArray,countTable,occTable)   return result 

อ้างอิง

1. http://nbviewer.jupyter.org/gist/BenLangmead/6860491 https://www.cs.jhu.edu/~langmea/resources/lecture_notes/bwt_and_fm_index.pdf https://www.youtube.com/watch?v=kvVGj5V65io https://gist.github.com/Puriney/6324227