synthetic.hpp File Reference

Provides utilities for generating synthetic string datasets for benchmark testing. More...

#include <string>
#include <vector>

Include dependency graph for synthetic.hpp:

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

Go to the source code of this file.

Functions
std::string	get_random_word (size_t length) noexcept
	Generates a random string of specified length.
std::vector< std::string >	get_random_words (size_t length, size_t num_words, double mean_lcp_length) noexcept
	Generates a collection of random strings with controlled commonality.

Detailed Description

Provides utilities for generating synthetic string datasets for benchmark testing.

This file contains functions for generating random strings with controllable properties such as length, quantity, and shared prefix length. These synthetic datasets are used for benchmarking various trie implementations under controlled conditions.

The implementation uses a diverse alphabet containing lowercase letters, uppercase letters, digits, and special characters to generate strings with randomized content.

See also

BitString.cuh

SkipTrie.hpp

ParallelSkipTrie.cuh

Definition in file synthetic.hpp.

Function Documentation

get_random_word()

std::string get_random_word ( size_t  length )

noexcept

Generates a random string of specified length.

Creates a string using characters from a predefined alphabet containing lowercase letters, uppercase letters, digits, and special characters. Each character is selected independently using a uniform random distribution.

The implementation uses C++'s standard random number facilities (std::mt19937) with either a random seed or an optional fixed seed for reproducible results.

Parameters

length

The desired length of the random string.

Returns

std::string A newly generated random string.

See also

get_random_words()

Generates a random string of specified length.

Generates a random string of specified length using characters from the ALPHABET. The implementation uses a static random number generator (std::mt19937) initialized with either a random seed from std::random_device or an optional fixed seed for reproducible results.

Each character in the string is selected independently using a uniform distribution over the entire alphabet, ensuring equal probability for all characters.

Parameters

length

The desired length of the random string.

Returns

std::string A newly generated random string of the specified length.

See also

synthetic.hpp for the function declaration and additional documentation.

Definition at line 59 of file synthetic.cpp.

{
    // Use a static random device for initialization of the generator
    static std::random_device rd;
    // Uncomment for deterministic generation with fixed seed:
    // static std::mt19937 gen(0);
    // Use random seed for non-deterministic generation
    static std::mt19937 gen(rd());
 
    // Create uniform distribution for selecting characters from the alphabet
    std::uniform_int_distribution<size_t> dis(0, ALPHABET.size() - 1);
 
    // Pre-allocate string of requested length
    std::string str(length, '\0');
    // Fill the string with randomly selected characters from the alphabet
    std::generate_n(str.begin(), length, [&] { return ALPHABET[dis(gen)]; });
 
    return str;
}

get_random_words()

std::vector< std::string > get_random_words ( size_t  length, size_t  num_words, double  mean_lcp_length  )

noexcept

Generates a collection of random strings with controlled commonality.

Creates a set of random strings where each string has a specified length, and pairs of strings are likely to share a common prefix of a length drawn from a Poisson distribution with the specified mean. To ensure uniqueness, each string includes a unique signature at the end.

The generated dataset has the following specific properties:

1. Each string has the exact same length (specified by 'length' parameter)
2. Each string has a unique signature at the end to ensure uniqueness
3. Strings share common prefixes with lengths following a Poisson distribution

The algorithm first generates random words, then adds unique signatures, and finally creates controlled common prefixes between the strings. The unique signatures are created by encoding the string's index as a base-N number, where N is the alphabet size. The length of this signature is calculated to ensure all strings can have a unique value.

This function is particularly useful for benchmarking trie data structures with controlled LCP (Longest Common Prefix) distributions.

Parameters

length	The length of each string to generate.
num_words	The number of strings to generate.
mean_lcp_length	The mean length of the Longest Common Prefix (LCP) between strings.

Returns

std::vector<std::string> A vector containing the generated strings.

See also

get_random_word()

Generates a collection of random strings with controlled commonality.

Generates a collection of random strings with controlled Longest Common Prefix (LCP) properties. The implementation follows these steps:

1. Generate num_words random strings of the specified length.
2. Calculate the minimum signature length needed to ensure uniqueness.
3. Add a unique signature at the end of each string by encoding its index.
4. For each string, generate a random LCP length from a Poisson distribution.
5. Replace part of each string to create the desired LCP pattern while preserving the unique signature.

The Poisson distribution ensures that the LCP lengths follow a realistic distribution with the specified mean, while the unique signatures guarantee that all strings remain distinct regardless of the LCP modifications.

Parameters

length	The length of each string to generate.
num_words	The number of strings to generate.
mean_lcp_length	The mean length of the Longest Common Prefix between strings.

Returns

std::vector<std::string> A vector containing the generated strings.

See also

synthetic.hpp for the function declaration and additional documentation.

Definition at line 100 of file synthetic.cpp.

{
    // Use Poisson distribution to generate varying LCP lengths with specified mean
    static std::random_device rd;
    // Uncomment for deterministic generation with fixed seed:
    // static std::mt19937 gen(0);
    // Use random seed for non-deterministic generation
    static std::mt19937 gen(rd());
 
    // Create distribution for common prefix lengths
    std::poisson_distribution<size_t> dis(mean_lcp_length);
 
    // Initialize vector with completely random words of specified length
    std::vector<std::string> words(num_words, get_random_word(length));
 
    // Calculate required signature length to ensure uniqueness
    // The length must satisfy: alphabet_size^signature_length > num_words
    // Using logarithm properties: signature_length > log(num_words)/log(alphabet_size)
    unsigned signature_length = std::ceil(std::log(num_words) / std::log(ALPHABET.size()));
 
    for (size_t i = 0; i < num_words; ++i)
    {
        auto& word = words[i];
 
        // Create a unique signature at the end of each word
        // This encodes the index i as a base-ALPHABET.size() number
        size_t i_copy = i;
        for (size_t j = 0; j < signature_length; ++j)
        {
            word[j + length - signature_length] = ALPHABET[i_copy % ALPHABET.size()];
            i_copy /= ALPHABET.size();
        }
 
        // Generate a random LCP length from the Poisson distribution
        size_t difference = dis(gen);
 
        // Skip modification if the difference would affect the unique signature
        if (difference >= length - signature_length)
        {
            continue;
        }
 
        // Generate a new random substring to replace part of the word
        // This creates varying common prefix lengths between words
        std::string random_word = get_random_word(length - difference - signature_length);
        std::copy(random_word.begin(), random_word.end(), word.begin() + difference);
    }
 
    return words;
}