За реализација на многу програми и софтверски решенија, потребно е да се употребат текстуални низи и разни структури и алгоритми поврзани со нив. На пример, замислете софтверско решение со кое што треба да имплементираме речник, решение каде што треба да зачувуваме имиња на корисници и слично.

Повеќе корисни податочни структури и алгоритми за работа со текстуални низи се веќе имплементирани во програмскиот јазик C++. На пример, можеме да користиме string за реализација на текстуалните податоци, дел од нив да ги зачуваме во set<string> и потоа да проверуваме кои од нив се наоѓаат таму, итн. Но, постојат и проблеми каде што треба да вршиме ефикасни проверки на тоа колку текстуални низи имаат одреден префикс (почеток), ефикасна проверка колку пати е внесен некој збор, итн. За решавање на вакви и слични проблеми, можеме да користиме т.н. дрво на префикси (анг. trie, или prefix tree).

Забелешка: Префикс на еден збор претставува збор кој ги содржи првите неколку букви од почетниот збор, во истиот редослед. На пример, префикси на зборот кокошка се к, ко, кок, коко, кокош, и кокошк (понекогаш, може да решиме дека ќе го разгледуваме и самиот збор како префикс - кокошка).

Генералната идеја кај дрвото на префикси е претставена на сликата подолу. Како што можете да видите, дрвото има корен (означен со кругот кој се наоѓа најгоре), од каде што почнуваме со разгледување на текстуалните податоци кои се наоѓаат во дрвото на префикси. Како што се движиме надолу (низ врските), можеме да прочитаме кои зборови се претставени со истото. На пример, ако ги следиме врските кои се дадени од левата страна, ќе видиме дека во дрвото е запишан зборот “daca”, но и зборовите “ax”, “doo”, и “www”. Движејки се надолу низ дрвото (почнувајќи од коренот), можеме и едноставно да кажеме кои префикси на внесените зборови се наоѓаат во истото (“d”, “da”, “dac”, итн).

При имплементацијата на дрво на префикси, ќе користиме структура на податоци (struct) за секој елемент во дрвото (секој круг од сликата), и кај секој елемент ќе запишеме колку зборови завршуваат во тој елемент (на пример, во последниот круг доле-лево, каде што завршува daca, ќе запишеме 1), колку зборови поминуваат низ елементот (со цел да можеме да одредиме колку зборови постојат во дрвото со тој префикс), а ќе чуваме и 26 врски за секој елемент (круг) до следното ниво од дрвото. Бројот 26 е одбран, во овој случај, бидејќи во латиницата постојат 26 букви. Доколку во дрвото сакаме да чуваме текстуални низи кои можат да содржат и други вредности (на пример, и бројки), ќе чуваме по 36 врски (26 букви + 10 цифри), итн.

Оваа дискусија е најдобро да ја продолжиме по разгледувањето на самиот изворен код. Притоа, истиот ќе содржи наредби за динамичко алоцирање на меморија (new TrieNode()), со цел да создаваме врски во дрвото само онаму каде што има потреба. На пример, од едно теме во дрвото можеби постојат само неколку можни следни знаци (3 наместо 26), па нема потреба да создаваме 26 нови темиња непотребно (иако ќе имаме низа од 26 покажувачи, само дел од нив ќе покажуваат кон нешто, а останатите ќе ја содржат вредноста NULL). Ова можете да го забележите и од сликата дадена погоре, каде што од темињата немаме по 26 врски до следното ниво, туку само по неколку. Реализацијата во програмскиот јазик C++ е дадена во продолжение. Внимавајте на коментарите дадени во самата програма, бидејќи тие служат за дообјаснување на она што се случува во истата.

#include <iostream>
#include <string>
using namespace std;

struct TrieNode 
{
     
     int prefixes;  //broj na prefiksi koi pominuvaat niz ovoj element
     int words;     //broj na zborovi koi zavrshuvaat kaj ovoj element
     
     struct TrieNode *child[26];
};


//funkcija koja sozdava "TrieNode" i gi inicijalizira vrednostite
struct TrieNode *createNode() 
{
     struct TrieNode *node = new TrieNode();
     node->prefixes = 0;
     node->words = 0;
     
     for (int i=0; i < 26; i++) 
     {
          node->child[i] = NULL;
     }
     
     return node;
}


//funkcija za dodavanje na nov zbor
void insertWord(TrieNode *root, string word) 
{
     struct TrieNode *current = root;
     
     for (int i=0; i < word.size(); i++) 
     {
          int index = word[i] - 'a';
          
          if (!current->child[index]) 
          {
               //nema vrska do slednoto nivo
               current->child[index] = createNode();
          }
          
          //odi do sledniot znak, vo slednoto nivo
          //(shto ili vekje postoi, ili go sozdavame so prethodniot chekor)
          current->prefixes++;
          current = current->child[index];
     }
     
     //imame dodadeno sve so prethodniot for ciklus
     //i (current) pokazuva onamu kade shto zavrshuva zborot,
     //pa samo treba da go zgolemime soodvetniot brojac (kolku
     //pati e dodaden tochno ovoj zbor vo drvoto)
     current->words++;
}


//funkcija koja broi kolku pati zborot "word" e dodaden vo drvoto
int countWords(TrieNode *root, string word) 
{
     struct TrieNode *current = root;
     
     for (int i=0; i < word.size(); i++) 
     {
          int index = word[i] - 'a';
          
          if (!current->child[index]) 
          {
               //nema vrska, pa brojot e 0 (nema pat vo drvoto)
               return 0;
          }
          
          //inaku, odi do slednoto nivo
          current = current->child[index];
     }
     
     //dojdovme do krajot, pa samo treba da go vratime brojot na zborovi
     return current->words;
}


//funkcija koja broi kolku zborovi vo drvoto go imaat soodvetniot "prefix"
int countPrefixes(TrieNode *root, string prefix) 
{
     struct TrieNode *current = root;
     
     for (int i=0; i < prefix.size(); i++) 
     {
          int index = prefix[i] - 'a';
          
          if (!current->child[index]) 
          {
               //nema vrska, pa brojot na prefiksi e 0
               return 0;
          }
          
          //inaku, odi do slednoto nivo
          current = current->child[index];
     }
     
     //dojdovme do krajot, pa samo treba da go vratime brojot na prefiksi
     return current->prefixes;
}





int main()
{
     
     
     struct TrieNode *root = createNode();
     insertWord(root, string("daca"));
     insertWord(root, string("doo"));
     insertWord(root, string("www"));
     insertWord(root, string("zzz"));
     insertWord(root, string("zzz"));
     
     cout << countPrefixes(root, string("xyz")) << endl; //pechati 0
     cout << countPrefixes(root, string("w")) << endl;   //pechati 1 ("www")
     cout << countPrefixes(root, string("ww")) << endl;  //pechati 1 ("www")
     cout << countPrefixes(root, string("d")) << endl;   //pechati 2 ("daca", "doo")
     
     cout << countWords(root, string("hello")) << endl;  //pechati 0
     cout << countWords(root, string("daca")) << endl;   //pechati 1 ("daca")
     cout << countWords(root, string("www")) << endl;    //pechati 1 ("www")
     cout << countWords(root, string("zzz")) << endl;    //pechati 2 ("zzz", "zzz")
     cout << countWords(root, string("z")) << endl;      //pechati 0
     return 0;
}

Сите операции (insertWord, countPrefixes и countWords) имаат временска сложеност O(L), каде што L е должината на зборот/текстот кој што е аргумент на соодветната функција. Притоа, самата анализа е едноставна – имаме линеарна временска сложеност која произлегува од фактот што во функциите имаме само еден for циклус, и дека во него само се движиме низ дрвото (притоа, евентуално, создавајќи нови врски, доколку тие не постојат).

Забележете и дека функциите countPrefixes() и countWords() се практично идентични, со таа разлика што кај едната го враќаме бројот на префикси current->prefixes, а кај другата колку пати го имаме внесено соодветниот збор во дрвото на префикси current->words. Операторот “->” ни овозможува да пристапиме до вредностите на current, иако current е покажувач до структура (поради динамичкото алоцирање на меморија) – наместо да мораме да пишуваме наредби од типот (*current).prefixes, каде што прво го претвораме покажувачот во структура, и слично.

Инаку, сите три функции како параметар го добиваат коренот на дрвото на префикси, за да знаат од каде да почнат со движење низ истото. Понатаму, тие одржуваат променлива current, која што памети на која позиција (круг) во дрвото се наоѓаме во дадениот момент. Сите тие користат for циклус за да се движат низ текстуалниот податок (зборот), почнувајќи од неговиот почеток, и разгледувајќи ги неговите знаци. Наместо да користиме for циклус, може да се користи и рекурзија - но мене повеќе ми се допаѓа оваа реализација.

Кај функцијата insertWord(), како што се движиме низ самото дрво, можно е да откриеме дека не постои одредена врска - во тој случај истата ја додаваме користејќи ја наредбата createNode(). Бидејќи еден збор може да има повеќе префикси (чиј број зависи од бројот на знаци во зборот – на пример, префикси на зборот “daca” се “d”, “da”, “dac”), при секоја итерација на циклусот го зголемуваме бројот на префикси кај елементот во кој се наоѓаме. Така, на пример, доколку некој ја повика функцијата countPrefixes() за “d”, или за “dac”, ќе добие резултат 1.

За крај, забележете дека сите текстуални низи кои се користат од нашата програма мора да се составени само од мали латинични букви (abcdef...). Доколку, покрај мали букви, треба да разликуваме и други, треба наместо 26 да користиме повеќе врски до следните нивоа во дрвото. Или, доколку големите и малите букви треба да ги третираме идентично (како "daca" и "DACA" да е еден ист збор), тогаш можеме пред извршувањето на било која од функциите, да ги претвориме зборовите така што истите ќе се состојат само од мали букви ("DACA" во "daca"), без да има потреба да менуваме било што во нашата имплементација на дрвото на префикси.

//koristi C++11 - http://mendo.mk/Lecture.do?id=26

//funkcija za pretvoranje na golemi bukvi vo mali
string to_lowercase(string input)
{
     string output = "";
     for (auto letter : input)
     {
          if (letter >= 'A' && letter <= 'Z')
          {
               
               //pretvori od golema vo mala bukva,
               //taka shto kje ja odzemesh razlikata
               //vo ASCII kodot na 'A' i 'a'
               output += (char)(letter - ('A' - 'a'));
          }
          else
          {
               output += letter;
          }
     }
     
     return output;
}

Најдолг префикс

Во претходниот дел, се запознавме со основите на дрвото на префикси, како да внесеме нов текстуален податок во дрвото, да изброиме број на префикси, итн. Се разбира, ваква структура може да се искористи и за решавање на други проблеми, имајќи го во предвид само нејзиниот изглед и како податоците се зачувани во истата.

На пример, покрај внесувањето на зборови во структурата, нека треба да напишеме и функција која што, за даден нов збор X, ќе пресмета кој збор кој се наоѓа во дрвото и е најдолг можен префикс на X. На пример, ако во дрвото на префикси се наоѓаат зборовите “hello”, “mr”, “h”, “how”, “are”, “you”, и ни е даден зборот "hellothere", тогаш треба да се врати "hello". Ако пак ни е даден зборот “howard”, тогаш одговорот e “how”, бидејќи е тоа најдолгиот цел збор кој е префикс на “howard” и се наоѓа во дрвото. Доколку во дрвото на префикси се наоѓаше и зборот “howardhoward”, повторно ќе требаше како резултат функцијата да го врати зборот “how” - бидејќи, како што го дефиниравме проблемот, истата треба да го врати “ЗБОРОТ кој е најдолг можен префикс на X”, а “howardhoward” не е префикс на “howard” (туку баш обратно, "howard" е префикс на "howardhoward"). Од друга страна пак, иако сега во дрвото се наоѓа и "howardhoward", функцијата не треба да врати како резултат ниту “howar”, бидејќи тоа не е целосен збор од дрвото, туку само префикс на нешто што сме додале претходно.

За решавање на овој проблем, потребно е само да се движиме низ буквите од зборот “howard” една по една, почнувајќи од почетокот, и така разгледувајќи нови зборови од дрвото на префикси. Како што ќе се движиме низ дрвото, ќе користиме и променлива која што ќе памети колку букви сме сретнале досега, за да можеме да вратиме соодветен резултат.

string longestPrefix(TrieNode *root, string word) 
{
     
     struct TrieNode *current = root;
     
     int countAppendedLetters = 0;
     int lengthLongestPrefixFound = 0;
     
     for (int i=0; i < word.size(); i++) 
     {
          int index = word[i] - 'a';
          
          if (!current->child[index]) 
          {
               //nema vrska, pa vrati go najdobroto shto sme go nashle dosega
               break;
          }
          
          //inaku, odi do slednoto nivo
          current = current->child[index];
          countAppendedLetters++;
          
          //ako toa nivo oznachuva zbor, togash 
          //najdovme nov prefiks so pogolema dolzhina
          if (current->words > 0) 
          {
               lengthLongestPrefixFound = countAppendedLetters;
          }
     }
     
     return word.substr(0, lengthLongestPrefixFound);
}

Нормално, временската сложеност и на оваа функција ќе биде O(L). Нема потреба да се менува ниту еден друг дел од реализацијата на дрвото на префикси кое го видовме претходно, па може да се искористат функциите како insertWord(), на пример, за внесување на почетните елементи во дрвото.

Дозвола за користење: CC BY-NC 2.5 ©