Вейвлет Дерево

Рекурсивне розбиття алфавіту

Дерево хвиль (вейвлета) будується з послідовності S довжиною n над алфавітом розмірності сигма, зазвичай після відображення символів у послідовні цілі числа від 0 до сигма мінус 1. Будівництво починається з кореня з повною послідовністю та повним діапазоном алфавітів. На кожному вузлі діапазон алфавітів, який зараз призначено цьому вузлу, ділиться на нижню та верхню половини, зазвичай якомога рівніше, щоб дерево залишалося збалансованим. Для кожного положення в послідовності алгоритм перевіряє, до якої половини належить символ на цій позиції, і додає 0 або 1 у бітовий вектор у тому ж порядку зліва направо, як сама послідовність. Після побудови бітового вектора позиції розділяються за значенням бітів: всі позиції з нульовим значенням збираються, зберігаючи відносний порядок, в послідовність, яка стає вхідними даними лівого дитини, і всі позиції з одиничним значенням аналогічно формують вхідні дані правої дитини. Важливо зазначити, що цей крок розділення не потрібно зберігати явно під час запиту, оскільки операція ранжування бітового вектора може на вимогу відновити відображення між позиціями батьків і дітей. Ліва дитина рекурсивно обробляє свою половину алфавіту та утворений підпослідовність, а права дитина робить те ж саме, доки діапазон алфавітів вузла не містить лише один символ. Цей вузол є листком і йому не потрібен бітовий вектор, оскільки кожне положення, що досягає його, вже має цей символ. Глибина рекурсії обмежена стеленим логарифмом за основою 2 від сигми, оскільки на кожному рівні алфавітний діапазон ділиться навпіл. Оскільки кожне початкове положення вносить точно один біт на кожному рівні, через який воно проходить, і проходить через один вузол на рівні, загальна кількість збережених бітів у всіх бітових векторах у дереві становить n разів висоту дерева, яка дорівнює порядку n log sigma. Це вже близьке до початкової інформаційної місткості будь-якої послідовності над цим алфавітом, а з використанням бітових векторів з урахуванням ентропії простір може ще більше зменшитися до нульового порядку емпіричної ентропії S, що зазвичай значно менше, ніж log sigma, коли частоти символів відхилені.

Короткі вектори бітів: двигун під ним

Галузи гарантії базуються виключно на векторах бітів. У кожному вузлі дерева хвильових хвиль використовуються короткі вектори бітів, які забезпечують ефективний ранжування та відбір. Саме тут термін «короткий» заслужив свою назву. Простий вектор бітів, що зберігається як масив простих біт, може відповідати на запити доступу — тобто читати біт у позиції i — постійним часом, але обчислення ранжування — кількість одиничних бітів серед перших i позицій — вимагає сканування до i бітів, а відбір — знаходження позиції k-го одиничного біта — ще повільніше. Структури короткого ранжування та відбору вирішують цю проблему, створюючи додатковий індекс на основі невеликих індексів: класичний підхід розділяє вектор бітів на блоки та суперблоки, попередньо обчислюючи кумулятивні підрахунки одиниць на межах блоків і використовуючи швидкі інструкції з підрахунку одиниць апаратного забезпечення або невеликі попередньо обчислені таблиці пошуку для завершення підрахунку в блоці. Ключовим досягненням цих структур є те, що допоміжний індекс займає лише порядок n над log n або іноді порядок n log log n над log n бітів поверх вектора бітів, що асимптотично незначний порівняно з самим вектором бітів, часто описується як o від n додаткових біт, фактично безкоштовний простір для запитів постійного часу. Відбір здійснюється або за допомогою аналогічної структури, або, більш поширено на практиці, за допомогою бінарного пошуку над індексом ранжування, комбінованого з локальним скануванням, що забезпечує логарифмічний або майже постійний час залежно від використаної варіації. Кожен окремий вектор бітів всередині дерева хвильових хвиль на кожному рівні рекурсії є однією з цих структур короткого ранжування та відбору, а не простим масивом. Це деталі, які легко пропустити, але є причиною того, як працює дерево хвильових хвиль: без ефективної підтримки коротких бітів у кожному вузлі, запит ранжування до загальної послідовності деградує до лінійного сканування на кожному рівні, руйнуючи логарифмічний часовий діапазон, який розроблено для цієї структури. Оскільки навантаження на рівень підпорядковане підлога, загальне дерево хвильових хвиль одночасно успадковує майже межу простору ентропії та швидкий часовий діапазон.

Відповідь: доступ, ранжування та вибір

Цей ефект пояснює, як працюють вейвлет-дерева. Вони використовують рекурсивний шаблон для обчислення трьох основних запитів: доступ (access), ранжування (rank) та вибір (select). Кожен з цих запитів починається з кореня дерева і рухається вниз до листка, використовуючи бітові операції на кожному рівні. Запит «доступ» (access) визначає символ у позиції i в початковій послідовності. Він робить це, перевіряючи відповідний біт у бітовому векторі кореня. Якщо біт дорівнює 0, запит рекурсивно викликається для лівого піддерева на позиції, визначеній рангом 0 до i в бітовому векторі кореня. Якщо біт дорівнює 1, запит рекурсивно викликається для правого піддерева. Цей процес повторюється, поки не буде досягнутий листок, який містить відповідь. Запит «ранжування» (rank) визначає, скільки разів символ c зустрічається серед перших i позицій послідовності. Він також використовує рекурсивний шаблон, але замість того, щоб визначати символ, він обчислює кількість входжень символу c, використовуючи рангові операції на кожному рівні. Запит «вибір» (select) визначає позицію k-го входоження символу c у послідовності. Він починається з листка для c і рухається до кореня, використовуючи операції вибору на кожному рівні, щоб перевести позицію в піддереві назад у позицію в батьківському піддереві. Усі три запити потребують логарифмічного часу щодо довжини послідовності, незалежно від її розміру, оскільки кожен запит виконується за константною або майже константною часом.

Дерева Вейвлетів у FM-індексі для пошуку геному

Дерева вейвлетів мають значні застосування, зокрема всередині FM-індексу – стислого індексу повного тексту, який широко використовується в біоінформаційних інструментах, таких як BWA та Bowtie для вирівнювання коротких послідовностей ДНК проти посилання геному. FM-індекс побудований на основі перетворення Бюрроу-Вілер, зворотного перестановки тексту, яка схильна групувати схожі контексти разом, що робить трансформований рядок більш стислим, ніж оригінальний. Основне запитання, на яке покладається FM-індекс, називається зворотним пошуком, і його внутрішній цикл повторно потребує підрахунку кількості входжень символу в префіксах рядка BWT, що є точним запитом рангу, який будуть виконувати дерева вейвлетів. Зберігання рядка BWT як простого масиву дозволило б постійний доступ, але лінійний час рангу, що зробило б внутрішній цикл занадто повільним для геномних текстів, що містять мільярди основ. Збереження BWT у вигляді дерева вейвлетів надає логарифмічний час рангу для будь-якого символу алфавіту, і оскільки ДНК використовує невеликий алфавіт з чотирьох основ, скоригований на кілька додаткових символів для wildcard та sentinel, ефективний час запиту надзвичайно швидкий у практиці, часто лише два або три обчислення рангу глибоко. Зворотний пошук розширює зіположену модель одного символу з кінця, на кожному кроці використовуючи два запити рангу на вейвлет-дерево-закодованому BWT для зменшення інтервалу, що представляє всі суфікси тексту, починаючи з зіположені моделі. Після обробки всього запиту шаблону ширина кінцевого інтервалу безпосередньо дає кількість входжень цього шаблону в геномі, відповідь без розпакування однієї основи оригінальної послідовності. Розташування фактичних геномних позицій збігів також використовує операції вибору, поєднані зі зразковим суфіксним масивом, але сам крок підрахунку, який більшість інструментів вирівнювання використовують для швидкого відхилення або підтвердження кандидатів на відповідність, виконується повністю за запитами рангу до дерева вейвлетів. Оскільки дерево вейвлетів одночасно стискає BWT до його ентропії та підтримує ці запити швидко, вказівки геному масштабу на кілька гігабайт пам'яті замість десятків гігабайт, які потребував би наївний представлення.

Будівництво дерева хвиль

Побудова дерева хвиль на папері, рівень за рівнем з використанням явного проходу для розділення символів у кожному вузлі, займає час порядку O(n log σ), де σ - кількість різних символів, і приблизно таку ж кількість робочого простору, що є достатнім для багатьох застосунків, але може стати вузьким місцем для дуже великих текстів, таких як цілі геноми або великі текстові корпуси. Існують швидші алгоритми побудови, які будують усі бітові вектори певного рівня в один лінійний прохід по вихідній послідовності, використовуючи той факт, що шлях символу через дерево повністю визначається його бітовим представленням, і деякі методи побудови з використанням зовнішньої пам'яті або паралельної побудови зменшують пікове використання пам’яті ще більше, що важливо, коли вхідні дані самі по собі є кількома гігабайтами. Збалансовані за алфавітом дерева хвиль, іноді звані деревами хвиль із чіткою бінарною структурою дерева, розділяють діапазон алфавітів рівномірно на кожному вузлі незалежно від частоти символів, що є простим і забезпечує висоту в межах від стелі log₂σ, де σ - кількість різних символів. Альтернатива, дерево Хеффа, замість цього будує дерево відповідно до коду Хаффмана, отриманого з частот символів, тому загальні символи сидять близько до кореня з короткими кодами та рідкісні символи сидять глибше з довгими кодами; це зміщує використання простору від порядку O(n log σ) бітів до емпіричного нульового порядку ентропії послідовності, на шкоду втраті узгодженого обмеження log σ на час запиту, оскільки деякі запити стають повільнішими, ніж інші залежно від частоти символів. Ще одна варіація, матриця хвиль, підтримує фіксовану кількість рівнів, що дорівнює бітовому довжині алфавіту, але переставляє групування позицій на кожному рівні за допомогою стабільного розділення за значенням біта по всьому рівню замість кожного вузла, що спрощує реалізацію, покращує кешування та часто є бажаним форматуванням у сучасних бібліотеках лаконічних структур даних. У всіх цих варіантах основний контракт залишається незмінним: замінити послідовність на дерево ранжування та вибору бітових векторів і, в обмін, отримати доступ, ранжувати та обирати все приблизно за логарифмічний час у просторі, близькому до вмісту власної послідовності.”]}**”**

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

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

Усе, що вище, працює прямо у вашому браузері — відкрийте Wavelet Tree і змінюйте параметри під час роботи. Нічого не встановлюється, нічого не завантажується на сервер, уся модель живе в одній вкладці.