FM-индекс

• Основы FM-индекса

  • FM-индекс — это сжатый полнотекстовый индекс, основанный на преобразовании Берроуза-Уилера. 
  • Создан Паоло Феррагиной и Джованни Манзини для эффективного сжатия и запросов подстрок. 

• Структура данных и операции

  • FM-индекс создается путем преобразования текста с помощью BWT, что позволяет эффективно сжимать и индексировать данные. 
  • Строки матрицы M представляют собой отсортированные суффиксы текста, а первый столбец F имеет сходство с массивами суффиксов. 
  • Отображение от последнего к первому позволяет сопоставлять индексы в L с позициями в исходной строке T. 

• Функции FM-индекса

  • Счетчик операций подсчитывает количество повторений шаблона в тексте. 
  • Операция locate находит позицию символа в тексте по индексу в L. 

• Приложения FM-индекса

  • Используется в биоинформатике для сопоставления строк и выравнивания последовательностей. 
  • Имеет более 2000 ссылок на применение в различных областях. 

• Дополнительные ресурсы

  • Ссылки на трансформацию Берроуза-Уилера, массив суффиксов, сжатый массив суффиксов, выравнивание последовательностей и вейвлет-деревья.