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» (angle Full-text index in Minute space),[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 redakti
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 redakti
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.
| I | F | L | |
|---|---|---|---|
| 1 | $ | abracadabr | a |
| 2 | a | $abracadab | r |
| 3 | a | bra$abraca | d |
| 4 | a | bracadabra | $ |
| 5 | a | cadabra$ab | r |
| 6 | a | dabra$abra | c |
| 7 | b | ra$abracad | a |
| 8 | b | racadabra$ | a |
| 9 | c | adabra$abr | a |
| 10 | d | abra$abrac | a |
| 11 | r | a$abracada | b |
| 12 | r | acadabra$a | b |
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 j, tiel ke F[j] = L[i], kun la helpo de tablo C[c] kaj funkcio Aperoj(c, k).
|
|
|
La mapado lasta-al-unuan povas nun esti priskribata kiel LF(i) = C[L[i]] + Aperoj(L[i], i). Ekzemple, en vico 9, L estas «a» kaj la sama troveblas en vico 5 en la unua kolumno de F, do LF(9) devus esti 5 kaj LF(9) = C[a] + Aperoj(a, 9) = 5. Por ĉiu vico i de la matrico, la karaktro en la lasta kolumno L[i] venas antaŭ la karaktero en la unua kolumno F[i] ankaŭ en T. Fine, se L[i] = T[k], do L[LF(i)] = T[k - 1], kaj uzante la egalecon oni eblas akiri ĉenon de T el L. La FM-indekso mem estas kompaktigo de la ĉeno L kune kun C kaj Occ en kelka formo, kaj ankaŭ informacio kiu mapas elekton da indicoj en L al pozicioj en la originala ĉeno T. |
|
Kalkulu redakti
La operacio kalkulu konsideras ŝablonon P[1..p] kaj eligas la nombron de aperoj de tiu skemo en la originala teksto T. Ĉar la vicoj de la matrico M estas ordigitaj kaj ĝi enhavas ĉiun sufikson de T, la aperoj de la ŝablono P 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 [C[a] + 1..C[a+1]] = [2..6]. Ĉi tiu intervalo super L reprezentas ĉiun karaktron de T kiu havas sufiksan komencante kun a.
- La sekvanta serĉenda karaktro estas «r». La nova intervalo estas C[r] + Aperoj(r, komenco-1) + 1..C[r] + Aperoj(r, fino)] = [10 + 0 + 1..10 + 2] = [11..12], se
komencoestas la indekso de la komenco de la intervalo kajfinoestas la fino. Ĉi tiu intervalo super L korespondas al ĉiuj karaktroj de T kiuj havas sufiksojn komencantaj kun ra. - La lasta serĉenda karaktro estas b. La nova intervalo estas [C[b] + Aperoj(b, komenco-1) + 1..C[b] + Aperoj(b, fino)] = [6 + 0 + 1..6 + 2] = [7..8]. Ĉi tiu intervalo super L 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 T. Ĉar Aperoj(c, k) povas esti elfarata en konstanta tempo, la kalkulo povas kompletiĝi en lineara tempo laŭ la longeco de la skemo: O(p) tempo.
Trovu redakti
La operacio nome trovu prenas kiel enigo indekson de karaktro en L kaj eligas ties pozicion i en T. 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 L al indekso en T, subaro da indeksoj en L estas asociitaj kun pozicio en T. Se L[j] 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 P[1..p] en teksto T[1..u] en O(p + aperoj logε u) tempo kun po bitoj por eniga simbolo por ajna k ≥ 0.[1]
Aplikoj redakti
legado de mapo de DNA redakti
La FM-indekso estis sukcese (>2000 citaĵoj) aplikita por aproksimi ĉenan serĉon/sinsekvan vicigon; vidu Bowtie bowtie-bio
Referencoj redakti
- ↑ 1,0 1,1 1,2 Paolo Ferragina and Giovanni Manzini (2000). "Opportunistic Data Structures with Applications". 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
- ↑ . Fm-index version 2. Dipartimento di Informatica, University of Pisa, Italy (September 2005). Alirita 2018-08-15.
- ↑ P. Ferragina, G. Manzini, V. Mäkinen and G. Navarro. An Alphabet-Friendly FM-index. In Proc. SPIRE'04, pages 150-160. LNCS 3246.
- ↑ (2010-06-15) “Efficient construction of an assembly string graph using the FM-index”, Bioinformatics 26 (12), p. i367–i373. doi:10.1093/bioinformatics/btq217.
- En tiu ĉi artikolo estas uzita traduko de teksto el la artikolo FM-index en la angla Vikipedio.