Vidi fonton por 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 (informadikisto)|Ĝovani Mandzini]], kiuj priskribis ĝin kiel oportunisma datumstrukturo ĉar ĝi permesas kompaktigi la enigan tekston kaj samtempe permesi solvi rapide subĉenajn serĉojn.<ref name="opportunistic_2000">Paolo Ferragina and Giovanni Manzini (2000). [http://eprints.adm.unipi.it/2028/1/TR-00-03.ps.gz "Opportunistic Data Structures with Applications".]{{404|date=September 2024 |bot=InternetArchiveBot |fix-attempted=yes }} Proceedings of the 41st Annual Symposium on Foundations of Computer Science. p.390.</ref> La literojn «FM» devenas de la priskribo «Plenateksta indekso en eta spaco» ({{Lang-en|Full-text index in Minute space}}),<ref>Paolo Ferragina and Giovanni Manzini (2005). [https://web.cs.ucdavis.edu/~gusfield/cs224f11/ferragina2005.pdf "Indexing Compressed Text".] Journal of the ACM, 52, 4 (Jul. 2005). p. 553</ref> 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 [[DSPACE|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».<ref>{{Cite web|url=http://pages.di.unipi.it/ferragina/Libraries/fmindexV2/index.html|title=Fm-index version 2|last=Ferragina|first=Paolo|last2=Venturini|first2=Rossano|date=September 2005|website=www.di.unipi.it|publisher=Dipartimento di Informatica, University of Pisa, Italy|access-date=2018-08-15}}</ref> Kiel kroma plibonigo, la alfabeto-amika FM-indekso, kombinas la uzon de kompatigo kaj de [[Wavelet Tree|arboj Wavelet]]<ref name="FGMN04">P. Ferragina, G. Manzini, V. Mäkinen and G. Navarro. An Alphabet-Friendly FM-index. ''In Proc. SPIRE'04'', pages 150-160. LNCS 3246.</ref> signife malpliigas la uzadon de spaco por grandaj alfabetoj.

La FM-indekso estis adoptita, inter aliaj, en [[bioinformadiko]].<ref>{{Cite journal|last=Simpson|first=Jared T.|last2=Durbin|first2=Richard|date=2010-06-15|title=Efficient construction of an assembly string graph using the FM-index|journal=Bioinformatics|volume=26|issue=12|pages=i367–i373|doi=10.1093/bioinformatics/btq217|issn=1367-4803|pmc=2881401|pmid=20529929}}</ref>

== 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 [[transformo de Burrows-Wheeler|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.
{| cellpadding="0" border="0" align="center"
!{{Math|I}}
!{{Math|F}}
!
!{{Math|L}}
|-
|1
|{{Mono|$}}
|{{Mono|abracadabr}}
|{{Mono|a}}
|-
|2
|{{Mono|a}}
|{{Mono|$abracadab}}
|{{Mono|r}}
|-
|3
|{{Mono|a}}
|{{Mono|bra$abraca}}
|{{Mono|d}}
|-
|4
|{{Mono|a}}
|{{Mono|bracadabra}}
|{{Mono|$}}
|-
|5
|{{Mono|a}}
|{{Mono|cadabra$ab}}
|{{Mono|r}}
|-
|6
|{{Mono|a}}
|{{Mono|dabra$abra}}
|{{Mono|c}}
|-
|7
|{{Mono|b}}
|{{Mono|ra$abracad}}
|{{Mono|a}}
|-
|8
|{{Mono|b}}
|{{Mono|racadabra$}}
|{{Mono|a}}
|-
|9
|{{Mono|c}}
|{{Mono|adabra$abr}}
|{{Mono|a}}
|-
|10
|{{Mono|d}}
|{{Mono|abra$abrac}}
|{{Mono|a}}
|-
|11
|{{Mono|r}}
|{{Mono|a$abracada}}
|{{Mono|b}}
|-
|12
|{{Mono|r}}
|{{Mono|acadabra$a}}
|{{Mono|b}}
|}
La BWT mem permesas iom da kompaktigo; ekzemple, per [[Movo al fronto|movo-al-fronto]] kaj per la [[Huffman-kodado|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 [[sufikstabelo|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 {{Math|j}}, tiel ke {{Math|F[j]}} = {{Math|L[i]}}, kun la helpo de tablo {{Math|C[c]}} kaj funkcio Aperoj(c, k).

* {{Math|C[c]}} estas tablo kiu, por ĉiu karaktro {{Math|c}} en la alfabeto, enhavas la nombron de aperoj en la teksto de [[karaktro]]j kiuj estas alfabete pli etaj.
* La funk{{Math|c}}io Aperoj(c, k) estas la nombro de aperoj de karaktro c en la prefikso L[1..K]. Feraĝina kaj Mandzini  montris,<ref name="opportunistic_2000" /> ke eblas komputi Aperoj(c, k) en konstanta tempo.
|
{| class="wikitable" style="text-align: center; float: right" border="1"
|+{{Math|C[c]}} of "ard$rcaaaabb"
!{{Math|c}}
|$
|
|B
|C
|D
|R
|-
!{{Math|C[c]}}
|0
|1
|6
|8
|9
|10
|}
|}
{| 
|
La mapado lasta-al-unuan povas nun esti priskribata kiel {{Math|LF(i) {{=}}<nowiki> C[L[i]] + Aperoj(L[i], i)</nowiki>}}. Ekzemple, en vico 9, {{Math|L}} estas «{{Math|a}}» kaj la sama troveblas en vico 5 en la unua kolumno de {{Math|F}}, do {{Math|LF(9)}} devus esti 5 kaj {{Math|LF(9) {{=}} C[a] + Aperoj(a, 9) {{=}} 5}}. Por ĉiu vico {{Math|i}} de la matrico, la karaktro en la lasta kolumno {{Math|L[i]}} venas antaŭ la karaktero en la unua kolumno {{Math|F[i]}} ankaŭ en T. Fine, se {{Math|L[i] {{=}} T[k]}}, do {{Math|L[LF(i)] {{=}} T[k - 1]}}, kaj uzante la egalecon oni eblas akiri ĉenon de {{Math|T}} el {{Math|L}}.

La FM-indekso mem estas kompaktigo de la ĉeno {{Math|L}} kune kun {{Math|C}} kaj {{Math|Occ}} en kelka formo, kaj ankaŭ informacio kiu mapas elekton da indicoj en {{Math|L}} al pozicioj en la originala ĉeno {{Math|T}}.
|
{| class="wikitable" style="text-align: center; float: right" border="1"
|+{{Math|Occ(c, k)}} of "ard$rcaaaabb"
!
!a
!r
!d
!$
!r
!c
!a
!a
!a
!a
!b
!b
|-
!
!1
!2
!3
!4
!5
!6
!7
!8
!9
!10
!11
!12
|-
!$
|0
|0
|0
|1
|1
|1
|1
|1
|1
|1
|1
|1
|-
!a
|1
|1
|1
|1
|1
|1
|2
|3
|4
|5
|5
|5
|-
!b
|0
|0
|0
|0
|0
|0
|0
|0
|0
|0
|1
|2
|-
!c
|0
|0
|0
|0
|0
|1
|1
|1
|1
|1
|1
|1
|-
!d
|0
|0
|1
|1
|1
|1
|1
|1
|1
|1
|1
|1
|-
!r
|0
|1
|1
|1
|2
|2
|2
|2
|2
|2
|2
|2
|}
|}

== Kalkulu ==
La operacio ''kalkulu'' konsideras ŝablonon {{Math|P[1..p]}} kaj eligas la nombron de aperoj de tiu skemo en la originala teksto {{Math|T}}. Ĉar la vicoj de la matrico {{Math|M}} estas ordigitaj kaj ĝi enhavas ĉiun sufikson de {{Math|T}}, la aperoj de la ŝablono {{Math|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 {{Math|<nowiki>[C[a] + 1..C[a+1]] </nowiki>{{=}} [2..6]}}. Ĉi tiu intervalo super {{Math|L}} reprezentas ĉiun karaktron de {{Math|T}} kiu havas sufiksan komencante kun ''a''.
# La sekvanta serĉenda karaktro estas «r». La nova intervalo estas {{Math|C[r] + Aperoj(r, komenco-1) + 1..C[r] + Aperoj(r, fino)] {{=}}}} {{Math|[10 + 0 + 1..10 + 2] {{=}}}} {{Math|[11..12]}}, se <code>komenco</code> estas la indekso de la komenco de la intervalo kaj <code>fino</code> estas la fino. Ĉi tiu intervalo super {{Math|L}} korespondas al ĉiuj karaktroj de {{Math|T}} kiuj havas sufiksojn komencantaj kun ''ra''.
# La lasta serĉenda karaktro estas ''b''. La nova intervalo estas {{Math|[C[b] + Aperoj(b, komenco-1) + 1..C[b] + Aperoj(b, fino)] {{=}}}} {{Math|[6 + 0 + 1..6 + 2] {{=}}}} {{Math|[7..8]}}. Ĉi tiu intervalo super {{Math|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 {{Math|T}}. Ĉar <code>Aperoj(c, k)</code> povas esti elfarata en konstanta tempo, la kalkulo povas kompletiĝi en lineara tempo laŭ la longeco de la skemo: {{Math|O(p)}} tempo.

== Trovu ==
La operacio nome ''trovu'' prenas kiel enigo indekson de karaktro en {{Math|L}} kaj eligas ties pozicion {{Math|i}} en {{Math|T}}. Ekzemple, <code>trovu(7) = 8</code>. 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 {{Math|L}} al indekso en {{Math|T}}, subaro da indeksoj en {{Math|L}} estas asociitaj kun pozicio en {{Math|T}}. Se {{Math|L[j]}} havas pozicion asociita kun ĝi, <code>trovu(j)</code> estas simplega. Se ĝi ne estas asociita, la ĉeno estas sekvita kun <code>LF(i)</code> ĝis rilata indekso estas trovita. Asociante taŭgan nombron de indeksoj, oni povas kalkuli supran limigon. ''Trovu'' povas trovi occ aperojn de ŝablono {{Math|P[1..p]}} en teksto {{Math|T[1..u]}} en {{Math|O(p + ''aperoj'' log<sup>&epsilon;</sup> u)}} tempo kun po <math>O \left(H_k(T) + {{\log\log u}\over{\log^\epsilon u}} \right)</math> bitoj por eniga simbolo por ajna {{Math|k &ge; 0}}.<ref name="opportunistic_2000" />

== Aplikoj ==

=== legado de mapo de DNA ===
La FM-indekso estis sukcese (>2000 citaĵoj) aplikita por aproksimi ĉenan serĉon/sinsekvan vicigon; vidu ''Bowtie'' {{URL|http://bowtie-bio.sourceforge.net/index.shtml}}

== Referencoj ==
{{referencoj}}

* {{tradukita|lingvo=en|artikolo=FM-index|revizio=1076478286}}

{{bibliotekoj}}
[[Kategorio:Ĉenaj datumstrukturoj]]