FM-индекс

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

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

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

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

Предыстория [ править ]

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

Структура данных FM-индекса [ править ]

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

я	Ф		л
1	$	абракадабр	а
2	а	$абракадаб	р
3	а	бюстгальтер $ абрака	д
4	а	Бракадабра	$
5	а	Кадабра$AB	р
6	а	дабра$абра	с
7	б	Ра$абракад	а
8	б	ракадабра$	а
9	с	адабра$абр	а
10	д	абра$абрак	а
11	р	а$абракада	б
12	р	акадабра$а	б

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

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

C[c] — это таблица, в которой для каждого символа c в алфавите содержит количество вхождений в текст лексически меньших символов.
Функция Occ(c, k) — количество вхождений символа c в префиксе Л[1..к] . Феррагина и Манзини показали ^[1] что можно вычислить Occ(c, k) в постоянное время.

C[c] of " ард$rcaaaabb "
с	$	а	б	с	д	р
С[с]	0	1	6	8	9	10

Сопоставление «последний-первый» теперь можно определить как LF(i) = C[L[i]] + Occ(L[i], i) . Например, в строке 9: L это а и то же самое a можно найти в строке 5 первого столбца Ф , так что 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] и используя равенство можно извлечь строку Т из Л.

Сам FM-индекс представляет собой сжатие строки Л вместе с С и Occ в той или иной форме, а также информацию, которая отображает набор индексов в L в позиции в исходной строке Т.

Occ(c, k) из " ард$rcaaaabb "
	а	р	д	$	р	с	а	а	а	а	б	б
	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
с	0	0	0	0	0	1	1	1	1	1	1	1
д	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 отсортированы и содержат каждый суффикс T , появления шаблона P будут находиться рядом друг с другом в одном непрерывном диапазоне. Операция повторяется по шаблону в обратном направлении. Для каждого символа в шаблоне находится диапазон, в котором этот символ является суффиксом. Например, подсчет узора «бюстгальтер» в «абракадабре» выполняется следующим образом:

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

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

Найдите [ править ]

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

Чтобы отобразить индекс в L к одному в T , подмножество индексов в L связаны с положением в Т. Если L[j] имеет связанную с ним позицию, locate(j) тривиален. Если он не связан, за строкой следует LF(i) до тех пор, пока не будет найден связанный индекс. Связав подходящее количество индексов, можно найти верхнюю границу. Функция Locate может быть реализована для поиска вхождений шаблона. P[1.. p ] в тексте T[1.. u ] в $O(p + occ log е ты)$ время с $O\left(H_{k}(T)+{{\log \log u} \over {\log ^{\epsilon }u}}\right)$ бит на входной символ для любого $k \geq 0$ . ^[1]

Приложения [ править ]

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

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

См. также [ править ]

Ссылки [ править ]

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

[opportunistic_2000-1] Перейти обратно: ^а ^б ^с Паоло Феррагина и Джованни Манзини (2000). «Оппортунистические структуры данных с приложениями». Материалы 41-го ежегодного симпозиума по основам информатики. стр.390.

[2] Паоло Феррагина и Джованни Манзини (2005). «Индексирование сжатого текста». Журнал ACM, 52, 4 (июль 2005 г.). п. 553

[3] Феррагина, Паоло; Вентурини, Россано (сентябрь 2005 г.). «Fm-индекс версия 2» . www.di.unipi.it . Кафедра компьютерных наук, Пизанский университет, Италия . Проверено 15 августа 2018 г.

[FGMN04-4] П. Феррагина, Г. Манзини, В. Мякинен и Г. Наварро. FM-индекс, дружественный к алфавиту. В Proc. СПАЙР'04 , стр. 150-160. ЛНКС 3246.

[5] Симпсон, Джаред Т.; Дурбин, Ричард (15 июня 2010 г.). «Эффективное построение графа ассемблерной строки с использованием FM-индекса» . Биоинформатика . 26 (12): i367–i373. doi : 10.1093/биоинформатика/btq217 . ISSN 1367-4803 . ПМЦ 2881401 . ПМИД 20529929 .

[1]

[2]

[3]

[4]

[5]