pathtrie

A specialised trie for paths in the style of a Patricia or radix trie, with optional optimised FST output.

The intended usage of this data structure is for optimally storing and querying keys that have a large number of shared prefixes, such as file paths in a file system.

This crate is partly inspired by the fst crate by Andrew Gallant. There are a few significant differences to that crate, however:

• Simplicity of implementation was prioritised over speed
• The trie structure is mutable and can be later written into an FST
• Insertions do not need to be in lexicographical order

It is a goal of this project to stabilise the FST format once proven to be bug-free.

Usage

Add this to your Cargo.toml:

[dependencies]
pathtrie = "0.1"

Where is this used?

• box - a modern replacement for the zip file format

License

Licensed under either of

• Apache License, Version 2.0, (LICENSE-APACHE or http://www.apache.org/licenses/LICENSE-2.0)
• MIT license (LICENSE-MIT or http://opensource.org/licenses/MIT)

at your option.