Spisu treści:
Definicja - Co oznacza drzewo sufiksów?
Drzewo sufiksów jest narzędziem często używanym do analizy ciągów tekstowych. Jest to rodzaj drzewa cyfrowego, które wykorzystuje metody algorytmiczne do ujawnienia struktury łańcucha i jego podzbiorów. Jest to rodzaj drzewa Patricia, struktury służącej do przechowywania zestawu ciągów znaków.
Techopedia wyjaśnia drzewo sufiksów
Drzewa sufiksowe mogą być używane do wielu rzeczy. Zasadniczo drzewa te przechowują wszystkie podzbiory danego ciągu tekstowego. Mając to na uwadze, inne ciągi tekstowe można dopasować do drzewa sufiksów, aby dowiedzieć się, czy są one zawarte w początkowym ciągu wejściowym.
Drzewo sufiksów zostało opracowane z biegiem czasu przez takie postacie jak Weiner i McCreight w latach 70. i Ukkonen w latach 90. Adaptacje wizualne drzewa sufiksów pokazują, jak algorytm obsługuje podzbiory ciągu tekstowego. Alternatywnie drzewo sufiksów można udostępniać w notacji matematycznej.
Drzewa sufiksów są zwykle używane do znajdowania określonych pod-wzorów w większym zestawie ciągów. Programiści używają wyszukiwania drzewa sufiksów, aby usprawnić wyszukiwanie, aby znaleźć każde wystąpienie, w którym dany podciąg jest reprezentowany w strukturze danych. Można wyszukiwać drzewa sufiksów w celu znalezienia sekwencji DNA, współrzędnych badawczych lub dowolnego innego rodzaju ciągu znaków.
