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

ดัชนีเอฟเอ็ม (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]

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