biotechnologia


 
 

Tablica suffixowa

Tablica suffixowa jest strukturą danych, która jest przeznaczona do wydajnego wyszukiwania dużego tekstu. Ta struktura danych najprościej ujmując jest tablicą zawierającą wszystkie wskaźniki do przyrostków tekstowych, które są posortowane w sposób alfabetyczny. Każdy przyrostek jest łańcuchem, który zaczyna się w pewnej pozycji w tekście i kończy razem z jego końcem. Wyszukiwanie tekstu może być wykonywane przez przeszukiwanie binarne przy użyciu tablicy suffixowej (przyrostków).

Konstrukcja tablicy suffixowej (przyrostków) - załóżmy, że mamy przykładowy tekst - "abracadabra" i chcemy zbudować tablicę dla tego tekstu.

Po pierwsze należy przypisać indeksy kolejnym literom tekstu przykładowego. Indeksy określają pozycje, które mogą być przeszukiwane. W naszym przykładzie indeksy są przypisane dla każdego znaku, tak więc możemy później przeszukać przykładowy tekst w dowolnych pozycjach używając tablicy suffixowej.




Po drugie powinniśmy uporządkować indeksy zgodnie z ich odpowiednimi przyrostkami. Zgodność między indeksami, a przyrostkami wygląda następująco:




Po sortowaniu:




Finalnie rezultat sortowania sprawia iż indeksy stają się tablicą suffixową dla przykładowego tekstu.




Szukanie w przykładowym tekście może być wykonane przez wyszukiwanie binarne za pomocą utworzonej tablicy suffixowej. Poniższa ilustracja przedstawia proces poszukiwania w przykładowym tekście ciągu znaków "ra". Numerowane strzałki pokazują kolejność przetwarzania.




Użyłem algorytmu SearchLeft do znalezienia wzorca wyszukiwania w danym ciągu. Przeskakiwanie algorytmu w całych wierszach tablicy suffixowej są rejestrowane i wyświetlane jako 'route'. Wzorzec wyszukiwania zostanie uznany za występujący po raz pierwszy jeśli pójdziemy tą drogą. Przykład poniżej:
Wzór: cad
Cały ciąg: abracadabra
SearchLeft algorytm zajmie 0.05 sekund
ShiftAnd algorytm zajmie 0.11 sekund

Implementacja dostępna w pliku SuffixArray.zip, który znajduje się pod adresem:
http://cs.elitepc.pl/SuffixArray
lub
tutaj



Autor: Krzysztof Wołk

Komentarze

Widok Uszereguj
Tylko zarejestrowani mogą dodawać komentarze. Zarejestruj się/Zaloguj

Podręcznik biotechnologii

Kto jest online

219 gości oraz 0 użytkowników online.

Jesteś niezarejestrowanym lub niezalogowanym użytkownikiem.


 
 
 
Partnerzy:

laboratoria.net Nauka w Polsce Academio Fundacja NanoNet BioCen - BioCentrum Edukacji Naukowej Notatek.pl cebioforum.com materialyinzynierskie.pl Wspieram.to - POLSKI KICKSTARTER - Polska platforma finansowania społecznoœciowego.Tu zrealizujš się Twoje pomysły. VitaInSilica Portal popularnonaukowy

Portal: Redakcja . Współpraca . Kontakt . Polecamy



Wszystkie prawa zastrzeżone 2006-2016 e-biotechnologia.pl
stat4u