Arbori Sufix

. ARBORI SUFIX

1. Definirea problemei

Potrivirea secvenţelor de caractere este o problemă pe care programatorii au plasat-o ca punct de plecare. Câteva sarcini de programare, cum ar fi compresarea datelor sau secvenţei ADN, poate ajuta enorm la îmbunătăţirea algoritmului de potrivire a caracterelor. Acest articol discută comparativ structura de date, arbore de sufixe şi arată cum caracteristicile acestui tip de arbore pot fi utilizate la atacarea problemelor dificile de de potrivire a şirurilor de caractere.

Imaginaţi-vă că tocmai aţi fost angajat ca un programator care lucrează la un proiect secventierea ADN-ului. Cercetatorii sunt ocupaţi în împărţirea materialului genetic virale, producând secvenţe fragmentate de nucleotide. Ei trimit aceste secvenţe la un server, de la care se aşteaptă apoi să găsească secvenţe într-o bază de date de baze de genomi. Genomul pentru un virus dat poate avea sute de mii de nucleotide şi astfel pot exista sute de viruşi în baza de date. Se aşteaptă să se implementeze acest lucru ca un proiect client / server, care oferă un feedback în timp real lui Ph. D. S. Care este cel mai bun mod de a vorbi despre acest lucru?

Este evident că în acest moment o căutare forţată a unui şir va fi foarte ineficientă. Acest tip de căutare s-ar cere să efectueze o comparaţie şir la fiecare nucleotidă unică în fiecare genomului în baza de date. Testarea un fragment lung, care are o rata mare de succes parţială meciuri ar face clientul / serverul arata ca sistemul de un lot de masini de prelucrare antic. Provocarea este de a veni cu un şir de potrivire eficientă soluţie.

2.Soluţia intuitivă

Cât timp baza de date pe care se testează este invariantă, procesarea pentru a simplifica căutarea pare o idee bună. O preprocesare apropiată este de a construi un arbore trie.Un trie este un arbore menit să stocheze şiruri. Fiecare nod al lui va avea în general un număr de fii egal cu mărimea alfabetului şirurilor de caractere care trebuiesc stocate. Fiecare muchie care porneşte din tată spre fii şi va fi etichetată cu o literă distinctă a alfabetului. Etichetele legăturilor de pe un drum de la rădăcină până la o frunză vor alcătui un cuvânt stocat în arbore.

Pentru căutarea prin textul dat , o abordare directă la un arbore de căutare oferă un lucru numit trie sufix. (O structură trie sufix se află la doar un pas distanţă de destinaţia finală, arborele de sufixe). Un trie este un tip de arbore, care are N ramuri posibile de la fiecare nod, unde N este numărul de caractere din alfabet. Cuvântul "sufix" este utilizat în acest caz pentru a se referi la faptul că trie conţine toate sufixele unui bloc de text dat (probabil un genom viral).

Figura 1

Arborele trie sufix reprezentând textul "BANANAS"

Figura 1 prezintă un trie sufix pentru cuvântul BANANAS. Există două fapte importante de reţinut despre acest trie. În primul rând, pornind de la nodul rădăcină, fiecare dintre sufixele cuvântului BANANAS se găsesc în trie, începând cu BANANE, ANANAS, NANAS, si terminând cu un solitar S. În al doilea rând, datorită acestei organizări, puteţi căuta orice alt subşir al cuvântul, pornind de la rădăcină spre următoarele potriviri din josul arborelui până la final .

Al doilea punct este ceea ce face structura trie sufix o construcţie aşa de interesantă. Dacă aveţi un text de intrare de lungime N, precum şi un şir de căutare de lungime M, o tradiţională putere de căutare va avea nu mai putin N *M comparaţii de caractere pentru a finaliza căutarea. Tehnica căutării optimizate, cum ar fi algoritmul Boyer-Moore poate garanta căutări care necesită nu mai mult de M + N comparaţii, cu o performanţă medie mai bună. Dar structura trie sufix distruge această performanţă, solicitând doar M comparaţii de caractere, indiferent de lungimea textului propus cautării!