#fst #patricia #radix #trie #radix-trie #data-structure


A specialised trie for paths in the style of a Patricia or radix trie

2 releases

0.1.1 Sep 5, 2020
0.1.0 Sep 5, 2020

#847 in Filesystem

Download history 11/week @ 2023-02-11 31/week @ 2023-02-18 4/week @ 2023-02-25 23/week @ 2023-03-04 11/week @ 2023-03-11 19/week @ 2023-03-18 5/week @ 2023-03-25 16/week @ 2023-04-01 20/week @ 2023-04-08 17/week @ 2023-04-15 5/week @ 2023-04-22 37/week @ 2023-04-29 13/week @ 2023-05-06 9/week @ 2023-05-13 7/week @ 2023-05-20 31/week @ 2023-05-27

65 downloads per month





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.


Add this to your Cargo.toml:

pathtrie = "0.1"

Where is this used?

  • box - a modern replacement for the zip file format


Licensed under either of

at your option.


~31K SLoC