Сжатый массив суффиксов

• Основы сжатых массивов суффиксов

  • Сжатые массивы суффиксов — это структура данных для сопоставления с образцом в информатике. 
  • Они улучшают работу с суффиксными массивами, обеспечивая быстрый поиск строк с небольшим индексом. 

• Поиск в тексте

  • Сжатые массивы суффиксов поддерживают поиск произвольных шаблонов в тексте, время поиска обычно O(m) или O(m + log(n)). 
  • Используемое пространство обычно пропорционально энтропии текста K-го порядка и составляет O(nH 
  • k 
  • (T)) + o(n). 

• Создание и эффективность

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

• Практическое использование

  • Сжатые массивы суффиксов эффективны в использовании памяти и обеспечивают быстрое сопоставление на месте. 
  • Они могут быть адаптированы для использования во внешней памяти с помощью геометрической двойственности и блочного доступа. 

• Реализации и рекомендации

  • Существуют открытые реализации сжатых массивов суффиксов, включая Bowtie и Bowtie2 для биоинформатики, SDSL для множества структур данных и FEMTO для внешней памяти. 
  • Ссылки на дополнительные ресурсы и реализации доступны на веб-сайте Pizza & Chili.