FM-индекс - FM-index

В Информатика, FM-индекс сжатый полнотекстовый индекс подстроки на основе Преобразование Барроуза-Уиллера, с некоторым сходством с массив суффиксов. Его создали Паоло Феррагина и Джованни Манзини,^[1] которые описывают его как гибкую структуру данных, поскольку она позволяет сжимать входной текст, в то же время разрешая быстрые запросы подстроки. Название означает полнотекстовый индекс в минутах.^[2]

Его можно использовать для эффективного поиска количества вхождений шаблона в сжатый текст, а также для определения местоположения каждого вхождения. Время запроса, а также необходимое пространство для хранения, имеет сублинейная сложность относительно размера входных данных.

Первоначальные авторы усовершенствовали свой оригинальный подход и назвали его «FM-Index версии 2».^[3] Дальнейшее улучшение, удобный для алфавита FM-индекс, сочетает в себе использование усиления сжатия и вейвлет-деревья ^[4] чтобы значительно сократить занимаемое пространство для больших алфавитов.

FM-индекс нашел применение, среди прочего, в биоинформатика.^[5]

Фон

Использование индекса - распространенная стратегия эффективного поиска в большом объеме текста. Когда размер текста превышает размер, который разумно помещается в основной памяти компьютера, необходимо сжимать не только текст, но и индекс. Когда был введен FM-индекс, было несколько предложенных решений, которые основывались на традиционных методах сжатия и пытались решить проблему сопоставления сжатых данных. Напротив, FM-индекс - это сжатый самоиндекс, что означает, что он сжимает данные и индексирует их одновременно.

Структура данных FM-индекса

FM-индекс создается, сначала беря Преобразование Барроуза-Уиллера (BWT) введенного текста. Например, BWT строки Т = "abracadabra $" - это "ard $ rcaaaabb", и здесь он представлен матрицей M где каждая строка - это поворот текста, а строки отсортированы лексикографически. Преобразование соответствует последнему столбцу с меткой L.

я	F		L
1	$	абракадабр	а
2	а	$ abracadab	р
3	а	бюстгальтер $ abraca	d
4	а	бракадабра	$
5	а	кадабра $ ab	р
6	а	dabra $ abra	c
7	б	ra $ abracad	а
8	б	ракадабра $	а
9	c	адабра $ абр	а
10	d	abra $ abrac	а
11	р	a $ abracada	б
12	р	acadabra $ a	б

Сам по себе BWT допускает некоторое сжатие, например, двигаться вперед и Кодирование Хаффмана, но у преобразования есть еще больше применений. Строки в матрице по сути являются отсортированными суффиксами текста, а первый столбец F матрицы имеет сходство с массивы суффиксов. То, как массив суффиксов соотносится с BWT, лежит в основе FM-индекса.

Можно сделать сопоставление столбцов "последний-первый" LF (я) из индекса я к индексу j, так что F [j] = L [я], с помощью таблицы C [c] и функция Ок (c, k). C [c] таблица, в которой для каждого символа c в алфавите содержит количество вхождений в текст лексически меньших символов. Функция Ок (c, k) это количество вхождений символа c в префиксе L [1..k]. Феррагина и Манзини показали[1] что можно вычислить Ок (c, k) в постоянное время.

C [c] из "ard $ rcaaaabb" c $ а б c d р C [c] 0 1 6 8 9 10

Сопоставление "последний-первый-первый" теперь можно определить как LF (i) = C [L [i]] + Occ (L [i], i). Например, в строке 9 L является а и то же самое а можно найти в строке 5 в первом столбце F, так LF (9) должно быть 5 и LF (9) = C [a] + Occ (a, 9) = 5. Для любой строки я матрицы, символ в последнем столбце L [я] предшествует символу в первом столбце F [i] также в T. Наконец, если L [i] = T [k], тогда L [LF (i)] = T [k - 1], и используя равенство, можно извлечь строку Т из L. Сам FM-индекс - это сжатие строки L вместе с C и Ок в той или иной форме, а также информацию, которая отображает набор индексов в L на позиции в исходной строке Т.

Ок (c, k) из "ard $ rcaaaabb" а р d $ р c а а а а б б 1 2 3 4 5 6 7 8 9 10 11 12 $ 0 0 0 1 1 1 1 1 1 1 1 1 а 1 1 1 1 1 1 2 3 4 5 5 5 б 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 р 0 1 1 1 2 2 2 2 2 2 2 2

Считать

Операция считать берет образец P [1..p] и возвращает количество вхождений этого шаблона в исходный текст Т. Поскольку строки матрицы M отсортированы и содержат каждый суффикс Т, вхождения шаблона п будут рядом друг с другом в едином непрерывном диапазоне. Операция повторяется в обратном порядке по шаблону. Для каждого символа в шаблоне находится диапазон, в котором этот символ является суффиксом. Например, подсчет выкройки «бюстгальтер» в «абракадабре» выполняется следующим образом:

1. Первый символ, который мы ищем, это а, последний символ в шаблоне. Начальный диапазон установлен на [C [a] + 1..C [a + 1]] = [2..6]. Этот диапазон превышает L представляет каждого персонажа Т суффикс, начинающийся с а.
2. Следующий персонаж, который нужно искать, это р. Новый ассортимент [C [r] + Occ (r, start-1) + 1..C [r] + Occ (r, end)] = [10 + 0 + 1..10 + 2] = [11..12], если Начните - это индекс начала диапазона и конец это конец. Этот диапазон превышает L все персонажи Т суффиксы которых начинаются с ра.
3. Последний персонаж, на который стоит обратить внимание, это б. Новый ассортимент [C [b] + Occ (b, start-1) + 1..C [b] + Occ (b, end)] = [6 + 0 + 1..6 + 2] = [7..8]. Этот диапазон превышает L все символы, суффикс которых начинается с бюстгальтер. Теперь, когда весь шаблон обработан, количество совпадает с размером диапазона: 8 - 7 + 1 = 2.

Если диапазон становится пустым или границы диапазона пересекаются друг с другом до того, как был найден весь образец, образец не встречается в Т. Потому что Ок (c, k) может выполняться за постоянное время, счет может завершаться за линейное время по длине шаблона: О (п) время.

Найдите

Операция найти принимает в качестве входных данных индекс символа в L и возвращает свою позицию я в Т. Например найти (7) = 8. Чтобы найти каждое вхождение шаблона, сначала определяется диапазон символов, суффикс которого является шаблоном, так же, как считать эксплуатация нашла диапазон. Затем можно определить положение каждого символа в диапазоне.

Чтобы отобразить индекс в L одному в Т, подмножество индексов в L связаны с положением в Т. Если L [j] имеет позицию, связанную с ним, найти (j) тривиально. Если он не связан, за строкой следует LF (я) пока не будет найден связанный индекс. Сопоставив подходящее количество индексов, можно найти верхнюю границу. Найдите может быть реализован, чтобы найти ок. вхождения образца P [1..p] в тексте Т [1..u] в O (p + ок. бревно^ε u) время с ${displaystyle Oleft(H_{k}(T)+{{log log u} over {log ^{epsilon }u}}ight)}$ бит на входной символ для любого k ≥ 0.^[1]

Приложения

Картирование чтения ДНК

Индекс FM с обратным отслеживанием был успешно применен (> 2000 ссылок) для приблизительного сопоставления строк / выравнивания последовательностей, см. Bowtie http://bowtie-bio.sourceforge.net/index.shtml

Смотрите также

• Преобразование Барроуза – Уиллера
• Массив суффиксов
• Сжатый массив суффиксов
• Выравнивание последовательности
• Вейвлет-дерево

Рекомендации

1. Паоло Феррагина и Джованни Манзини (2000). «Оппортунистические структуры данных с приложениями». Материалы 41-го ежегодного симпозиума по основам компьютерных наук. стр.390.
2. Паоло Феррагина и Джованни Манзини (2005). «Индексирование сжатого текста». Журнал ACM, 52, 4 (июль 2005). п. 553
3. Феррагина, Паоло; Вентурини, Россано (сентябрь 2005 г.). «FM-индекс версия 2». www.di.unipi.it. Dipartimento di Informatica, Пизанский университет, Италия. Получено 2018-08-15.
4. П. Феррагина, Дж. Манзини, В. Мякинен и Г. Наварро. FM-указатель, удобный для алфавита. В Proc. SPIRE'04, страницы 150-160. LNCS 3246.
5. Симпсон, Джаред Т .; Дурбин, Ричард (15.06.2010). «Эффективное построение графа сборочной строки с использованием FM-индекса». Биоинформатика. 26 (12): i367 – i373. Дои:10.1093 / биоинформатика / btq217. ISSN  1367-4803. ЧВК  2881401. PMID  20529929.