tries

intentos

Esta clase proporciona la base para construir un contenedor basado en TRIE.

En su forma básica, la clase TTRIE se puede usar para almacenar elementos de datos basados en 16, 32 y 64 bits.

La estructura proporciona una implementación de TRIE de profundidad fija, que a su vez, hace que el mismo tiempo para encontrar, eliminar y agregar nodos.

El orden de la estructura es o (d) donde D es la profundidad del trie, que depende si se construye para almacenar valores de 16, 32 o 64 bits. Para 16 bits d = 4 para 32 bits d = 8 y para 64 bits d = 16

Para mantener el tamaño del nodo pequeño, solo se utilizarán 16 ramas por nodo y los indicadores de indicadores y los índices internos del puntero están codificados en una palabra de 16 bits y en un entero de 64 bits.

Los punteros a las ramas se manejan dinámicamente, por lo que solo se asigna un puntero en la matriz de punteros cuando se necesita agregar una nueva rama, esto minimiza el desperdicio de matriz de punteros pre-asignados a ramas de nivel inferior. Sin embargo, se desacelere.

Las hojas se asignan en el lugar en lugar de los nodos individuales apuntados por el último nodo de rama.

Finalmente, los nodos de hoja pueden controlarse dinámicamente por la clase derivada de TTRIE, lo que permite una fácil implementación de diccionarios que usan TTRIE como base.

En general, hacer algunas pruebas que almacenan memoria asignada por el asignador de Lázaro (Freepascal) en una MAC representa alrededor del 40% de eficiencia de almacenamiento en proporción al tamaño de los objetos almacenados, lo que no es malo dado el rendimiento para agregar, encontrar y eliminar operaciones.

La clase también proporciona un método de paquete que se utiliza para mantener el almacenamiento bajo control cuándo se han emitido muchos retirados.

Tintegerhashtrie y Tstringhashtrie se proporcionan como descendientes de la clase genérica Thashtrie. Thashtrie tiene dos modos de operación:

• Use la tabla hash para el nodo raíz, con estructura Trie con 16 nodos por cubo para el siguiente nivel
• Estructura de hashtrie completa del nodo raíz

La tabla hash proporciona un mejor rendimiento, por supuesto, pero Hashtrie tiene una huella de memoria más eficiente al almacenar una pequeña cantidad de elementos.

Probado TStringhashtrie contra las clases de Diccionario de Tdiccionario de Delphi <> y C# Dictionary <>.

Tstringhashtrie vence a las implementaciones de C# y Delphi. La diferencia es mayor cuando se usa tabla hash para el nodo raíz.

La huella de memoria en general para cargas grandes también es mejor, que varía de 30% -40% mejor. Para un pequeño número de elementos, definitivamente, utilizando Hashtrie Pure en lugar del nodo de raíz de tabla hash usará dramáticamente menos memoria.

Las pruebas compiladas en Delphi 2007 produjeron resultados aún mejores porque las cadenas no tuvieron que someterse a una conversión de UTF16 a ANSI antes de insertar en la estructura.

TStringhashtrie Support Unicode en forma UTF8.