Trie - Uma estrutura de dados poderosa

Imagem de capa Trie - Uma estrutura de dados poderosa

O Trio - Uma estrutura de dados poderosa

O que é um Trio (trie)

Muitos de vocês conhecerão uma árvore binária. Você tem um nó raiz e dependendo se o valor for maior que a raiz ou nó ele vai para a esquerda (se for menor) ou para a direita da raiz (se for maior). Cada nó (incluindo o nó raiz) pode conter no máximo 2 filhos. Se quisermos adicionar um novo item à nossa árvore, temos que adicionar um novo nível com as regras descritas acima.

O Trie não está longe disso. Em vez de ter no máximo 2 filhos podemos ter k filhos (portanto, um número arbitrário). A ideia é adicionarmos palavras pelo seu caráter individual. Se duas palavras têm o mesmo prefixo (portanto, o início da palavra) elas compartilham exatamente o mesmo prefixo em nossa árvore, vamos dar uma olhada na animação a seguir para torná-la um pouco mais visível. Adicionamos as seguintes três palavras: Tree, Trie, Tetris

A primeira palavra Árvore é apenas uma "linha". Mas podemos ver assim que adicionamos a segunda palavra Trie, ramificamos depois de Tr. Isso faz sentido, pois Tree e Trie compartilham o prefixo Tr. Quando adicionamos Tetris, ramificamos após o T porque apenas o T é o prefixo comum entre todas essas palavras. Se adicionássemos uma palavra como Banana, não teríamos nenhum prefixo comum e nos ramificaríamos do nó raiz (o elemento vazio no topo).

Antes de mergulharmos no código, quero destacar por que essa é uma boa estrutura de dados para preenchimento automático. Vamos supor em nosso exemplo que o usuário digite "Tr". Se descermos nosso Trie, sabemos que Tree e Trie compartilham esse prefixo. Tada temos a nossa palavra. Também procurar uma palavra específica é fácil, pois basta seguir os ramos do nosso Trie e verificar se encontramos ou não uma folha.

Complexidade de tempo e espaço

Agora uma palavra sobre a complexidade do tempo e do espaço. Adicionar uma nova palavra pode levar até a quantidade total da palavra que desejamos adicionar. Mas esse é o pior caso. Apenas lembre-se do nosso exemplo de banana acima. nós só tínhamos palavras com T, portanto, banana levaria 7 caracteres adicionais em nosso Trie. Mas se adicionarmos a palavra Chá, isso levaria apenas o a adicional.

  • Complexidade Espacial Pior Caso: O(n)
  • Complexidade Espacial - Caso Médio: O(n)

Onde o Trie brilha é em sua complexidade de tempo. Para pesquisar, inserir, excluir e encontrar palavras com base em um determinado prefixo, sempre leva tempo O(n). n aqui significa a palavra que queremos inserir, pesquisar ou excluir. E isso está em contraste direto com um HashSet que verificaremos mais tarde.

O capítulo a seguir mostrará como construir seu próprio Trie.

Adicionando um item

Vamos começar a criar nossa classe Trie.

/// This represents the Trie. More specific this would be a TrieNode but we keep it simple.
/// The user would hold the "root" node
public  class  Trie
{
    // if we have a leaf then we know that node is the end of some word
    private  bool isLeaf;
    
    // We can have k children. The key of the dictionary is "our" current character
    private IDictionary<char, Trie> Children { get; set; } = new Dictionary<char, Trie>();
}

Vou comentar o código o máximo possível para orientá-lo o que está acontecendo.

public  void  Add(ReadOnlySpan<char> word)
{
    var current = Children;
    // We want to go through every element of our word
    for (var i = 0; i < word.Length; i++)
    {
       // For every character we check whether or node we already have this in our Trie
       var node = CreateOrGetNode(word[i], current);
       // Set the current node to the one returned so in the next iteration of the for loop we can check against this letter
       current = node.Children;
       
       // If we are at the last character (so our word is completely integrated) mark this node as leaf
       if (i == word.Length - 1)
       {
           node.isLeaf = true;
        }
     }
}

private  static Trie CreateOrGetNode(char currentCharacter, IDictionary<char, Trie> children)
{
    Trie trie;
    // If the character we are iterating through already exists then we have a shared prefix
    // Imagine we added Tree already and want to add "Trie" now.
    // Now we want to add the "T" of "Trie" then this if would evaluate to true as this is already in our data structure
    if (children.ContainsKey(currentCharacter))
    {
        trie = children[currentCharacter];
    }
    // If not we create a new branch with the current letter
    else
    {
       trie = new Trie();
       children.Add(currentCharacter, trie);
    }
    
    return trie;
}

Encontrar

public  bool  Find(ReadOnlySpan<char> word)
{
    // Check just if the word is empty. If so return always false. You could also always return true.  if (word.IsEmpty)
    if (word.IsEmpty)
    {
        return  false;
    }
    
    // Find the node in our trie which has the word
    var node = FindNode(word);
    
    // If the node is null that means FindNode didn't find the word
    // But we also have to check whether or not the node is a leaf
    // Imagine we add the word "Hello" to our Trie. If we then afterwards want to Find "hel" this should return false.
    // "hel" is only a common prefix but we never added the word "hel" itself
    return node != null && node.isLeaf;
}

private Trie FindNode(ReadOnlySpan<char> word)
{
   var children = Children;
   Trie currentTrie = null;
   
   // we just go through all the children until we are done with all the characters of our word
   foreach (var character in word)
   {
      // If we found the current character we save the node and continue
      if (children.ContainsKey(character))
      {
          currentTrie = children[character];
          children = currentTrie.Children;
       }
       // if the character is not present we know we don't have this word
       else
       { 
          return  null;
        }
     }
     
     return currentTrie;
}

StartsWith

Bem, este é uma simplificação do último. Queremos apenas saber se temos essa string presente em nosso Trie.

public  bool  StartsWith(ReadOnlySpan<char> word)
{
    if (word.IsEmpty)
    {
        return  false;
    }
    
    // Here is the difference. We don't care if it isn't a leave.
    return FindNode(word) != null;
}   

StartsWith

Agora, este podemos aproveitar para conclusão automática. Imagine que temos as palavras "Olá", "Chá", "Casa" e "Ervas" em nosso Trie. Uma chamada para StartsWith("He") deve retornar "Hello" e "Herbs".

public IEnumerable<string> GetWordsWithPrefix(string prefix)
{
    // Find the node (like StartsWith)
    var node = FindNode(prefix);
    if (node == null)
    {
       // If we can't find the node we are done. We found all the words starting with the prefix (or none)
       yield  break;
    }
    
    // We return every word we found given by the prefix
    // We just have to go down all possible branches from the found node... so basically all the children
    // That is what Collect does
     foreach (var word in Collect(node, prefix.ToList()))
     {
         yield  return word;
     }
     
     static IEnumerable<string> Collect(Trie node, List<char> prefix)
     {
        // If we don't have any further children, we are done, we are at the end!
        if (node.Children.Count == 0)
        {
            yield return new string(prefix.ToArray());
        }
        
        // Go through every child
        foreach (var child in node.Children)
        {
           // We collect recursively. Because also our children will have children. So what we are doing here is breadth first
           prefix.Add(child.Key);
           foreach (var t in Collect(child.Value, prefix))
           {
               yield  return t;
           }
           
           // We found something therefore we remove the last element and go to the next word
           prefix.RemoveAt(prefix.Count - 1);
        }
    }
}

No final, em Recursos, você encontrará todo o código novamente se quiser dar uma olhada na imagem completa.

Atuação

Usei a seguinte configuração de teste: peguei as 1000 palavras mais comuns daqui do idioma inglês e adicionei-as uma vez em um HashSet e uma vez em nosso Trie recém-definido. Depois comparei o tempo que levou para a) encontrar uma única palavra eb) encontrar todas as palavras que compartilham um determinado prefixo. Aqui está a configuração do teste:

public  class  TrieVsHashSet
{
    private  readonly HashSet<string> _hashSet = new();
    private  readonly Trie _trie = new();
    
    [GlobalSetup]
    public  void  Setup()
    {
        var wordsToAdd = File.ReadAllLines("1000words.txt");
        
        foreach (var word in wordsToAdd)
        {
            _hashSet.Add(word);
            _trie.Add(word);
        }
     }
     
     [Benchmark]
     public IList<string> FindAllInHashSet() => _hashSet.Where(h => h.StartsWith("Hel")).ToList();
     
     [Benchmark]
     public IList<string> FindAllInTrie() => _trie.GetWordsWithPrefix("Hel").ToList();
     
     [Benchmark]
     public bool FindOneInHashSet() => _hashSet.Any(h => h == "happy");
     
     [Benchmark]
     public bool FindOneInTrie() => _trie.Find("happy");
}

E aqui estão os resultados:

BenchmarkDotNet=v0.13.1, OS=Windows 10.0.19043.1586 (21H1/May2021Update)
Intel Core i7-7820HQ CPU 2.90GHz (Kaby Lake), 1 CPU, 8 logical and 4 physical cores
.NET SDK=6.0.201
    [Host]     : .NET 6.0.3 (6.0.322.12309), X64 RyuJIT
     DefaultJob : .NET 6.0.3 (6.0.322.12309), X64 RyuJIT
|           Método |   Quer dizer |       Erro |     StdDev |  Gen 0 |   Alocado |
|----------------- |-------------:|-----------:|-----------:|-------:|----------:|
| FindAllInHashSet | 34,846.74 ns | 261.200 ns | 231.547 ns |    -   |     128 B |
|    FindAllInTrie |     45.53 ns |   0.585 ns |   0.547 ns | 0.0229 |      96 B |
| FindOneInHashSet |  5,285.91 ns | 102.328 ns | 109.490 ns | 0.0076 |      40 B |
|    FindOneInTrie |     85.50 ns |   0.501 ns |   0.444 ns |   -    |      -    |

Não há comparação. O HashSet é 100x mais lento que o nosso Trie. E o código que temos não está muito bem otimizado. A única otimização que fiz foi usar ReadOnlySpan em vez de strings, mas poderíamos fazer ainda mais se quisermos. Claro que uma parte da equação eu não medi: Adicionar. Aqui o HashSet ganharia claramente. E isso pinta também nosso cenário onde usaríamos um Trie. Não precisamos reconstruir o Trie (ou adicionar palavras) com muita frequência, mas usamos algo como Find ou StartsWith com frequência.

Por que o Trie é muito mais rápido? Se você der uma olhada na animação no topo do artigo, verá que só precisamos percorrer todos os caracteres individuais através do Trie para encontrar uma palavra. Se tivermos uma palavra de comprimento 5, só temos que fazer 5 passos. Em um HashSet esse não é o caso. A complexidade de tempo aqui é log(n), mas n é a quantidade total de entradas que temos em nosso conjunto de hash e não o comprimento da palavra que estamos procurando.

Aqui a visualização de encontrar a palavra "Trie":

Agora o mesmo vale para encontrar palavras com um determinado prefixo. Vimos anteriormente como a fase de coleta é implementada em nosso Trie. Fizemos apenas uma busca em largura para encontrar todas as palavras com esse prefixo. Novamente, o conjunto de hash não pode aproveitar essas informações. Tem que passar por todos os baldes para encontrar todas as palavras.

Componente Typeahead no Blazor

Podemos usar nosso Trie recém-criado para construir um componente de entrada de digitação antecipada rápida. Vou postar o código e embutir toda a seção de código necessária para você entender melhor:

@using LinkDotNet.Blog.Web.Features.Components.Typeahead

@* We are using Bootstrap 5 example here. I want my input and the suggestion directly under each other*@
<div class="row">
    @*
    Every time the user inputs a text we update our suggestion
    You could also add debouncing and stuff here
    *@
    <input @oninput="UpdateAutoCompletion"  value="@content"/>
    @* Only show suggestions if we have at least one *@
    @if (similarWords.Any())
    {
        @*
        Not super sexy but it does what we want. We are using a select element
        which shows all the words and we can change/click on it so that the
        input element will change
        *@
        <select size="@AutoCompleteCount" @onchange="UseSelectedWord">
            @foreach (var similarWord in similarWords)
            {
               <option value="@similarWord">@similarWord</option>
            }
         </select>
     }
 </div>
 @code {
     // Let the parent tell which words we have to "index"
     [Parameter] public IEnumerable<string> AllWords { get; set; }
     // The maximum amount of suggestion we will give
     [Parameter] public  int AutoCompleteCount { get; set; } = 10;
     
     private  readonly Trie trie = new();
     private  string content = string.Empty;
     private List<string> similarWords = new();
     
     // Create the Trie once
     // You could also use OnParameterSet and re-create the trie when the parameters change
     protected  override  void  OnInitialized()
     {
         // Lets order the words alphabetically - so it is easier for the user to select her/his word
         foreach (var word in AllWords.OrderBy(w => w))
         {
             trie.Add(word);
         }
     }
     
     private void UpdateAutoCompletion(ChangeEventArgs inputEventArgs)
     {
        content = inputEventArgs.Value.ToString();
        // Get all words from our Trie which share the prefix (at most AutoCompleteCount)
        similarWords = trie.GetWordsWithPrefix(content).Take(AutoCompleteCount).ToList();
     }
     
     private void UseSelectedWord(ChangeEventArgs obj)
     {
         content = obj.Value.ToString();
         similarWords.Clear();
     }
}

Agora apenas o componente de chamada está faltando:

@page "/"

<PageTitle>Index</PageTitle>

<h1>Enter a word (start with captial letter)</h1>

<div class="col-2 ms-5">
   <InputTypeAHead AllWords="_words" AutoCompleteCount="5"></InputTypeAHead>
</div>
@code {

     private  readonly  string[] _words =
     {
         "Cat", "Car", "Dog", "Day", "Hamster", "School", "Sand", "Tea", "Water",
         "Cold", "Weather", "Blazor", "Dotnet", "CSharp", "Steven", "Giesel", "Example", "Blog", "Stamp", "Stencil"
      };
}

O resultado final deve ser algo assim:

O código fonte para isso pode ser encontrado aqui

Limitações

  1. O maior problema com essa implementação é que o preenchimento automático funciona apenas em palavras únicas. Poderíamos adicionar "Hello World" ao Trie, mas o Trie pensaria que é uma palavra. Portanto, digitar o prefixo "Wo" não retornará "World" e digitar "Hel" retornará apenas a coisa toda "Hello World".
  2. Em seu estado atual, "Gato" e "gato" são duas coisas diferentes. O Trie diferencia maiúsculas de minúsculas. Você pode torná-lo facilmente insensível a maiúsculas e minúsculas, se quiser. Eu também coloquei todo o meu repositório com muitos algoritmos de string na seção Recursos, mas aqui está se você quiser ver a implementação que não diferencia maiúsculas de minúsculas.

Recursos