Trie

Giriş
Açıklaması şöyle. Bu veri yapısını telefon rehberini belleğe sığdırmak için kullandım.

A trie, also called digital tree and sometimes radix tree or prefix tree (as they can be searched by prefixes), is a kind of search tree—an ordered tree data structure ...

Radix Tree yazısına bakabilirsiniz

Trie Kullanan Algoritmalar
Aho-Corasick algoritması "string searching" algoritmalarından bir tanesi. Trie kullanılarak çözülebilir.

Avatajları
Şöyledir.

The basics:
 *Predictable O(k) lookup time where k is the size of the key
 *Lookup can take less than k time if it's not there
 *Supports ordered traversal
 *No need for a hash function
 *Deletion is straightforward

New operations:
 *You can quickly look up prefixes of keys, enumerate all entries with a given prefix, etc.

Binary Trie
Trie binary olmak zorunda değil.
Örnek
3 tane kelime içeren (shy,raku,rio) trie şeklen şöyledir.

              ROOT
          /     |  
        s       r    
      /      /     \
     h       a      i
    /      /       /
   y      k       o
         /  
        u

Örnek
Şöyledir

      A
     / \
    B   C
   / \   \
  D   E   F

Trie Tanımlama
Trie tanımlamada önemli olan şey bir node'un kaç tane daha node saklayabileceğine karar vermek. Ayrıca nod'lara ilave bilgiler de eklenebilir. Burada imla düzeltmesi (spell autocorrect) için kullanılan bir Trie var.

Örnek
Şöyle yaparız. Burada Dictionary kullanıldığı için bellek israfı yok

public class Trie : Dictionary<char, Trie>
{
  public void Add(string value)
  {
    var c = String.IsNullOrEmpty(value) ? '\0' : value[0];
    if (!this.ContainsKey(c))
    {
      this[c] = new Trie();
    }
    if (c != '\0')
    {
      this[c].Add(value.Substring(1));
    }
  }
}

Örnek
Basit bir trie için şöyle yaparız

class Trie {

Node root;

public Trie() {
  root = new Node();

}

boolean isPresent(String s) {
    
}

Node'lar ise şöyledir. Burada İngilizce Trie olduğu için 26 düğüm olacağı varsayılmış.

class Node {

  boolean terminal;
  int outDegree;
  Node[] children;

public Node() {
    terminal = false;
    outDegree = 0;
    children = new Node[26];
}

Örnek
Basit bir trie için şöyle yaparız. Önce Letter sınıfını tanımlarız.

//Trie taken from: https://stackoverflow.com/a/6073004
public struct Letter
{
  public const string Chars = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
  public static implicit operator Letter(char c)
  {
    return new Letter() { Index = Chars.IndexOf(c) };
  }
  public int Index;
  public char ToChar()
  {
    return Chars[Index];
  }
  public override string ToString()
  {
    return Chars[Index].ToString();
  }
}

Trie sınıfı şöyledir. Burada alt düğümler için yine Dictionary kullanılmış.

public class Trie
{
  public class Node
  {
    public string Word;
    public bool IsTerminal { get { return Edges.Count == 0 && Word != null; } }
    public Dictionary<Letter, Node> Edges = new Dictionary<Letter, Node>();
  }

  public Node Root = new Node();
  ...
}

Constructor şöyledir.

public Trie(string[] words)
{
  for (int w = 0; w < words.Length; w++)
  {
    var word = words[w];
    var node = Root;
    for (int len = 1; len <= word.Length; len++)
    {
      var letter = word[len - 1];
      Node next;
      if (!node.Edges.TryGetValue(letter, out next))
      {
        next = new Node();

        node.Edges.Add(letter, next);
      }

      if (len == word.Length)
      {
        next.Word = word;
      }

      node = next;
    }
  }
}

Add metodu

Şöyle yaparız.

tring[] arr = ...;
trie.Add(arr);

findByPrefix metodu
Örnek
Şöyle yaparız.

t.findByPrefix("rabb");

Örnek
Şöyle yaparız.

string FindLongestWord(Trie.Node node, string input, int charIndex)
{
  var character = char.ToUpper(input[charIndex]);

  string longestWord = null;

  foreach (var edge in node.Edges)
  {
    if (edge.Key.ToChar() == character)
    {
      var foundWord = edge.Value.Word;

      if (!edge.Value.IsTerminal)
      {
        var longerWord = FindLongestWord(edge.Value, input, charIndex + 1);
        if (longerWord != null) foundWord = longerWord;
      }

      if (foundWord != null && (longestWord == null ||
          edge.Value.Word.Length > longestWord.Length))
      {
        longestWord = foundWord;
      }
    }
  }
  return longestWord;
}

findValidPrefixes metodu
Elimizde şöyle bir Trie olsun.

public class SimpleTrie {
  private static final int ALPHABET_COUNT = 26;

  class TrieNode {
    char value;
    TrieNode[] children;
    boolean isValidWord;

    TrieNode() {
      this(' ');
    }

    TrieNode(char value) {
      this.value = value;
      children = new TrieNode[ALPHABET_COUNT];
      isValidWord = false;
     }
  }

  private TrieNode root = new TrieNode();

  public void insert(String word) {
    TrieNode current = root;

    for (int i = 0; i < word.length(); i++) {
      char c = word.charAt(i);

      if (current.children[c - 'a'] == null) {
        current.children[c - 'a'] = new TrieNode(c);
      }

      current = current.children[c - 'a'];
    }

      current.isValidWord = true;
  }
}

Şöyle yaparız.

public List<String> findValidPrefixes(String word) {
  List<String> prefixes = new ArrayList<>();
  TrieNode current = root;

  StringBuilder traversedPrefix = new StringBuilder();

  for (int i = 0; i < word.length(); i++) {
    char c = word.charAt(i);

    if (current.children[c - 'a'] != null) {
      current = current.children[c - 'a'];
      traversedPrefix.append(c);

      if (current.isValidWord) {
        prefixes.add(traversedPrefix.toString());
      }
    }
  }

  return prefixes;
}

insert metodu
Şöyle yaparız.

Trie<String, String> t = new Trie<String, String>();
t.insert("pizza", "🍕");
t.insert("rabbit1", "🐇");
t.insert("rabbit2", "🐰");

t.findByPrefix("rabb");