splaytree-compression 2.0.0

Lossless compression using adaptive Splay Tree with BWT+MTF pipeline support

Splay Tree Compression

Lossless text compression using adaptive Splay Tree prefix coding.

This package implements an optimized Splay Tree-based compression algorithm with various performance improvements including:

• Array-based storage for better cache locality
• Semi-splaying strategies to reduce rotation overhead
• Block reset mechanisms for multi-domain data
• Configurable splay frequency

Installation

From local source

# Navigate to package directory
cd package

# Install in development mode (editable)
pip install -e .

# Or install normally
pip install .

From PyPI (if published)

pip install splaytree-compression

Quick Start

Command Line Interface

# Compress a file
splay-compress compress input.txt -o output.splay

# Compress with preset
splay-compress compress input.txt --preset fast

# Decompress
splay-compress decompress output.splay -o input.txt

Python API

from splaytree_compression import SplayCompressor

# Using preset
compressor = SplayCompressor(preset='balanced')
compressed = compressor.compress(data)
decompressed = compressor.decompress(compressed)

# Custom parameters
compressor = SplayCompressor.create_custom(
    splay_every=4,
    depth_threshold=10,
    target_depth=1,
    reset_block_bytes=64*1024
)
compressed = compressor.compress(data)

Low-level API

from splaytree_compression import SplayPrefixCoder

# Create coder
coder = SplayPrefixCoder(
    alphabet_size=256,
    splay_every=4,
    depth_threshold=10,
    target_depth=1,
    reset_block_bytes=64*1024
)

# Compress
compressed = coder.compress(data)

# Decompress (parameters are stored in header)
decompressed = SplayPrefixCoder.decompress(compressed)

Compression Presets

• fast: Optimized for speed

  • splay_every=8, target_depth=2
  • Best for large files where speed matters

• balanced: Balanced speed/ratio (default)

  • splay_every=4, depth_threshold=10, target_depth=1, reset_block_bytes=64KB
  • Good general-purpose setting

• best_ratio: Best compression ratio

  • splay_every=1, target_depth=0 (full splay)
  • Best compression but slower

Parameters

• alphabet_size (int, default 256): Size of alphabet (2-256)
• splay_every (int, default 1): Splay every k symbols (k>=1)
• depth_threshold (int, optional): Splay when depth > threshold
• target_depth (int, default 0): Target depth for semi-splay (0 = full splay to root)
• reset_block_bytes (int, optional): Reset tree every N bytes

Performance

Based on benchmarks, the optimized version achieves:

• ~3.75x speedup compared to baseline
• Compression ratio: ~0.75-0.78 (depending on data)
• Suitable for educational/research purposes

Note: This algorithm is not intended to compete with industrial compression algorithms like zlib or LZMA, but rather serves as a research tool to understand adaptive prefix coding with Splay Trees.

Documentation

• INSTALL.md: Detailed installation instructions
• PACKAGE_USAGE.md: Usage guide with examples
• PUBLISH.md: Guide for publishing to PyPI

Examples

Compress with custom parameters

splay-compress compress input.txt \
    --splay-every 8 \
    --target-depth 2 \
    -o output.splay

Batch compression

from pathlib import Path
from splaytree_compression import SplayCompressor

compressor = SplayCompressor(preset='balanced')

for file in Path('data').glob('*.txt'):
    with open(file, 'rb') as f:
        data = f.read()
    
    compressed = compressor.compress(data)
    
    with open(file.with_suffix('.splay'), 'wb') as f:
        f.write(compressed)
    
    print(f"Compressed {file}: {len(data)} -> {len(compressed)} bytes")

Development

# Install in development mode with dev dependencies
pip install -e ".[dev]"

# Run tests
python test_package.py

# Format code
black splaytree_compression/

# Type checking
mypy splaytree_compression/

License

MIT License

References

Based on research paper: "Advanced Lossless Text Compression Algorithm Based on Splay Tree Adaptive Methods"

Contributing

Contributions are welcome! Please feel free to submit a Pull Request.