Giriş
Açıklaması şöyle. Bu veri yapısını telefon rehberini belleğe sığdırmak için kullandım.
Trie Kullanan Algoritmalar
Aho-Corasick algoritması "string searching" algoritmalarından bir tanesi. Trie kullanılarak çözülebilir.
Avatajları
Şöyledir.
Binary Trie
Trie binary olmak zorunda değil.
Örnek
3 tane kelime içeren (shy,raku,rio) trie şeklen şöyledir.
Şöyledir
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.
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
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Şöyledir
A
/ \
B C
/ \ \
D E FTrie 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
Basit bir trie için şöyle yaparız
Basit bir trie için şöyle yaparız. Önce Letter sınıfını tanımlarız.
Örnek
Şöyle yaparız.
Şöyle yaparız.
Elimizde şöyle bir Trie olsun.
Şöyle yaparız.
Şö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));
}
}
}Basit bir trie için şöyle yaparız
class Trie {
Node root;
public Trie() {
root = new Node();
}
boolean isPresent(String s) {
}class Node {
boolean terminal;
int outDegree;
Node[] children;
public Node() {
terminal = false;
outDegree = 0;
children = new Node[26];
}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();
}
}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();
...
}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);Örnek
Şöyle yaparız.
t.findByPrefix("rabb");Şö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;
}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;
}
}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;
}Şöyle yaparız.
Trie<String, String> t = new Trie<String, String>();
t.insert("pizza", "🍕");
t.insert("rabbit1", "🐇");
t.insert("rabbit2", "🐰");
t.findByPrefix("rabb");
