Trie on abstraktne andmestruktuur, mille nimi tuleneb sõnast reTRIEval. Põhilised operatsioonid on find, insert, sort ja delete, mistõttu on trie sarnane teiste otsingupuudega nagu BST. Trie iseärasus on, et otsing sõltub ainult päringu suurusest, mitte sisestatud andmete arvust. Knuth on kunagi nimetanud triesid aasta andmestruktuuriks, seega peab neis midagi head olema, eks?
Triet saab kasutada ka sõnastikuna, mida kutsutakse nn. subset dictionary(tõlge?), mis laieneb paljudele praktislistele probleemidele. Üks variant on näiteks Partial Match probleem, kus on sõnastikus mingid andmed ja nende leidmiseks on antud ainult osaline päring. Ütleme, et sõnastikus on “trie”, “true”, “tire”, ja päring on “tr..”, kus “.” tähistab suvalist sümbolit, mida me ei tea. Siis vastuseks on “true” ja “trie”. Samamoodi, kui päring on “t…”, siis on vastuseks “trie”, “true”, “tire”. Selline päring sarnaneb ristsõna lahendamisele, kus osad tähed on lihtsalt puudu.
Keerukus on sellel päringul päringu p (p[1],…,p[m]) p[i] = {0,1,.} (tähestik on ainult 0 ja 1 ja “.” on see spets sümbol) 1 <= i <= m puhul O(n^lg(2-s/m)), kus s on “suva” sümbolite arv. Sellest keerukusest on lihtsam aru saada, kui päris koodi vaadata.
Praktiliselt võib selliseid päringuid kombinatoorselt spämmida sinna andmestruktuuri, mis annab veel huvitavaid kasutusvõimalusi.
Siin on näidiskood sellise päringu jaoks. Arendamise/progemise koha pealt oleks huvitav, kui see klass kasutaks generics-eid ka selliselt, et võid teise andmestruktuuri(mingi dictionary) määrata, mida TrieCNode siis sisemiselt kasutaks. Antud juhul on see SortedDictionary<T>. Selleks peaks wrappima need andmestruktuurid, mida tahaks kasutada mingisse klassi ilmselt, et kasutada where: T <interface name> lauset. Ma ei tea kas see oleks tehtav, aga väga generic oleks igaljuhul. Siis oleks konstruktor midagi sellist Trie<SortedDictionary, string>;//kasutan sõlmedes BST-d ja value on string. Või Trie<Array, object>; //kasutan Arrayt ja value on object tüüpi.
Praegu siiski näidis selline:
TrieCompressed<string> trie = new TrieCompressed<string>();
trie.Insert(“keyword”, “object”);
List<string> h = trie.Partial(“ke.w…”);
Nimi on natuke eksitav, tänu sõnale Compressed. Tegemist ikka tavalise trie, mitte patricia trie või muu sellisega, lihtsalt veits pakitud. Arvestava kokkupakkimise saavutamiseks kasutatakse graafe(DAWG) suht samamoodi nagu triet. Ajalooliselt ma pakun huupi, et esimene trie oli lihtsalt ühe juurega puu, kus kõik sõnad läksid eri lehtedeks. Sellega on probleem, et mõned sõnad on sarnased, siis lükati asju kokku väheke(nali).
Partial Match päringu sain raamatust “Heuristic Search Theory and Applications”, mis iseenesest on küll heuristiliste meetodite uurimiseks, kuid minuarust üks parimaid raamatuid üldse.
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Collections.Specialized;
namespace _101_search_algorithms
{
public class TrieCompressed<T> where T:class
{
public TrieCompressed()
{
root = new TrieCNode<T>();
}
public TrieCNode<T> root;
public int Count = 0;
int alphabet_size;
//one of any characters
char dont_care_symbol = '.';
List<T> returnList = new List<T>();
public List<T> GetSortedItems()
{
//radix sort
List<T> sorted = new List<T>();
Stack<TrieCNode<T>> stack = new Stack<TrieCNode<T>>();
TrieCNode<T> tmp_node;
tmp_node = root;
stack.Push(root);
while (stack.Count > 0)
{
tmp_node = stack.Pop();
if (tmp_node.Object != null)
sorted.Add(tmp_node.Object);
SortedDictionary<char,TrieCNode<T>>.KeyCollection KeyCollection =tmp_node.Next.Keys;
for (int i = KeyCollection.Count - 1; i >= 0; --i )
{
stack.Push(tmp_node.Next[KeyCollection.ElementAt(i)]);
}
}
return sorted;
}
public List<T> Partial(string query)
{
returnList.Clear();
PartialMatch(root, query, 0);
return returnList;
}
void PartialMatch(TrieCNode<T> u, string query, int l)
{
if (l == query.Length)
{
//if leaf
if (u.Object != null)
{
T obj = u.Object;
returnList.Add(obj);
}
return;
}
//if not "don't care symbol"
if (query[l] != dont_care_symbol)
{
if(u.Next.ContainsKey(query[l]))//if (u.Next[(int)query[l]] != null && u.Next[(int)query[l]].Object == null)
PartialMatch(u.Next[query[l]], query, l + 1);
}
else
{
foreach (KeyValuePair<char, TrieCNode<T>> keyval in u.Next)
{
PartialMatch(keyval.Value, query, l + 1);
}
}
}
public T Delete(string deleteKey)
{
TrieCNode<T> tmp_node;
T tmp_object;
bool finished = false;
Stack<TrieCNode<T>> stack = new Stack<TrieCNode<T>>();
tmp_node = root;
int i;
for (i = 0; i < deleteKey.Length; i++)
{
if (!tmp_node.Next.ContainsKey(deleteKey[i]))
return null;
else
{
tmp_node = tmp_node.Next[deleteKey[i]];
stack.Push(tmp_node);
}
}
if (tmp_node.Object == null)
return null;
tmp_object = tmp_node.Object;
//remove all nodes not necessary, root is not on the stack, so it's never deleted
tmp_node = stack.Pop();
tmp_node.Object = null;
finished = tmp_node.Next.Count > 0;
if (!finished)
{
tmp_node = null;
--i;
}
while (stack.Count > 0 && !finished)
{
tmp_node = stack.Pop();
tmp_node.Next.Remove(deleteKey[i]);
finished = tmp_node.Next.Count > 0;
finished = tmp_node.Object == null;
if (!finished)
{
//tmp_node.Next = null;
tmp_node = null;
--i;
}
}
--Count;
return tmp_object;
}
public T Find(string query_string)
{
TrieCNode<T> tmp_node;
tmp_node = root;
for (int i = 0; i < query_string.Length; i++)
{
if (!tmp_node.Next.ContainsKey(query_string[i]))
{
//not found query string
return null;
}
else
{
tmp_node = tmp_node.Next[query_string[i]];
}
}
return tmp_node.Object;
}
public bool Insert(string newKey, T newObject)
{
TrieCNode<T> tmp_node;
TrieCNode<T> new_node;
tmp_node = root;
System.Diagnostics.Debug.Assert(root != null);
for (int i = 0; i < newKey.Length; i++)
{
if (!tmp_node.Next.ContainsKey(newKey[i]))
{
new_node = new TrieCNode<T>();
tmp_node.Next.Add(newKey[i],new_node);
}
//move to next
tmp_node = tmp_node.Next[newKey[i]];
}
if (tmp_node.Object != null)
{
//string already exists
return false;
}
else
{
tmp_node.Object = newObject;
++Count;
return true;
}
}
}
public class TrieCNode<T> where T:class
{
public TrieCNode()
{
//+1 for pointer to the object;
Next = new SortedDictionary<char, TrieCNode<T>>();
Object = null;
}
//can switch this for any dictionary
public SortedDictionary<char,TrieCNode<T>> Next;// TrieCNode[] Next;
public TrieCNode<T> NextMem;
public T Object;
}
}
minusite 