Войти
На компьютере наука, FM-индекс - это сжатый полнотекстовый индекс подстроки, основанный на преобразовании Барроуза-Уиллера, с некоторым сходством с массив суффиксов. Он был создан Паоло Феррагиной и Джованни Манзини, которые описывают его как гибкую структуру данных, поскольку она позволяет сжимать входной текст, но при этом позволяет выполнять быстрые запросы подстроки. Название расшифровывается как полнотекстовый индекс в минутном пространстве.
Его можно использовать для эффективного определения количества вхождений шаблона в сжатый текст, а также определения положения каждого вхождения. Время запроса, а также требуемое пространство для хранения имеют сублинейную сложность по отношению к размеру входных данных.
Первоначальные авторы усовершенствовали свой оригинальный подход и окрестили его «FM-Index версии 2». Дальнейшее улучшение, удобный для алфавита FM-индекс, сочетает в себе использование усиления сжатия и вейвлет-деревьев, чтобы значительно сократить использование пространства для больших алфавитов.
FM-индекс нашел применение, среди прочего, в биоинформатике.
Использование индекса - распространенная стратегия для эффективного поиска в большом объеме текста. Когда размер текста превышает размер, который разумно помещается в основной памяти компьютера, возникает необходимость сжимать не только текст, но и индекс. Когда был введен FM-индекс, было предложено несколько решений, которые основывались на традиционных методах сжатия и пытались решить проблему сопоставления сжатых данных. Напротив, FM-индекс - это сжатый самоиндекс, что означает, что он сжимает данные и индексирует их одновременно.
FM-индекс создается путем первого принятия преобразования Барроуза-Уиллера (BWT) входного текста. Например, BWT строки T = "abracadabra $" - это "ard $ rcaaaabb", и здесь он представлен матрицей M, где каждая строка представляет собой поворот текста, а строки были отсортированы лексикографически. Преобразование соответствует последнему столбцу 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 |
Сам по себе BWT допускает некоторое сжатие, например, с перемещением вперед и кодировка Хаффмана, но преобразование имеет еще больше применений. Строки в матрице - это, по сути, отсортированные суффиксы текста, а первый столбец F матрицы имеет сходство с массивами суффиксов . То, как массив суффиксов соотносится с BWT, лежит в основе FM-индекса.
Можно сделать отображение LF (i) столбца "последний-первый" из индекса i в индекс j, такое, что F [j] = L [i], с помощью таблицы C [c ] и функцию Occ (c, k).
|
|
Последнее - преобразование в первое теперь можно определить как LF (i) = C [L [i]] + Occ (L [i], i). Например, в строке 9 L - это a, и такое же значение a можно найти в строке 5 в первом столбце F, поэтому LF (9) должно быть 5, а LF (9) = C [a] + Occ (a, 9) = 5. Для любой строки i матрицы символ в последнем столбце L [i] предшествует символу в первом столбце F [i] также в T. Наконец, если L [i] = T [k], тогда L [LF (i)] = T [k - 1], и, используя равенство, можно извлечь строку T из L. Сам FM-индекс является сжатием строки L вместе с C и Occ в некоторой форме, а также информация, которая отображает выбор индексов в L в позиции в исходной строке T. |
|
Счетчик операций принимает шаблон P [1..p] и возвращает количество вхождений этого шаблона в исходный текст T. Поскольку строки матрицы M отсортированы, и он содержит каждый суффикс из T, вхождения шаблона P будут рядом друг с другом в одном непрерывном диапазоне. Операция повторяется в обратном порядке по шаблону. Для каждого символа в шаблоне находится диапазон, в котором этот символ является суффиксом. Например, подсчет паттерна «бюстгальтер» в «абракадабре» выполняется следующим образом:
Если диапазон становится пустым или границы диапазона пересекаются друг с другом до того, как весь шаблон будет обработан После поиска шаблон не встречается в T. Поскольку Occ (c, k) может выполняться за постоянное время, счет может завершаться за линейное время по длине шаблона: время O (p).
Операция locate принимает в качестве входных данных индекс символа в L и возвращает его позицию i в T. Например, locate (7) = 8. Чтобы найти каждое вхождение шаблона, сначала определяется диапазон символов, суффикс которого является шаблоном, точно так же, как операция подсчета нашла диапазон. Затем можно определить положение каждого символа в диапазоне.
Чтобы отобразить индекс в L на один в T, подмножество индексов в L связано с позицией в T. Если L [j] имеет связанную с ним позицию, locate (j) тривиально. Если он не связан, за строкой следует LF (i), пока не будет найден связанный индекс. Сопоставив подходящее количество индексов, можно найти верхнюю границу. Функция Locate может быть реализована для поиска вхождений шаблона P [1..p] в тексте T [1..u] за время O (p + occ log u) с 
Индекс FM с обратным отслеживанием успешно (>2000 цитирований) применяется для приблизительного сопоставления строк / выравнивания последовательностей, см. Bowtie http://bowtie-bio.sourceforge.net/index.shtml
