Alphabet Size Considerations

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90

/**
 * Calculate trie density statistics
 * Useful for determining optimal implementation
 */
interface TrieDensityStats {
    totalNodes: number;
    totalChildren: number;
    avgChildrenPerNode: number;
    maxChildren: number;
    minChildren: number;
    alphabetSize: number;
    avgDensity: number;  // avgChildren / alphabetSize
}
 
function analyzeTrieDensity<T extends { children: Map<string, T> }>(
    root: T,
    alphabetSize: number
): TrieDensityStats {
    let totalNodes = 0;
    let totalChildren = 0;
    let maxChildren = 0;
    let minChildren = Infinity;
    
    function traverse(node: T): void {
        totalNodes++;
        const childCount = node.children.size;
        totalChildren += childCount;
        maxChildren = Math.max(maxChildren, childCount);
        if (childCount > 0) {
            minChildren = Math.min(minChildren, childCount);
        }
        
        for (const child of node.children.values()) {
            traverse(child);
        }
    }
    
    traverse(root);
    
    const avgChildrenPerNode = totalChildren / totalNodes;
    const avgDensity = avgChildrenPerNode / alphabetSize;
    
    return {
        totalNodes,
        totalChildren,
        avgChildrenPerNode,
        maxChildren,
        minChildren: minChildren === Infinity ? 0 : minChildren,
        alphabetSize,
        avgDensity
    };
}
 
/**
 * Recommend implementation strategy based on density
 */
function recommendImplementation(stats: TrieDensityStats): string {
    const { avgDensity, alphabetSize } = stats;
    
    // Very small alphabet - array is always fine
    if (alphabetSize <= 4) {
        return "Array: Alphabet is tiny, array overhead negligible";
    }
    
    // Small alphabet with good density - array recommended
    if (alphabetSize <= 26 && avgDensity > 0.2) {
        return "Array: Small alphabet with >20% density makes array efficient";
    }
    
    // Small alphabet but sparse - consider hash map
    if (alphabetSize <= 26 && avgDensity <= 0.2) {
        return "Hash Map or Array: Low density suggests hash map, but array is still reasonable";
    }
    
    // Medium alphabet - hash map usually better
    if (alphabetSize <= 128) {
        if (avgDensity > 0.5) {
            return "Array: High density justifies array for faster access";
        }
        return "Hash Map: Medium alphabet with typical density favors hash map";
    }
    
    // Large alphabet - hash map required
    return `Hash Map: Alphabet size ${alphabetSize} is too large for arrays`;
}
 
// Example usage:
// const stats = analyzeTrieDensity(myTrieRoot, 26);
// console.log("Average density:", (stats.avgDensity * 100).toFixed(1) + "%");
// console.log("Recommendation:", recommendImplementation(stats));

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106

/**
 * Adaptive Trie Node that switches between array and hash map
 * based on actual density observed during operation
 */
class AdaptiveTrieNode {
    private static readonly ARRAY_THRESHOLD = 26; // Max alphabet for array mode
    private static readonly DENSITY_SWITCH_THRESHOLD = 0.4; // Convert to array at 40% density
    
    // Starts in hash map mode
    private mode: 'array' | 'hashmap' = 'hashmap';
    private arrayChildren: (AdaptiveTrieNode | null)[] | null = null;
    private mapChildren: Map<string, AdaptiveTrieNode> = new Map();
    
    isEndOfWord: boolean = false;
    
    /**
     * Get child, works with either storage mode
     */
    getChild(char: string): AdaptiveTrieNode | undefined {
        if (this.mode === 'array') {
            const index = char.charCodeAt(0) - 'a'.charCodeAt(0);
            if (index >= 0 && index < 26) {
                return this.arrayChildren![index] ?? undefined;
            }
            // Fall back to map for out-of-range characters
            return this.mapChildren.get(char);
        }
        return this.mapChildren.get(char);
    }
    
    /**
     * Set child, potentially triggering mode conversion
     */
    setChild(char: string, node: AdaptiveTrieNode): void {
        if (this.mode === 'array') {
            const index = char.charCodeAt(0) - 'a'.charCodeAt(0);
            if (index >= 0 && index < 26) {
                this.arrayChildren![index] = node;
            } else {
                this.mapChildren.set(char, node);
            }
        } else {
            this.mapChildren.set(char, node);
            this.maybeConvertToArray();
        }
    }
    
    /**
     * Check if we should convert from hash map to array
     */
    private maybeConvertToArray(): void {
        // Only consider conversion if alphabet is suitable
        if (this.mode !== 'hashmap') return;
        
        // Count lowercase letter children
        let lowercaseCount = 0;
        let otherCount = 0;
        
        for (const char of this.mapChildren.keys()) {
            const code = char.charCodeAt(0);
            if (code >= 97 && code <= 122) { // 'a' to 'z'
                lowercaseCount++;
            } else {
                otherCount++;
            }
        }
        
        // If mostly lowercase with high density, convert
        const density = lowercaseCount / 26;
        if (otherCount === 0 && density >= AdaptiveTrieNode.DENSITY_SWITCH_THRESHOLD) {
            this.convertToArrayMode();
        }
    }
    
    /**
     * Convert from hash map to array storage
     */
    private convertToArrayMode(): void {
        this.arrayChildren = new Array(26).fill(null);
        
        for (const [char, node] of this.mapChildren) {
            const index = char.charCodeAt(0) - 'a'.charCodeAt(0);
            if (index >= 0 && index < 26) {
                this.arrayChildren[index] = node;
            }
        }
        
        // Keep map for any non-lowercase characters
        const newMap = new Map<string, AdaptiveTrieNode>();
        for (const [char, node] of this.mapChildren) {
            const index = char.charCodeAt(0) - 'a'.charCodeAt(0);
            if (index < 0 || index >= 26) {
                newMap.set(char, node);
            }
        }
        this.mapChildren = newMap;
        this.mode = 'array';
    }
    
    /**
     * Get current mode (useful for debugging/analysis)
     */
    getMode(): 'array' | 'hashmap' {
        return this.mode;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110

/**
 * DNA Sequence Trie - Optimized for 4-character alphabet
 * 
 * Perfect example of array-based implementation for tiny, dense alphabet
 */
class DNATrieNode {
    // Fixed 4-slot array for {A, C, G, T}
    // Index: A=0, C=1, G=2, T=3
    children: (DNATrieNode | null)[] = [null, null, null, null];
    
    // End of sequence marker
    isEndOfSequence: boolean = false;
    
    // Optional: Store sequence ID or metadata
    sequenceId: string | null = null;
    
    private static readonly NUCLEOTIDE_INDEX: Record<string, number> = {
        'A': 0, 'C': 1, 'G': 2, 'T': 3
    };
    
    private static readonly INDEX_TO_NUCLEOTIDE: string[] = ['A', 'C', 'G', 'T'];
    
    getChild(nucleotide: string): DNATrieNode | null {
        const index = DNATrieNode.NUCLEOTIDE_INDEX[nucleotide.toUpperCase()];
        if (index === undefined) {
            throw new Error(`Invalid nucleotide: ${nucleotide}`);
        }
        return this.children[index];
    }
    
    setChild(nucleotide: string, node: DNATrieNode): void {
        const index = DNATrieNode.NUCLEOTIDE_INDEX[nucleotide.toUpperCase()];
        if (index === undefined) {
            throw new Error(`Invalid nucleotide: ${nucleotide}`);
        }
        this.children[index] = node;
    }
    
    *iterateChildren(): Generator<[string, DNATrieNode]> {
        for (let i = 0; i < 4; i++) {
            if (this.children[i] !== null) {
                yield [DNATrieNode.INDEX_TO_NUCLEOTIDE[i], this.children[i]!];
            }
        }
    }
}
 
class DNATrie {
    private root: DNATrieNode = new DNATrieNode();
    
    /**
     * Insert a DNA sequence
     * Time: O(n) where n is sequence length
     * Space: O(n) worst case for new sequences
     */
    insert(sequence: string, sequenceId?: string): void {
        let current = this.root;
        
        for (const nucleotide of sequence.toUpperCase()) {
            if (!current.getChild(nucleotide)) {
                current.setChild(nucleotide, new DNATrieNode());
            }
            current = current.getChild(nucleotide)!;
        }
        
        current.isEndOfSequence = true;
        current.sequenceId = sequenceId ?? null;
    }
    
    /**
     * Find all sequences with a given prefix (e.g., for primer matching)
     */
    findByPrefix(prefix: string): string[] {
        const results: string[] = [];
        let current = this.root;
        
        // Navigate to prefix node
        for (const nucleotide of prefix.toUpperCase()) {
            const child = current.getChild(nucleotide);
            if (!child) return results;
            current = child;
        }
        
        // DFS to collect all sequences
        this.collectSequences(current, prefix, results);
        return results;
    }
    
    private collectSequences(
        node: DNATrieNode, 
        currentSequence: string, 
        results: string[]
    ): void {
        if (node.isEndOfSequence) {
            results.push(currentSequence);
        }
        
        for (const [nucleotide, child] of node.iterateChildren()) {
            this.collectSequences(child, currentSequence + nucleotide, results);
        }
    }
}
 
// Usage example
const dnaTrie = new DNATrie();
dnaTrie.insert("ATCGATCG", "seq1");
dnaTrie.insert("ATCGTTTT", "seq2");
dnaTrie.insert("GCGCGCGC", "seq3");
 
console.log(dnaTrie.findByPrefix("ATCG")); // ["ATCGATCG", "ATCGTTTT"]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65

/**
 * Estimate trie memory usage based on implementation choice
 */
interface TrieMemoryEstimate {
    arrayBasedBytes: number;
    hashMapBasedBytes: number;
    recommendation: string;
    breakEvenChildren: number;
}
 
function estimateTrieMemory(
    nodeCount: number,
    avgChildrenPerNode: number,
    alphabetSize: number,
    pointerSize: number = 8  // 64-bit default
): TrieMemoryEstimate {
    // Array-based: each node has |Σ| pointers + bool + object overhead
    const arrayNodeBytes = alphabetSize * pointerSize + 24; // +24 for object + bool
    const arrayBasedBytes = nodeCount * arrayNodeBytes;
    
    // Hash map-based: per-entry cost + base overhead
    const mapBaseOverhead = 48;  // Empty map object
    const mapEntryBytes = 40;     // Key + value + internal pointers
    const mapCapacityFactor = 1.5; // Load factor overhead
    
    const mapNodeBytes = mapBaseOverhead + 
        Math.ceil(avgChildrenPerNode * mapCapacityFactor) * mapEntryBytes;
    const hashMapBasedBytes = nodeCount * mapNodeBytes;
    
    // Calculate break-even point
    // arrayNodeBytes = mapBaseOverhead + k * mapEntryBytes * capacityFactor
    // k = (arrayNodeBytes - mapBaseOverhead) / (mapEntryBytes * capacityFactor)
    const breakEvenChildren = 
        (arrayNodeBytes - mapBaseOverhead) / (mapEntryBytes * mapCapacityFactor);
    
    let recommendation: string;
    if (alphabetSize > 256) {
        recommendation = "Hash Map: Alphabet too large for arrays";
    } else if (avgChildrenPerNode > breakEvenChildren) {
        recommendation = `Array: Average children (${avgChildrenPerNode.toFixed(1)}) > break-even (${breakEvenChildren.toFixed(1)})`;
    } else if (breakEvenChildren - avgChildrenPerNode < 2) {
        recommendation = "Either: Close to break-even point";
    } else {
        recommendation = `Hash Map: Average children (${avgChildrenPerNode.toFixed(1)}) < break-even (${breakEvenChildren.toFixed(1)})`;
    }
    
    return {
        arrayBasedBytes,
        hashMapBasedBytes,
        recommendation,
        breakEvenChildren
    };
}
 
// Example analysis
const estimate = estimateTrieMemory(
    50000,  // 50K nodes
    3.5,    // average 3.5 children per node
    26      // lowercase alphabet
);
 
console.log("Array-based:", (estimate.arrayBasedBytes / 1024 / 1024).toFixed(1), "MB");
console.log("Hash map-based:", (estimate.hashMapBasedBytes / 1024 / 1024).toFixed(1), "MB");
console.log("Break-even at:", estimate.breakEvenChildren.toFixed(1), "children/node");
console.log("Recommendation:", estimate.recommendation);