Checks for unique decodability

This repo is an informal collection of functions that (attempt to) check whether a given list of code words is uniquely decodable.

Note: If you're just looking to check if a word list is uniquely decodable, I'd point you to my Word List Auditor tool.

A hypothesis

I think that best way to do check if a list is uniquely decodable is to implement the Sardinas–Patterson algorithm, but it might not be the only way?

Included implementations of Sardinas-Patterson

So far this project includes two implementations of Sardinas-Patterson:

• The one Sam Schlinkert wrote for Tidy (src/schlinkert.rs)
• An implementation by GitHub user @Colfenor, apparently based on this paper by Michael Rodeh (src/colfenor_rodeh.rs). Seems to be very fast detecting if a list is not uniquely decodable, but struggles with longer (8,000-word) uniquely decodable lists?

Running tests

cargo test

Running benchmarks

This project uses Criterion.rs v0.5 to benchmark.

cargo bench

FYI running all benchmarks can take a few minutes, depending on which are commented in and out.

Adding your own procedure/implementation

I 100% welcome and encourage you to contribute to this project, either with your own implementation of Sardinas-Patterson, or some other way of checking for unique decodability. See the current modules for requirements.

Potentially helpful links

• Sardinas-Patterson algorithm Wikipedia page
• A YouTube video explaining Sardinas-Patterson
• A blog post about implementation Sardinas-Patterson in Python
• An implementation of Sardinas-Patterson in C++
• An interesting-looking paper?