jwalsh / jwalsh/hy-algorithms

Implement compression data structures

Open
#40 0 comments 0 reactions 0 assignees View on GitHub
data-structure difficulty:hard
Dominant language
Hy
Stars
2
Forks
0
PR merge metrics
No merged PRs in 30d

Description

Create implementations for space-efficient data structures:

## Compact data structures:
- Succinct arrays
- Compressed bitvectors
- Wavelet trees
- Compressed suffix arrays
- FM-index
- LOUDS (Level-Order Unary Degree Sequence)
- Succinct tree representations

## Specific implementations:
- Rank and select operations on bitvectors
- Compressed tries
- Succinct dictionaries
- Space-efficient hash tables
- Memory-efficient trees

## Applications:
- Text indexing
- Genome sequence analysis
- Large graph representation
- Information retrieval systems

## Requirements:
- Provide space usage analysis
- Include time complexity for operations
- Create test cases with large datasets
- Document compression vs. speed trade-offs

This collection will demonstrate data structures that achieve near-optimal space usage while still supporting efficient operations, which is crucial for applications dealing with massive datasets.

Contributor guide

Open the contributing guide

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.