FM-Index
In der Informatik ist ein FM-Index eine verlustfreie Komprimierung basierend auf der Burrows-Wheeler-Transformation mit einigen Ähnlichkeiten zur Tabelle der Suffixe . Diese Komprimierungsmethode wurde von Paolo Ferragina und Giovanni Manzini entwickelt, die sie als Mehrzweckalgorithmus beschreiben, der auf einer raffinierten Datenstruktur basiert. Der Name steht für „ F ull Textindex in M inute Raum “ .
Dieser Algorithmus kann zusätzlich zur Komprimierung verwendet werden, um die Anzahl der Vorkommen eines Musters in komprimiertem Text effizient zu ermitteln und die Position jedes Vorkommens des Musters in komprimiertem Text zu lokalisieren. Sowohl die Zeit als auch der erforderliche Speicherplatz sind im Vergleich zur Größe der Eingabedaten sublinear komplex. Das heißt, die erforderliche Ausführungszeit und der erforderliche Speicherplatz sind nicht proportional zur Größe der Eingabedaten.
Die Autoren entwickelten Verbesserungen an ihrem ursprünglichen Ansatz und nannten diese neue Komprimierungsmethode "FM-Index Version 2". Eine weitere Verbesserung, "alphabetfreundliches" FM, kombiniert die Verwendung von Kompressionsstimulation und Wavelets , um den Platzbedarf bei Verwendung großer Alphabete drastisch zu reduzieren.
Der FM-Index wurde unter anderem in der Bioinformatik verwendet .
Rahmen
Die Verwendung eines Index ist eine gängige Strategie zur effizienten Suche in einem großen Textkörper. Wenn der Text größer ist als der Hauptspeicher des Computers, muss nicht nur der Text, sondern auch der Index komprimiert werden. Bei der Einführung des FM-Index wurden bereits mehrere Lösungen vorgeschlagen, um dieses doppelte Ziel zu erreichen. Sie basierten auf traditionellen Komprimierungsmethoden, mit denen auch versucht wurde, das Problem der Indexkomprimierung zu lösen. Im Gegensatz dazu verwendet der FM-Index einen nativ komprimierten Index, was bedeutet, dass er gleichzeitig Daten komprimieren und indizieren kann.
FM-Indexstrukturen
Ein FM-Index wird erstellt, indem zuerst die Burrows-Wheeler-Transformation (BWT) des Eingabetextes durchgeführt wird. Zum Beispiel ist die BWT der Zeichenfolge T = "abracadabra" "ard $ rcaaaabb", und hier wird sie durch die Matrix M dargestellt, wobei jede Zeile eine Drehung des Textes ist und die Zeilen lexikographisch sortiert wurden. Die Transformation ist die letzte Spalte mit der Bezeichnung L .
| ich | F. | L. | |
|---|---|---|---|
| 1 | $ | Abrakadabr | beim |
| 2 | beim | $ Abrakadab | r |
| 3 | beim | BH $ Abraca | d |
| 4 | beim | Bracadabra | $ |
| 5 | beim | cadabra $ ab | r |
| 6 | beim | dabra $ abra | vs. |
| 7 | b | ra $ abracad | beim |
| 8 | b | racadabra $ | beim |
| 9 | vs. | adabra $ abr | beim |
| 10 | d | abra $ abrac | beim |
| 11 | r | ein $ Abrakada | b |
| 12 | r | acadabra $ a | b |
Die BWT selbst ermöglicht eine Kompression mit, beispielsweise nach vorne verlagert und Huffman - Codierung , aber die Umwandlung in anderen Verwendungen. Die Zeilen der Matrix sind im Grunde die sortierten Suffixe des Textes, und die erste Spalte F der Matrix weist Ähnlichkeiten mit der Tabelle der Suffixe auf . Diese Verknüpfung zwischen der Suffix-Tabelle und dem BWT ist das Herzstück des FM-Index.
|
Es ist möglich , mit Hilfe einer Tabelle C [c] eine Entsprechungstabelle zwischen der letzten und der ersten Spalte LF (i) von einem Index i zu einem Index j wie F [j] = L [i] zu erstellen. und "OCC (c, k) .
|
|
|
Die Entsprechungstabelle zwischen der letzten und der ersten Spalte kann nun definiert werden als LF (i) = C [L [i]] + Occ (L [i], i) . Zum Beispiel ist in Zeile 9 L 'a' und dasselbe 'a' in Zeile 5 in der ersten Spalte F , also sollte LF (9) 5 sein und LF (9) = C [a] + Occ (a 9) = 5 . Für jede Zeile i der Matrix steht das Zeichen in der letzten Spalte L [i] vor dem Zeichen in der ersten Spalte F [i], auch in T. Wenn schließlich L [i] = T [k] ist , dann ist L [LF (i)] = T [k - 1] , und unter Verwendung der Gleichheit ist es möglich, eine Zeichenkette T von L zu extrahieren . Der FM-Index selbst ist eine Komprimierung der L- Kette mit C und OCC , aber auch Informationen, die eine Auswahl von L-förmigen Indizes Positionen in der ursprünglichen T- Kette zuordnen . |
|
Anzahl
Die Betriebszählung nimmt ein Muster P [1..p] und gibt die Anzahl der Vorkommen des Musters in der ursprünglichen T . Da die Zeilen der Matrix M sortiert sind und jedes Suffix von T enthalten , werden die Vorkommen des Musters P in einem einzigen kontinuierlichen Bereich nebeneinander liegen. Dieser Vorgang wird auf dem Muster retrograd wiederholt. Für jedes Zeichen im Muster wird die Reihe von Zeilen gefunden, die dieses Zeichen als Suffix haben. Die Suche nach dem Muster "BH" in "Abrakadabra" erfolgt beispielsweise wie folgt:
- Das erste Zeichen, das wir suchen, ist ' a ', das letzte Zeichen im Muster. Der anfängliche Satz von Zeilen ist definiert als [C [a] + 1..C [a + 1] = [2..6] . Dieser Satz von Zeilen über L repräsentiert jedes Zeichen in T , dessen Suffix mit a beginnt .
- Das nächste zu suchende Zeichen ist r . Der neue Satz von Zeilen ist [C [r] + Occ (r, Start-1) + Occ (r, Ende), 1..C [r]] = [10 + 0 + 1..10 + 2] = [11..12] , wenn start der Startindex des Bereichs und end das Ende ist. Dieser Satz von Zeilen in L enthält alle Zeichen in T , deren Suffixe mit ra beginnen .
- Das letzte zu betrachtende Zeichen ist b . Der neue Satz von Zeilen ist [C [b] + Occ (b, Start-1) + 1..C [b] + Occ (b, Ende)] = [6 + 0 + 1..6 + 2] = [7..8] . Dieser Satz von Zeilen auf L besteht aus allen Zeichen, deren Suffix mit BH beginnt . Nachdem das gesamte Muster verarbeitet wurde, entspricht die Anzahl der Bereichsgröße: 8-7 + 1 = 2 .
Wenn der Bereich leer ist oder wenn sich die Grenzen des Liniensatzes kreuzen, bevor das gesamte Muster untersucht wird, bedeutet dies, dass das Muster in T nicht auftritt . Da OCC (c, k) in konstanter Zeit durchgeführt werden kann, kann die Zählung in linearer Zeit proportional zur Länge des Musters durchgeführt werden: Zeit von O (p) .
Lokalisieren
Der Betrieb Suche nimmt als Eingabe einen Index eines Zeichens in L und gibt seine Position i in T . Suchen Sie zum Beispiel (7) = 8 . Um alle Vorkommen eines Musters zu finden, müssen Sie zuerst den Zeichenbereich ermitteln, dessen Suffix das Muster ist, genauso wie bei der Zähloperation . Dann kann die Position jedes Zeichens im Bereich gefunden werden.
Um einen Index in L in einem Index in T abzubilden , wird eine Teilmenge der Indizes L einer Position in T zugeordnet . Wenn L [j] eine Position zugeordnet ist, ist es trivial , den Ort (j) zu finden . Wenn keine zugeordneten Positionen vorhanden sind, wird die Suche in der Zeichenfolge mit LF (i) fortgesetzt, bis ein zugeordneter Index gefunden wird. Durch die Zuordnung einer angemessenen Anzahl von Indizes findet man eine Obergrenze. Die Entdeckung Betrieb kann Vorkommen finden implementiert OCC P [1..p] in einem Text T [1..u] in O (p + OCC log ε u) Zeit mit Bits pro Eingabesymbol für jedes k ≥ 0 .
Anwendungen
DNA-Read-Mapping
FM-Index mit Feedback wurde erfolgreich (> 2000 Zitate) auf die Ausrichtung genomischer Sequenzen angewendet, siehe http://bowtie-bio.sourceforge.net/index.shtml p ...
Anmerkungen und Referenzen
- Paolo Ferragina und Giovanni Manzini (2000). "Opportunistische Datenstrukturen mit Anwendungen". Vorträge des 41. jährlichen Symposiums über Grundlagen der Informatik. p. 390 .
- Der Name bedeutet vielleicht auch Index von F erragina und M anzini?
- Paolo Ferragina und Giovanni Manzini (2005). Indizieren von komprimiertem Text, Journal of the ACM , 52, 4, (Jul. 2005). p. 553- .
- Paolo Ferragina und Rossano Venturini “FM-Index Version 2”
- P. Ferragina, G. Manzini, V. Mäkinen und G. Navarro. Ein alphabetfreundlicher FM-Index. In Proc. SPIRE'04, Seiten 150-160. LNCS 3246.
- Simpson, Jared T. und Durbin, Richard (2010). "Effiziente Erstellung eines Assembly-String-Diagramms unter Verwendung des FM-Index". Bioinformatics, 26, 12 (17. Juni). p. i367.