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

ดัชนีเอฟเอ็ม (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.ใส่ตัวอักษรที่ต้องการหาตำแหน่ง
	เช่น ตำแหน่งของ ab	
		หาแถวที่ขึ้นต้นด้วยตัว a และมี b ต่อท้าย
      $abaaba
  → a$abaab←
  → aaba$ab←
  → aba$aba
  → abaaba$
      ba$abaa
      baaba$a

4.ต้องการหาตำแหน่ง 
	เช่น ตำแหน่งของ a	
		หาแถวที่ขึ้นต้นด้วยตัว ba และมี a ต่อท้าย
     $abaaba
     a$abaab
     aaba$ab
     aba$aba
     abaaba$
 → ba$abaa←
 → baaba$a←

5.ตัดตำแหน่งอื่นออกจะเหลือตำแหน่งที่มีเฉพาะ  อยู่ที่ [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

อ้างอิง
  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