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. La literojn «FM» devenas de la priskribo «Plenateksta indekso en eta spaco» (), 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 Wavelet 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.

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.

|}

|}

## 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 O \left(H_k(T) + {{\log\log u}\over{\log^\epsilon u}} \right) 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