FM-indekso

En informadiko, la FM-indekso estas kompaktiga plenteksta subĉena indekso bazata sur la transformo de Burrows–Wheeler, kun kelkaj similecoj al la sufiksa tabelo. Ĝin kreis Paolo Feraĝina kaj Ĝovani Mandzini, kiuj priskribis ĝin kiel oportunisma datumstrukturo ĉar ĝi permesas kompaktigi la enigan tekston kaj samtempe permesi solvi rapide subĉenajn serĉojn.Paolo Ferragina and Giovanni Manzini (2000). "Opportunistic Data Structures with Applications". Proceedings of the 41st Annual Symposium on Foundations of Computer Science. p.390. La literojn «FM» devenas de la priskribo «Plenateksta indekso en eta spaco» (),Paolo Ferragina and Giovanni Manzini (2005). "Indexing Compressed Text". Journal of the ACM, 52, 4 (Jul. 2005). p. 553 sed ankaŭ reprezentas la inicialojn de la du aŭtoroj.

Oni povas ĝin uzi por efike trovi la nombron de aperoj de ŝablono ene de la kunpremita teksto, tiel kiel trovi la pozicion de ĉiu apero. La tempo por la kompletigo, tiel kiel la postulata spaco sur disko, havas sublineara komplekseco laŭ la grando de la eniga datumo.

La originalaj aŭtoroj elpensis plibonigojn kompare al la originala dezajno kaj nomis ĝin «FM-Indekso versio 2». Kiel kroma plibonigo, la alfabeto-amika FM-indekso, kombinas la uzon de kompatigo kaj de arboj WaveletP. Ferragina, G. Manzini, V. Mäkinen and G. Navarro. An Alphabet-Friendly FM-index. In Proc. SPIRE'04, pages 150-160. LNCS 3246. signife malpliigas la uzadon de spaco por grandaj alfabetoj.

La FM-indekso estis adoptita, inter aliaj, en bioinformadiko.

 Enkonduko 
Uzante indekson estas ofta strategio por efike serĉi grandan korpon de teksto. Ĉiufoje kiam la teksto estas pli granda ol kio akcepteble konvenas enteni ene de ĉefa memoro de komputilo, oni bezonas kompaktigi ne nur la tekston sed ankaŭ la indekson. Kiam la FM-indekso ekaperis, en la scienca literatura oni jam proponis plurajn solvojn kiuj estis bazitaj sur tradiciaj kompaktigaj metodoj. Kontraste, la FM-indekso estas  kompaktiga mem-indekso, kiu signifas, ke ĝi kompaktigas la datumojn kaj indeksas ilin samtempe.

 Strukturo de la FM-indekso 
Oni kreas FM-indekson prenante la transformon de Burrows–Wheeler (BWT) de la eniga teksto. Ekzemple, la BWT de la ĉeno T = "abracadabra$" estas "ard$rcaaaabb", kaj ĉi tie ĝi estas reprezentata de la matrico M kie ĉiu vico estas rotacio de la teksto; La vicoj estas ordigitaj laŭ la alfabeta ordo. La transformo respondas al la lasta kolumno kun etikedo L.
123456789101112
La BWT mem permesas iom da kompaktigo; ekzemple, per movo-al-fronto kaj per la kodo de Huffman, sed la transformo havas eĉ pli da uzoj. La vicoj en la matrico estas esence la ordigitaj sufiksoj de la teksto kaj la unua kolumno F el la matrico dividas similecojn kun sufiksaj tabeloj. La rilato inter la sufiksa tabelo kaj la BWT estas la koro de la FM-indekso.
Oni eblas fari kolumnan mapon lasta-al-unuan LF(i) de indekso i al indekso , tiel ke  = , kun la helpo de tablo  kaj funkcio Aperoj(c, k).

  estas tablo kiu, por ĉiu karaktro  en la alfabeto, enhavas la nombron de aperoj en la teksto de karaktroj kiuj estas alfabete pli etaj.
 La funkio Aperoj(c, k) estas la nombro de aperoj de karaktro c en la prefikso L[1..K]. Feraĝina kaj Mandzini  montris, ke eblas komputi Aperoj(c, k) en konstanta tempo.+ of "ard$rcaaaabb"$BCDR0168910
La mapado lasta-al-unuan povas nun esti priskribata kiel . Ekzemple, en vico 9,  estas «» kaj la sama troveblas en vico 5 en la unua kolumno de , do  devus esti 5 kaj . Por ĉiu vico  de la matrico, la karaktro en la lasta kolumno  venas antaŭ la karaktero en la unua kolumno  ankaŭ en T. Fine, se , do , kaj uzante la egalecon oni eblas akiri ĉenon de  el .

La FM-indekso mem estas kompaktigo de la ĉeno  kune kun  kaj  en kelka formo, kaj ankaŭ informacio kiu mapas elekton da indicoj en  al pozicioj en la originala ĉeno .+ of "ard$rcaaaabb"ard$rcaaaabb123456789101112$000111111111a111111234555b000000000012c000001111111d001111111111r011122222222

 Kalkulu 
La operacio kalkulu konsideras ŝablonon  kaj eligas la nombron de aperoj de tiu skemo en la originala teksto . Ĉar la vicoj de la matrico  estas ordigitaj kaj ĝi enhavas ĉiun sufikson de , la aperoj de la ŝablono  estos ĉiu apud la alia en ununura kontinua intervalo. La operacio ripetiĝas iteracie super la ŝablono. Por ĉiu karaktro en la skemo, oni trovas la intervalon kiu enhavas la karaktron kiel sufikso. Ekzemple, por kalkuli la nombro de aperoj de bra ene de abracadabra, oni procedas kiel jenas:

 Oni unue serĉas la karaktron a, t.e., la lasta karaktro de la ŝablono. La komenca intervalo estas agordata kiel . Ĉi tiu intervalo super  reprezentas ĉiun karaktron de  kiu havas sufiksan komencante kun a.
 La sekvanta serĉenda karaktro estas «r». La nova intervalo estas   , se komenco estas la indekso de la komenco de la intervalo kaj fino estas la fino. Ĉi tiu intervalo super  korespondas al ĉiuj karaktroj de  kiuj havas sufiksojn komencantaj kun ra.
 La lasta serĉenda karaktro estas b. La nova intervalo estas   . Ĉi tiu intervalo super  korespondas al ĉiuj karaktroj kiuj havas sufikson komencanta kun bra. Post pasi super la tuta ŝablono, oni povas diri, ke la kalkula samas al la dimensio de la intervalo, t.e., 8 - 7 + 1 = 2.

Se la intervalo iĝas malplena aŭ la intervalaj limoj transiras ĉiun la alian antaŭ ol la tuta ŝablono estas kontrolata, tio signifas, ke la ŝablono nenie okazas en . Ĉar Aperoj(c, k) povas esti elfarata en konstanta tempo, la kalkulo povas kompletiĝi en lineara tempo laŭ la longeco de la skemo:  tempo.

 Trovu 
La operacio nome trovu prenas kiel enigo indekson de karaktro en  kaj eligas ties pozicion  en . Ekzemple, trovu(7) = 8. Por eltrovi ĉiun aperon de ŝablono, unue la intervalo de karaktro estas trovenda kies sufikso estas la ŝablono en la sama maniero laŭ kiu la operacio kalkulu trovas la intervalon. Tiam, eblas trovi la pozicion de ĉiu karaktro en la intervalo.

Por mapi indekson en  al indekso en , subaro da indeksoj en  estas asociitaj kun pozicio en . Se  havas pozicion asociita kun ĝi, trovu(j) estas simplega. Se ĝi ne estas asociita, la ĉeno estas sekvita kun LF(i) ĝis rilata indekso estas trovita. Asociante taŭgan nombron de indeksoj, oni povas kalkuli supran limigon. Trovu povas trovi occ aperojn de ŝablono  en teksto  en  tempo kun po  bitoj por eniga simbolo por ajna .

 Aplikoj 

 legado de mapo de DNA 
La FM-indekso estis sukcese (>2000 citaĵoj) aplikita por aproksimi ĉenan serĉon/sinsekvan vicigon; vidu Bowtie 

 Referencoj 



Kategorio:Ĉenaj datumstrukturoj