Implementujem zásielku prediktívneho zadávania textuvo VB.NET - v podstate autocompletion, pokiaľ ide o použitie trie. Som urobil môj trie rekurzívnu dátovú štruktúru založenú na triede generických slovníkov.
Je to v podstate:
class WordTree Inherits Dictionary(of Char, WordTree)
Každé písmeno v jednom slove (všetky horné) sa používaako kľúč k novému WordTrie. Nulový znak na liste označuje ukončenie slova. Ak chcete nájsť slovo začínajúce predponou, prechádzam triekom, pokiaľ ide o moje predpony, a potom zhromažďovať všetky deti slová.
Moja otázka sa v podstate týka implementáciesamotný tri. Používam slovníkovú hash funkciu na vetvenie môjho stromu, mohol by som použiť zoznam a urobiť lineárne vyhľadávanie v zozname, alebo urobiť niečo iné Čo je hladké presunúť tu? Je to rozumný spôsob, ako robiť svoje rozvetvenie?
Vďaka.
aktualizácia:
Len aby som objasnil, v podstate sa pýtam, čislovníkový rozvetvovací prístup je samozrejme nižší ako niektorá iná alternatíva. Aplikácia, v ktorej používam túto dátovú štruktúru, používa iba veľké písmená, takže možno najlepší je prístup na matici.V budúcnosti by som mohol použiť rovnakú dátovú štruktúru pre zložitejšiu situáciu typu headhead (viac znakov). , znie to ako slovník je správny prístup - až do bodu, keď potrebujem použiť niečo komplexnejšie vo všeobecnosti.
odpovede:
3 pre odpoveď č. 1Ak je to len 26 písmen ako 26 vstupných polí, potom vyhľadávanie je podľa indexu, pravdepodobne má menej priestoru ako Slovník, ak je zoznam vedier dlhší ako 26.
3 pre odpoveď č. 2
Ak sa obávate o priestor, môžete použiť kompresiu bitmapy na platné prechody bajtov, za predpokladu limitu 26char.
class State // could be struct or whatever
{
int valid; // can handle 32 transitions -- each bit set is valid
vector<State> transitions;
State getNextState( int ch )
{
int index;
int mask = ( 1 << ( toupper( ch ) - "A" )) -1;
int bitsToCount = valid & mask;
for( index = 0; bitsToCount ; bitsToCount >>= 1)
{
index += bitsToCount & 1;
}
transitions.at( index );
}
};
Existujú aj iné spôsoby, ako počítať bit Tu, index do vektora je počet nastavených bitov v platnom bitset. druhou alternatívou je priama indexovaná sústava štátov;
class State
{
State transitions[ 26 ]; // use the char as the index.
State getNextState( int ch )
{
return transitions[ ch ];
}
};
2 pre odpoveď č. 3
Dobrá štruktúra údajov, ktorá je efektívna vo vesmíre a potenciálne umožňuje vyhľadávanie sub-lineárnych prefixov, je ternárny vyhľadávací strom. Peter Kankowski má fantastický článok o tom. Používa C, ale je to jednoduchý kód, akonáhle pochopíte dátovú štruktúru. Ako už bolo spomenuté, toto je štruktúra, ktorú ispell používa na korekciu pravopisu.
2 pre odpoveď № 4
Urobil som to (implementácia triedy) v C s 8 bitovými znakmi a jednoducho použil verziu poľa (ako to naznačuje odpoveď "26 znakov").
Ale predpokladám, že chcete úplnú unicodepodpora (pretože .NET char je unicode, okrem iných dôvodov). Za predpokladu, že musíte mať podporu pre unicode, hľadanie hash / map / dictionary je pravdepodobne najlepšou stávkou, pretože pole 64K v každom uzle nebude fungovať veľmi dobre.
O jedinom hackete som sa na to mohol zamyslieťje uložiť celé reťazce (prípony alebo prípadne "in-fixes") na vetvách, ktoré ešte nie sú rozdelené, v závislosti na tom, ako riedka strom, er, trie, je. To však pridáva veľa logiky na detekciu reťazcov typu multi-char a rozdelí sa, keď sa zavedie alternatívna cesta.
Čo je vzorec čítania v závislosti od aktualizácie?
---- aktualizácia júl 2013 ---
Ak.NET reťazce majú funkciu ako java na získanie bajtov pre reťazec (ako utf-8), potom mazať pole v každom uzle, ktoré reprezentujú aktuálnu pozíciu Hodnota byte je pravdepodobne dobrý spôsob, ako ísť. matice s variabilnou veľkosťou s prvými / poslednými hraničnými ukazovateľmi v každom uzle, pretože veľa uzlov bude mať len malé písmená ASCII, alebo len veľké písmená alebo číslice 0-9 v niektorých prípadoch.
0 pre odpoveď č. 5
Našla som burst trie " byť veľmi priestorovo efektívne. Napísal som svoje vlastné burácanie tria v Scale ktorý tiež opätovne používa niektoré nápady, ktoré som našiel v implementácii GWT trie.I použil to v Stripe Capture the Flag súťaž o problém, ktorý bol multi-uzol s malým množstvom pamäte RAM.