ZipTrie.hpp File Reference

Defines the ZipTrie class, a dynamic, ranked trie structure for efficient string storage and prefix operations. More...

#include "BitString.cuh"
#include <compare>
#include <limits>
#include <vector>
#include <cmath>
#include <random>
#include <fstream>
#include <optional>
#include <string>
#include <type_traits>
#include <ostream>
#include <algorithm>
#include <iostream>

Include dependency graph for ZipTrie.hpp:

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Classes
struct	MemoryEfficientLCP
	Represents an approximate Longest Common Prefix (LCP) length in a memory-efficient format. More...
struct	GeometricRank
	Represents a rank used in zip-zip trees, typically generated randomly for balancing. More...
class	ZipTrie< CHAR_T, MEMORY_EFFICIENT, RANK_T, CHAR_SIZE_BITS >
	Implements a zip trie, a data structure combining properties of tries and zip trees for storing strings efficiently. More...
struct	ZipTrie< CHAR_T, MEMORY_EFFICIENT, RANK_T, CHAR_SIZE_BITS >::SearchResults
	Holds the results returned by a search operation (search method). More...
struct	ZipTrie< CHAR_T, MEMORY_EFFICIENT, RANK_T, CHAR_SIZE_BITS >::AncestorLCPs
	Stores the Longest Common Prefix (LCP) values associated with the path from the root down to a node's parent. More...
struct	ZipTrie< CHAR_T, MEMORY_EFFICIENT, RANK_T, CHAR_SIZE_BITS >::Bucket
	Represents a single node (bucket) within the ZipTrie's internal storage. More...
struct	ZipTrie< CHAR_T, MEMORY_EFFICIENT, RANK_T, CHAR_SIZE_BITS >::ComparisonResult
	Holds the result of comparing a search/insert key x with a node v's key, considering the context of ancestor LCPs. More...

Detailed Description

Defines the ZipTrie class, a dynamic, ranked trie structure for efficient string storage and prefix operations.

This file contains the definition of the ZipTrie template class and its associated helper structs (MemoryEfficientLCP, GeometricRank). A ZipTrie combines properties of tries (prefix sharing) and zip trees (rank-based balancing using "zips") to store keys (represented by BitString) efficiently while aiming for logarithmic expected depth for operations like insertion and search. Navigation relies heavily on comparing keys based on their Longest Common Prefix (LCP) with ancestor paths, providing significant speedups compared to character-by-character comparisons deep within the trie.

Definition in file ZipTrie.hpp.