c++ - ingles - trie significado
Implementación de Trie (12)
¿Hay implementaciones de trie con rapidez y caché en C / C ++? Sé lo que es un trie, pero no quiero reinventar la rueda, implementarlo yo mismo.
Compartiendo mi implementación "rápida" para Trie, probada solo en el escenario básico:
#define ENG_LET 26
class Trie {
class TrieNode {
public:
TrieNode* sons[ENG_LET];
int strsInBranch;
bool isEndOfStr;
void print() {
cout << "----------------" << endl;
cout << "sons..";
for(int i=0; i<ENG_LET; ++i) {
if(sons[i] != NULL)
cout << " " << (char)(''a''+i);
}
cout << endl;
cout << "strsInBranch = " << strsInBranch << endl;
cout << "isEndOfStr = " << isEndOfStr << endl;
for(int i=0; i<ENG_LET; ++i) {
if(sons[i] != NULL)
sons[i]->print();
}
}
TrieNode(bool _isEndOfStr = false):isEndOfStr(_isEndOfStr), strsInBranch(0) {
for(int i=0; i<ENG_LET; ++i) {
sons[i] = NULL;
}
}
~TrieNode() {
for(int i=0; i<ENG_LET; ++i) {
delete sons[i];
sons[i] = NULL;
}
}
};
TrieNode* head;
public:
Trie() { head = new TrieNode();}
~Trie() { delete head; }
void print() {
cout << "Preorder Print : " << endl;
head->print();
}
bool isExists(const string s) {
TrieNode* curr = head;
for(int i=0; i<s.size(); ++i) {
int letIdx = s[i]-''a'';
if(curr->sons[letIdx] == NULL) {
return false;
}
curr = curr->sons[letIdx];
}
return curr->isEndOfStr;
}
void addString(const string& s) {
if(isExists(s))
return;
TrieNode* curr = head;
for(int i=0; i<s.size(); ++i) {
int letIdx = s[i]-''a'';
if(curr->sons[letIdx] == NULL) {
curr->sons[letIdx] = new TrieNode();
}
++curr->strsInBranch;
curr = curr->sons[letIdx];
}
++curr->strsInBranch;
curr->isEndOfStr = true;
}
void removeString(const string& s) {
if(!isExists(s))
return;
TrieNode* curr = head;
for(int i=0; i<s.size(); ++i) {
int letIdx = s[i]-''a'';
if(curr->sons[letIdx] == NULL) {
assert(false);
return; //string not exists, will not reach here
}
if(curr->strsInBranch==1) { //just 1 str that we want remove, remove the whole branch
delete curr;
return;
}
//more than 1 son
--curr->strsInBranch;
curr = curr->sons[letIdx];
}
curr->isEndOfStr = false;
}
void clear() {
for(int i=0; i<ENG_LET; ++i) {
delete head->sons[i];
head->sons[i] = NULL;
}
}
};
GCC se envía con un puñado de estructuras de datos como parte de sus "estructuras de datos basadas en políticas". Esto incluye unas pocas implementaciones.
http://gcc.gnu.org/onlinedocs/libstdc++/ext/pb_ds/trie_based_containers.html
He obtenido muy buenos resultados (muy buen equilibrio entre rendimiento y tamaño) con marisa-trie en comparación con varias implementaciones de TRIE mencionadas con mi conjunto de datos.
He tenido buena suerte con libTrie . Puede que no sea específicamente caché optimizado, pero el rendimiento siempre ha sido decente para mis aplicaciones.
Las optimizaciones de caché son algo que probablemente tendrá que hacer, porque tendrá que ajustar los datos en una sola línea de caché, que generalmente es algo así como 64 bytes (lo que probablemente funcionará si comienza a combinar datos, como punteros). . Pero es complicado :-)
Me di cuenta de que la pregunta era sobre implementaciones listas, pero para referencia ...
Antes de saltar sobre Judy, debería haber leído " Comparación de rendimiento de Judy con tablas hash ". Luego, buscar en Google el título probablemente le dará toda una vida de discusión y reconstrucciones para leer.
El único que conozco explícitamente en memoria caché es el HAT-trie .
El HAT-trie, cuando se implementa correctamente, es muy bueno. Sin embargo, para la búsqueda de prefijos, necesita un paso de clasificación en los intervalos de hash, lo que de alguna manera choca con la idea de una estructura de prefijo.
Un trie algo más simple es el burst-trie que esencialmente le da una interpolación entre un árbol estándar de algún tipo (como un BST) y un trie. Me gusta conceptualmente y es mucho más fácil de implementar.
Referencias
- Un artículo de implementación de Double-Array Trie (incluye una implementación de
C) - TRASH - Una estructura de datos LC-trie y hash dinámica - (una referencia en PDF de 2006 que describe un LC-trie dinámico utilizado en el kernel de Linux para implementar la búsqueda de direcciones en la tabla de enrutamiento de IP)
También puede probar TommyDS en http://tommyds.sourceforge.net/
Vea la página de puntos de referencia en el sitio para una comparación de velocidad con nedtries y judy.
si está buscando una implementación de ANSI C, puede "robarla" de FreeBSD. El archivo que está buscando se llama radix.c . Se usa para administrar datos de enrutamiento en kernel.
Burst Trie parece ser un poco más eficiente en el uso del espacio. No estoy seguro de la cantidad de eficiencia de caché que puede obtener de cualquier índice, ya que los cachés de CPU son muy pequeños. Sin embargo, este tipo de trie es lo suficientemente compacto como para mantener grandes conjuntos de datos en RAM (donde un Trie normal no lo haría).
Escribí una implementación de Scala de un trie de ráfaga que también incorpora algunas técnicas de ahorro de espacio que encontré en la implementación de escritura anticipada de GWT.
Matrices de Judy : matrices dinámicas dispersas, ordenadas y muy rápidas para bits, enteros y cadenas. Las matrices de Judy son más rápidas y más eficientes en cuanto a la memoria que cualquier árbol de búsqueda binaria (incluidos los árboles avl y red-black-trees).