Text Preprocessing, Tokenization & Vectorization

In computational linguistics and modern artificial intelligence, human natural language constitutes an unstructured, highly ambiguous, discrete symbolic signal. Unlike numerical sensor telemetry or pixel matrices in computer vision, text lacks intrinsic spatial or geometric structure: words are categorical symbols whose semantic relationships cannot be inferred from their raw character encodings. Before an algorithm—whether a linear support vector machine, an XGBoost classifier, or a multi-billion parameter transformer—can operate on textual data, the raw Unicode byte stream must be normalized, segmented into discrete tokens, and projected into a structured mathematical vector space.

Modern Natural Language Processing (NLP) replaces crude whitespace splitting and rule-based regex hacks with rigorous mathematical tokenization and representation frameworks. Spanning Unicode normalization forms (NFC/NFKC), subword segmentation algorithms (Byte-Pair Encoding, WordPiece, and SentencePiece), statistical weighting schemes (TF-IDF), and high-dimensional sparse representations (Feature Hashing), text representation establishes the foundational signal processing pipeline upon which all downstream language understanding depends.

1. Lexical Normalization and Morphological Analysis#

The Text Representation Hierarchy#

Text processing operates across a multi-tier linguistic hierarchy:

+-----------------------------------------------------------------------------------+
|                        LINGUISTIC REPRESENTATION SPECTRUM                         |
+-----------------------------------------------------------------------------------+
|  1. GRAPHEMIC / UNICODE TIER: Byte-level UTF-8 encoding, Unicode codepoints       |
|  2. LEXICAL / MORPHOLOGICAL TIER: Affixes, stems, lemmas, inflectional variations |
|  3. SUBWORD / TOKEN TIER: Character n-grams, BPE merges, WordPiece subwords       |
|  4. SYNTACTIC TIER: Parts of Speech (POS), dependency trees, parse constituency   |
|  5. SEMANTIC VECTOR TIER: Sparse TF-IDF spaces, dense embeddings (Word2Vec, BERT) |
+-----------------------------------------------------------------------------------+

Unicode Normalization: NFC, NFD, NFKC, and NFKD#

Raw text ingested from web scraping, social media feeds, or PDF optical character recognition (OCR) exhibits severe visual equivalence anomalies due to Unicode codepoint ambiguities. For instance, the accented character é can be represented in two distinct ways:

• Precomposed Form: A single codepoint U+00E9 (Latin Small Letter E with Acute).
• Decomposed Form: A sequence of two codepoints: U+0065 (Latin Small Letter E) followed by U+0301 (Combining Acute Accent).

While rendered identically by modern font engines, standard string comparison operators treat these sequences as completely unequal:

"\ u00e9" ≠ "e\ u0301"

Unicode defines four canonical normalization forms:

1. NFC (Normalization Form Canonical Composition): Characters are decomposed and then recomposed to canonical precomposed forms. Favored for general web text and standard search indices.
2. NFD (Normalization Form Canonical Decomposition): Characters are decomposed into base characters and independent combining diacritics. Essential when stripping accents.
3. NFKC (Normalization Form Compatibility Composition): Replaces compatibility variants (e.g., ligature fi U+FB01 is converted to f + i; superscript ² U+00B2 is converted to 2) followed by canonical composition. Highly recommended for standard machine learning pipelines.
4. NFKD (Normalization Form Compatibility Decomposition): Decomposes compatibility characters and canonical characters into base components.

Stemming vs. Lemmatization#

Inflected languages modify words to express grammatical tense, mood, gender, and number (e.g., organizes, organizing, organized, organization). To collapse these morphological variants to a unified canonical form, NLP applies two paradigms:

STEMMING (Heuristic Suffix Stripping):
"running"     -->  "run"
"organization"-->  "organ"
"university"  -->  "univers"   (Crude truncation, non-dictionary word!)

LEMMATIZATION (Morphological Dictionary Lookup with POS):
"running" (Verb)  -->  "run"
"running" (Noun)  -->  "running"
"better" (Adj)    -->  "good"  (Preserves semantic root via lexical database!)

• Stemming (e.g., Porter, Lancaster, Snowball): Implements rule-based algorithmic heuristic string rewrites. The Porter Stemmer executes five sequential condition stages (e.g., replacing sses with ss, or stripping ing if the preceding stem contains a vowel). While computationally fast (O(1) per word), stemming produces non-words (comput, sens) and suffers from over-stemming (collapsing unrelated words: universal, universe, university → univers) and under-stemming (failing to collapse related forms: adhere, adhesion).
• Lemmatization (e.g., WordNet, spaCy): Employs a full morphological lexicon and grammatical analysis. By accepting a Part-of-Speech (POS) tag alongside the token, a lemmatizer resolves irregular forms correctly (e.g., ran → run, better → good). While computationally heavier (O(log N) dictionary lookup), it guarantees valid dictionary lemmas.

2. Modern Subword Tokenization Algorithms#

Classic NLP tokenized text by splitting on whitespace and punctuation. This approach fails catastrophically in modern deep learning:

1. Out-Of-Vocabulary (OOV) Pathology: If an unseen word appears at inference time (e.g., pre-computation, bio-mechanics, neuro-symbolic), word-level models map it to a generic [UNK] (Unknown) token, losing all semantic information.
2. Vocabulary Explosion: Natural language vocabularies follow Zipf's Law (f(r) ∝ 1/r). Storing full word dictionaries requires millions of embedding vectors, consuming tens of gigabytes of GPU VRAM.

Modern Large Language Models (LLMs) universally solve this via Subword Tokenization, which dynamically segments frequent words as whole tokens while decomposing rare or novel words into meaningful morphological subword fragments.

+-----------------------------------------------------------------------------------+
|                        SUBWORD TOKENIZATION ARCHITECTURE                          |
+-----------------------------------------------------------------------------------+
|  RAW INPUT STRING: "The unconstitutionalities of the decree..."                   |
|                                                                                   |
|  BYTE-PAIR ENCODING (BPE / GPT-4):                                                |
|  ["The", " un", "constitution", "alities", " of", " the", " decree", "..."]       |
|                                                                                   |
|  WORDPIECE (BERT):                                                                |
|  ["the", "un", "##constitution", "##ali", "##ties", "of", "the", "decree", "..."] |
|                                                                                   |
|  SENTENCEPIECE / UNIGRAM (Llama / T5):                                            |
|  [" The", " un", "constitution", "alities", " of", " the", " decree", "..."]     |
+-----------------------------------------------------------------------------------+

Byte-Pair Encoding (BPE)#

Originally a lossless data compression algorithm (Gage, 1994), Byte-Pair Encoding was adapted to NLP by Sennrich et al. (2016) and powers GPT-2, GPT-3, GPT-4, and RoBERTa:

The BPE Training Algorithm:

1. Initialize the vocabulary V with all unique atomic characters appearing in the corpus, plus an end-of-word symbol </w>.
2. Represent every word in the training corpus as a sequence of space-separated characters.
3. Count the co-occurrence frequency of all adjacent symbol pairs across the entire corpus.
4. Identify the single most frequent pair (c_i, c_j) and merge it into a new composite symbol c_{ij} = c_i c_j.
5. Add c_{ij} to vocabulary V.
6. Repeat steps 3–5 iteratively until V reaches the target vocabulary size K (e.g., K = 50,000 in GPT-2 or K = 100,000 in GPT-4).

Byte-Level BPE:

Modern transformers (GPT-4, LLaMA) operate on raw UTF-8 bytes rather than Unicode characters. Because any text can be represented as a sequence of 256 possible byte values (0 to 255), byte-level BPE starts with an initial base vocabulary of exactly 256 bytes. Consequently, the OOV problem is mathematically eliminated: any arbitrary Unicode character, foreign script, emoji, or binary payload can be represented without ever emitting an [UNK] token.

WordPiece and Unigram Language Model#

• WordPiece (BERT): Similar to BPE in that it iteratively builds a vocabulary from characters. However, instead of selecting the pair with the highest raw co-occurrence frequency, WordPiece selects the pair that maximizes the likelihood of the language model over the training data, equivalent to maximizing the mutual information:

Score(u, v) = (count(uv) / count(u) × count(v))

• Unigram Language Model (SentencePiece / T5): Unlike BPE's bottom-up iterative merging, Unigram uses a top-down pruning approach. It initializes with a massive vocabulary of millions of candidate subwords and iteratively prunes the bottom 20\% of subwords whose removal induces the smallest increase in the corpus cross-entropy loss. At tokenization time, it finds the optimal segmentation using the Viterbi dynamic programming algorithm over subword probabilities.

3. Vectorization Paradigms: Bag-of-Words and TF-IDF#

Before neural embeddings, statistical vectorization mapped variable-length text documents into fixed-dimensional vectors in R^V, where V is vocabulary size.

Bag-of-Words (BoW) & N-Grams#

Let corpus D = \{d_1, d_2, …, d_M\} contain a finite vocabulary of V unique terms:

V = \{w_1, w_2, …, w_V\}

The Bag-of-Words representation of document d_j is a vector:

x_j = [c_{1, j}, c_{2, j}, …, c_{V, j}]^T ∈ R^V

where c_{i, j} represents the raw frequency count of word w_i in document d_j.

• Limitation 1: Total Loss of Syntax and Order: "Dog bites man" and "Man bites dog" map to identical vectors.
• Limitation 2: Extreme Sparsity: With a standard vocabulary of V = 100,000 terms, a typical 50-word document vector is 99.95\% zeros.
• N-Gram Extension: To retain local phrase structure, BoW is extended to N-grams (consecutive sequences of n tokens: unigrams n=1, bigrams n=2, trigrams n=3). However, the vocabulary size grows exponentially (V ≈ |V_{unigram}|^n), inducing severe memory pressure.

Term Frequency-Inverse Document Frequency (TF-IDF)#

Raw term frequency suffers from a fatal flaw: ubiquitous words like the, is, and and appear with high frequency across all documents, drowning out rare, domain-specific discriminative keywords like transformer, encryption, or leukemia.

TF-IDF attenuates common words while amplifying distinctive terms through a composite weighting function:

TF-IDF(t, d, D) = TF(t, d) × IDF(t, D)

1. Term Frequency (TF): Quantifies local importance within a specific document d:

TF(t, d) = (f_{t,d} / ∑_{t' ∈ d} f_{t',d})

where f_{t, d} is the raw count of term t in document d.

1. Inverse Document Frequency (IDF): Quantifies global discriminative rarity across the entire corpus D:

IDF(t, D) = ln(((1 + |D|) / (1 + |{d ∈ D : t ∈ d}|))) + 1

(Standard scikit-learn smoothed formulation). If a term appears in every single document (|\{d ∈ D : t ∈ d\}| = |D|), its IDF value shrinks towards zero. If it appears in only 1 out of 1,000,000 documents, its IDF value is high.

1. L2 Normalization: To prevent long documents from dominating short documents purely due to higher raw word counts, document vectors are projected onto the unit hypersphere:

v_{norm} = (v / \|v\|_2) = (v / √(∑_{i=1}^V v_i^2))

Cosine Similarity Metric#

In normalized vector spaces, semantic document similarity is measured via the Cosine Similarity:

CosineSimilarity(u, v) = (u · v / \|u\|_2 \|v\|_2) = cos(θ)

For L2-normalized vectors (\|u\|_2 = \|v\|_2 = 1), cosine similarity simplifies to the Euclidean dot product:

CosineSimilarity(u, v) = u · v = ∑_{i=1}^V u_i v_i

Cosine similarity ranges from 0 (completely orthogonal, disjoint vocabularies) to 1 (identical lexical distributions).

4. Production Memory Architecture: Sparse Matrices & Feature Hashing#

Compressed Sparse Row (CSR) Format#

Storing a 500,000 × 100,000 TF-IDF matrix as a standard 64-bit IEEE-754 floating-point dense array in memory requires:

500,000 × 100,000 × 8 bytes = 400,000,000,000 bytes = 400 GB of RAM

Because natural language matrices are over 99.8\% sparse, production systems mandate Compressed Sparse Row (CSR) storage:

A sparse matrix is decomposed into three compact 1D arrays:
1. data:       Float array of non-zero values [v_0, v_1, v_2, ...]
2. indices:    Integer array of column indices corresponding to data entries
3. indptr:     Integer array of row start offsets (size M + 1)

If the matrix contains only 100 non-zero entries per document:

Memory_{CSR} = (500,000 × 100 × 8 bytes (data)) + (500,000 × 100 × 4 bytes (indices)) ≈ 600 MB

CSR reduces memory footprint by > 99.8\%, enabling multi-million document corpora to fit comfortably within single-server RAM.

The Hashing Trick (Feature Hashing)#

In streaming architectures where text arrives continuously in real time, maintaining an in-memory string-to-integer dictionary ({"machine": 0, "learning": 1, ...}) causes unbounded memory growth and makes distributed parallelization difficult (requiring synchronization of dictionary state across worker nodes).

The Hashing Trick (Weinberger et al., 2009) projects arbitrary string tokens directly into a bounded feature vector of fixed dimensionality B = 2^b using a fast non-cryptographic hash function (e.g., MurmurHash3):

h(w) = MurmurHash3(w) mod B

x[h(w)] += sign(w) × weight(w)

• Advantages: Requires zero vocabulary storage in memory; operates statelessly in streaming pipelines; memory footprint is strictly bounded to B buckets.
• Hash Collisions: Multiple distinct words may hash to the identical index (h(w_1) = h(w_2)). However, in high-dimensional spaces (b ≥ 20 ⟹ B ≥ 1,048,576), statistical learning theory proves that collision noise cancels out in expectation, preserving downstream classifier accuracy.

5. University-Grade Checkpoint Practice Problems#

Problem 1: Byte-Pair Encoding (BPE) Iterative Tokenizer Construction#

Context: An NLP research laboratory trains a Byte-Pair Encoding (BPE) subword tokenizer on a domain-specific vocabulary.

The training corpus consists of the following four normalized word types and their respective corpus occurrence frequencies:

• "low": frequency 5
• "lower": frequency 2
• "newest": frequency 6
• "widest": frequency 3

Following standard BPE specification, each word is initialized as a space-separated sequence of individual characters terminated by an explicit end-of-word boundary symbol </w>:

• "l o w </w>" (5)
• "l o w e r </w>" (2)
• "n e w e s t </w>" (6)
• "w i d e s t </w>" (3)

Task:

1. List the initial base character vocabulary V_0 and determine its cardinality |V_0|.
2. Compute the co-occurrence frequencies of all adjacent symbol pairs in the initial corpus, and identify the winning pair for Merge Iteration 1.
3. Execute Merge Iteration 2, Merge Iteration 3, and Merge Iteration 4, clearly stating the updated word representations, the selected merge pair, and the resulting vocabulary at each step.
4. Given the trained vocabulary V_4, demonstrate the step-by-step greedy segmentation of an unseen out-of-vocabulary word:

Target Word = "lowest"

Solution:

1. Initial Base Character Vocabulary V_0:

* Extracting all unique characters and boundary marker from the initial words:

V_0 = \{'d', 'e', 'i', 'l', 'n', 'o', 'r', 's', 't', 'w', '</w>'\}

* Initial vocabulary cardinality: |V_0| = 11 tokens.

1. Merge Iteration 1:

* Calculate pair co-occurrence frequencies:

* ('l', 'o'): in low (5) + in lower (2) = 7

* ('o', 'w'): in low (5) + in lower (2) = 7

* ('w', '</w>'): in low (5) = 5

* ('w', 'e'): in lower (2) + in newest (6) = 8

* ('e', 'r'): in lower (2) = 2

* ('r', '</w>'): in lower (2) = 2

* ('n', 'e'): in newest (6) = 6

* ('e', 's'): in newest (6) + in widest (3) = 9

* ('s', 't'): in newest (6) + in widest (3) = 9

* ('t', '</w>'): in newest (6) + in widest (3) = 9

* ('w', 'i'): in widest (3) = 3

* ('i', 'd'): in widest (3) = 3

* ('d', 'e'): in widest (3) = 3

* Ties occur at frequency 9 between ('e', 's'), ('s', 't'), and ('t', '</w>'). Breaking tie deterministically by lexical order:

Winning Pair 1 = ('e', 's') (frequency 9)

* New token created: es

* Updated corpus:

* "l o w </w>" (5)

* "l o w e r </w>" (2)

* "n e w es t </w>" (6)

* "w i d es t </w>" (3)

* Vocabulary: V_1 = V_0 ∪ \{'es'\} (|V_1| = 12).

1. Merge Iterations 2, 3, and 4:

Iteration 2*:

* Candidate pairs:

* ('es', 't'): in newest (6) + in widest (3) = 9

* ('t', '</w>'): in newest (6) + in widest (3) = 9

* ('w', 'e'): in lower (2) + in newest (6) = 8

* ('l', 'o'): 7, ('o', 'w'): 7

* Highest frequency: ('es', 't') with frequency 9.

* Winning Pair 2: ('es', 't') → est.

* Updated corpus:

* "l o w </w>" (5)

* "l o w e r </w>" (2)

* "n e w est </w>" (6)

* "w i d est </w>" (3)

* Vocabulary: V_2 = V_1 ∪ \{'est'\} (|V_2| = 13).

Iteration 3*:

* Candidate pairs:

* ('est', '</w>'): in newest (6) + in widest (3) = 9

* ('w', 'e'): 8

* ('l', 'o'): 7, ('o', 'w'): 7

* Winning Pair 3: ('est', '</w>') → est</w>.

* Updated corpus:

* "l o w </w>" (5)

* "l o w e r </w>" (2)

* "n e w est</w>" (6)

* "w i d est</w>" (3)

* Vocabulary: V_3 = V_2 ∪ \{'est</w>'\} (|V_3| = 14).

Iteration 4*:

* Candidate pairs:

* ('w', 'e'): in lower (2) + in newest (6) = 8

* ('l', 'o'): 7

* ('o', 'w'): 7

* Winning Pair 4: ('w', 'e') → we.

* Updated corpus:

* "l o w </w>" (5)

* "l o we r </w>" (2)

* "n e we est</w>" (6)

* "w i d est</w>" (3)

* Vocabulary: V_4 = V_3 ∪ \{'we'\} (|V_4| = 15).

1. Tokenization of Unseen Word `"lowest"`:

* Target word initialized with characters: l o w e s t </w>

* Applying ordered merge rules from V_4:

* Rule 1 (e + s → es): l o w es t </w>

* Rule 2 (es + t → est): l o w est </w>

* Rule 3 (est + </w> → est</w>): l o w est</w>

* Rule 4 (w + e → we): Not applicable (no w e sequence).

* Final subword segmentation of "lowest":

['l', 'o', 'w', 'est</w>'] or ['low', 'est']

Result*: The unseen word "lowest" is seamlessly broken down into known base characters and morphological suffix est</w>, avoiding [UNK].

Problem 2: Exact TF-IDF Vectorization & Cosine Similarity Derivation#

Context: An automated document clustering engine analyzes a collection of M = 3 documents (D = \{d_1, d_2, d_3\}):

• d_1: "distributed systems process streams"
• d_2: "distributed algorithms process graphs"
• d_3: "real time streams process data"

Text Preprocessing Rules:

• All words are lowercased and whitespace-tokenized.
• Vocabulary V comprises all unique terms across the corpus, ordered alphabetically.
• Term Frequency TF(t, d) is defined as the raw relative frequency:

TF(t, d) = (f_{t,d} / ∑_{t' ∈ d} f_{t',d})

• Inverse Document Frequency IDF(t, D) uses the standard smoothed logarithmic formula:

IDF(t, D) = ln((1 + |D| / 1 + DF(t))) + 1

where |D| = 3, and DF(t) is the count of documents containing term t.

• Document vectors are L2-normalized: v = x / \|x\|_2.

Task:

1. Construct the ordered vocabulary V and compute the Document Frequency DF(t) and IDF(t) for every term.
2. Compute the unnormalized TF-IDF vector x_1 for document d_1.
3. Compute the unnormalized TF-IDF vector x_2 for document d_2.
4. Compute the L2 norms \|x_1\|_2 and \|x_2\|_2.
5. Calculate the exact Cosine Similarity between document d_1 and document d_2.

Solution:

1. Vocabulary Construction and IDF Computation:

* Extracting unique terms alphabetically:

V = [algorithms, data, distributed, graphs, process, real, streams, systems, time]

Vocabulary size |V| = 9 terms.

* Document occurrences:

* algorithms: in d_2 ⟹ DF = 1

* data: in d_3 ⟹ DF = 1

* distributed: in d_1, d_2 ⟹ DF = 2

* graphs: in d_2 ⟹ DF = 1

* process: in d_1, d_2, d_3 ⟹ DF = 3

* real: in d_3 ⟹ DF = 1

* streams: in d_1, d_3 ⟹ DF = 2

* systems: in d_1 ⟹ DF = 1

* time: in d_3 ⟹ DF = 1

* Computing IDF(t) = ln((1 + 3 / 1 + DF)) + 1 = ln((4 / 1 + DF)) + 1:

* For DF = 1: IDF = ln(4 / 2) + 1 = ln(2) + 1 ≈ 0.693147 + 1 = 1.69315

* For DF = 2: IDF = ln(4 / 3) + 1 ≈ 0.287682 + 1 = 1.28768

* For DF = 3: IDF = ln(4 / 4) + 1 = ln(1) + 1 = 0 + 1 = 1.00000

1. Unnormalized TF-IDF Vector for d_1:

* d_1 has 4 words: distributed (1), systems (1), process (1), streams (1).

* TF = 1/4 = 0.25 for each present word.

* Coordinates across the 9 vocabulary dimensions:

* x_{1, algorithms} = 0

* x_{1, data} = 0

* x_{1, distributed} = 0.25 × 1.28768 = 0.32192

* x_{1, graphs} = 0

* x_{1, process} = 0.25 × 1.00000 = 0.25000

* x_{1, real} = 0

* x_{1, streams} = 0.25 × 1.28768 = 0.32192

* x_{1, systems} = 0.25 × 1.69315 = 0.42329

* x_{1, time} = 0

* x_1 = [0, 0, 0.32192, 0, 0.25000, 0, 0.32192, 0.42329, 0]^T

1. Unnormalized TF-IDF Vector for d_2:

* d_2 has 4 words: distributed (1), algorithms (1), process (1), graphs (1).

* TF = 1/4 = 0.25 for each present word.

* Coordinates:

* x_{2, algorithms} = 0.25 × 1.69315 = 0.42329

* x_{2, data} = 0

* x_{2, distributed} = 0.25 × 1.28768 = 0.32192

* x_{2, graphs} = 0.25 × 1.69315 = 0.42329

* x_{2, process} = 0.25 × 1.00000 = 0.25000

* Remaining components = 0.

* x_2 = [0.42329, 0, 0.32192, 0.42329, 0.25000, 0, 0, 0, 0]^T

1. L2 Norm Calculation:

* \|x_1\|_2 = √(0.32192^2 + 0.25000^2 + 0.32192^2 + 0.42329^2)

\|x_1\|_2 = √(0.10363 + 0.06250 + 0.10363 + 0.17917) = √(0.44893) ≈ 0.67002

* \|x_2\|_2 = √(0.42329^2 + 0.32192^2 + 0.42329^2 + 0.25000^2)

\|x_2\|_2 = √(0.17917 + 0.10363 + 0.17917 + 0.06250) = √(0.52447) ≈ 0.72420

1. Cosine Similarity Calculation:

* Dot product x_1 · x_2:

The only non-zero overlapping dimensions are distributed and process:

x_1 · x_2 = (0.32192 × 0.32192) + (0.25000 × 0.25000) = 0.10363 + 0.06250 = 0.16613

* Cosine Similarity:

CosineSimilarity(d_1, d_2) = (x_1 · x_2 / \|x_1\|_2 \|x_2\|_2) = (0.16613 / 0.67002 × 0.72420) = (0.16613 / 0.48523) ≈ 0.34237 (34.24\%)

Interpretation*: Despite sharing 2 out of 4 words (50\% Jaccard token overlap), the cosine similarity is tempered to 34.24\% because the most frequent common word (process) carries low IDF weight, while discriminative terms (systems, algorithms, graphs) separate them.

Problem 3: Feature Hashing Collision Probability & Information Preservation#

Context: A high-velocity cybersecurity log analysis engine vectorizes incoming web server query logs into a bounded feature vector using the Hashing Trick (MurmurHash3).

System Parameters:

• The hash vector uses b = 18 bits, providing B = 2^{18} = 262,144 hash buckets.
• The system ingests a batch containing V = 25,000 unique extracted n-gram tokens.

Assumptions:

• The hash function behaves as a uniform random oracle, distributing tokens independently across all B buckets with probability p = 1 / B.

Task:

1. Using the Poisson approximation to the Birthday Paradox, derive the mathematical formula for the probability P(≥ 1 collision) of at least one hash collision.
2. Compute the numerical probability of at least one collision occurring among the 25,000 tokens.
3. Calculate the Expected Number of Collisions E[C] across the hash vector.
4. Calculate the minimum bit size b_{min} required to guarantee that the expected number of collisions E[C] ≤ 0.10.

Solution:

1. Poisson Approximation of Collision Probability:

* Total possible pairs among V tokens:

N_{pairs} = C(V, 2) = (V(V - 1) / 2)

* The probability that an arbitrary pair hashes to the same bucket is 1 / B.

* Under the Poisson approximation:

λ = (V(V - 1) / 2B) ≈ (V^2 / 2B)

* The probability of zero collisions is P(C = 0) = e^{-λ}.

* The probability of at least one collision:

P(≥ 1 collision) = 1 - e^{-(V^2 / 2B)}

1. Numerical Collision Probability:

* Given V = 25,000 and B = 262,144:

λ = (25,000^2 / 2 × 262,144) = (625,000,000 / 524,288) ≈ 1,192.09

* Evaluating probability:

P(≥ 1 collision) = 1 - e^{-1,192.09} ≈ 1 - 0 = 1.000000 (100\%)

Result*: A collision is statistically guaranteed.

1. Expected Number of Collisions E[C]:

* Let indicator variable I_{ij} = 1 if tokens i and j collide.

* By Linearity of Expectation:

E[C] = ∑_{1 ≤ i < j ≤ V} E[I_{ij}] = C(V, 2) × (1 / B) = (V(V - 1) / 2B)

* Substituting values:

E[C] = (25,000 × 24,999 / 2 × 262,144) = (624,975,000 / 524,288) ≈ 1,192.05 colliding pairs

* Out of 25,000 unique tokens, approximately 1,192 pairs experience collision. Because 1,192 / 25,000 ≈ 4.77\%, over 95\% of features remain completely uncorrupted.

1. Minimum Bit Dimension for E[C] ≤ 0.10:

(V^2 / 2B) ≤ 0.10 ⟹ B ≥ (V^2 / 0.20) = 5 × V^2

* Substituting V = 25,000:

B ≥ 5 × (25,000)^2 = 5 × 625,000,000 = 3,125,000,000 buckets

* Solving for bit width b:

2^b ≥ 3.125 × 10^9 ⟹ b ≥ log_2(3.125 × 10^9) = (ln(3.125 × 10^9) / ln(2)) ≈ (21.862 / 0.69315) ≈ 31.54

Conclusion*: To achieve almost zero collisions (E[C] ≤ 0.10), the hash table requires b = 32 bits (B = 4.29 billion buckets).

Problem 4: CSR Sparse Matrix vs. Dense Memory Efficiency Analysis#

Context: A legal discovery search engine indexes a corpus of M = 800,000 legal case documents.

Corpus Characteristics:

• Extracted vocabulary: V = 120,000 unique unigram and bigram tokens.
• Average document length after stop-word removal: L = 180 unique terms per document.
• Matrix sparsity:

S = 1 - (180 / 120,000) = 1 - 0.0015 = 0.9985 (99.85\% sparse)

We compare two in-memory matrix storage formats:

• Format 1 (Dense Float64 2D Array):

* Dimensions: M × V.

* Data type: Standard 64-bit IEEE-754 float (8 bytes per entry).

• Format 2 (Compressed Sparse Row - CSR):

* data array: 64-bit float (8 bytes) for every non-zero entry.

* indices array: 32-bit unsigned integer (4 bytes) recording column position for every non-zero entry.

* indptr array: 64-bit unsigned integer (8 bytes) recording row start offsets (size M + 1).

Task:

1. Calculate the total physical RAM memory footprint (in Gigabytes) required to store the matrix in Format 1 (Dense).
2. Calculate the total physical RAM memory footprint (in Megabytes) required to store the matrix in Format 2 (CSR).
3. Compute the absolute memory savings (in GB) and the compression ratio achieved by CSR.
4. If the search engine runs on a cloud server with 32 GB of RAM, determine whether Format 1 and Format 2 can execute in memory without triggering swap or OOM kills.

Solution:

1. Format 1 (Dense Array) Memory Footprint:

* Total matrix cells:

N_{cells} = M × V = 800,000 × 120,000 = 96,000,000,000 cells (96 billion)

* Bytes per cell = 8 bytes.

* Total memory:

Mem_{dense} = 96,000,000,000 × 8 bytes = 768,000,000,000 bytes

* Converting to Gigabytes (10^9 decimal / 1024^3 binary):

Mem_{dense} = 768 GB (decimal) or (768 × 10^9 / 1,073,741,824) ≈ 715.26 GiB

1. Format 2 (CSR) Memory Footprint:

* Total non-zero entries (NNZ):

NNZ = M × L = 800,000 × 180 = 144,000,000 non-zero entries (144 million)

* data array footprint:

Mem_{data} = NNZ × 8 bytes = 144,000,000 × 8 = 1,152,000,000 bytes

* indices array footprint:

Mem_{indices} = NNZ × 4 bytes = 144,000,000 × 4 = 576,000,000 bytes

* indptr array footprint (M + 1 elements):

Mem_{indptr} = (800,000 + 1) × 8 bytes = 6,400,008 bytes

* Total CSR memory:

Mem_{CSR} = 1,152,000,000 + 576,000,000 + 6,400,008 = 1,734,400,008 bytes

* Converting to Megabytes and Gigabytes:

Mem_{CSR} ≈ 1,734.4 MB ≈ 1.734 GB (decimal) (1.615 GiB)

1. Efficiency Comparison:

* Absolute memory saved:

Δ Mem = 768.0 GB - 1.734 GB = 766.266 GB saved

* Compression ratio:

Ratio = (Mem_dense / Mem_CSR) = (768,000,000,000 / 1,734,400,008) ≈ 442.8×

CSR format is over 442× smaller* than the dense array.

1. Hardware Feasibility (32 GB Server):

* Format 1 requires 715.3 GiB, which is over 22× larger than total physical RAM (32 GB). The operating system would immediately terminate the process with an OutOfMemory kill.

* Format 2 requires only 1.615 GiB, consuming less than 5.1\% of the server's 32 GB RAM, leaving over 30 GB available for OS caches, index lookups, and concurrent search threads.