04.27
Ostatnio przy implementacji aplikacji dla platformy Mediaroom, napotkałem na problem ustalania podzbioru pewnego danego zbioru napisów, który to podzbiór miałby zawierać wszystkie stringi rozpoczynające się ustalonym prefiksem. Jak nietrudno się domyśleć, procedura potrzebna mi była do implementacji listy podpowiedzi – użytkownik rozpoczyna wprowadzanie tekstu, a na ekranie pojawia mu się lista podpowiedzi – scenariusz szeroko stosowany we współczesnym webie. W aplikacjach dla telewizji ma on jednak o wiele większe znaczenie, bo możliwości wprowadzania tekstu za pomocą pilota są raczej ograniczone (stosuje się metodę triple-tap znaną z komórek).
Problem przedstawia się zatem następująco: mając zadaną tablicę ze stringami (lista wszystkich możliwych sugestii), dla określonego prefiksu (ciągu znaków), podać listę tych stringów z tablicy wejściowej, które rozpoczynają się od prefiksu.
Trywialne rozwiązanie:
//dane wejściowe
String[] input = strings.ToArray();
//prefiks, dla którego szukamy podzbioru
String prefix = "ab";
String[] subset = Array.FindAll<String>(
input,
new Predicate<string>(s => s.StartsWith(prefix))
);
ma jedną zaletę – zajmuje mało kodu. Niestety poza tym ma same wady:
- Czas ustalenia interesującego nas podzbioru zależy liniowo od wielkości danych wejściowych (liczby stringów w tablicy). Przy, powiedzmy, 50 tysiącach stringów użytkownik zauważalnie długo czeka na podpowiedź.
- Łatwo zauważyć, że dla każdej kolejnej wpisanej litery prefiksu, zawężamy wynik poszukiwań – dla n-tej litery prefiksu wynikiem jest podzbiór uzyskany w poprzednim kroku, dla n-1 litery. Trywialna metoda nie korzysta jednak z tej obserwacji i dla każdej litery proces poszukiwania zaczynany jest na nowo.
Z pomocą przychodzą drzewa trie (czyt. traj). Trie jest drzewem poszukiwań, którego wierzchołki są oznaczone kolejnymi prefiksami słów z listy. Prócz prefiksu wierzchołek zawiera informacje o słowach z listy, które “pasują” do tego prefiksu. Oczywiście w celach optymalizacji, w drzewie nie są przechowywane same podzbiory wyjściowego zbioru, tylko indeks początkowy i końcowy danego podzbioru.
Przykład:
Trie - przykład
Powyższe drzewo trie zawiera dane o prefiksach dla następującej listy słów:
- AR
- AS
- B
- DO
- ELA
- ELF
- EM
Żeby otrzymać informację o podzbiorze stringów zaczynających się od prefiksu “EL” należy przejść od korzenia przez węzeł “E” aż do węzła “L” – otrzymujemy indeksy 4-5, czyli słowa “ELA” i “ELF”. Warto zauważyć, że koszt wyszukania interesującego nas podzbioru nie zależy teraz od wielkości danych wejściowych.
Zanim przystąpimy do napisania funkcji budującej drzewo, zdefiniujmy najpierw dane pomocnicze: strukturę Prefix, i klasę TreeNode<T>.
Prefix:
public struct Prefix
{
int _start;
public int Start
{
get { return _start; }
set { _start = value; }
}
int _end;
public int End
{
get { return _end; }
set { _end = value; }
}
char _letter;
public char Letter
{
get { return _letter; }
set { _letter = value; }
}
public Prefix(int start, int end, char letter)
{
_start = start;
_end = end;
_letter = letter;
}
}
TreeNode:
public class TreeNode<T>
{
private TreeNode _parent = null;
protected List<TreeNode> _children = new List<TreeNode>();
private T _value;
public void AddChild(TreeNode child)
{
if (!_children.Contains(child))
{
_children.Add(child);
child._parent = this;
}
}
public TreeNode Parent
{
get { return _parent; }
set { _parent = value; }
}
public TreeNode(T value)
{
this._value = value;
}
public TreeNode(T value, TreeNode[] children)
{
new TreeNode(value);
_children = new List<TreeNode>(children);
}
public T Value
{
get { return _value; }
set { _value = value; }
}
public List<TreeNode> Children
{
get { return _children; }
}
}
Powyższa klasa jest bardzo prostą implementacją węzła drzewa przechowującego zadany typ danych o zbiorze synów trzymanych za pomocą listy generycznej.
Mając tak zdefiniowane klasy pomocnicze, możemy napisać rekurencyjną metodę tworzącą drzewo trie:
public class Trie
{
private String[] _input;
private TreeNode<Prefix> _tree;
private char[] _availableChars;
private void MakeNode(TreeNode<Prefix> root, int indexOfString)
{
int wordIndex = root.Value.Start;
int lastIndex = wordIndex;
bool nodeStarted = false;
char character = '';
char prevChar = character;
while (wordIndex <= root.Value.End)
{
String s = _input[wordIndex];
prevChar = character;
if (indexOfString < s.Length)
{
if (s[indexOfString] != character)
{
character = s[indexOfString];
if (nodeStarted)
{
Prefix newPair = new Prefix(lastIndex, wordIndex - 1, prevChar);
lastIndex = wordIndex;
TreeNode<Prefix> newNode = new TreeNode<Prefix>(newPair);
root.AddChild(newNode);
nodeStarted = false;
}
}
else
{
nodeStarted = true;
wordIndex++;
}
}
else
{
wordIndex++;
}
}
if (nodeStarted)
{
root.AddChild(new TreeNode<Prefix>(new Prefix(lastIndex, root.Value.End, character)));
}
foreach (TreeNode<Prefix> child in root.Children)
{
MakeNode(child, indexOfString + 1);
}
}
public Trie(String[] input)
{
_input = input;
_tree = new TreeNode<Prefix>(new Prefix(0, _input.Length - 1, ''));
MakeNode(_tree, 0);
}
}
Kluczowa jest metoda MakeNode, która w sposób rekurencyjny tworzy listę synów dla istniejących wierzchołków drzewa trie, w oparciu o drugi parametr, który określa indeks bieżącej litery w szukanych stringach.
Mając utworzone drzewo trie dla danego zbioru stringów, możemy wywoływać następującą metodę z klasy Trie:
public String[] GetStringsForPrefix(string prefix)
{
TreeNode<Prefix> current = _tree;
for (int i = 0; i < prefix.Length; i++)
{
current = current.Children.Find(new Predicate<TreeNode<Prefix>>(t => t.Value.Letter == prefix[i]));
if (current == null)
{
return null;
}
}
int length = current.Value.End - current.Value.Start + 1;
string[] result = new string[length];
Array.Copy(_input, current.Value.Start, result, 0, length);
return result;
}
która zwróci nam interesujący nas podzbiór stringów. W ten sposób mamy rozwiązanie początkowego problemu.
Powyższa implementacja struktury danych trie z całą pewnością może być bardziej optymalna – chciałem jednak zachować czytelność kodu i zaprezentować ogólną ideę tworzenia drzewa trie, a nie skupiać się na optymalizacji.
Wadą drzew trie jest ich stosunkowo duży rozmiar w pamięci (jak duży? od czego zależy? czy można go zmniejszyć?). Można to poprawić stosując tzw. drzewa Patricia, czyli wariant drzew trie, w których zamiast liter do etykietowania krawędzi (w naszej implementacji: węzłów), stosujemy całe stringi. Takie skompresowane drzewo trie tworzy się przez usuwanie węzłów mających tylko jednego syna i modyfikację drzewa, tak aby skrócić ścieżkę poszukiwań.
Drzewa trie nie są jedynym sposobem na szybkie rozwiązanie opisanego na wstępie problemu, ale warto wiedzieć o ich istnieniu i umieć je zaimplementować. W szczególności dlatego, że w pewnych okolicznościach są wydajniejsze niż drzewa BST.
