String Algorithms: Từ Pattern Matching đến Text Compression
Hãy thử nghĩ về điều này: mỗi khi bạn nhấn Ctrl+F trong trình duyệt, tìm kiếm một từ trong tài liệu dài hàng nghìn dòng, kết quả hiện ra gần như tức thì. Hoặc khi bạn nén một thư mục 500MB xuống còn 100MB bằng ZIP, chỉ mất vài giây. Đằng sau những hành động tưởng chừng đơn giản đó là các string algorithms đã được nghiên cứu và tối ưu trong nhiều thập kỷ.
Trong thế giới mà 75-80% dữ liệu là text dạng phi cấu trúc hoặc bán cấu trúc, việc xử lý chuỗi hiệu quả không chỉ là tính năng bổ sung - nó là yêu cầu cốt lõi. Mỗi ứng dụng, từ search engines đến DNA sequencing, từ text editors đến network intrusion detection, đều phụ thuộc vào khả năng tìm kiếm và nén dữ liệu text một cách nhanh chóng.
Tuy nhiên có một sự thật thú vị: không phải algorithm phức tạp nào cũng tốt hơn. Java's String.indexOf() vẫn dùng brute force cho các pattern ngắn vì đôi khi sự đơn giản chiến thắng. Gzip kết hợp nhiều kỹ thuật thay vì dùng một algorithm "tốt nhất". Vấn đề không phải là tìm "algorithm tốt nhất", mà là hiểu khi nào dùng cái nào và tại sao.
Bài viết này sẽ đi sâu vào hai nhóm algorithms quan trọng nhất trong string processing: Pattern Matching (tìm kiếm chuỗi con) và Text Compression (nén dữ liệu). Chúng ta sẽ không chỉ xem cách triển khai, mà còn phân tích các đánh đổi, complexity, và quan trọng nhất - quy trình ra quyết định khi chọn algorithm cho trường hợp sử dụng cụ thể.
Part I: Pattern Matching
Pattern matching là bài toán cơ bản: cho text T độ dài n và pattern P độ dài m, tìm tất cả vị trí xuất hiện của P trong T. Nghe có vẻ đơn giản, nhưng với text dài hàng triệu ký tự, cách tiếp cận ngây thơ có thể khiến ứng dụng của bạn chậm như rùa.
1. Brute Force: Sức mạnh của sự đơn giản
Cách hoạt động
Brute force làm chính xác những gì tên gọi ngụ ý: thử mọi vị trí có thể. Đặt pattern ở vị trí 0, so sánh từng ký tự từ trái sang phải. Nếu mismatch, dịch chuyển pattern sang phải một vị trí và bắt đầu lại. Đơn giản như vậy.
function bruteForceSearch(text, pattern) {
const n = text.length;
const m = pattern.length;
const positions = [];
for (let i = 0; i <= n - m; i++) {
let j;
for (j = 0; j < m; j++) {
if (text[i + j] !== pattern[j]) {
break;
}
}
if (j === m) {
positions.push(i);
}
}
return positions;
}
const text = "ABABDABACDABABCABAA";
const pattern = "ABAB";
console.log(bruteForceSearch(text, pattern));
Complexity Analysis
Đây là phần thú vị. Brute force có performance khác nhau đáng kể tùy thuộc vào input characteristics:
Best case: O(n) Xảy ra khi ký tự đầu tiên của pattern xuất hiện hiếm trong text. Ví dụ: tìm "ZZZ" trong text toàn chữ A. Mỗi vị trí chỉ cần 1 phép so sánh là thất bại ngay.
Average case: O(n + m) Với text ngẫu nhiên và pattern ngẫu nhiên, mismatches thường xảy ra rất sớm (vài ký tự đầu tiên). Xác suất khớp tại một vị trí bất kỳ là (1/alphabet_size)^m, cực kỳ nhỏ với m lớn. Trong thực tế, brute force hoạt động tốt một cách đáng ngạc nhiên.
Worst case: O(m × n) Đây là điểm yếu nghiêm trọng. Xảy ra khi text và pattern có cấu trúc lặp lại:
Text: "AAAAAAAAAB" (n = 10)
Pattern: "AAAAB" (m = 5)
Position 0: AAAA matches, B mismatches → 5 comparisons
Position 1: AAAA matches, B mismatches → 5 comparisons
...
Position 5: AAAAB fully matches → 5 comparisons
Total: 6 × 5 = 30 comparisons
Vấn đề là gì? Mỗi lần mismatch, ta bỏ đi tất cả information về những ký tự đã match. Text pointer quay lại về vị trí cũ + 1, và pattern pointer đặt lại về 0. Lãng phí công sức tính toán.
Khi nào nên dùng Brute Force?
Brute force không phải lúc nào cũng là lựa chọn tồi:
Dùng khi:
- Pattern rất ngắn (m < 5): chi phí của các thuật toán phức tạp không biện minh được
- Text nhỏ: với vài KB dữ liệu, sự khác biệt về hiệu suất không đáng kể
- Tìm kiếm một lần: không cần tiền xử lý vì chỉ tìm kiếm một lần
- Sự đơn giản trong triển khai là ưu tiên: 10 dòng code so với 50 dòng
Tránh khi:
- Pattern dài (m > 10) trên text lớn
- Cấu trúc lặp lại trong text/pattern (trường hợp xấu nhất)
- Yêu cầu thời gian thực với đầu vào lớn
- Nhiều lần tìm kiếm trên cùng text (phân bổ được chi phí tiền xử lý)
Bài học thực tế: Java's String.indexOf() bên trong dùng brute force tối ưu cho các pattern ngắn, chuyển sang các algorithm phức tạp cho các pattern dài. Biết khi nào đơn giản là tốt hơn là kỹ năng quan trọng.
2. Knuth-Morris-Pratt (KMP): Learning from partial matches
Vấn đề cốt lõi của Brute Force
Xem ví dụ này:
Text: A B C D A B C D A B C E
Pattern: A B C D A B D
^^^^^^X (mismatch at position 6)
Brute force thinking: "Mismatch! Start over ở position 1."
Nhưng thử suy nghĩ khác đi. Ta vừa match được 6 ký tự: "ABCDAB". Information này quý giá! Ta biết rằng:
- Positions 1-3 ("BCD") không thể match với pattern start ("ABC")
- Position 4-5 ("AB") lại CHÍNH XÁC match với pattern start!
Vậy tại sao phải re-examine những ký tự đã biết? Ta có thể bỏ qua thẳng đến position 4, tiếp tục từ pattern[2].
KMP philosophy: Never re-examine text characters. Use knowledge from partial matches để skip ahead intelligently.
LPS Array: The self-knowledge of pattern
LPS = Longest Proper Prefix which is also Suffix. Nghe trừu tượng, nhưng concept rất trực quan.
Với mỗi position i trong pattern, LPS[i] trả lời câu hỏi: "Trong substring pattern[0…i], proper prefix dài nhất nào cũng là suffix?"
Proper prefix: Prefix không bằng chính string đó.
Ví dụ với pattern "ABCDABD":
Pattern: A B C D A B D
Index: 0 1 2 3 4 5 6
LPS: 0 0 0 0 1 2 0
Position 4 (ABCDA):
- Prefixes: "", "A", "AB", "ABC", "ABCD"
- Suffixes: "", "A", "DA", "CDA", "BCDA"
- Longest match: "A" → LPS[4] = 1
Position 5 (ABCDAB):
- Prefixes: "", "A", "AB", "ABC", "ABCD", "ABCDA"
- Suffixes: "", "B", "AB", "DAB", "CDAB", "BCDAB"
- Longest match: "AB" → LPS[5] = 2
Position 6 (ABCDABD):
- No prefix equals suffix → LPS[6] = 0
Tại sao LPS array hữu ích?
Khi mismatch xảy ra ở pattern[j], ta đã match được pattern[0…j-1] với text. LPS[j-1] cho ta biết: "The last LPS[j-1] characters của matched portion chính là first LPS[j-1] characters của pattern."
Điều này nghĩa là: thay vì start over, ta có thể tiếp tục từ pattern[LPS[j-1]].
Visual example:
Text: A B C D A B C D A B E
Pattern: A B C D A B D
^^^^^^X
Matched: ABCDAB (6 chars)
LPS[5] = 2
Ta biết last 2 chars của matched text ("AB") = first 2 chars của pattern
→ Jump to comparing pattern[2] with current text position
Text: A B C D A B C D A B E
Pattern: A B C D A B D
^ Continue here, không cần re-examine "AB"
Building LPS Array một cách hiệu quả
Naive approach: với mỗi position, check all possible prefix lengths → O(m²) or worse.
Smart approach: Use dynamic programming. LPS values đã computed giúp ta compute LPS values mới.
function computeLPS(pattern) {
const m = pattern.length;
const lps = new Array(m).fill(0);
let len = 0;
let i = 1;
while (i < m) {
if (pattern[i] === pattern[len]) {
len++;
lps[i] = len;
i++;
} else {
if (len !== 0) {
len = lps[len - 1];
} else {
lps[i] = 0;
i++;
}
}
}
return lps;
}
console.log(computeLPS("ABCDABD"));
console.log(computeLPS("ABABCABAA"));
Time complexity: O(m)
Tại sao? Amortized analysis. Pointer i chỉ tăng, never decreases → maximum m increments. Pointer len có thể increase maximum m lần (bounded by i), và decrease maximum m lần total (không thể drop below 0). Total operations: O(m).
KMP Search Implementation
function KMPSearch(text, pattern) {
const n = text.length;
const m = pattern.length;
const lps = computeLPS(pattern);
const positions = [];
let i = 0;
let j = 0;
while (i < n) {
if (text[i] === pattern[j]) {
i++;
j++;
}
if (j === m) {
positions.push(i - j);
j = lps[j - 1];
} else if (i < n && text[i] !== pattern[j]) {
if (j !== 0) {
j = lps[j - 1];
} else {
i++;
}
}
}
return positions;
}
const text = "ABABDABACDABABCABAA";
const pattern = "ABABCABAA";
console.log(KMPSearch(text, pattern));
Detailed trace example
Text: "ABABDABACDABABCABAA", Pattern: "ABABCABAA"
LPS for pattern: [0, 0, 1, 2, 0, 1, 2, 3, 1]
Step 1: Match A B A B
i=0-3, j=0-3: All match
Step 2: Mismatch at i=4
text[4] = 'D', pattern[4] = 'C'
j = lps[3] = 2
Step 3: Continue from pattern[2]
text[4] = 'D', pattern[2] = 'A'
Mismatch, j = lps[1] = 0
Step 4: Continue from pattern[0]
text[4] = 'D', pattern[0] = 'A'
Mismatch, j = 0 → i++
Step 5: Start matching from i=5
Match: A B A C
Mismatch at i=8: text[8]='C', pattern[4]='C' matches!
Continue matching...
Step 6: Full match at position 10
Pattern fully matches from index 10 to 18
Output: [10]
Key observation: Text pointer i never backtracks. Ta chỉ move forward, không bao giờ re-examine characters.
Complexity Analysis
Total complexity: O(n + m)
Preprocessing: O(m) - Build LPS array
Search: O(n) - Amortized analysis:
- Pointer
iadvances from 0 to n → at most n increments - Pointer
jcan increase at most n times (bounded by i's progress) - Pointer
jcan decrease at most n times total (amortized) - Total: O(n) comparisons
Space: O(m) - Store LPS array
So sánh với brute force:
Worst case input (repetitive):
Text: "AAAAAAAAAB" (n=10)
Pattern: "AAAAB" (m=5)
Brute Force: O(m × n) = 50 comparisons
KMP: O(n + m) = 15 comparisons
Khi nào dùng KMP?
Advantages:
- Guaranteed O(n + m) performance, no worst case
- Never backtracks on text (critical cho streaming data)
- Predictable performance cho production systems
- Educational value: teaches DP và amortized analysis
Disadvantages:
- More complex implementation (40+ lines vs 10 lines)
- O(m) extra space
- Preprocessing overhead không justify cho small inputs
- Trong thực tế, Boyer-Moore thường nhanh hơn (better cache locality)
Use cases:
- Long patterns (m > 10)
- Repetitive pattern structure (worst case cho brute force)
- Streaming data (cannot backtrack)
- Need guaranteed performance (real-time systems)
- Multiple searches with same pattern (amortize preprocessing)
Real-world context: Nhiều text editors và search tools dùng hybrid approach - brute force cho m < 5, KMP hoặc Boyer-Moore cho m ≥ 10.
Part II: Text Compression
Chuyển từ pattern matching sang compression, ta đang giải quyết một problem hoàn toàn khác: làm sao represent same information với fewer bits? Compression không phải là black magic - nó là khai thác các mẫu và sự dư thừa trong data.
3. Run-Length Encoding (RLE): Simplicity at its finest
Philosophy
RLE là simplest compression algorithm có thể. Idea: thay thế các chuỗi ký tự giống nhau liên tiếp với (count, character) pair.
Input: "AAAAAABBBCCCCCCDDA"
Output: "6A3B6C2D1A"
Original: 18 characters
Compressed: 10 characters
Savings: 44%
Implementation
function rleEncode(input) {
if (!input) return '';
let encoded = '';
let count = 1;
for (let i = 1; i <= input.length; i++) {
if (i < input.length && input[i] === input[i - 1]) {
count++;
} else {
encoded += count + input[i - 1];
count = 1;
}
}
return encoded;
}
function rleDecode(encoded) {
let decoded = '';
for (let i = 0; i < encoded.length; i += 2) {
const count = parseInt(encoded[i]);
const char = encoded[i + 1];
decoded += char.repeat(count);
}
return decoded;
}
console.log(rleEncode("WWWWWWBBBWWWW"));
console.log(rleDecode("6W3B4W"));
Complexity: O(n) cho cả encode và decode. Space: O(1) extra.
The Dark Side: Negative Compression
Vấn đề lớn nhất của RLE: nó có thể làm file lớn hơn!
const input = "ABCDEF";
const encoded = rleEncode(input);
console.log(`Input: "${input}" (${input.length} chars)`);
console.log(`Encoded: "${encoded}" (${encoded.length} chars)`);
Mỗi character thành 2 characters (count + char). No repetition = no compression benefit, chỉ toàn chi phí.
Statistical reality:
- Với random data: 85.37% cases show size increase
- Average increase: 50.56%
Giải pháp:
- Hybrid encoding: Chỉ encode khi run length ≥ 3
- Dựa trên đánh dấu: Dùng special marker để báo encoded run
- Analyze first: Check xem data có phù hợp cho RLE không
function smartRLEEncode(input) {
if (!input) return '';
let encoded = '';
let i = 0;
while (i < input.length) {
let count = 1;
const char = input[i];
while (i + count < input.length && input[i + count] === char) {
count++;
}
if (count >= 3) {
encoded += `*${count}${char}`;
} else {
encoded += char.repeat(count);
}
i += count;
}
return encoded;
}
console.log(smartRLEEncode("AAAAAABCDEF"));
console.log(smartRLEEncode("ABCDEF"));
When to use RLE?
Hoàn hảo cho:
- Binary images (black & white documents: fax machines)
- Simple graphics (logos, icons với vùng màu đồng nhất)
- Bitmap images với large vùng đồng nhất
- Scientific data với các chuỗi dài of identical values
Tồi cho:
- Natural photos (biến đổi cao)
- Normal text (rarely has long runs)
- Already compressed data
- Random or varied data
Real-world applications:
- Fax transmission (CCITT standard)
- TIFF image format (optional)
- BMP file format (as component)
- Old game sprites
- PCX image format
RLE dạy bài học quan trọng: không phải mọi data đều compressible. Hiểu your data characteristics là chìa khóa to choosing right algorithm.
4. Huffman Coding: Frequency-based optimization
The Morse Code Insight
Năm 1952, David Huffman (student lúc đó) nghĩ ra một idea xuất sắc: áp dụng Morse code principle vào binary compression.
Morse code đã intuitively làm điều này:
- E (most common):
• - T (common):
— - Q (rare):
— — • —
Common letters → short codes. Rare letters → long codes. Result: giảm thiểu độ dài thông điệp trung bình.
Huffman hình thức hóa this với binary trees để achieve optimal prefix-free codes.
Fixed-length vs Variable-length
const text = "ABRACADABRA";
const freqs = {};
for (const char of text) {
freqs[char] = (freqs[char] || 0) + 1;
}
console.log(freqs);
Fixed-length encoding:
- ASCII: 11 × 8 = 88 bits
- 3-bit codes (5 unique chars): 11 × 3 = 33 bits
Huffman encoding:
Frequencies: A=5, B=2, R=2, C=1, D=1
Huffman codes:
A: 0 (1 bit - most frequent)
R: 10 (2 bits)
B: 110 (3 bits)
C: 1110 (4 bits)
D: 1111 (4 bits)
Total: 5×1 + 2×2 + 2×3 + 1×4 + 1×4 = 23 bits
Compression: 88 → 23 bits = 74% reduction!
Building Huffman Tree
Algorithm bottom-up sử dụng min-heap:
class HuffmanNode {
constructor(char, freq, left = null, right = null) {
this.char = char;
this.freq = freq;
this.left = left;
this.right = right;
}
isLeaf() {
return !this.left && !this.right;
}
}
class MinHeap {
constructor() {
this.heap = [];
}
insert(node) {
this.heap.push(node);
this.bubbleUp(this.heap.length - 1);
}
bubbleUp(index) {
while (index > 0) {
const parentIndex = Math.floor((index - 1) / 2);
if (this.heap[index].freq >= this.heap[parentIndex].freq) break;
[this.heap[index], this.heap[parentIndex]] = [this.heap[parentIndex], this.heap[index]];
index = parentIndex;
}
}
extractMin() {
if (this.heap.length === 0) return null;
if (this.heap.length === 1) return this.heap.pop();
const min = this.heap[0];
this.heap[0] = this.heap.pop();
this.bubbleDown(0);
return min;
}
bubbleDown(index) {
while (true) {
let smallest = index;
const left = 2 * index + 1;
const right = 2 * index + 2;
if (left < this.heap.length && this.heap[left].freq < this.heap[smallest].freq) {
smallest = left;
}
if (right < this.heap.length && this.heap[right].freq < this.heap[smallest].freq) {
smallest = right;
}
if (smallest === index) break;
[this.heap[index], this.heap[smallest]] = [this.heap[smallest], this.heap[index]];
index = smallest;
}
}
size() {
return this.heap.length;
}
}
function buildHuffmanTree(text) {
const freqMap = {};
for (const char of text) {
freqMap[char] = (freqMap[char] || 0) + 1;
}
const heap = new MinHeap();
for (const [char, freq] of Object.entries(freqMap)) {
heap.insert(new HuffmanNode(char, freq));
}
while (heap.size() > 1) {
const left = heap.extractMin();
const right = heap.extractMin();
const parent = new HuffmanNode(
null,
left.freq + right.freq,
left,
right
);
heap.insert(parent);
}
return heap.extractMin();
}
Visual construction cho "ABRACADABRA":
Initial: C(1), D(1), B(2), R(2), A(5)
Step 1: Merge C(1) + D(1) → CD(2)
Heap: [CD(2), B(2), R(2), A(5)]
Step 2: Merge CD(2) + B(2) → CDB(4)
Heap: [R(2), CDB(4), A(5)]
Step 3: Merge R(2) + A(5) → RA(7)
Heap: [CDB(4), RA(7)]
Step 4: Merge CDB(4) + RA(7) → ROOT(11)
Final tree:
[ROOT:11]
/ \
[CDB:4] [RA:7]
/ \ / \
[CD:2] B(2) R(2) A(5)
/ \
C(1) D(1)
Codes (left=0, right=1):
C: 000
D: 001
B: 01
R: 10
A: 11
Generate codes and Encode/Decode
function generateCodes(root, code = '', codes = {}) {
if (!root) return codes;
if (root.isLeaf()) {
codes[root.char] = code || '0';
return codes;
}
generateCodes(root.left, code + '0', codes);
generateCodes(root.right, code + '1', codes);
return codes;
}
function huffmanEncode(text) {
if (!text) return { encoded: '', tree: null, codes: {} };
const tree = buildHuffmanTree(text);
const codes = generateCodes(tree);
let encoded = '';
for (const char of text) {
encoded += codes[char];
}
return { encoded, tree, codes };
}
function huffmanDecode(encoded, tree) {
if (!encoded || !tree) return '';
let decoded = '';
let current = tree;
for (const bit of encoded) {
current = bit === '0' ? current.left : current.right;
if (current.isLeaf()) {
decoded += current.char;
current = tree;
}
}
return decoded;
}
const text = "ABRACADABRA";
const { encoded, tree, codes } = huffmanEncode(text);
console.log("Original:", text);
console.log("Codes:", codes);
console.log("Encoded:", encoded);
console.log("Bits:", `${text.length * 8} → ${encoded.length}`);
console.log("Decoded:", huffmanDecode(encoded, tree));
Complexity và Optimality
Time complexity:
- Building tree: O(n log n), n = unique characters
- Insert vào heap: O(log n)
- Extract và merge: O(n) operations × O(log n)
- Encoding: O(m), m = text length
- Lookup code: O(1) với hash map
- Decoding: O(k), k = encoded bits
- Traverse tree cho mỗi bit
Space complexity:
- Tree: O(n) - Tối đa 2n-1 nodes
- Code table: O(n)
- Encoded output: Tối ưu for given frequency distribution
Optimality theorem: Huffman coding produces optimal prefix-free code. Không có prefix-free code nào khác có shorter average length cho cùng frequency distribution.
Proof sketch: Greedy merging strategy ensures lowest-frequency characters ở deepest levels (longest codes), highest-frequency ở shallowest levels (shortest codes).
Real-world Applications
File formats:
- GZIP, PKZIP (DEFLATE = LZ77 + Huffman)
- BZIP2 (Burrows-Wheeler Transform + Huffman)
Image/Video:
- JPEG (Huffman encode DCT coefficients)
- PNG (DEFLATE với Huffman component)
- Most video codecs
Network:
- HTTP/2 HPACK header compression
- WebSocket compression
When to use:
- Non-uniform character distribution (critical!)
- Text files, log files
- Can do two-pass analysis (first pass: frequencies, second pass: encode)
- Lossless compression required
When to avoid:
- Uniform distribution (no benefit, pure chi phí)
- Streaming data (need frequencies upfront)
- Very small files (chi phí > benefit)
- Already compressed data (frequency distribution already optimized)
Practical consideration: Huffman tree phải được transmitted cùng compressed data (as header) để decode. Với small files, chi phí này có thể negate compression benefits.
5. Lempel-Ziv-Welch (LZW): Dictionary-based adaptation
A Different Philosophy
So với Huffman (character-level, frequency-based), LZW hoàn toàn khác biệt:
Huffman asks: "Which characters appear frequently?" LZW asks: "Which phrases repeat?"
Core idea: Build dictionary của patterns dynamically, replace repeating phrases với dictionary indices.
Key innovations:
- No preprocessing needed (thuật toán thích ứng)
- Dictionary built on-the-fly during compression
- Encoder và decoder xây dựng các từ điển giống hệt nhau một cách đồng bộ
- Works well cho data với repetitive phrases (English text, source code)
How LZW Works
Initial state:
const dictionary = new Map();
for (let i = 0; i < 256; i++) {
dictionary.set(String.fromCharCode(i), i);
}
Dictionary starts với all single characters (ASCII 0-255). Codes 256+ available cho multi-character strings.
Compression algorithm:
- w = first character
- For each subsequent character c:
- If w+c exists in dictionary: w = w+c (extend phrase)
- Else:
- Output code for w
- Add w+c to dictionary với next available code
- w = c (start new phrase)
- Output code for remaining w
Key principle: Khớp dài nhất tham lam. Luôn mở rộng cụm từ càng dài càng tốt.
Compression Example với Detailed Trace
Input: "ABABABA"
function lzwCompress(input) {
const dictionary = new Map();
for (let i = 0; i < 256; i++) {
dictionary.set(String.fromCharCode(i), i);
}
let w = '';
const result = [];
let dictSize = 256;
for (const c of input) {
const wc = w + c;
if (dictionary.has(wc)) {
w = wc;
} else {
result.push(dictionary.get(w));
dictionary.set(wc, dictSize++);
w = c;
}
}
if (w !== '') {
result.push(dictionary.get(w));
}
return result;
}
console.log(lzwCompress("ABABABA"));
Step-by-step trace:
Dictionary starts:
65='A', 66='B', ..., 255,
next available=256
Step 1: c='A'
w='', wc='A'
'A' in dict → w='A'
Step 2: c='B'
w='A', wc='AB'
'AB' NOT in dict
→ Output: 65 ('A')
→ Add: 256='AB'
→ w='B'
Step 3: c='A'
w='B', wc='BA'
'BA' NOT in dict
→ Output: 66 ('B')
→ Add: 257='BA'
→ w='A'
Step 4: c='B'
w='A', wc='AB'
'AB' IS in dict (code 256)
→ w='AB'
Step 5: c='A'
w='AB', wc='ABA'
'ABA' NOT in dict
→ Output: 256 ('AB')
→ Add: 258='ABA'
→ w='A'
Step 6: c='B'
w='A', wc='AB'
'AB' IS in dict
→ w='AB'
Step 7: c='A'
w='AB', wc='ABA'
'ABA' IS in dict (code 258)
→ w='ABA'
Step 8: End of input
→ Output: 258 ('ABA')
Compressed: [65, 66, 256, 258]
Original: 7 chars × 8 bits = 56 bits
Compressed: 4 codes × 9 bits = 36 bits
Compression: 36% reduction
Notice how dictionary thích ứng: sau khi thấy "AB" lần đầu, các lần xuất hiện tiếp theo được mã hóa hiệu quả.
Decompression Algorithm
Decompression khó hơn vì một trường hợp đặc biệt: encoder có thể output code chưa tồn tại trong decoder's dictionary!
function lzwDecompress(compressed) {
const dictionary = new Map();
for (let i = 0; i < 256; i++) {
dictionary.set(i, String.fromCharCode(i));
}
let w = String.fromCharCode(compressed[0]);
let result = w;
let dictSize = 256;
for (let i = 1; i < compressed.length; i++) {
const code = compressed[i];
let entry;
if (dictionary.has(code)) {
entry = dictionary.get(code);
} else if (code === dictSize) {
entry = w + w[0];
} else {
throw new Error(`Invalid code: ${code}`);
}
result += entry;
dictionary.set(dictSize++, w + entry[0]);
w = entry;
}
return result;
}
const compressed = [65, 66, 256, 258];
console.log(lzwDecompress(compressed));
The special case: Code === dictSize
Xảy ra khi pattern = previousstring + previousstring[0]. Encoder outputs code chưa added vào decoder's dictionary yet.
Example:
Input: "AAAA"
Compression:
- Output 'A' (65), add 256='AA'
- Output 'AA' (256), add 257='AAA'
- Output 'A' (65)
But what if input was "AAAAAA"?
- After outputting 256='AA' and adding 257='AAA'
- Next we'd output 257='AAA' (which decoder hasn't added yet!)
Solution: Decoder suy luận entry = w + w[0] khi code === dictSize.
Complexity và Dictionary Management
Time complexity:
- Compression: O(n) với efficient dictionary (trie or hash map)
- Decompression: O(n), usually faster than compression
Space complexity:
- Dictionary size grows không giới hạn → need chiến lược
Dictionary management strategies:
- Kích thước cố định (đơn giản nhất):
const MAX_DICT_SIZE = 4096;
if (dictSize < MAX_DICT_SIZE) {
dictionary.set(wc, dictSize++);
}
- Reset when full (adaptive):
if (dictSize >= MAX_DICT_SIZE) {
dictionary.clear();
initializeDictionary();
dictSize = 256;
}
- LRU replacement (complex but hiệu quả):
```
**Performance characteristics:**
- Compression ratio: Up to 77% reduction cho repetitive text
- English text: Typically 50% compression
- Source code: Often 60-70% compression
- Best với repeated phrases (natural language, logs)
- Poor với already-compressed data hoặc random data
#### Real-world Applications và Context
**Historical use:**
- GIF image format (still active)
- TIFF (optional)
- Unix `compress` utility (deprecated)
- PDF (optional)
- V.42bis modem compression
**Patent controversy:**
- Patented by Unisys in 1985
- Led to GIF licensing issues
- Patents expired 2003-2004
- Nhiều projects switched to alternatives (PNG, GZIP) during patent era
**When to use LZW:**
- Text với repetitive phrases
- One-pass compression needed (streaming)
- Fast decompression critical
- Working với GIF format
- Sufficient memory for dictionary
- English text, source code, log files
**When to avoid:**
- Already compressed data (no patterns to khai thác)
- Random data (dictionary grows without benefit)
- Severely limited memory
- Need absolute best ratio (use LZMA, bzip2)
**Modern context:**
- Component of DEFLATE (used by gzip, PNG)
- Educational value: teaches dictionary-based compression
- Still relevant trong certain domains (GIF, some embedded systems)
---
## Comparison & Decision Making
### Algorithm Comparison Matrix
| Metric | Brute Force | KMP | RLE | Huffman | LZW |
|--------|-------------|-----|-----|---------|-----|
| **Problem** | Pattern match | Pattern match | Compression | Compression | Compression |
| **Approach** | Try all positions | LPS array | Count runs | Frequency codes | Dictionary |
| **Time** | O(mn) worst | O(n+m) | O(n) | O(n log n) | O(n) |
| **Space** | O(1) | O(m) | O(1) | O(k) | O(dict) |
| **Preprocessing** | None | O(m) | None | Frequency analysis | None |
| **Passes** | One | One | One | Two | One |
| **Adaptive** | No | No | No | No | Yes |
| **Best compression** | N/A | N/A | 50-90% (runs) | 40-70% (varied freq) | 50-80% (phrases) |
| **Worst case** | Pattern/text size | None | Negative (increase!) | Uniform dist | Random data |
| **Implementation** | Trivial | Medium | Trivial | Complex | Complex |
| **Real-world** | String.indexOf() | Some editors | Fax, BMP | JPEG, MP3 | GIF, DEFLATE |
### Decision Framework
#### Pattern Matching: Brute Force vs KMP
**Choose Brute Force when:**
javascript function shouldUseBruteForce(patternLength, textLength, isOneTime) { return ( patternLength < 5 || textLength < 1000 || isOneTime ); }
**Choose KMP when:**
javascript function shouldUseKMP(patternLength, textLength, isStreaming, needsGuarantee) { return ( patternLength >= 10 || textLength > 1000000 || isStreaming || needsGuarantee ); }
#### Compression: RLE vs Huffman vs LZW
**Analyze your data first:**
javascript function analyzeData(data) { const charFreq = new Map(); let maxRun = 1, currentRun = 1; const phrases = new Map();
for (let i = 0; i < data.length; i++) { charFreq.set(data[i], (charFreq.get(data[i]) || 0) + 1);
if (i > 0 && data[i] === data[i - 1]) {
currentRun++;
maxRun = Math.max(maxRun, currentRun);
} else {
currentRun = 1;
}
if (i >= 2) {
const phrase = data.substring(i - 2, i + 1);
phrases.set(phrase, (phrases.get(phrase) || 0) + 1);
}
}
const uniqueChars = charFreq.size; const avgRun = maxRun; const repeatedPhrases = Array.from(phrases.values()) .filter(count => count > 1).length;
const freqVariance = calculateVariance(Array.from(charFreq.values()));
return { uniqueChars, avgRun, repeatedPhrases, freqVariance, recommendation: recommendAlgorithm(avgRun, freqVariance, repeatedPhrases) }; }
function recommendAlgorithm(avgRun, freqVariance, repeatedPhrases) { if (avgRun > 5) return 'RLE'; if (freqVariance > 50 && repeatedPhrases < 10) return 'Huffman'; if (repeatedPhrases > 20) return 'LZW'; return 'Try multiple and benchmark'; }
function calculateVariance(values) { const mean = values.reduce((a, b) => a + b, 0) / values.length; const squaredDiffs = values.map(v => Math.pow(v - mean, 2)); return squaredDiffs.reduce((a, b) => a + b, 0) / values.length; }
const testData = "AAAAAABBBBCCCCCC"; console.log(analyzeData(testData));
**Decision tree:**
Is data mostly runs of same character? ├─ YES → RLE └─ NO │ ├─ High frequency variance + few repeated phrases? │ └─ YES → Huffman │ └─ Many repeated phrases/words? └─ YES → LZW
Special cases:
- Already compressed? → Don't compress
- Need streaming? → LZW or adaptive Huffman
- Need best ratio? → Try combinations (DEFLATE)
- Very small file? → May not be worth it
### Real-world Hybrid Approaches
Most production systems combine techniques:
**DEFLATE (used by gzip, PNG, ZIP):**
- LZ77 (predecessor of LZW): Find repeated strings
- Huffman: Encode LZ77 output
- Result: Better than either alone
**JPEG:**
- DCT transform
- Quantization
- Huffman encoding
**Practical implementation example:**
javascript class HybridCompressor { compress(data) { const analysis = analyzeData(data);
if (analysis.avgRun > 5) {
return {
algorithm: 'RLE',
data: rleEncode(data)
};
}
if (analysis.repeatedPhrases > 20) {
const lzwCompressed = lzwCompress(data);
const huffmanCompressed = huffmanEncode(data).encoded;
return lzwCompressed.length < huffmanCompressed.length
? { algorithm: 'LZW', data: lzwCompressed }
: { algorithm: 'Huffman', data: huffmanCompressed };
}
return {
algorithm: 'Huffman',
data: huffmanEncode(data)
};
}
decompress(compressed, algorithm) { switch (algorithm) { case 'RLE': return rleDecode(compressed); case 'LZW': return lzwDecompress(compressed); case 'Huffman': return huffmanDecode(compressed.data, compressed.tree); default: throw new Error('Unknown algorithm'); } } } ```
Conclusion
Key Takeaways
Pattern Matching Lessons:
- Sự đơn giản có giá trị: Brute force không phải lúc nào cũng bad. Với small inputs, chi phí của sophisticated algorithms không biện minh được.
- Tái sử dụng thông tin: KMP teaches us một nguyên tắc cơ bản - đừng throw away information đã có. LPS array là ví dụ hoàn hảo của preprocessing giúp online performance.
- Trade-offs are everywhere: O(1) space vs O(m) space. Simple code vs complex code. Average-case performance vs worst-case guarantee.
Compression Lessons:
- Know your data: RLE perfect cho runs, terrible cho varied data. Huffman needs frequency variance. LZW needs phrase repetition.
- No universal best: Algorithm tốt nhất depends hoàn toàn on data characteristics và constraints.
- Preprocessing vs streaming: Huffman requires two passes. LZW adaptive với one pass. Trade compression ratio for streaming capability.
- Combination beats individual: Real-world systems (DEFLATE, BZIP2) combine multiple techniques.
Universal Principles
Xuyên suốt cả pattern matching và compression, một số principles emerge:
1. Preprocessing can amortize costs KMP's LPS array, Huffman's frequency analysis - upfront work đền đáp với repeated operations.
2. Space-time tradeoffs are fundamental Brute force: O(1) space, O(mn) time worst case. KMP: O(m) space, O(n+m) time guaranteed.
3. Understand your input distribution Random data: Compression fails, simple search works. Repetitive data: RLE/LZW excel, KMP shines. Varied frequencies: Huffman optimal.
4. Context matters Streaming? One-pass algorithms. Multiple searches? Amortize preprocessing. Small files? Overhead dominates. Production? Predictability > average-case speed.
5. Đo lường, đừng giả định Benchmark với real data. Theoretical complexity không tell whole story (cache effects, constant factors, implementation quality).
Further Learning
Advanced pattern matching:
- Boyer-Moore: Thường nhanh hơn KMP trong thực tế
- Rabin-Karp: Rolling hash for multiple pattern matching
- Aho-Corasick: Multiple pattern matching simultaneously
- Suffix arrays/trees: Preprocessing text for multiple queries
Advanced compression:
- LZ77/LZSS: Basis of DEFLATE
- LZMA: Tỷ lệ nén hiện đại nhất
- Burrows-Wheeler Transform: Used in bzip2
- Arithmetic coding: Tốt hơn Huffman về mặt lý thuyết
- Context modeling: Adaptive prediction
Practical resources:
- Implement algorithms from scratch (phương pháp học tốt nhất)
- Visualize với VisuAlgo.net
- Read source code: zlib (compression), V8's string search
- Practice: LeetCode problems tagged "string"
- Books: "Algorithms" by Sedgewick, "Introduction to Algorithms" by CLRS
Final Thoughts
String algorithms demonstrate một sự thật cơ bản về software engineering: không có viên đạn bạc. Mỗi algorithm có điểm mạnh và điểm yếu. Mỗi use case có các ràng buộc riêng biệt.
Master developer không phải người biết "the best algorithm", mà là người biết đặt đúng câu hỏi:
- Data characteristics gì?
- Constraints gì? (memory, time, streaming)
- Trade-offs nào chấp nhận được?
- Production requirements gì? (predictability, average case, worst case)
Với pattern matching: Đừng assume KMP luôn tốt hơn. Với compression: Đừng mù quáng apply Huffman to everything.
Phân tích. Đo lường. Chọn khôn ngoan. And sometimes, simple brute force is exactly what you need.
Bài viết tiếp theo: Advanced Pattern Matching - Boyer-Moore và Multiple Pattern Matching với Aho-Corasick. (Comment để thúc đẩy động lực thêm cho tác giả!)
