Intentos comprimidos

Un trie es una estructura de datos que almacena strings como una estructura de datos de árbol . El número máximo de hijos en un Node es igual al tamaño del alfabeto. Uno puede imprimir fácilmente letras en orden alfabético, lo que no es posible con hash .

Propiedades de Trie :

• Es un árbol de múltiples vías.
• Cada Node tiene de 1 a N hijos.
• Cada Node hoja corresponde a la string almacenada, que es una string de caracteres en un camino desde la raíz hasta su lado.

Tipos de Trie :

• Triángulo estándar
• Sufijo Trio
• Triángulo comprimido

Triángulo comprimido :

Intenta con Nodes de grado al menos 2 . Se logra comprimiendo los Nodes del trie estándar. También se conoce como Radix Tries . Se utiliza para lograr la optimización del espacio.

Dado que los Nodes están comprimidos. Comparemos visualmente la estructura del árbol estándar y el árbol comprimido para un mejor enfoque. En términos de memoria , un árbol trie comprimido usa muy pocas cantidades de Nodes, lo que brinda una gran ventaja de memoria (especialmente para strings largas) con prefijos comunes largos. En términos de velocidad, un árbol de trie normal sería un poco más rápido porque sus operaciones no implican ninguna operación de string, son bucles simples.

En la imagen de abajo, el árbol de la izquierda es un trie estándar, el árbol de la derecha es un trie comprimido.

Implementación:

Un Node trie estándar se ve así:

class node {
    node[] children = new node[26];
    boolean isWordEnd;
}

class node:
  def __init__(self):
      self.node = [None]*26
    self.isWordEnd=False

Pero para un trie comprimido, el rediseño del árbol será como sigue, en el trie general, un borde ‘a’ se denota por este elemento particular en la array de referencias, pero en el trie comprimido, «Un borde ‘cara’ es denotado por este elemento particular en la array de referencias”. El código es-:

class node {
    node[] children = new node[26];
    StringBuilder[] edgeLabel = new StringBuilder[26];
    boolean isEnd;
}

class node:
    def __init__(self):
      self.children = [None]*26
      sefl.edgeLabel = [None]*26
      self.isEnd=False

Node en Trie comprimido:

class CompressedNode {
    int bitNumber;
    int data;
    CompressedNode leftChild, rightChild;
}

class node:
    def __init__(self):
      self.bitNumber=0
      self.data=None
      self.leftChild, self.rightChild=None,None

Prueba de clase comprimida:

class CompressedNode {
 
    // Root Node
    private CompressedNode root;
 
    private static final int MaxBits = 10;
 
    // Constructor
    public CompressedNode() { root = null; }
 
    // Function to check if empty
    public boolean isEmpty() { return root == null; }
 
    // Function to clear
    public void makeEmpty() { root = null; }
}

class CompressedNode {
 
    #Root Node
    root=CompressedNode()
 
       MaxBits = 10
 
    #Constructor
    def __init__(self):
          self.root = None
 
    #Function to check if empty
    def isEmpty(self):
          return self.root == None
 
    #Function to clear
    def makeEmpty(self):
          self.root = None

Buscando en Trie comprimido:

Buscar en un árbol Trie comprimido es muy parecido a buscar . Aquí, en lugar de comparar un solo carácter, comparamos strings. 

// Function to search a key k
// in the trie
public boolean search(int k)
{
    // Find the number of bits
    int numOfBits = (int)(Math.log(k) / Math.log(2)) + 1;
 
    // If error occurs
    if (numOfBits > MaxBits) {
        System.out.println("Error : Number too large");
        return false;
    }
 
    // Search Node
    CompressedNode searchNode = search(root, k);
 
    // If the data matches
    if (searchNode.data == k)
        return true;
 
    // Else return false
    else
        return false;
}

# Function to search a key k
# in the trie
import math
def search(k):
 
    # Find the number of bits
    numOfBits = int(math.log2(k)) + 1
 
    # If error occurs
    if (numOfBits > MaxBits) :
        print("Error : Number too large")
        return False
     
 
    # Search Node
    searchNode = search(root, k)
 
    # If the data matches
    if (searchNode.data == k):
        return True
 
    # Else return false
    else:
        return False

Insertar un elemento en Compressed Trie:

// Function to implement the insert
// functionality in the trie
private CompressedNode insert(
    CompressedNode t, int ele)
{
    CompressedNode current, parent;
    CompressedNode lastNode, newNode;
    int i;
 
    // If Node is NULL
    if (t == null) {
        t = new CompressedNode();
        t.bitNumber = 0;
        t.data = ele;
        t.leftChild = t;
        t.rightChild = null;
        return t;
    }
 
    // Search the key ele
    lastNode = search(t, ele);
 
    // If already present key
    if (ele == lastNode.data) {
        System.out.println(
            "Error : key is already present\n");
        return t;
    }
 
    for (i = 1; bit(ele, i) == bit(lastNode.data, i); i++)
        ;
 
    current = t.leftChild;
    parent = t;
    while (current.bitNumber > parent.bitNumber
           && current.bitNumber < i) {
        parent = current;
        current = (bit(ele, current.bitNumber))
                      ? current.rightChild
                      : current.leftChild;
    }
 
    newNode = new CompressedNode();
    newNode.bitNumber = i;
    newNode.data = ele;
    newNode.leftChild = bit(ele, i) ? current : newNode;
    newNode.rightChild = bit(ele, i) ? newNode : current;
 
    if (current == parent.leftChild)
        parent.leftChild = newNode;
    else
        parent.rightChild = newNode;
 
    return t;
}

# Function to implement the insert
# functionality in the trie
def insert( t, ele):
    # If Node is None
    if (t == None) :
        t = CompressedNode()
        t.bitNumber = 0
        t.data = ele
        t.leftChild = t
        t.rightChild = None
        return t
     
 
    # Search the key ele
    lastNode = search(t, ele)
 
    # If already present key
    if (ele == lastNode.data) :
        print(
            "Error : key is already present")
        return t
     
    i=1
    while(bit(ele, i) == bit(lastNode.data, i)):
        i+=1
         
 
    current = t.leftChild
    parent = t
    while (current.bitNumber > parent.bitNumber and current.bitNumber < i) :
        parent = current
        current = current.rightChild if (bit(ele, current.bitNumber)) else current.leftChild
 
    newNode = CompressedNode()
    newNode.bitNumber = i
    newNode.data = ele
    newNode.leftChild = current if bit(ele, i) else newNode
    newNode.rightChild = newNode if bit(ele, i) else current
 
    if (current == parent.leftChild):
        parent.leftChild = newNode
    else:
        parent.rightChild = newNode
 
    return t

A continuación se muestra el programa para implementar todas las funciones del Trie comprimido:

// Java program to implement the
// Compressed Trie
 
class Trie {
 
    // Root Node
    private final Node root = new Node(false);
 
    // 'a' for lower, 'A' for upper
    private final char CASE;
 
    // Default case
    public Trie() { CASE = 'a'; }
 
    // Constructor accepting the
    // starting symbol
    public Trie(char CASE)
    {
        this.CASE = CASE;
    }
 
    // Function to insert a word in
    // the compressed trie
    public void insert(String word)
    {
        // Store the root
        Node trav = root;
        int i = 0;
 
        // Iterate i less than word
        // length
        while (i < word.length()
               && trav.edgeLabel[word.charAt(i) - CASE]
                      != null) {
 
            // Find the index
            int index = word.charAt(i) - CASE, j = 0;
            StringBuilder label = trav.edgeLabel[index];
 
            // Iterate till j is less
            // than label length
            while (j < label.length() && i < word.length()
                   && label.charAt(j) == word.charAt(i)) {
                ++i;
                ++j;
            }
 
            // If is the same as the
            // label length
            if (j == label.length()) {
                trav = trav.children[index];
            }
            else {
 
                // Inserting a prefix of
                // the existing word
                if (i == word.length()) {
                    Node existingChild
                        = trav.children[index];
                    Node newChild = new Node(true);
                    StringBuilder remainingLabel
                        = strCopy(label, j);
 
                    // Making "facebook"
                    // as "face"
                    label.setLength(j);
 
                    // New node for "face"
                    trav.children[index] = newChild;
                    newChild
                        .children[remainingLabel.charAt(0)
                                  - CASE]
                        = existingChild;
                    newChild
                        .edgeLabel[remainingLabel.charAt(0)
                                   - CASE]
                        = remainingLabel;
                }
                else {
 
                    // Inserting word which has
                    // a partial match with
                    // existing word
                    StringBuilder remainingLabel
                        = strCopy(label, j);
 
                    Node newChild = new Node(false);
                    StringBuilder remainingWord
                        = strCopy(word, i);
 
                    // Store the trav in
                    // temp node
                    Node temp = trav.children[index];
 
                    label.setLength(j);
                    trav.children[index] = newChild;
                    newChild
                        .edgeLabel[remainingLabel.charAt(0)
                                   - CASE]
                        = remainingLabel;
                    newChild
                        .children[remainingLabel.charAt(0)
                                  - CASE]
                        = temp;
                    newChild
                        .edgeLabel[remainingWord.charAt(0)
                                   - CASE]
                        = remainingWord;
                    newChild
                        .children[remainingWord.charAt(0)
                                  - CASE]
                        = new Node(true);
                }
 
                return;
            }
        }
 
        // Insert new node for new word
        if (i < word.length()) {
            trav.edgeLabel[word.charAt(i) - CASE]
                = strCopy(word, i);
            trav.children[word.charAt(i) - CASE]
                = new Node(true);
        }
        else {
 
            // Insert "there" when "therein"
            // and "thereafter" are existing
            trav.isEnd = true;
        }
    }
 
    // Function that creates new String
    // from an existing string starting
    // from the given index
    private StringBuilder strCopy(
        CharSequence str, int index)
    {
        StringBuilder result
            = new StringBuilder(100);
 
        while (index != str.length()) {
            result.append(str.charAt(index++));
        }
 
        return result;
    }
 
    // Function to print the Trie
    public void print()
    {
        printUtil(root, new StringBuilder());
    }
 
    // Function to print the word
    // starting from the given node
    private void printUtil(
        Node node, StringBuilder str)
    {
        if (node.isEnd) {
            System.out.println(str);
        }
 
        for (int i = 0;
             i < node.edgeLabel.length; ++i) {
 
            // If edgeLabel is not
            // NULL
            if (node.edgeLabel[i] != null) {
                int length = str.length();
 
                str = str.append(node.edgeLabel[i]);
                printUtil(node.children[i], str);
                str = str.delete(length, str.length());
            }
        }
    }
 
    // Function to search a word
    public boolean search(String word)
    {
        int i = 0;
 
        // Stores the root
        Node trav = root;
 
        while (i < word.length()
               && trav.edgeLabel[word.charAt(i) - CASE]
                      != null) {
            int index = word.charAt(i) - CASE;
            StringBuilder label = trav.edgeLabel[index];
            int j = 0;
 
            while (i < word.length()
                   && j < label.length()) {
 
                // Character mismatch
                if (word.charAt(i) != label.charAt(j)) {
                    return false;
                }
 
                ++i;
                ++j;
            }
 
            if (j == label.length() && i <= word.length()) {
 
                // Traverse further
                trav = trav.children[index];
            }
            else {
 
                // Edge label is larger
                // than target word
                // searching for "face"
                // when tree has "facebook"
                return false;
            }
        }
 
        // Target word fully traversed
        // and current node is word
        return i == word.length() && trav.isEnd;
    }
 
    // Function to search the prefix
    public boolean startsWith(String prefix)
    {
        int i = 0;
 
        // Stores the root
        Node trav = root;
 
        while (i < prefix.length()
               && trav.edgeLabel[prefix.charAt(i) - CASE]
                      != null) {
            int index = prefix.charAt(i) - CASE;
            StringBuilder label = trav.edgeLabel[index];
            int j = 0;
 
            while (i < prefix.length()
                   && j < label.length()) {
 
                // Character mismatch
                if (prefix.charAt(i) != label.charAt(j)) {
                    return false;
                }
 
                ++i;
                ++j;
            }
 
            if (j == label.length()
                && i <= prefix.length()) {
 
                // Traverse further
                trav = trav.children[index];
            }
            else {
 
                // Edge label is larger
                // than target word,
                // which is fine
                return true;
            }
        }
 
        return i == prefix.length();
    }
}
 
// Node class
class Node {
 
    // Number of symbols
    private final static int SYMBOLS = 26;
    Node[] children = new Node[SYMBOLS];
    StringBuilder[] edgeLabel = new StringBuilder[SYMBOLS];
    boolean isEnd;
 
    // Function to check if the end
    // of the string is reached
    public Node(boolean isEnd)
    {
        this.isEnd = isEnd;
    }
}
 
class GFG {
 
    // Driver Code
    public static void main(String[] args)
    {
        Trie trie = new Trie();
 
        // Insert words
        trie.insert("facebook");
        trie.insert("face");
        trie.insert("this");
        trie.insert("there");
        trie.insert("then");
 
        // Print inserted words
        trie.print();
 
        // Check if these words
        // are present or not
        System.out.println(
            trie.search("there"));
        System.out.println(
            trie.search("therein"));
        System.out.println(
            trie.startsWith("th"));
        System.out.println(
            trie.startsWith("fab"));
    }
}

# Java program to implement the
# Compressed Trie
 
class Trie:
 
    # Root Node
    root = Node(False)
    CASE=''
 
    # Default self.CASE
    def Trie(self, CASE='a') : self.CASE = CASE
     
 
    # Function to insert a word in
    # the compressed trie
    def insert(self,word):
        # Store the root
        trav = root
        i = 0
 
        # Iterate i less than word
        # length
        while (i < word.length() and trav.edgeLabel[word.charAt(i) - self.CASE] is not None) :
 
            # Find the index
            index = ord(word[i]) - ord(self.CASE); j = 0
            label = trav.edgeLabel[index]
 
            # Iterate till j is less
            # than label length
            while (j < len(label) and i < len(word) and label[j] == word[i]) :
                i+=1
                j+=1
             
 
            # If is the same as the
            # label length
            if (j == label.length()) :
                trav = trav.children[index]
             
            else :
 
                # Inserting a prefix of
                # the existing word
                if (i == word.length()) :
                    existingChild = trav.children[index]
                    newChild = Node(True)
                    remainingLabel = strCopy(label, j)
 
                    # Making "facebook"
                    # as "face"
                    label.setLength(j)
 
                    # New node for "face"
                    trav.children[index] = newChild
                    newChild.children[ord(remainingLabel[0])-ord(self.CASE)] = existingChild
                    newChild.edgeLabel[ord(remainingLabel.charAt(0))- ord(self.CASE)] = remainingLabel
                 
                else :
 
                    # Inserting word which has
                    # a partial match with
                    # existing word
                    remainingLabel = strCopy(label, j)
 
                    newChild = Node(False)
                    remainingWord = strCopy(word, i)
 
                    # Store the trav in
                    # temp node
                    temp = trav.children[index]
 
                    trav.children[index] = newChild
                    newChild.edgeLabel[ord(remainingLabel.charAt(0)) - ord(self.CASE)]=remainingLabel
                    newChild.children[ord(remainingLabel.charAt(0)) - ord(self.CASE)]=temp
                    newChild.edgeLabel[ord(remainingWord.charAt(0)) - ord(self.CASE)] = remainingWord
                    newChild.children[ord(remainingWord.charAt(0)) - ord(self.CASE)] = Node(True)
                return
             
         
 
        # Insert new node for new word
        if (i < len(word)):
            trav.edgeLabel[ord(word.charAt(i)) - ord(self.CASE)] = strCopy(word, i)
            trav.children[ord(word.charAt(i)) - ord(self.CASE)] = Node(True)
         
        else :
 
            # Insert "there" when "therein"
            # and "thereafter" are existing
            trav.isEnd = True
         
     
 
    # Function that creates new String
    # from an existing string starting
    # from the given index
    def strCopy(self, str, index):
        result = ''
 
        while (index != len(str)) :
            result+=str.charAt(index)
            index+=1
         
 
        return result
     
 
    # Function to print the word
    # starting from the given node
    def printUtil(self,node, str):
        if (node.isEnd) :
            print(str)
         
 
        for i in range(node.edgeLabel.length):
 
            # If edgeLabel is not
            # None
            if (node.edgeLabel[i] != None) :
                length = len(str)
 
                str = str.append(node.edgeLabel[i])
                printUtil(node.children[i], str)
                str = str.delete(length, str.length())
             
         
     
 
    # Function to search a word
    def search(self,word):
        i = 0
 
        # Stores the root
        trav = root
 
        while (i < len(word) and trav.edgeLabel[ord(word.charAt(i)) - ord(self.CASE)]
                      != None) :
            index = ord(word.charAt(i)) - ord(self.CASE)
            label = trav.edgeLabel[index]
            j = 0
 
            while (i < word.length() and j < label.length()) :
 
                # Character mismatch
                if (word.charAt(i) != label.charAt(j)) :
                    return False
                 
 
                i+=1
                j+=1
             
 
            if (j == len(label) and i <= len(word)) :
 
                # Traverse further
                trav = trav.children[index]
             
            else :
 
                # Edge label is larger
                # than target word
                # searching for "face"
                # when tree has "facebook"
                return False
             
         
 
        # Target word fully traversed
        # and current node is word
        return i == len(word) and trav.isEnd
     
 
    # Function to search the prefix
    def startsWith(self,prefix):
        i = 0
 
        # Stores the root
        trav = root
 
        while (i < prefix.length() and trav.edgeLabel[prefix.charAt(i) - self.CASE]is not None) :
            index = ord(prefix.charAt(i)) - ord(self.CASE)
            label = trav.edgeLabel[index]
            j = 0
 
            while (i < prefix.length() and j < label.length()) :
 
                # Character mismatch
                if (prefix.charAt(i) != label.charAt(j)) :
                    return False
                 
 
                i+=1
                j+=1
             
 
            if (j == len(label) and j<= len(prefix)) :
 
                # Traverse further
                trav = trav.children[index]
             
            else :
 
                # Edge label is larger
                # than target word,
                # which is fine
                return True
             
         
 
        return i == prefix.length()
     
 
 
# Node class
class Node :
 
    def __init__(self):
        # Number of symbols
        self.SYMBOLS = 26
        self.children = [None]*26
        self.edgeLabel = [None]*SYMBOLS
        self.isEnd=False
 
    # Function to check if the end
    # of the string is reached
    def Node(self,isEnd):
        self.isEnd = isEnd
     
 
 
class GFG :
 
    # Driver Code
    if __name__ == '__main__':
        trie = Trie()
 
        # Insert words
        trie.insert("facebook")
        trie.insert("face")
        trie.insert("this")
        trie.insert("there")
        trie.insert("then")
 
        # Print inserted words
        trie.print()
 
        # Check if these words
        # are present or not
        print(
            trie.search("there"))
        print(
            trie.search("therein"))
        print(
            trie.startsWith("th"))
        print(
            trie.startsWith("fab"))

face
facebook
then
there
this
true
false
true
false