Implementación Trie en Python

1. Trie estructura de datos en Python
2. Insertar una cadena en un Trie en Python
3. Buscar un elemento en un Trie en Python
4. Implementación Trie en Python

Los intentos son las estructuras de datos que usamos para almacenar cadenas. Nos permiten buscar cadenas de texto de la manera más eficiente posible.

Este artículo discutirá cómo podemos implementar un Trie en Python.

Trie estructura de datos en Python

Puede considerar un Trie como un árbol donde cada nodo consta de un carácter. Cada nodo tiene uno o más hijos dependiendo de si es un carácter interno de una cadena o el último carácter.

El nodo que representa el último carácter de una cadena no tiene hijos y marca el final de la cadena. Incluiremos una variable indicadora en la definición de clase para marcar el final de una cadena.

Cada nodo en Trie puede tener un máximo de 26 hijos si almacenamos cadenas que consisten solo en letras minúsculas en inglés. Si las cadenas tienen caracteres distintos de los alfabetos, el número máximo de hijos de un nodo en particular es igual al número total de caracteres distintos.

Puede definir una clase de Nodo en Python para implementar un nodo de Trie, como se muestra en el siguiente ejemplo.

class Node:
    def __init__(self):
        self.children = []
        for i in range(26):
            self.children.append(None)
        self.isLeafNode = False

Aquí, creamos una lista llamada niños utilizada para definir si un personaje es o no un hijo del nodo actual. Como consideramos 26 caracteres, inicializamos la lista con 26 valores Ninguno.

Si un carácter no es hijo del nodo actual, su posición contendrá el valor Ninguno. De lo contrario, la posición correspondiente a ese carácter almacena el nodo para ese carácter.

Al insertar caracteres en la lista de hijos, almacenamos los nodos hijos en el orden alfabético de los caracteres. En otras palabras, el nodo hijo de la letra a se almacenará en el índice 0, el nodo hijo de la letra b se almacenará en el índice 1, etc.

Después de crear un nodo, necesitamos crear una clase para definir un Trie. En la clase, definiremos un nodo vacío con una lista que contiene 26 valores Ninguno para representar los 26 caracteres del alfabeto inglés.

Llamaremos al Nodo vacío el nodo raíz.

class Trie:
    def __init__(self):
        self.root = Node()

Cada vez que se inserta una cadena en el Trie, el nodo que representa el primer carácter de la cadena se convierte en el hijo del nodo raíz. Tenga en cuenta que almacenaremos los nodos que contengan los siguientes caracteres de las cadenas como elementos de lista según su posición.

Después de crear el nodo raíz, implementaremos los métodos para insertar una palabra en el Trie y buscar una palabra en el Trie en las siguientes secciones.

Insertar una cadena en un Trie en Python

Para insertar un carácter en el Trie, primero encontraremos la longitud de la cadena que se va a insertar. Después de eso, comenzaremos a rastrear el Trie desde el nodo raíz del Trie.

El siguiente es el algoritmo para insertar una cadena en el Trie:

1. Calcule la longitud de la cuerda que se insertará en el Trie. Guárdelo en una variable strLen.
2. Tome una variable rastreador y asigne el nodo raíz del Trie a la variable.
3. Si está en el nivel n, compruebe si el carácter n de la cadena está presente en ese nivel en el Trie. En caso afirmativo, almacene su posición en la lista de hijos en una variable posición; luego, vaya a 5; de lo contrario, vaya a 4.
4. Cree un nuevo nodo para el Trie y asígnelo al índice posición del rastreador.
5. Mueva el rastreador al siguiente nivel.
6. Comprobar si hemos llegado al final de la cadena; en caso afirmativo, vaya a 7; de lo contrario, vaya a 3.
7. Marque el nodo actual como el final de la cadena.

Habiendo discutido el algoritmo, implementemos ahora este algoritmo para insertar una cadena en un Trie en Python.

def insert(self, input_str):
    strLen = len(input_str)
    crawler = self.root
    for level in range(strLen):
        character = input_str[level]
        position = ord(character) - ord("a")
        if crawler.children[position] is None:
            crawler.children[position] = Node()
        crawler = crawler.children[position]
    crawler.isLeafNode = True

Buscar un elemento en un Trie en Python

Para buscar si una cadena está presente en un Trie o no, usaremos el siguiente algoritmo.

1. Inicialice una variable crawler y asigne el nodo raíz del Trie a la variable.
2. Calcular la longitud de la cadena a buscar en el Trie. Guárdelo en una variable strLen.
3. En un nivel n, busque si el carácter n de la cadena está presente en la lista de hijos. En caso afirmativo, pase a 4; de lo contrario, devuelve False.
4. Compruebe si el nodo actual es un nodo hoja. En caso afirmativo, devuelva True; de lo contrario, incremente n y vaya a 3.

Hemos definido el algoritmo para buscar una cadena en un Trie. Implementémoslo en Python.

def search(self, input_str):
    crawler = self.root
    strLen = len(input_str)
    for level in range(strLen):
        character = input_str[level]
        position = ord(character) - ord("a")
        if crawler.children[position] is None:
            return False
        crawler = crawler.children[position]
    return crawler.isLeafNode

Implementación Trie en Python

Como hemos implementado los métodos para las operaciones de búsqueda e inserción en un Trie en Python, ejecutemos el código usando algunas operaciones de ejemplo.

class Node:
    def __init__(self):
        self.children = []
        for i in range(26):
            self.children.append(None)
        self.isLeafNode = False


class Trie:
    def __init__(self):
        self.root = Node()

    def insert(self, input_str):
        strLen = len(input_str)
        crawler = self.roothave
        for level in range(strLen):
            character = input_str[level]
            position = ord(character) - ord("a")
            if crawler.children[position] is None:
                crawler.children[position] = Node()
            crawler = crawler.children[position]
        crawler.isLeafNode = True

    def search(self, input_str):
        crawler = self.root
        strLen = len(input_str)
        for level in range(strLen):
            character = input_str[level]
            position = ord(character) - ord("a")
            if crawler.children[position] is None:
                return False
            crawler = crawler.children[position]
        return crawler.isLeafNode


x = Trie()
myStr = "aditya"
print("Inserting the string:", myStr)
x.insert(myStr)
myStr = "delftstack"
print("Inserting the string:", myStr)
x.insert(myStr)
myStr = "aaditya"
print("Inserting the string:", myStr)
x.insert(myStr)
print("aditya is present in the trie:", x.search("aditya"))
print("delftstack is present in the trie:", x.search("delftstack"))
print("python is present in the trie:", x.search("python"))

Producción :

Inserting the string: aditya
Inserting the string: delftstack
Inserting the string: aaditya
aditya is present in the trie: True
delftstack is present in the trie: True
python is present in the trie: False

Primero implementamos un Trie en Python usando los algoritmos discutidos anteriormente en este ejemplo. Después de eso, insertamos tres cuerdas, aditya, delftstack y aaditya en el Trie.

Luego, realizamos operaciones de búsqueda en el Trie para comprobar si las cadenas aditya, delftstack y python estaban presentes en el Trie o no. Puede observar la salida en el ejemplo.