Tries.jl

A Julia prefix tree. Trie is an associative data structure with keys of type NTuple{N,K} where N and values of type V.
Author gkappler
Popularity
4 Stars
Updated Last
10 Months Ago
Started In
May 2020

Tries

Dev Build Status Codecov

Trie is a small package providing a tree-like data structure implemented on a Dict backend and using AbstractTrees for printing and traversal. Trie generalizes DataStructures.Trie from AbstractString keys to arbitrary NTuple{N,K} where N key types.

Some design decisions for a trie::Trie{K,V} regarding keytype and getindex might change in future versions based on discussions with the community. :

  • getindex(trie, ks::K...) and setindex!(trie, v, ks::K...) consider Trie as sparse representation of an object with values::Union{V,Missing} referenced by any finite N-dimensional key ks::NTuple{N,K} where N.
  • keytype(trie) currently is K, should it be ks::NTuple{N,K} where N?
  • Future versions might switch backend to Andy Ferris Dictionaries.jl. Contributions, thoughts and suggestions very welcome!

julia> using Tries

julia> x=Trie((:a,)=>"a",
              (:a,:b)=>"c",
       	   (:a,:c,:d)=>"z",
       	   (:a,:b,:d)=>1)
Trie{Symbol,Any}
└─ :a => "a"
   ├─ :b => "c"
   │  └─ :d => 1
   └─ :c
      └─ :d => "z"

julia> eltype(x)
Any

julia> x[:a,:b]
SubTrie{Symbol,Any} @ :a, :b => "c"
└─ :d => 1

julia> x[:a,:b].path
(:a, :b)

julia> get(x[:a,:b])
"c"

julia> get(x[:a][:b,:d])
1

julia> #
       get(x,[:a,:b])
"c"

julia> x[:z]="added"
"added"

julia> get(x[:z])
"added"

julia> x[:z,:n]="n"
"n"

julia> x[:z]
SubTrie{Symbol,Any} @ :z => "added"
└─ :n => "n"

julia> x[:z,:n]="m"
"m"

julia> x[:z]
SubTrie{Symbol,Any} @ :z => "added"
└─ :n => "m"

julia> x
Trie{Symbol,Any}
├─ :a => "a"
│  ├─ :b => "c"
│  │  └─ :d => 1
│  └─ :c
│     └─ :d => "z"
└─ :z => "added"
   └─ :n => "m"
julia> using Tries

julia> x=Trie{Int,Int}(0) Trie{Int64,Int64} => 0

julia> subtrie!(x, 1,2,3,4,5) do x x[end]+1 end SubTrie{Int64,Int64} @ 1, 2, 3, 4, 5 => 6

julia> x Trie{Int64,Int64} => 0 └─ 1 => 2 └─ 2 => 3 └─ 3 => 4 └─ 4 => 5 └─ 5 => 6 ⋮

julia> collect(keys(x)) 6-element Array{Tuple{Vararg{Int64,N} where N},1}: () (1,) (1, 2) (1, 2, 3) (1, 2, 3, 4) (1, 2, 3, 4, 5)

Tries is used in CombinedParsers.jl for fast prefix tree matching (see docs).

Required Packages

Used By Packages