Масив префіксів: Індексація кожного кінця рядка

Що таке префікс?

Префікс рядка – це все, що починається з певної позиції і йде до кінця рядка. Якщо рядок – «banana», то у нього є шість префіксів: banana, anana, nana, ana, na та a. Зверніть увагу, що сам повноцінний рядок також вважається префіксом, починаючи з позиції 0. Загалом, рядок довжиною n має рівно n префіксів, кожен з яких починається з можливої стартової позиції, включаючи порожній префікс, якщо його враховувати (хоча більшість реалізацій зупиняються перед цим). Це відрізняється від суфікса, який – це все, що починається з початку рядка до певної точки розриву, і ще відрізняється від випадкового підрядка, який може починатися та закінчуватися будь-де посередині. Ключова перевага префіксів полягає в тому, що будь-який підрядок оригінального тексту є префіксом лише одного суфікса – суфікса, який починається там же, де й підрядок. Отже, якщо ви хочете дізнатися, чи міститься у «banana» шаблон «ana», ви насправді запитуєте, чи є «ana» префіксом будь-якого з шести суфіксів «banana». Розглянемо перелічені вище суфікси: «ana» дійсно є префіксом суфікса «ana» та також є префіксом «anana». Це переосмислення – і є ключем до суфіксного масиву: замість пошуку в повному тексті за шаблоном, ми організовуємо всі суфікси так, щоб знаходження шаблону стало пошуком діапазону суфіксів, які його містять як префікс. Варто підкреслити, що ця техніка стосується одного рядка та його внутрішніх віддзеркалень – повторюваних фрагментів, симетричних закономірностей, а не колекції багатьох різних слів, як у структурі триєвого словника.

Побудова масиву: Найпростіший спосіб

Найбільш прямий шлях побудови суфіксного масиву – надзвичайно простий. По-перше, згенеруйте всі n суфіксів заданої рядка. По-друге, відсортуйте їх за допомогою звичайного алфавітного, або лексикографічного, порівняння. По-третє, записуйте лише початковий індекс кожного суфікса в цьому відсортованому порядку, відкидаючи фактичний текст суфікса, оскільки його завжди можна відновити з вихідного рядка плюс індекс. Для слова «banana», сортування шести суфіксів за алфавітним порядком дає: a, ana, anana, banana, na, nana, що відповідають початковим позиціям 5, 3, 1, 0, 4, 2. Ця послідовність позицій, 5, 3, 1, 0, 4, 2, є суфіксним масивом. Проблемою цього підходу є не ефективність. Порівняння двох суфіксів символ за символом може займати час пропорційний довжині рядка в найгіршому випадку, оскільки два суфікси можуть мати дуже довге спільне початок перед тим, як відрізнятися. З n суфіксами для сортування та загальним сортом порівняння, який потребує порядку n log n порівнянь, і кожен перевірка символів коштує до n символів, загальна робота становить порядок n квадратний log n у найгіршому випадку. Для короткого слова, як «banana», це миттєве, але для людського хромосоми з сотнями мільйонів основ або великої кількості документів, порядок n квадратний log n стає повністю непрактичним, потенційно вимагаючи більше часу, ніж вік Всесвіту. Цей наївний метод цінний для формування інтуїції та для малих прикладів, але будь-яке реальне розгортання, особливо в конвеєрах секвенування геному, які повинні індексувати цілі хромосоми, потребує фундаментально швидшої стратегії побудови.

Ефективне побудову масиву: подвоєння префіксів і нахил

Швидші алгоритми побудови суфіксного масиву уникають порівнювання суфіксів символ за символом з нуля кожного разу. Найпоширеніший підхід називається подвоєнням префіксів. Він працює в раундах. У першому раунді кожен суфікс ранжується лише на основі свого першого символу, використовуючи звичайний алфавітний порядок, тому ідентичні перші символи отримують один і той самий рейтинг. У другому раунді кожен суфікс ранжується за допомогою пари рейтингів: його власний поточний рейтинг плюс поточний рейтинг суфіксу, що починається на два символи пізніше, які разом ефективно узагальнюють перші два символи. В наступному раунді вікно порівняння подвоюється ще раз, до чотирьох символів, потім восьми, потім шістнадцять і так далі, завжди використовуючи рейтинги, обчислені в попередньому раунді, а не знову читаючи необроблене текстове джерело. Оскільки вікно подвоюється кожного разу, потрібно приблизно log n раундів, перш ніж кожен суфікс матиме унікальний рейтинг, і кожен раунд можна завершити за час порядку n log n, використовуючи ефективний сортувальний алгоритм, що дає загальний час побудови порядку n log n помножений на log n, що вже є значним покращенням порівняно з простим методом і може бути ще більше оптимізовано за допомогою технік радікс-сортування. Ще швидша родина алгоритмів, найвідомішим із яких є DC3 алгоритм (також відомий як нахилний алгоритм), досягає справжнього часу порядку n. Концептуально DC3 розділяє суфікси на групи на основі їх початкової позиції за модулем 3, рекурсивно сортує одну керовану групу за допомогою розумного зменшення до меншої версії тієї ж проблеми, а потім об'єднує залишки суфікси з результатів цього рекурсивного кроку. Деталі складні, але винагорода полягає в тому, що навіть суфіксні масиви для цілих геномів або великих текстових корпусів можна побудувати за час, приблизно пропорційний розміру вхідних даних, що пояснює, чому ці алгоритми лежать в основі реальної біоінформатики та інфраструктури пошуку.

Пошук за бінарний пошук

Після побудови та сортування масиву суфіксів пошук шаблону довжиною m у тексті довжиною n стає надзвичайно швидким. Оскільки суфікси розташовані в алфавітному порядку, всі суфікси, які починаються з даного шаблону, знаходяться разом у одному безперервному блоці масиву, так само як усі слова, що починаються з «cat», сидять разом на словнику. Це означає, що можна використовувати бінарний пошук, повторно перевіряючи середній суфікс зменшуваного діапазону та порівнюючи шаблон із його першими m символами, щоб знайти цей блок. Кожне порівняння під час бінарного пошуку коштує щонайбільше порядку m оглядів символів, оскільки вам потрібно лише розглянути перші m символи кандидата-суфікса, щоб побачити, чи відповідає шаблон як префікс. Бінарний пошук сам по собі потребує приблизно log n порівнянь, щоб звузити діапазон від n кандидатів до цільового діапазону. Множення цих величин разом дає загальний час пошуку порядку m log n, який майже не залежить від розміру навколишнього тексту, лише від довжини шуканого шаблону та логарифма довжини тексту. Два бінарних пошуки, один для знаходження найлівішого суфікса, що відповідає, і один для знаходження найправішого, розкривають не тільки те, чи існує шаблон, але й скільки разів він зустрічається та на яких позиціях, оскільки кожен суфікс у цьому зіставленому блоці відповідає одному випадку. Це величезний прогрес порівняно з прямим скануванням необробленого тексту, яке в найгіршому випадку займає час пропорційний повній довжині тексту, помноженій на довжину шаблону. Для пошуку короткого фрагмента ДНК проти цілого хромосоми або запиту пошуковика проти великої індексованої документації ця різниця визначає, чи завершиться пошук миттєво чи займе непрактично багато часу.

Масив LCP: Індексація кожного кінця рядка

Масив LCP чудово поєднується з супутньою структурою під назвою масив найдовших спільних префіксів (LCP), що означає ‘longest common prefix’. Кожен запис у масиві LCP фіксує, скільки літер поділяє два сусідніх суфікси в відсортованому порядку. Ця додаткова інформація прискорює пошуки, оскільки бінарний пошук може пропустити непотрібні порівняння символів, які вже було проведено, і безпосередньо відповідає на інші запитання. Найбільше значення має найдовше значення будь-де в масиві LCP, яке миттєво розкриває найдовший повторюваний фрагмент тексту, найдовшу частину, яка з'являється більше одного разу. Об’єднання двох рядків унікальним роздільником і подальше вивчення масиву LCP цього об’єднаного рядка дозволяє визначити найдовший спільний підрядок між двома початковими рядками, що використовується в детекції плагіату та порівнянні ДНК між видами. Зрозуміло, запитання виникає: як це співвідноситься з подібними структурами? Дерево суфіксів зберігає ту саму інформацію про суфікси, але у вигляді явного розгалуженого дерева, де спільні префікси стискаються в спільних шляхах від кореня; воно відповідає на багато з тих самих запитань і деякі більш складні запити так само швидко, але покажчики та внутрішні вузли зазвичай споживають помітно більше пам’яті, ніж прості масиви цілих чисел, які потребують суфіксний масив і масив LCP. Це справді корисна компромісна угода: суфіксні масиви жертвують деякою гнучкістю запитів та елегантністю побудови для меншого розміру пам’яті, що має велике значення при індексації геномів з мільярдами основ. Варто також чітко розрізняти це від триє, який цей сайт охоплює в іншому місці: триє зазвичай будується з багатьох окремих слів або ключів для підтримки пошуку префіксів у цілій колекції, тоді як суфіксний масив будується від усіх суфіксів одного рядка, розкриваючи внутрішню повторювану структуру всередині цього одного фрагменту тексту, а не зв’язки між багатьма різними записами.

Часті запитання

Спробуйте наживо

Усе, що вище, працює прямо у вашому браузері — відкрийте Suffix Array: Indexing Every Ending of a String і змінюйте параметри під час роботи. Нічого не встановлюється, нічого не завантажується на сервер, уся модель живе в одній вкладці.