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.[1] La literojn «FM» devenas de la priskribo «Plenateksta indekso en eta spaco» (Ŝablono:Lang-en),[2] 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».[3] Kiel kroma plibonigo, la alfabeto-amika FM-indekso, kombinas la uzon de kompatigo kaj de arboj Wavelet[4] signife malpliigas la uzadon de spaco por grandaj alfabetoj.
La FM-indekso estis adoptita, inter aliaj, en bioinformadiko.[5]
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.
|
Oni eblas fari kolumnan mapon lasta-al-unuan LF(i) de indekso i al indekso Ŝablono:Math, tiel ke Ŝablono:Math = Ŝablono:Math, kun la helpo de tablo Ŝablono:Math kaj funkcio Aperoj(c, k).
|
|
|
La mapado lasta-al-unuan povas nun esti priskribata kiel Ŝablono:Math. Ekzemple, en vico 9, Ŝablono:Math estas «Ŝablono:Math» kaj la sama troveblas en vico 5 en la unua kolumno de Ŝablono:Math, do Ŝablono:Math devus esti 5 kaj Ŝablono:Math. Por ĉiu vico Ŝablono:Math de la matrico, la karaktro en la lasta kolumno Ŝablono:Math venas antaŭ la karaktero en la unua kolumno Ŝablono:Math ankaŭ en T. Fine, se Ŝablono:Math, do Ŝablono:Math, kaj uzante la egalecon oni eblas akiri ĉenon de Ŝablono:Math el Ŝablono:Math. La FM-indekso mem estas kompaktigo de la ĉeno Ŝablono:Math kune kun Ŝablono:Math kaj Ŝablono:Math en kelka formo, kaj ankaŭ informacio kiu mapas elekton da indicoj en Ŝablono:Math al pozicioj en la originala ĉeno Ŝablono:Math. |
|
Kalkulu
La operacio kalkulu konsideras ŝablonon Ŝablono:Math kaj eligas la nombron de aperoj de tiu skemo en la originala teksto Ŝablono:Math. Ĉar la vicoj de la matrico Ŝablono:Math estas ordigitaj kaj ĝi enhavas ĉiun sufikson de Ŝablono:Math, la aperoj de la ŝablono Ŝablono:Math 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 Ŝablono:Math. Ĉi tiu intervalo super Ŝablono:Math reprezentas ĉiun karaktron de Ŝablono:Math kiu havas sufiksan komencante kun a.
- La sekvanta serĉenda karaktro estas «r». La nova intervalo estas Ŝablono:Math Ŝablono:Math Ŝablono:Math, se
komencoestas la indekso de la komenco de la intervalo kajfinoestas la fino. Ĉi tiu intervalo super Ŝablono:Math korespondas al ĉiuj karaktroj de Ŝablono:Math kiuj havas sufiksojn komencantaj kun ra. - La lasta serĉenda karaktro estas b. La nova intervalo estas Ŝablono:Math Ŝablono:Math Ŝablono:Math. Ĉi tiu intervalo super Ŝablono:Math 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 Ŝablono:Math. Ĉar Aperoj(c, k) povas esti elfarata en konstanta tempo, la kalkulo povas kompletiĝi en lineara tempo laŭ la longeco de la skemo: Ŝablono:Math tempo.
Trovu
La operacio nome trovu prenas kiel enigo indekson de karaktro en Ŝablono:Math kaj eligas ties pozicion Ŝablono:Math en Ŝablono:Math. 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 Ŝablono:Math al indekso en Ŝablono:Math, subaro da indeksoj en Ŝablono:Math estas asociitaj kun pozicio en Ŝablono:Math. Se Ŝablono:Math 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 Ŝablono:Math en teksto Ŝablono:Math en Ŝablono:Math tempo kun po bitoj por eniga simbolo por ajna Ŝablono:Math.[1]
Aplikoj
legado de mapo de DNA
La FM-indekso estis sukcese (>2000 citaĵoj) aplikita por aproksimi ĉenan serĉon/sinsekvan vicigon; vidu Bowtie Ŝablono:URL
Referencoj
- ↑ 1,0 1,1 1,2 Paolo Ferragina and Giovanni Manzini (2000). "Opportunistic Data Structures with Applications".Ŝablono:404 Proceedings of the 41st Annual Symposium on Foundations of Computer Science. p.390.
- ↑ Paolo Ferragina and Giovanni Manzini (2005). "Indexing Compressed Text". Journal of the ACM, 52, 4 (Jul. 2005). p. 553
- ↑ Ŝablono:Cite web
- ↑ P. Ferragina, G. Manzini, V. Mäkinen and G. Navarro. An Alphabet-Friendly FM-index. In Proc. SPIRE'04, pages 150-160. LNCS 3246.
- ↑ Ŝablono:Cite journal