Аналіз методів побудови узагальнених суфіксних дерев

Размещено на http://www.allbest.ru/

Аналіз методів побудови узагальнених суфіксних дерев

Садовий Ян Станіславович

здобувач ступеня доктора філософії, Державний університет «Житомирська політехніка», м. Житомир

Анотація

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

Окремо дано характеристику найбільш поширеним на даний час таких методів побудови узагальнених суфіксних дерев, як Алгоритм Вайнера, Маккрайта, Укконена, Фараха-Колтона, алгоритм побудови узагальнених суфіксних дерев з багатьох суфіксних дерев та алгоритм побудови узагальнених суфіксних дерев з масивів суфіксів. Для кожного методу дано опис, вказано переваги та недоліки, наведено програмну реалізацію для деяких з них.

У статті виконано огляд способів попередньої обробки (індексування) рядків і використовуваних для цього структур даних з метою прискорення пошуку в рядках. Розглянуто модифікацію даної структури-розріджене суфіксне дерево, яке будується не над усіма суфіксами індексованих текстів, а лише над деякими їх підмножинами. Описано необхідні зміни, які робляться в алгоритмі Укконена побудови суфіксного дерева.

Подальше дослідження із вдосконаленню алгоритму Укконена може бути реалізоване в таких напрямках: - паралелізація, - оптимізація простору,- алгоритмічна оптимізація, - гібридні підходи.

Ключові слова: суфіксні дерева, препроцесинг, кешування, алгоритм Вайнера, Маккрайта, Укконена, Фараха-Колтона, розпаралелювання.

Abstract

Sadovyi Ian Stanislavovych PhD candidate, Zhytomyr State Technological University, Zhytomyr

ANALYSIS OF METHODS FOR CONSTRUCTING GENERALIZED SUFFIX TREES

The presented study is devoted to the analysis of methods for constructing generalized suffix trees. It is shown that one of the most versatile data structures is the suffix tree. The main concepts and definitions related to suffix trees are given. Two main drawbacks of suffix trees are identified - high memory requirements and poor spatial locality, which make caching strategies used by the operating system inefficient. It is stated that the basis for the methods of generalized suffix trees is the construction of a specific type of suffix tree that allows to estimate the degree of occurrence of key phrases in the source corpus of texts. The basis for analyzing a set of texts is the construction of a generalized suffix tree for a collection of strings on input, as well as the imposition of key phrases on the resulting AST. The main areas of application of generalized suffix trees are as follows: search for patterns in textual data, data compression, analysis of DNA or protein sequence data, and classification of textual data into categories.

A separate characterization is given for the most widely used methods for constructing generalized suffix trees, such as the Weiner, McCreight, Ukkonen, Farach-Colton algorithms, the Generalized Suffix Tree algorithm from multiple suffix trees, and the algorithm for constructing generalized suffix trees from suffix arrays. For each method, a description is given, advantages and disadvantages are indicated, and a program implementation is provided for some of them.

The article reviews ways of preprocessing (indexing) strings and data structures used for this purpose to speed up string search. A modification of this structure is considered - the sparse suffix tree, which is built not over all suffixes of indexed texts, but only over some of their subsets. The necessary changes made to the Ukkonen algorithm for constructing a suffix tree are described.

Further research in improving the Ukkonen algorithm can be pursued in the following directions: parallelization, space optimization, algorithmic optimization, and hybrid approaches.

Keywords: suffix trees, preprocessing, caching, Weiner, McCreight, Ukkonen, Farach-Colton, parallelization.

Постановка проблеми

узагальнене суфіксне дерево

Серед різноманіття методик аналізу текстів метод узагальнених суфіксних дерев виділяється тим, що належить до нечисленного класу моделей, що представляють текст як послідовність символів, але не як послідовність слів. Це дозволяє досягти високого ступеня незалежності від мови аналізованих текстів, а також виключає необхідність виконувати їх попередню обробку, яка часто виявляється досить трудомісткою.

В основі методів узагальнених суфіксних дерев лежить побудова суфіксного дерева спеціального виду, що дозволяє оцінювати ступінь входження ключових словосполучень у вихідний корпус текстів. Основою для аналізу набору текстів є власне побудова узагальненого суфіксного дерева для надходить на вхід колекції рядків, а також накладення на отримане УСД ключових словосполучень. Основними областями використання узагальнених суфіксних дерев є таке: пошук шаблонів у текстових даних, стиснення даних, аналіз послідовностей ДНК або білкових даних, класифікація текстових даних за категоріями. Найвідоміші застосування суфіксних дерев пов'язані з дослідницькими проектами (наприклад, проєкт Arabidopsis thaliana в Мічиганському університеті та Університеті Міннесоти та проєкт Saccharomyces cerevisiae (пивні дріжджі), що виконується в Інституті Макса Планка).

Аналіз останніх досліджень і публікацій

Значні за обсягом дослідженні із побудови узагальнених суфіксних дерев проведені такими науковцями, як Фарах-Колтон М. [2], Ukkonen E. [8], Адігєєв М. Г. [1], Weiner P. [9], Edward M. A. [6].

Мета статті - аналіз методів побудови узагальнених суфіксних дерев.

Матеріали та методи дослідження

Для досягнення визначеної мети і поставлених завдань була використана наступна група теоретичних методів: історіографічний, порівняльний, систематизації та концептуалізації наукових ідей, моделювання. Серед використаних загальнонаукових методів: аналіз, дедукція та індукція, за допомогою яких опрацьовувалися інформація та результати, отримані за допомогою інших методів. У процесі дослідження використані методи: порівняння, аналогії, аналізу, синтезу та узагальнення - для розкриття змісту основних понять та термінів.

Поряд із значним поширення суфіксних дерев для них існує також два основні недоліки - високі вимоги до пам'яті, адже потрібно зберігати суфіксне дерево, затрати часу для препроцесинг та погана просторова локальність, внаслідок чого використовувані операційною системою стратегії кешування виявляються малозастосовними. І через це суфіксне дерево майже не придатне для обробки великих обсягів вхідних даний.

Загалом, узагальнені дерева суфіксів є потужним інструментом для аналізу великих обсягів текстових даних та послідовностей, що робить їх важливою структурою даних у сучасних програмах аналізу даних.

При роботі з уже побудованим узагальненим суфіксним деревом у зовнішній пам яті часто будуть відбуватися звернення до вузлів дерева на різних сторінках. В результаті цього стратегії кешування, використовувані операційною системою, виявляються малозастосовними. На даний час використовують два шляхи вирішення цієї проблеми. Перше полягає в пошуку спеціальних способів представлення суфіксного дерева у зовнішній пам яті, щоб більш ефективно використовувати особливості блочного обміну з диском і використовуваний операційної системою спосіб кешування (або реалізувати власний механізм управління кешуванням).

Другий спосіб полягає у використанні розріджених (нещільних) суфіксних дерев [1], які будуються не над всіма суфіксами індексованих текстів, а тільки над деякою їх підмножиною (при цьому критерій вибору суфіксів може визначатися конкретним завданням).

Виклад основного матеріалу

Для побудови суфіксного дерева потрібно виконати попередню обробку (препроцесинг) однієї або кількох оброблюваних рядків; після цього суфіксне дерево дозволяє вирішувати багато завдань дуже швидко - за лінійний час від довжини рядка. До числа таких ефективно вирішуваних завдань відносяться завдання знаходження підрядка за заданим шаблоном, найбільшою загальною підрядка для декількох рядків, найбільших повторюваних підрядків, унікальних підрядків і багато інших.

Проаналізуємо найбільш поширені методи побудови узагальнених суфіксних дерев.

Алгоритм Вайнера. Даний алгоритм для побудови узагальненого дерева суфіксів (GST) за лінійний час був представлений в 1973 році Пітером Вайнером [9].

Побудова спрощеного суфіксного дерева для даного рядка w = аі... ап алгоритм послідовно будує суфіксні дерева для рядків w? = є, wi = Аі, W2 = aia2, і так далі для всіх префіксів w. Суфіксне дерево для порожнього рядка складається з однієї вершини і не містить суфіксних посилань. Кожне наступне суфіксное дерево виходить з попереднього його добудовуванням. Нехай дано суфіксне дерево для рядка v, а також покажчик на вершину, що відповідає цілому рядку v. Потрібно отримати суфіксне дерево для рядка Va, де а Є D. Для цього необхідно продовжити вершини, відповідні всім суфіксам рядка v, символом a. Вершини, відповідні всім суфіксам рядка v, можна переглянути, слідуючи за суфіксними посиланнями до повернення в корінь. Кожну з них слід продовжити символом а, і отримані вершини зв'язати в ланцюжок новими суфіксними посиланнями. Реалізується це за допомогою рекурсивної процедури продовження (x, а), яка отримує в якості аргументу вершину х, продовжує її до Ха, робить те ж саме з усіма її суфіксами і нарешті повертає вершину Ха. Тоді виклик v = продовження (v, a) обчислює всі необхідні продовження.

Дано: w = ai... an.

1: створюємо вершину є 2: v = є

3:for i = 1”.” n do

4: v = продовження (v, щ)

процедура продовження (v, a)

1: if із v ще не має переходу a then 2: створити вершину va, з'єднати v з va 3: if v ф є the^

4: нехай u = суфіксне--посилання [v]

5: нехай ua = продовження (u, a)

6: суфіксне--посилання [va] = ua 7: else

8: суфіксне--посилання [va] = є 9: return va

Хоча алгоритм Вайнера неефективний для великих вхідних даних, він став значним кроком на шляху до розробки більш ефективних алгоритмів побудови GST. Перелічимо переваги та недоліки використання алгоритму Вайнера для побудови GST:

Переваги:

лінійна складність часу: Алгоритм Вайнера має лінійну складність часу O (n), де n - загальна довжина всіх вхідних рядків. Це забезпечує ефективну побудову GST для великих наборів даних.

Алгоритм Вайнера був одним з перших алгоритмів лінійного часу, розроблених для побудови суфіксних дерев і він відіграв важливу роль у розробці більш ефективних алгоритмів, які з'явилися пізніше, таких як алгоритми Укконена та Маккрайта.

Недоліки алгоритму Вайнера:

використання пам'яті: як і інші алгоритми побудови дерева суфіксів, алгоритм Вайнера також створює дерево суфіксів (і, як наслідок, GST), яке може споживати значну кількість пам'яті, особливо для великих наборів даних. Це може бути обмежуючим фактором у деяких додатках.

складність алгоритму: Алгоритм Вайнера передбачає вставлення суфіксів у порядку зростання їх довжини та оновлення структури дерева за допомогою неявних посилань на суфікси. Цей процес може бути складнішим для розуміння та реалізації порівняно з більш простими альтернативами, такими як алгоритм Укконена.

застарілий і малопоширений: алгоритм Вайнера застарів і був

витіснений новішими, ефективнішими алгоритмами, такими як алгоритми Укконена та Маккрайта.

Алгоритм Маккрайта. Даний алгоритм для побудови узагальненого суфіксного дерева (GST) був представлений в 1976 році інформатиком Xerox

PARC (дослідницький центр Пало-Альто) [6]. Запропоновані Байєром та Маккрайтом В-дерева - це адаптація дерев пошуку для зберігання у зовнішній пам'яті. Головна ідея задумки передбачає використовувати вершини великої ступені - з тим, щоб кожна вершина займала один блок, а висота дерева зменшилася. Наприклад, якщо всі вершини мають ступінь 1000, то висота дерева з мільярдом вершин буде дорівнює всього лише трьом (а не тридцяти, як у двійкового дерева), і для пошуку потрібної сторінки потрібно прочитати тільки 4 блоки. Тобто, алгоритм Маккрайта будує узагальнене суфіксне дерево низхідним способом, використовуючи активну точку та кінцеву точку, і його часова складність дорівнює O (N log n), де N - загальна довжина всіх вхідних рядків [7].

Хоча алгоритм Маккрайта був значним покращенням порівняно з попереднім алгоритмом Вайнера (1973), він все ще не був лінійним. Тільки через два десятиліття Укконен представив свій лінійно-часовий алгоритм побудови дерев суфіксів, включаючи GSTS, що зробило побудову цих структур даних більш практичною для великих входів.

Тим не менш, алгоритм Маккрайта для побудови дерев суфіксів залишається класичним алгоритмом і послужив основою для багатьох подальших розробок в області рядкових алгоритмів.

Перелічимо переваги та недоліки алгоритму Маккрайта для побудови

GST:

Переваги:

лінійна складність часу: подібно до алгоритму Укконена, алгоритм Маккрайта має лінійну складність часу O (n), де n - загальна довжина всіх вхідних рядків. Це забезпечує ефективну побудову GST для великих наборів даних.

використовує підхід, що заснований на суфіксних посиланнях для прискорення процесу побудови дерева. Ці суфіксні посилання забезпечують швидший обхід та оновлення дерева під час вставки, що сприяє його загальній ефективності.

простота використання: Алгоритм Маккрайта концептуально простий, що робить його відносно легким для розуміння та реалізації.

Недоліки:

використання пам'яті: подібно до алгоритму Укконена, алгоритм Маккрайта також створює дерево суфіксів, яке може споживати значну кількість пам'яті, особливо для великих наборів даних. Це може бути обмежуючим фактором у деяких додатках.

складність розширення GST: адаптація алгоритму Маккрайта для побудови GST вимагає додаткових кроків та структур даних, таких як унікальні обмежувачі рядків для розрізнення вхідних рядків. Це може додати деяку складність до реалізації, має менше поширення та застосування у порівнянні з алгоритмом Укконена, тому для ознайомлення з ним є мала кількість доступних ресурсів, посібників та реалізацій.

Узагальнюючи, можна сказати, що алгоритм Маккрайта є ефективним методом побудови узагальнених суфіксних дерев з перевагами лінійної складності часу та підходу, заснованого на суфіксних зв'язках.

Одним з найбільш відомих алгоритмів, що дозволяють побудову суфіксного дерева за лінійний час є алгоритм Еско Укконена [8], інформатика з Університету Гельсінкі, що був представлений в 1995 році як альтернативу відомим до того часу алгоритмам Вайнера [9] і Маккрейта. Основна ідея полягає в тому, щоб вставити суфікси всіх рядків, один за одним, в єдине дерево суфіксів. Алгоритм Укконена будує GST за принципом «знизу вгору», використовуючи активну точку, суфіксне посилання та набір «кінцевих точок» для кожного вхідного рядка. Алгоритм використовує суфіксне посилання для з'єднання внутрішніх вузлів GST з відповідними вузлами в STS вхідних рядків. Щоб розрізнити рядки, можна використовувати унікальні роздільники рядків, які не відображаються в жодному з вхідних рядків.

Математично представити побудову суфіксного дерева можна так: для даного рядка довжини n за час O (n log k), де k - розмір алфавіту (якщо його вважати константою, то асимптотика виходить O (n)). Вхідними даними для алгоритму є рядок s і його довжина n, які передаються у вигляді глобальних змінних. Основна функція - build_tree, вона будує суфіксне дерево. Дерево зберігається у вигляді масиву структур node, де node [0] - корінь суфіксного дерева.

З метою простоти коду ребра зберігаються в тих же самих структурах: для кожної вершини в її структурі node записані дані про ребро, що входить в неї з попереднього. Звідси, в кожній node зберігаються: (l, r), що визначають мітку s [l.. r - 1] ребра, par - вершина, link - суфіксне посилання, next - список вихідних ребер. string s; int n;

struct node { int l, r, par, link; map<char, int> next; node (int l=0, int r=0, int par=-I)

:l (l), r (r), par (par), link (-1) {} int len() { return r - l; } int &get (char c) { if (!next. count (c))next [c] = -1;

return next [c];

}

};

node t [MAXN]; int sz;

int v, pos;

state (int v, int pos): v (v), pos (pos) {}

};

state ptr (0, 0); state go (state st, int l, int r) { while (l < r)

if (st. pos == t [st. v]. len()) {

st = state (t [st. v]. get (s [l] ), 0); if (st. v == -1) return st;

else {

if (s [t [st. v]. l + st. pos]!= s [l]) return state (-1, - 1); if (r-l <?t [st. v]. len() -- st. pos)

return state (st.v, st. pos + r-l); l + = t [st. v]. len() -- st. pos; st. pos = t [st. v]. len();

return st;

int split (state st) { if (st. pos == t [st. v]. len()) return st. v; if (st. pos == 0)

return t [st. v]. par; node v = t [st.v]; int id = sz++;

t [id] = node (v. l, v. l+st. pos, v. par); t [v. par]. get (s [v. l] ) = id; t [id]. get (s [v. l+st. pos]) = st.v; t [st. v]. par = id; t [st. v]. l += st. pos; return id;

}

int get--link (int v) { if (t [v]. link != -1) return t [v]. link; if (t [v]. par == -1) return 0; int to = get--link (t [v]. par);

return t [v]. link = split (go (state (to, t [to]. len()), t [v]. l + (t [v].par==0), t [v].r));

}

void tree--extend (int pos) {

for(;;){

state nptr = go (ptr, pos, pos+1); if (nptr. v != -1) { ptr = nptr; return;

int mid = split (ptr); int leaf = sz++; t [leaf] = n?de (pos, n, mid); t [mid], get (s [pos] )= leaf;

ptr. v = get_link (mid); ptr. pos = t [ptr.v]. len(); if (! mid) break;

}

}

void build_tree() { sz = 1;

for (int i=0; i<n; + +i) tree_extend (i);

Із метою підтримки узагальнених суфіксних дерев алгоритм Укконена потребує модифікації. Доповнення алгоритму ставить на меті зафіксувати в листах дерева посилання на відповідні записи із початкового набору даних. Кожен лист може містити одне або більше таких посилань, вказуючи на численні рядки. Кожен з рядків, що подаються на вхід, має бути доповнено термінальним символом. В цьому випадку необхідною і достатньою умовою є його унікальність по відношенню до початкових даних. Для різних рядків може використовуватися однаковий термінальний символ.

Під час побудови дерева, важливо відслідковувати поточний рядок, яким поповнюється структура. Для зручності можемо вважати, що посиланням на рядок є його порядковий номер в початкових даних. Для зберігання поточного посилання достатньо буде ввести ще одну службову змінну - індекс. Індекс буде збільшуватися на одиницю кожного разу, коли поточним символом виступає термінальний літерал, визначений заздалегідь. Ця змінна буде записуватися в листи дерева кожного разу, коли значення ребра, що веде до цього листа, містить в собі термінальний символ. При розділенні такого ребра, всі посилання відповідного вузла мають бути перенесені в новостворені листи. Нарешті, важливо зазначити, що після вставки в дерево термінального символу, всі службові змінні окрім індексу мають бути повернуті до початкового стану. Це дозволяє не додавати до дерева зайві суфікси, що після побудови довелось би модифікувати.

Проаналізуємо більш детально основні переваги та недоліки досліджуваного алгоритму. Важливими його переваг&ми є:

лінійна складність часу: алгоритм Укконена має лінійну складність часу, що означає, що він може побудувати GST за O (n) часу, де n - сукупна довжина всіх вхідних рядків. Це робить його дуже ефективним алгоритмом для великих наборів даних.

онлайн-побудова: на відміну від деяких інших алгоритмів, алгоритм Укконена дозволяє онлайн-побудову GST. Це означає, що можна додавати нові рядки до GST без необхідності перебудови цілого дерева, що корисно для динамічних наборів даних.

простота роботи з ним: алгоритм Укконена концептуально простіший порівняно з такими алгоритмами лінійного часу, як алгоритм Фараха-Колтона, Бендера та Демейна [4]. Це полегшує його розуміння та реалізацію.

значне поширення: завдяки своїй ефективності і простоті алгоритм Укконена широко застосовується на практиці і має багато практичних реалізацій на різних мовах програмування.

Недоліками досліджуваного алгоритму є:

використання значного обсягу пам'яті: дерева суфіксів і узагальнені дерева суфіксів можуть споживати значну кількість пам'яті, особливо при роботі з великими наборами даних.

складність розширення GST: хоча алгоритм Укконена концептуально простіший для побудови дерева з одним суфіксом, але його розширення для побудови GST вимагає додаткових кроків та структур даних, таких як унікальні термінатори рядків для розрізнення вхідних рядків, і це ускладнює реалізацію.

обмежене застосування до певних випадків використання: Алгоритм Укконена призначений для побудови дерев суфіксів та GST, тому він може бути не найкращим вибором для інших пов'язаних структур даних, таких як масиви суфіксів або стиснуті структури даних, де альтернативні алгоритми можуть бути більш ефективними.

Модифікований алгоритм Укконена для побудови узагальненого суфіксного дерева є комплекснішим і складнішим до імплементації, ніж побудова через конкатенацію. Втім, його використання є набагато більш ефективним. Найбільшою перевагою такого алгоритму виступає швидкість додавання нових даних до вже існуючою структури. Замість повної перебудови, дані можуть додаватися із тією ж швидкістю, що і під час початкового створення структури. Така швидкодія досягається за допомогою «онлайн» властивості алгоритму - для додавання нових записів, модифікований алгоритм Укконена не вимагає доступу до початкових даних, що вже занесені до структури.

Алгоритм Фарача-Колтона, Бендера та Демейна (FBD) для побудови узагальненого дерева суфіксів (GST) був представлений у 2000 році. Він був розроблений спеціалістами з інформатики в Університеті Рутгерса та Массачусетському технологічному інституту. Алгоритм FBD - це алгоритм лінійного часу для побудови GST з набору рядків. Він має часову складність O (N), де N - загальна довжина всіх вхідних рядків. Цей алгоритм покращив алгоритм Укконена, усунувши необхідність операції «розділення», яка була вузьким місцем алгоритму Укконена.

Алгоритм FBD забезпечує побудову gsts за лінійний час шляхом спочатку побудови стисненого масиву вхідних рядків, а потім перетворення його в GST. Стислий trie створюється за допомогою стратегії «розділяй і володарюй «і використовує техніку, яка називається» копіювання рядків», щоб усунути необхідність операції «розділення». Він широко використовувався на практиці і став стандартним алгоритмом для побудови GSTS. Його лінійна складність часу робить його практичним для аналізу великих обсягів текстових даних та послідовностей, і він використовувався у багатьох додатках, таких як біоінформатика, видобуток тексту та пошук інформації [3].

Головними перевагами досліджуваного алгоритму є таке:

лінійна часова складність: алгоритм FBD має лінійно-часову складність O (n), де n - сумарна довжина всіх вхідних рядків. Це забезпечує ефективну побудову GST для великих наборів даних.

гібридний метод побудови: алгоритм FBD використовує комбінацію методів побудови знизу вгору та зверху вниз, що робить його унікальним порівняно з іншими алгоритмами. Виконання стадії «знизу вгору» створює дерево, тоді як зворотна дія «зверху вниз» стискає його в суфіксне дерево. Такий гібридний підхід в деяких випадках може привести до більш ефективної побудови дерева.

теоретична оптимальність: алгоритм FBDA є теоретично оптимальним з точки зору кількості операцій, що виконуються при побудові дерева. Ця оптимальність може призвести до швидшого побудови певних наборів даних.

Вагомими недоліками алгоритму FBD є:

використання пам'яті: як і в інших алгоритмах побудови дерева суфіксів, FBD також створює дерево суфіксів, яке може споживати значну кількість пам'яті, особливо для великих наборів даних.

концептуальна складність алгоритму: гібридний метод побудови, що використовується в FBD, поряд з додатковими кроками, необхідними для його адаптації до побудови GST, може зробити алгоритм складнішим для розуміння та реалізації порівняно з більш простими альтернативами, такими як алгоритм Укконена.

незначне поширення: незначна кількість літературних джерел про FBD значно обмежує його практичне використання.

Аналіз наукової літератури дозволяє нам зробити висновок, що алгоритм Фараха-Колтона, Бендера і Демейна є ефективним і теоретично оптимальним методом побудови узагальнених дерев суфіксів, але мала кількість інформації не сприяє його поширенню серед науковців.

Алгоритм побудови узагальнених суфіксних дерев (GST) з багатьох суфіксних дерев було введено разом із введенням оригінального GST П. Вайнером у 1973 році. GST може бути сконструйований з кількох дерев суфіксів шляхом об'єднання їх в одне дерево. Отримане дерево представляє всі суфікси заданого набору рядків. Кожен вхідний рядок відповідає унікальному шляху в GST, а шляхи, що відповідають тим самим суфіксам, об'єднуються. Процес об'єднання дерев суфіксів може бути здійснений з використанням висхідного підходу, аналогічного алгоритму Укконена для побудови єдиного GST. Основна відмінність полягає в тому, що внутрішні вузли в об'єднаному дереві матимуть кілька ребер, по одному для кожного вхідного рядка [2].

Концепція GST з багатьох суфіксних дерев практично використана в біоінформатиці для порівняння та аналізу кількох геномних послідовностей та порівняння кількох текстових документів. Головними перевагами даного алгоритму є:

модульна конструкція: створюючи окремі дерева суфіксів для кожного вхідного рядка, процес побудови може бути більш модульним, що потенційно полегшує розпаралелювання або розподіл по декількох процесорних блоках.

поступові оновлення: побудова GST з декількох дерев суфіксів може бути оновлена поступово, додаючи або видаляючи окремі дерева суфіксів за потреби. Це може бути корисно в динамічних сценаріях, коли набір вхідних рядків змінюється з часом.

гнучкість: цей підхід забезпечує гнучкість у використанні різних алгоритмів побудови дерева суфіксів для різних вхідних рядків, залежно від конкретних властивостей або вимог кожного рядка.

Недоліками досліджуваного алгоритму є:

складність об'єднання: об'єднання декількох дерев суфіксів в один GST може бути складним процесом. Цей крок може включати додаткові алгоритми, такі як запропонований Гусфілдом, для ефективного об'єднання дерев без шкоди для лінійної складності часу.

використання значного обсягу пам'яті: побудова окремих дерев суфіксів для кожного вхідного рядку може призвести до високого використання пам'яті, особливо для великих наборів даних. Крім того, сам процес злиття може вимагати додаткових витрат пам'яті.

загальна ефективність: хоча модульна побудова окремих дерев суфіксів може дати певні переваги, загальна ефективність цього підходу може бути нижчою, ніж використання одного алгоритму лінійного часу, спеціально розробленого для побудови GST, такого як алгоритми Укконена або Маккрайта.

Таким чином, побудова узагальненого суфіксного дерева з декількох суфіксних дерев має деякі переваги, включаючи модульність, поступове оновлення та гнучкість. Однак цей підхід може включати більш складний процес злиття, більш високе використання пам'яті та потенційно нижчу загальну ефективність порівняно з використанням єдиного алгоритму лінійного часу, спеціально розробленого для побудови GST.

Алгорит побудови узагальнених суфіксних дерев (GST) з масивів суфіксів було вперше представлено в 2001 р. Абуелходою, Курцем та Олебушем. Масиви суфіксів - це альтернативна структура даних для зберігання суфіксів рядків. Процес побудови GST з масивів суфіксів передбачає побудову проміжної структури даних, яка називається масивом «перетворення Берроуза-Уілера» (BWT), який використовується для побудови GST. Масив BWT створюється шляхом спочатку сортування суфіксів вхідних рядків, а потім взяття останнього символу кожного суфікса для створення нового масиву. Масив BWT може бути використаний для ефективного обчислення масиву LCP, який потім використовується для побудови GST.

Перевага побудови GST з масивів суфіксів полягає в тому, що це більш економічно з точки зору простору, ніж побудова його безпосередньо з дерев суфіксів. Отриманий GST може бути використаний для ефективного пошуку шаблонів у наборі рядків, і він може бути використаний у багатьох додатках, таких як біоінформатика для аналізу геномних послідовностей та пошуку інформації для аналізу текстових даних.

Недоліками досліджуваного алгоритму є таке:

складність побудови: побудова GST з масивів суфіксів вимагає декількох кроків, включаючи побудову масиву суфіксів, масиву LCP і, нарешті, самого GST. Це може бути складніше, ніж використання одного алгоритму, спеціально розробленого для побудови GST, такого як алгоритми Укконена або Маккрайта [5].

компроміси в продуктивності: хоча масиви суфіксів споживають менше пам'яті, деякі запити, які можуть бути ефективно виконані за допомогою GST, можуть виконуватися повільніше з масивом суфіксів, що призводить до компромісів у продуктивності.

Таким чином, побудова GST з масивів суфіксів може бути перспективним підходом, особливо коли ефективність використання простору є пріоритетом. Однак процес побудови може бути складнішим і може включати компроміси в продуктивності порівняно з використанням алгоритмів, спеціально розроблених для побудови GST.

Висновки

Проведене дослідження дозволяє нам зробити такі висновки: алгоритм Укконена для побудови узагальнених суфіксних дерев є найкращим вибором для задач аналізу даних порівняно з іншими методами, які були проаналізовані в даній статті. Хоча алгоритми Маккрайта та Вайнера, можуть мати свої переваги, вони не пропонують такої комбінації переваг, як алгоритм Укконена.

Подальше дослідження із вдосконаленню алгоритму Укконена може бути реалізоване в таких напрямках: - паралелізація: застосовуючи методи розпаралелювання алгоритму, можна підвищити його продуктивність для великомасштабних наборів даних. - оптимізація простору: використовуючи структури даних, що заощаджують пам'ять, можна зменшити обсяг пам'яті, що займає результуючий GST. - алгоритмічна оптимізація: подальші дослідження самого алгоритму можуть призвести до вдосконалення процесу побудови або обробки конкретних крайніх випадків. - гібридні підходи: поєднання алгоритму Укконена з масивами суфіксів або перетворення Берроуза-Уілера може привести до розширення ефективних рішень для конкретних проблем аналізу даних.

Хоча алгоритм Укконена вже є ефективним методом побудови узагальнених суфіксних дерев, ці потенційні вдосконалення та оптимізація можуть ще більше підвищити його продуктивність, використання пам'яті або застосовність до різних завдань аналізу даних. Однак важливо мати на увазі, що доцільність та ефективність цих удосконалень можуть залежати від конкретних вимог та обмежень відповідного додатка.

Література:

1. Адігєєв М. Г., Бут А. А. Аналіз ефективності суфіксних дерев для вирішення деяких завдань біоінформатики. Сучасні проблем^и науки і осв-^^^и. 2012. № 6. С. 67-74.

2. Farach-Colton M., Ferragina P., & Muthukrishnan S. On the sorting-complexity of suffix tree construction. Journal o;f the AC1M (JAC^M), 2000. № 47(6). P. 987-1011.

3. Giegerich, R., & Kurtz, S. From ukkonen to McCreight and Weiner: A unifying view of linear-time sux tree construction. 1997. URL: https://hollywood.zbh.uni-hamburg.de/ uploads/pubs/pdf/GieKur1997.pdf (date of access: 16.05.2023).

4. Farach M. Optimal suffix tree construction with large alphabets. 38th Annual Symposium on Foundations of Computer Science, Miami Beach, FL, USA. URL: https://doi.org/10.1109/sfcs.1997.646102 (date of access: 16.05.2023).

5. Mansour, E., Allam, A., Skiadopoulos, S., & Kalnis, P. (2011). ERA: Efficient serial and parallel suffix tree construction for very long strings. In arXiv [cs.DB]. http://arxiv.org/abs/1109.6884 (date of access: 16.05.2023).

6. McCreight E. M. A space-economical suffix tree construction algorithm. Journal of the ACM, 1976. № 3(2). P. 262-272. URL: https://doi.org/10.1145/321941.321946 (date of access: 16.05.2023).

7. Uemura T., & Arimura H. Sparse and truncated suffix trees on variable-length codes. In Combinatorial Pattern Matching. Springer Berlin Heidelberg. 2011. P. 246-260.

8. Ukkonen E. On-line construction of suffix trees. Algorithmica. An International Journal in Computer Science. 1995. № 14(3). P. 249-260. URL: https://doi.org/10.1007/bf01206331 (date of access: 16.05.2023).

9. Weiner P. Linear pattern matching algorithm. 14th Annual IEEE Symposium on Switching and Automata Theo^^y. 1973. P. 1-11.

References:

1. Adigyeyev, M. G., But, A. A. (2012). Analiz efektivnosti sufiksnih derev dlya virishennya deyakih zavdan bioinformatiki [Analysis of the efficiency of suffix trees for solving some bioinformatics problems]. Suchasni problemi nauki i osviti - Current problems of science and education, 6, 67-74. [in Ukrainian]

2. Farach-Colton, M., Ferragina, P., & Muthukrishnan, S. (2000). On the sorting- complexity of suffix tree construction. Journal of the ACM, 47(6), 987-1011. https://doi.org/ 10.1145/355541.355547

3. Giegerich, R., & Kurtz, S. (1997). From ukkonen to McCreight and Weiner: A unifying view of linear-time sux tree construction. Uni-hamburg.de. URL: https://hollywood.zbh.uni- hamburg.de/uploads/pubs/pdf/GieKur1997.pdf (date of access: 16.05.2023).

4. Farach, M. (1997). Optimal suffix tree construction with large alphabets. In 38th Symposium on Foundations of Computer Science. IEEE Comput. Soc. URL: https://doi.org/10.1109/sfcs.1997.646102 (date of access: 16.05.2023).

5. Mansour E., Allam A., Skiadopoulos S., & Kalnis P. ERA: Efficient serial and parallel suffix tree construction for very long strings. In arXi^v [cs.DB]. 2011. URL: http://arxiv.org/ abs/1109.6884 (date of access: 16.05.2023).

6. McCreight, E. M. (1976). A space-economical suffix tree construction algorithm. Journal of the ACM, 23(2), 262-272. https://doi.org/10.1145/321941.321946

7. Uemura, T., & Arimura, H. (2011). Sparse and truncated suffix trees on variable-length codes. In Combinatorial Pattern Matching (pp. 246-260). Springer Berlin Heidelberg.

8. Ukkonen, E. (1995). On-line construction of suffix trees. Algorithmica. An International Journal in Computer Science, 14(3), 249-260. URL: https://doi.org/10.1007/bf01206331 (date of access: 16.05.2023).

9. Weiner, P. (1973). Linear pattern matching algorithm. 14th Annual IEEE Symposium on Switching and Automata Theory. P. 1-11. URL: https://cpsc.yale.edu/sites/default/files/files/ technical-reports/TR17%20Linear%20Pattern%20Matching%20ALgorithms.pd (date of access: 16.05.2023).

Размещено на Allbest.ru