Crate twie

twie [twaɪ] - Fast, compressed prefix tries.

This crate provides a Trie type that implements an associative container with slice-like keys. It has the following properties.

• Most one-shot operations are worst-case O(n), where n is the length of the key in bytes. This may require at most 2n tree hops, but the internal representation tries to minimize this where possible.

• Finding all prefixes of a string that are in the trie is also O(n). These prefixes are provided in order.

• Building a trie out of, e.g., an iterator is quadratic.

• Subtries of the whole trie (i.e. all entries with some particular prefix) can be operated on like regular tries (insertion is only supported from the root, unfortunately).

• Memory for storing keys is shared.

• The trie’s internal indexing type is configurable, which allows trading off maximum key size for shrinking the size of tree nodes, and thus, memory usage.

let words = Trie::<str, i32>::from([
  ("poise", 0),
  ("poison", 1),
  ("poisonous", 2),
  ("poison #9", 3),
]);

assert_eq!(
  words.prefixes("poisonous snake").map(|(k, _)| k).collect::<Vec<_>>(),
  ["poison", "poisonous"],
)

Here's a pretty diagram of what this trie looks like in memory.

  ┬╴[0]: ""
  │  ptrs: --|-/-/-/1|--|--
  │  
  └┬╴[1]: "?"
   │  hi: 0x7 'p'..='\u{7f}'
   │  ptrs: 2/-/-/-|--|--|--
   │  
   └┬╴[2]: "p"
    │  lo: 0x0 'p'
    │  ptrs: --|-/-/3/-|--|--
    │  
    └┬╴[3]: "p?"
     │  hi: 0x6 '`'..='o'
     │  ptrs: --|--|--|-/-/-/4
     │  
     └┬╴[4]: "po"
      │  lo: 0xf 'o'
      │  ptrs: --|-/-/5/-|--|--
      │  
      └┬╴[5]: "po?"
       │  hi: 0x6 '`'..='o'
       │  ptrs: --|--|-/6/-/-|--
       │  
       └┬╴[6]: "poi"
        │  lo: 0x9 'i'
        │  ptrs: --|-/-/-/7|--|--
        │  
        └┬╴[7]: "poi?"
         │  hi: 0x7 'p'..='\u{7f}'
         │  ptrs: -/-/-/8|--|--|--
         │  
         └┬╴[8]: "pois"
          │  lo: 0x3 's'
          │  ptrs: --|-/-/9/-|--|--
          │  
          └┬╴[9]: "pois?"
           │  hi: 0x6 '`'..='o'
           │  ptrs: --|-/10/-/-|--|-/-/-/12
           │  
           ├─╴[10]: "poise"
           │  lo: 0x5 'e'
           │  ptrs: --|--|--|--
           │  [0]: 0x55b3382cfc10 "poise" -> 0x55b3382cfc88 0
           │  
           └┬╴[12]: "poiso"
            │  lo: 0xf 'o'
            │  ptrs: --|-/-/11/-|--|--
            │  
            └┬╴[11]: "poiso?"
             │  hi: 0x6 '`'..='o'
             │  ptrs: --|--|--|-/-/14/-
             │  
             └┬╴[14]: "poison"
              │  lo: 0xe 'n'
              │  ptrs: -/-/15/-|-/-/13/-|--|--
              │  [1]: 0x55b3382d0570 "poison" -> 0x55b3382cfc94 1
              │  
              ├┬╴[15]: "poison?"
              ││  hi: 0x2 ' '..='/'
              ││  ptrs: 18/-/-/-|--|--|--
              ││  
              │└─╴[18]: "poison "
              │   lo: 0x0 ' '
              │   ptrs: --|--|--|--
              │   [3]: 0x55b3382cfae0 "poison #9" -> 0x55b3382cfcac 3
              │   
              └┬╴[13]: "poison?"
               │  hi: 0x6 '`'..='o'
               │  ptrs: --|--|--|-/-/-/16
               │  
               └─╴[16]: "poisono"
                  lo: 0xf 'o'
                  ptrs: --|--|--|--
                  [2]: 0x55b3382d0570 "poisonous" -> 0x55b3382cfca0 2
 

Structs

Iter

An in-order iterator over all values of a Trie.

IterMut

An in-order mutable iterator over all values of a Trie.

Prefixes

An iterator over all values of a Trie whose keys start with a particular prefix.

PrefixesMut

A mutable iterator over all values of a Trie whose keys start with a particular prefix.

Sub

A reference to some subtrie of a Trie.

SubMut

A reference to some subtrie of a Trie.

Subs

A depth-first iterator over all nonempty subtries of a Trie.

Trie

An radix prefix trie, optimized for searching for known prefixes of a string (for a fairly open-ended definition of “string”).

Traits

Buf

A trait for abstracting over str, [u8], and other byte-string-like types.

Index

A type usable as the internal index parameter of a Trie.