Префиксно стабло
уређена структура података која организује префиксе кључева у стабло From Wikipedia, the free encyclopedia
Remove ads
Префиксно стабло, дигитално стабло, три или трај (енгл. ) је структура података у облику уређеног стабла које се користи за чување елемената динамичког скупа или асоцијативног низа где су кључеви обично ниске карактера. За разлику од бинарног стабла претраге, ниједан чвор у стаблу не чува кључ који одговара том чвору. Уместо тога, сама његова позиција у стаблу одређује кључ који му одговара. Сви наследници неког чвора имају заједнички префикс ниске карактера која одговара том чвору, а корену одговара празна ниска. Уобичајено је да се вредности не додељују сваком чвору већ само листовима и неким унутрашњим чворовима који одговарају траженим кључевима.
Зове се префиксно стабло јер се може претраживати по префиксу. Енглеска реч trie потиче од средњег слога речи retrieval. Овај термин је први пут употребио Едвард Фредкин, који га је изговарао као /ˈtriː/ енгл. као у речи retrieval.[1][2] Међутим, други аутори име ове структуре изговарају као /ˈtraɪ/ енгл. , како би правили разлику од енгл. .[1][2][3]
У приказаном примеру, кључеви су део самих чворова а њихове одговарајуће вредности испод њих. Свака целовита реч има додељену произвољну целобројну вредност. Префиксно стабло се може посматрати као детерминистички коначни аутомат без петљи. Сваки коначни језик се може генерисати префиксно стабло аутоматом, и свако префиксно стабло се може сабити у Детерминистички ациклични коначни аутомат.
Није неопходно да кључеви буду експлицитно чувани у чворовима. (На слици, речи су приказане само како би се илустровао рад префиксног стабла).
Иако су код ове структуре, кључеви обично ниске карактера, не морају бити. Исти алгоритам се лако може адаптирати да обавља исте функције са уређеним листама било које конструкције, нпр. пермутације листе цифара или облика. Конкретно, битовско префиксно стабло ради са кључевима у виду индивидуалних битова.
Remove ads
Примене
Као замена за друге структуре података
Као што се и у наставку помиње, префиксно стабло има велики број предности у односу на бинарно стабло претраге.[4] Префиксно стабло се такође може користити и као замена за хеш табелу у односу на коју има следеће предности:
- Претрага префиксног стабла је бржа и у најгорем случају, временске сложености О (м) (где је м дужина тражене ниске карактера), у односу на лошију хеш табелу. Лошија хеш табела може имати колизије кључева (хеш функција слика различите кључеве на исту позицију хеш табеле). У најгорем случају, претрага у лошијој хеш таблели је временске сложености О(N), али много чешће О(1) са временском сложеношћу О(м) евалуације хеш табеле.
- Не постоји колизија различитих кључева у префиксно стабло .
- Простор за складиштење података са истим кључем је потребан само ако се подаци разликују.
- Нема потребе за хеш функцијом или за заменом хеш функције новом када се дода више кључева у префиксно стабло .
- Префиксно стабло може пружити алфабетско уређење вредности по кључу.
Код префиксног стабла података постоје и лоше стране:
- Префиксно стабло може бити спорије од хеш табеле при претрази, посебно када су подаци чувани на дисковима са случајним приступом или другим уређајима секундарне меморије код којих је време случајног приступа велико у поређењу са главном меморијом.[5]
- Неки кључеви, као што су бројеви са покретним зарезом, могу довести до великих ланаца префикса који су бескорисни. Ипак, битовско префиксно стабло може да ради са стандардом ИЕЕЕ.
- Нека префиксна стабла могу користити више меморије него хеш табела, јер се меморија алоцира за сваки карактер у траженој ниски карактера за разлику од једног парчета меморије које се алоцира код хеш табеле за ту исту ниску.
Представљање речника
Честа примета префиксног стабла је чување предиктивног текста или речника са могућношћу аутоматског комплетирања речи, попут оних у мобилним телефонима. Таква примета користи могућност префиксног стабла да брзо пронађе, унесе и обрише вредност; ипак, ако је чување речи из речника све што је потребно (тј. ако није потребно чување додатних информација уз речи), минимални детерминистички ациклични коначни аутомат користи мање меморије него префиксно стабло. То је због тога што ациклични детерминистички коначни аутомат може сабити идентичне гране стабла које одговарају истим суфиксима (или деловима) различитих речи које се чувају.
Префиксно стабло се такође користи и код имплементације алгоритама приближног поређења[6], као и код провере правописа.
Алгоритми
Лако се може описати претрага у префиксном стаблу. Нека префиксно стабло има рекурзивно својство, у сваком чвору се налази листа потомака префиксног стабла, индексирани следећим карактером у стрингу, а сваки чвор опционо садржи и вредност. Овде је овај тип података представљен у програмском језику Хаскел:
import Prelude hiding (lookup)
import Data.Map (Map, lookup)
data Trie a = Trie { value :: Maybe a,
children :: Map Char (Trie a) }
Вредност у префиксном стаблу можемо пронаћи на следећи начин
find :: String -> Trie a -> Maybe a
find [] t = value t
find (k:ks) t = do
ct <- lookup k (children t)
find ks ct
У императивном стилу, под претпоставком да већ постоји одговарајући тип података, може се описати исти алгоритам у програмском језику Пајтон. Притом, children представља мапу потомака чвора а крајњи чвор је онај који садржи валидну реч.
def find(node, key):
for char in key:
if char not in node.children:
return None
else:
node = node.children[char]
return node.value
Додавање новог елемента се одвија проласком кроз префиксно стабло на основу ниске која се додаје а затим додавањем нових чворова за суфикс ниске који се не налази у префиксном стаблу. У императивном псеудокоду се то може представити на следећи начин:
algorithm insert(root : node, s : string, value : any):
node = root
i = 0
n = length(s)
while i < n:
if node.child(s[i]) != nil:
node = node.child(s[i])
i = i + 1
else:
break
(* dodaj nove cvorove ako je potrebno *)
while i < n:
node.child(s[i]) = new node
node = node.child(s[i])
i = i + 1
node.value = value
Сортирање
Лексикографско сортирање скупа кључева се може постићи следећим алгоритмом базираном на префиксном стаблу:
- Убацити све кључеве у префиксно стабло.
- Одштампати све кључеве из триа путем префиксног обиласка стабла, што чини да излаз буде у растућем лексикографском поретку
Овај алгоритам представља варијацију радикс сортирања.
Префиксно стабло је основна структура података [[Бурстсорт]|буртсорта], који је (2007. године) био најбржи познати алгоритам за сортирање ниски карактера.[7] Ипак, данас постоје и бржи алгоритми за сортирање ниски карактера.[8]
Потпуно претраживање текста
Посебна врста префиксног стабла, суфиксно стабло, може се користити у индексирању свих суфикса у тексту како би се применило брзо претраживање целокупног текста.
Битовско префиксно стабло
Битовско префиксно стабло је слично основном који је заснован на карактерима, осим што се у овом случају обилазак врши помоћу појединачних битова, чинећи структуру бинарним стаблом. Имплементације ове структуре користе посебне процесорске инструкције да се брзо пронађе бит првог скупа из кључа одређене дужине(нпр. код ГЦЦ преводиоца то је инструкција __builtin_clz()). Ова вредност се потом користи у индексирању табеле величине 32 или 64 која показује на прве елементе битовског префиксног стабла са тим бројем водећих нула. Претрага се потом наставља уз провере сваког следећег бита из кључа и одабиром потомка child[0] или child[1] док се не нађе тражени елемент.
Иако овај процес звучи споро, због принципа локалитета и могућности ефикасног паралелизовања операција он заправо даје одличне перформансе на модерним процесорима. Тако рецимо, црвено-црно стабло даје много боље перформансе на папиру али у пракси не даје најбоље резултате управо како због ниске локалности (и самим тим лоше искоришћености кеша) тако и због тога што узрокује лошу искоришћеност проточне обраде. С друге стране, битовско префиксно стабло ретко приступа меморији а када то уради, обавља само читање. Због тога, битовско префиксно стабло све више постаје примарни избор у ситуацијама када се обавља доста додавања и брисања као што су меморијски алокатори (нпр. новије верзије чувеног dlmalloc алокатора и његобих потомака).
Пример имплементације битовског префиксног стабла у језицима C и C++ може се наћи на адреси http://www.nedprod.com/programs/portable/nedtries/.
Компримовано префиксно стабло
Када је префиксно стабло углавном статично, тј. када се операције додавања и брисања елемената не користе већ се само извршава претрага и када су кључеви независни од вредности самих чворова могуће је компримовати представљање префиксног стабла спајањем истих грана.[9] Ова примена се углавном користи код компримовања табела претраживања када је укупан скуп смештених кључева врло проређен у односу на сам простор података.
На пример, може се користити за представљање проређених скупова битова (нпр. подскупови много већих фиксних набројивих скупова) користећи префиксно стабло чији су кључеви позиције битовских елемената у целокупном скупу и то тако да се кључеви добијају од ниске карактера битова која је неопходна за кодирање позиције сваког елемента. Ппрефиксно стабло ће тада имати дегенерисан облик са недостајућим гранама, а компресија се омогућава чувањем листова стабла (делови скупа са фиксираном дужином) и њиховим комбиновањем када се установи да садрже исте делове или попуњавањем одговарајућих празнина.
Овакво компримовање се такође користи и у имплементацијама разних табела за брзу претрагу које враћају карактеристике Уникод карактера (нпр. табеле претраге које садрже комбинације базних и комбинованих карактера који су потребни у нормализацији Уникода). За такве примене, репрезентација је слична трансформисању великих једнодимензионих ретких табела у вишедимензионе матрице а потом коришћење координата хипер-матрице као стринг кључ некомпримованог префиксног стабла. Компримовање тада подразумева проналажење и спајање истих колона хипер-матрице како би се компримовала последња димензија у кључу; свака димензија хипер-матрице садржи почетну позицију у вектору следеће димензије за вредност сваке координате, а резултујући вектор се може компресовати ако је такође редак, тако да се свака димензија (везана за један ниво у префиксном стаблу) може компримовати посебно.
Неке имплементације подржавају такве компресије у динамичком ретком префиксном стаблу са омогућеним уношењем и брисањем елемента стабла. Овакве имплементације имају значајан трошак при растављању и спајању грана, а одређени уступци се праве између најмање величине компресованог префиксног стабла и брзине ажурирања, ограничавајући глобалну претрагу за упоређивање истих грана у ретком префиксном стаблу.
Резултат такве компресије може деловати слично као трансформисање префиксног стабла у усмерени ациклични граф, јер реверзна трансформација таквог графа у префиксно стабло је очигледна и увек могућа, ипак она је ограничена обликом кључа којим се индексирају чворови.
Један од других начина компресије је пресликавање структуре података у низ бајтова.[10] Овај приступ елиминише потребу за показивачима на чворове што знатно смањује меморијске захтеве и омогућава мапирање меморије што даље доводи до много ефикаснијег учитавања података у меморију.
Још један приступ компримовању је тзв. „паковање“ префиксног стабла.[2]
Remove ads
Предности у односу на друге алгоритме претраге
- Графички приказ понашања различитих алгоритама у односу на број елемената
Понашање Фредкин префиксног стабла као функција величине
(у овом случају, нед префиксног стабла, што подразумева имплементацију у месту, што узрокује да има знатно стрмију криву у односу на динамичке имплементације стабла)
Понашање црвено-црних стабала као функција величине
(у овом случају, BSD имплементацијаrbtree.h, која показује класичноO(log N)понашање)
Понашање хеш табеле као функција величине
(у овом случају,uthash, која у просеку испољава понашање сложеностиO(1))
За разлику од већине други структура података, префиксно стабло има чудну особину да је сложеност кода, а самим тим и потребно време, скоро идентично за операције додавања, брисања и претраживања. Као резултат тога, у ситуацијама када код врши додавање, брисање и проналажење елемената у једнакој мери, префиксно стабло може лако победити бинарно стабло претраге. С друге стране, ово стабло омогућава бољу подлогу за ефикасно кеширање процесорских инструкција и гранања.
Главне предности префиксног стабла над бинарним стаблом претраге (БСП):
- Операција претраге кључева је бржа. Претрага кључа дужине m има временску сложеност О(m). БСП врши О(log(n)) поређења кључева, где је n број елемената стабла, јер претрага зависи од висине стабла које је логаритамско ако је стабло балансирано. Стога, у најгорем случају, претрага у БСП има О(м лог н) временску сложеност. Такође, операције које користи префиксно стабло при претрази (приступ низу преко индекса који је карактер) су брзе на реалним машинама.
- Префиксно стабло је просторно ефикаснија структура када садржи велики број кратких кључева, јер су чворови заједнички кључевима са истим префиксима.
- Префиксно стабло олакшава проблем најдужег заједничког префикса.
- Број унутрашњих чворова од корена до листова је једнак дужини кључа, тако да нема потребе за балансирањем стабла.
Главне предности префиксног стабла над хеш табелом су:
- Префиксно стабло подржава уређене итерације док су итерације над хеш табелом у псеудо-случајном поретку, што зависи од хеш функције као и решавања колизија (што је одређено имплементацијом)
- Префиксно стабло олакшава проблем најдужег заједничког префикса.
- Префиксно стабло је у просеку бржи при уношењу елемента од хеш табеле јер хеш табела мора да преправи индексе када се напуни, што је скупа операција. Префиксно стабло стога има боље ограничену временску сложеност у најгорем случају.
- За кључеве мање дужине, префиксно стабло је брже јер нема коришћења хеш функције.
Remove ads
Види још
Референце
Литература
Спољашње везе
Wikiwand - on
Seamless Wikipedia browsing. On steroids.
Remove ads