FSP Algorithm

About the FSP Algorithm

The FSP (Find Similar Patterns) algorithm is a revolutionary data compression technique designed to efficiently reduce data size by identifying and leveraging similar patterns within the data. Unlike traditional compression methods, FSP specializes in working with small to medium-sized data volumes where conventional algorithms often introduce significant overhead.

How the FSP Algorithm Works

The FSP algorithm operates on the principle of identifying repeated patterns in data and replacing subsequent occurrences with references to the first occurrence. This approach significantly reduces redundancy without the overhead of traditional compression methods.

Compression Process

1. Pattern Discovery - The algorithm scans the input data to identify repeated patterns of lengths between the configured minimum and maximum values (typically 3-5 characters).
2. Automatic Pattern Selection - The algorithm automatically selects the optimal pattern length (3-5 characters) that maximizes repeated patterns while avoiding overhead from too-short sequences.
3. Reference Creation - For each repeated pattern, the algorithm creates a reference pointing to the first occurrence of that pattern. Patterns that repeat only once are stored as LITERAL to minimize REF overhead.
4. Byte-Exact Storage - REF and LITERAL are stored as raw bytes for exact size tracking. LITERAL stores 1 byte per character. REF stores position and length information.
5. Output Generation - The compressed output consists of a combination of literal data (for unique patterns) and references (for repeated patterns) and can be saved directly to a file.

Decompression Process

1. Parsing - The decompressor reads the compressed data, parsing literal values and references.
2. Reconstruction - For each reference, the decompressor looks up the referenced pattern and inserts it into the output.
3. Output - The original data is perfectly reconstructed by combining literal values and resolved references.

Implementation Details

The FSP algorithm is implemented in Python but can be easily ported to other programming languages. Below is the core implementation of the pattern finding and compression logic.

Pattern Discovery Function

def find_patterns(text, min_len=3, max_len=5):
    """Find repeated patterns in text and return dictionary with positions"""
    patterns = defaultdict(list)
    n = len(text)
    
    # Search for patterns of all lengths between min_len and max_len
    for L in range(min_len, max_len + 1):
        for i in range(n - L + 1):
            s = text[i:i+L]
            patterns[s].append(i)
    
    # Keep only patterns that occur more than once
    return {p: pos for p, pos in patterns.items() if len(pos) > 1}

Compression Function (Byte-Level)

def fsp_compress(text, min_len=3, max_len=5):
    """Compress text using the FSP algorithm with byte-level storage"""
    patterns = find_patterns(text, min_len, max_len)
    compressed = bytearray()
    i = 0
    
    while i < len(text):
        best_pat = None
        best_pos = None
        best_len = 0
        
        for pat, positions in patterns.items():
            if i in positions and len(pat) > best_len:
                # Find first previous occurrence
                prev_positions = [p for p in positions if p < i]
                if prev_positions:
                    best_pat = pat
                    best_pos = prev_positions[-1]
                    best_len = len(pat)
        
        if best_pat and best_pos is not None:
            # REF: 2 bytes pos + 1 byte len
            compressed += struct.pack(">HB", best_pos, best_len)
            i += best_len
        else:
            # LITERAL: 1 byte
            compressed.append(ord(text[i]))
            i += 1
            
    return compressed

Decompression Function (Byte-Level)

def fsp_decompress(compressed):
    """Decompress FSP-compressed data with byte-level storage"""
    output = []
    i = 0
    
    while i < len(compressed):
        # Check if next 3 bytes could be a REF
        if i + 3 <= len(compressed):
            pos, length = struct.unpack(">HB", compressed[i:i+3])
            # Valid REF: pos < len(output)
            if pos < len(output):
                output.extend(output[pos:pos+length])
                i += 3
                continue
        # Otherwise, literal
        output.append(compressed[i])
        i += 1
        
    return bytes(output).decode("ascii")

Pattern Length Guidelines

• Automatic min_len = 3–5 characters
• Max pattern length = 5–6 characters for longer repeats
• Short repetitive text → min_len=3, max_len=5
• Longer logs/technical text → min_len=4, max_len=6

Features & Advantages

Technical Advantages

• Minimal overhead for service information
• Ability to process data in streams
• Easy adaptation for working with binary data
• Support for incremental compression
• No dictionary storage requirements
• Lossless compression - perfect data reconstruction
• Cross-language implementable (Python, C, C++, Java, Rust, Go, etc.)
• Testable with speed measurement for compression and decompression

Detailed Examples

Example 1: Simple Text Compression

('LITERAL', 'H')
('LITERAL', 'e')
('LITERAL', 'l')
('LITERAL', 'l')
('LITERAL', 'o')
('LITERAL', ' ')
('LITERAL', 'f')
('LITERAL', 'r')
('LITERAL', 'i')
('LITERAL', 'e')
('LITERAL', 'n')
('LITERAL', 'd')
('LITERAL', '!')
('LITERAL', ' ')
('REF', 0, 5)  // Reference to "Hello"
('LITERAL', ' ')
('LITERAL', 'f')
('REF', 8, 5)  // Reference to "riend"
// ... additional references

Example 2: Binary Data Adaptation

def fsp_compress_binary(data, min_len=3, max_len=5):
    """Compress binary data using FSP algorithm"""
    patterns = defaultdict(list)
    n = len(data)
    
    # Search for patterns of all lengths between min_len and max_len
    for L in range(min_len, max_len + 1):
        for i in range(n - L + 1):
            pattern = data[i:i+L]
            patterns[pattern].append(i)
    
    # Keep only patterns that occur more than once
    patterns = {p: pos for p, pos in patterns.items() if len(pos) > 1}
    
    compressed = bytearray()
    i = 0
    
    while i < n:
        # Try to find the longest pattern starting at i
        best_pat = None
        best_pos = None
        best_len = 0
        
        for pat, positions in patterns.items():
            if i in positions and len(pat) > best_len:
                prev_positions = [p for p in positions if p < i]
                if prev_positions:
                    best_pat = pat
                    best_pos = prev_positions[-1]
                    best_len = len(pat)
        
        if best_pat and best_pos is not None:
            # REF: position + length
            compressed += struct.pack(">HB", best_pos, best_len)
            i += best_len
        else:
            # LITERAL: 1 byte
            compressed.append(data[i])
            i += 1
            
    return compressed

Example 3: File Output

# Save compressed to file
with open("output.txt", "wb") as f:
    f.write(compressed)

# Read compressed from file
with open("output.txt", "rb") as f:
    compressed_data = f.read()
    decompressed = fsp_decompress(compressed_data)

Comparison with Other Algorithms

Applications

Ideal Use Cases

Limitations

Changelog