Tipos de intentos

Un trie es una estructura de datos de recuperación de información en forma de árbol cuyos Nodes almacenan las letras de un alfabeto. También se conoce como árbol digital o árbol radix o árbol de prefijos. Los intentos se clasifican en tres categorías:

1. Triángulo estándar
2. Triángulo comprimido
3. Sufijo Trio

Trie estándar Un trie estándar tiene las siguientes propiedades:

1. Un Trie estándar tiene la siguiente estructura:

   class Node {
      
       // Array to store the nodes of a tree
       Node[] children = new Node[26];
   
       // To check for end of string
       boolean isWordEnd;
   }
   

2. Es una estructura de datos similar a un árbol ordenado .
3. Cada Node (excepto el Node raíz ) en un trie estándar está etiquetado con un carácter.
4. Los hijos de un Node están en orden alfabético.
5. Cada Node o rama representa un posible carácter de claves o palabras.
6. Cada Node o rama puede tener múltiples ramas.
7. El último Node de cada clave o palabra se utiliza para marcar el final de la palabra o Node.

A continuación se muestra la ilustración del Standard Trie:

Trie comprimido Un trie comprimido tiene las siguientes propiedades:

1. Un Trie Comprimido tiene la siguiente estructura:

   class Node {
   
       // Array to store the nodes of tree
       Node[] children = new Node[26];
   
       // To store the edgeLabel
       StringBuilder[] edgeLabel = new StringBuilder[26];
   
       // To check for end of string
       boolean isEnd;
   }
   

2. Un Compressed Trie es una versión avanzada del trie estándar.
3. Cada Node (excepto los Nodes hoja ) tiene al menos 2 hijos.
4. Se utiliza para lograr la optimización del espacio.
5. Para derivar un Trie comprimido a partir de un Trie estándar, se realiza la compresión de strings de Nodes redundantes.
6. Consiste en agrupar, reagrupar y desagrupar claves de caracteres.
7. Mientras realiza la operación de inserción, puede ser necesario desagrupar los caracteres ya agrupados.
8. Mientras realiza la operación de borrado, puede ser necesario reagrupar los caracteres ya agrupados.
9. Un trie T comprimido que almacena s strings ( claves ) tiene s Nodes externos y O (s) número total de Nodes.

A continuación se muestra la ilustración del Trie comprimido:

Sufijo Trie Un sufijo trie tiene las siguientes propiedades:

1. Un Trie Comprimido tiene la siguiente estructura:

   struct SuffixTreeNode { 
   
       // Array to store the nodes
       struct SuffixTreeNode *children[256]; 
      
       //pointer to other node via suffix link 
       struct SuffixTreeNode *suffixLink; 
      
       // (start, end) interval specifies the edge,
       // by which the node is connected to its 
       // parent node
       int start; 
       int *end; 
      
       // For leaf nodes, it stores the index of 
       // Suffix for the path  from root to leaf
       int suffixIndex; 
   }
   

2. Un Suffix Trie es una versión avanzada del trie comprimido.
3. La aplicación más común del sufijo trie es la coincidencia de patrones .
4. Mientras se realiza la operación de inserción, se almacenan tanto la palabra como sus sufijos.
5. Un sufijo trie también se usa en la coincidencia de palabras y la coincidencia de prefijos.
6. Para generar un sufijo trie, todos los sufijos de una string determinada se consideran palabras individuales.
7. Usando los sufijos, se construye trie comprimido.

A continuación se muestra la ilustración del sufijo Trie: