Requisito previo:
Trie es una estructura de datos útil que a menudo entra en juego cuando se realizan búsquedas de strings múltiples. En esta publicación, presentaremos el concepto de persistencia en esta estructura de datos. La persistencia simplemente significa retener los cambios. Pero, obviamente, retener los cambios provoca un consumo adicional de memoria y, por lo tanto, afecta la complejidad del tiempo.
Nuestro objetivo es aplicar la persistencia en Trie y también asegurarnos de que no se necesita más que la búsqueda de trie estándar, es decir , O(length_of_key) . También analizaremos la complejidad espacial adicional que provoca la persistencia sobre la complejidad espacial estándar de un Trie.
Pensemos en términos de versiones, es decir, para cada cambio/inserción en nuestro Trie creamos una nueva versión del mismo.
Consideraremos que nuestra versión inicial es la Versión-0. Ahora, a medida que hacemos cualquier inserción en el trie, crearemos una nueva versión para él y, de manera similar, realizaremos un seguimiento del registro para todas las versiones.
Pero crear todo el intento cada vez para cada versión sigue duplicando la memoria y afecta gravemente a la Complejidad espacial. Por lo tanto, esta idea fácilmente se quedará sin memoria para una gran cantidad de versiones.
Aprovechemos el hecho de que para cada nueva inserción en el trie, se visitarán/modificarán exactamente X (longitud_de_clave) Nodes. Por lo tanto, nuestra nueva versión solo contendrá estos X nuevos Nodes y el resto de los Nodes trie serán los mismos que la versión anterior. Por lo tanto, está bastante claro que para cada nueva versión solo necesitamos crear estos X nuevos Nodes, mientras que el resto de los trie Nodes se pueden compartir de la versión anterior.
Considere la siguiente figura para una mejor visualización:
Ahora, surge la Pregunta: ¿Cómo hacer un seguimiento de todas las versiones?
Solo necesitamos realizar un seguimiento del primer Node raíz para todas las versiones y esto servirá para realizar un seguimiento de todos los Nodes recién creados en las diferentes versiones, ya que el Node raíz nos brinda el punto de entrada para esa versión en particular. Para este propósito, podemos mantener una array de punteros al Node raíz del trie para todas las versiones.
Consideremos el siguiente escenario y veamos cómo podemos usar Persistent Trie para resolverlo.
Dada una array de strings, necesitamos determinar si existe una string en algún
rango [l, r] en la array. Para tener una analogía, considere que la array es una
lista de palabras en un diccionario en la i-ésima página (i es el índice de la array) y
necesitamos determinar si una palabra dada X existe en el rango de páginas [l, r]?
A continuación se muestra la implementación del problema anterior: –
C++
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
// Distinct numbers of chars in key
const int sz = 26;
// Persistent Trie node structure
struct PersistentTrie {
// Stores all children nodes, where ith children denotes
// ith alphabetical character
vector<PersistentTrie*> children;
// Marks the ending of the key
bool keyEnd = false;
// Constructor 1
PersistentTrie(bool keyEnd = false)
{
this->keyEnd = keyEnd;
}
// Constructor 2
PersistentTrie(vector<PersistentTrie*>& children, bool keyEnd = false)
{
this->children = children;
this->keyEnd = keyEnd;
}
// detects existence of key in trie
bool findKey(string& key, int len);
// Inserts key into trie
// returns new node after insertion
PersistentTrie* insert(string& key, int len);
};
// Dummy PersistentTrie node
PersistentTrie* dummy;
// Initialize dummy for easy implementation
void init()
{
dummy = new PersistentTrie(true);
// All children of dummy as dummy
vector<PersistentTrie*> children(sz, dummy);
dummy->children = children;
}
// Inserts key into current trie
// returns newly created trie node after insertion
PersistentTrie* PersistentTrie::insert(string& key, int len)
{
// If reached the end of key string
if (len == key.length()) {
// Create new trie node with current trie node
// marked as keyEnd
return new PersistentTrie((*this).children, true);
}
// Fetch current child nodes
vector<PersistentTrie*> new_version_PersistentTrie = (*this).children;
// Insert at key[len] child and
// update the new child node
PersistentTrie* tmpNode = new_version_PersistentTrie[key[len] - 'a'];
new_version_PersistentTrie[key[len] - 'a'] = tmpNode->insert(key, len + 1);
// Return a new node with modified key[len] child node
return new PersistentTrie(new_version_PersistentTrie);
}
// Returns the presence of key in current trie
bool PersistentTrie::findKey(string& key, int len)
{
// If reached end of key
if (key.length() == len)
// Return if this is a keyEnd in trie
return this->keyEnd;
// If we cannot find key[len] child in trie
// we say key doesn't exist in the trie
if (this->children[key[len] - 'a'] == dummy)
return false;
// Recursively search the rest of
// key length in children[key] trie
return this->children[key[len] - 'a']->findKey(key, len + 1);
}
// dfs traversal over the current trie
// prints all the keys present in the current trie
void printAllKeysInTrie(PersistentTrie* root, string& s)
{
int flag = 0;
for (int i = 0; i < sz; i++) {
if (root->children[i] != dummy) {
flag = 1;
s.push_back('a' + i);
printAllKeysInTrie(root->children[i], s);
s.pop_back();
}
}
if (flag == 0 and s.length() > 0)
cout << s << endl;
}
// Driver code
int main(int argc, char const* argv[])
{
// Initialize the PersistentTrie
init();
// Input keys
vector<string> keys({ "goku", "gohan", "goten", "gogeta" });
// Cache to store trie entry roots after each insertion
PersistentTrie* root[keys.size()];
// Marking first root as dummy
root[0] = dummy;
// Inserting all keys
for (int i = 1; i <= keys.size(); i++) {
// Caching new root for ith version of trie
root[i] = root[i - 1]->insert(keys[i - 1], 0);
}
int idx = 3;
cout << "All keys in trie after version - " << idx << endl;
string key = "";
printAllKeysInTrie(root[idx], key);
string queryString = "goku";
int l = 2, r = 3;
cout << "range : "
<< "[" << l << ", " << r << "]" << endl;
if (root[r]->findKey(queryString, 0) and !root[l - 1]->findKey(queryString, 0))
cout << queryString << " - exists in above range" << endl;
else
cout << queryString << " - does not exist in above range" << endl;
queryString = "goten";
l = 2, r = 4;
cout << "range : "
<< "[" << l << ", " << r << "]" << endl;
if (root[r]->findKey(queryString, 0) and !root[l - 1]->findKey(queryString, 0))
cout << queryString << " - exists in above range" << endl;
else
cout << queryString << " - does not exist in above range" << endl;
return 0;
}
Java
// Java program for the above approach
import java.io.*;
import java.util.*;
// Persistent Trie node structure
class PersistentTrie
{
// Stores all children nodes, where
// ith children denotes ith
// alphabetical character
PersistentTrie[] children;
// Marks the ending of the key
boolean keyEnd = false;
// Constructor 1
PersistentTrie(boolean keyEnd)
{
this.keyEnd = keyEnd;
}
// Constructor 2
PersistentTrie(PersistentTrie[] children,
boolean keyEnd)
{
this.children = children;
this.keyEnd = keyEnd;
}
// Detects existence of key in trie
boolean findKey(String key, int len,
PersistentTrie dummy)
{
// If reached end of key
if (key.length() == len)
// Return if this is a keyEnd in trie
return this.keyEnd;
// If we cannot find key[len] child in trie
// we say key doesn't exist in the trie
if (this.children[key.charAt(len) - 'a'] == dummy)
return false;
// Recursively search the rest of
// key length in children[key] trie
return this.children[key.charAt(len) - 'a'].findKey(
key, len + 1, dummy);
}
// Inserts key into trie
// returns new node after insertion
PersistentTrie insert(String key, int len)
{
// If reached the end of key string
if (len == key.length())
{
// Create new trie node with current trie node
// marked as keyEnd
return new PersistentTrie(this.children.clone(),
true);
}
// Fetch current child nodes
PersistentTrie[] new_version_PersistentTrie
= this.children.clone();
// Insert at key[len] child and
// update the new child node
PersistentTrie tmpNode
= new_version_PersistentTrie[key.charAt(len)
- 'a'];
new_version_PersistentTrie[key.charAt(len) - 'a']
= tmpNode.insert(key, len + 1);
// Return a new node with modified key[len] child
// node
return new PersistentTrie(
new_version_PersistentTrie, false);
}
}
class GFG{
static final int sz = 26;
// Dummy PersistentTrie node
static PersistentTrie dummy;
// Initialize dummy for easy implementation
static void init()
{
dummy = new PersistentTrie(false);
// All children of dummy as dummy
PersistentTrie[] children = new PersistentTrie[sz];
for(int i = 0; i < sz; i++)
children[i] = dummy;
dummy.children = children;
}
// dfs traversal over the current trie
// prints all the keys present in the current trie
static void printAllKeysInTrie(PersistentTrie root,
String s)
{
int flag = 0;
for(int i = 0; i < sz; i++)
{
if (root.children[i] != dummy)
{
flag = 1;
printAllKeysInTrie(root.children[i],
s + ((char)('a' + i)));
}
if (root.children[i].keyEnd)
System.out.println(s + (char)('a' + i));
}
}
// Driver code
public static void main(String[] args)
{
// Initialize the PersistentTrie
init();
// Input keys
List<String> keys = Arrays.asList(new String[]{
"goku", "gohan", "goten", "gogeta" });
// Cache to store trie entry roots after each
// insertion
PersistentTrie[] root
= new PersistentTrie[keys.size() + 1];
// Marking first root as dummy
root[0] = dummy;
// Inserting all keys
for(int i = 1; i <= keys.size(); i++)
{
// Caching new root for ith version of trie
root[i]
= root[i - 1].insert(keys.get(i - 1), 0);
}
int idx = 3;
System.out.println("All keys in trie " +
"after version - " + idx);
String key = "";
printAllKeysInTrie(root[3], key);
String queryString = "goku";
int l = 2, r = 3;
System.out.println("range : " + "[" + l +
", " + r + "]");
if (root[r].findKey(queryString, 0, dummy) &&
!root[l - 1].findKey(queryString, 0, dummy))
System.out.println(queryString +
" - exists in above range");
else
System.out.println(queryString +
" - does not exist in " +
"above range");
queryString = "goten";
l = 2;
r = 4;
System.out.println("range : " + "[" + l +
", " + r + "]");
if (root[r].findKey(queryString, 0, dummy) &&
!root[l - 1].findKey(queryString, 0, dummy))
System.out.println(queryString +
" - exists in above range");
else
System.out.println(queryString +
" - does not exist in above range");
}
}
// This code is contributed by jithin
All keys in trie after version - 3 gohan goku goten range : [2, 3] goku - does not exist in above range range : [2, 4] goten - exists in above range
Complejidad de tiempo: como se discutió anteriormente, visitaremos todos los X (longitud de la clave) número de Nodes en el trie mientras se inserta; Por lo tanto, estaremos visitando el número X de estados y en cada estado haremos una cantidad de trabajo de O (sz) al dar me gusta a los hijos sz de la versión anterior con la versión actual para los Nodes trie recién creados. Por lo tanto, la complejidad del tiempo de inserción se convierte en O(length_of_key * sz) . Pero la búsqueda sigue siendo lineal a lo largo de la longitud de la clave que se va a buscar y, por lo tanto, la complejidad temporal de la búsqueda de una clave sigue siendo O (longitud_de_la_clave) como un intento estándar.
Complejidad espacial:Obviamente, la persistencia en las estructuras de datos viene con un intercambio de espacio y consumiremos más memoria al mantener las diferentes versiones del trie. Ahora, visualicemos el peor de los casos: para la inserción, estamos creando Nodes O (longitud_de_clave) y cada Node recién creado ocupará un espacio de O (sz) para almacenar sus elementos secundarios. Por lo tanto, la complejidad del espacio para la inserción de la implementación anterior es O (longitud_de_clave * sz).