The btrie Reference Manual

This is the btrie Reference Manual, version 0.2.1, generated automatically by Declt version 4.0 beta 2 "William Riker" on Mon Feb 26 14:46:45 2024 GMT+0.

Table of Contents


1 Introduction


2 Systems

The main system appears first, followed by any subsystem dependency.


2.1 btrie

Branch trie - a generic trie implementation with branch widths.

* Implementation is generic: keys can be of sequences of any type.
* Branch width of a trie node tells how many branches go through that node and can be used to calculate probabilites for different suffixes.

Author

Peter Hillerström <>

License

Simplified BSD license.

Version

0.2.1

Dependencies
  • arnesi (system).
  • split-sequence (system).
  • lift (system).
Source

btrie.asd.

Child Component

btrie.lisp (file).


3 Files

Files are sorted by type and then listed depth-first from the systems components trees.


3.1 Lisp


3.1.1 btrie/btrie.asd

Source

btrie.asd.

Parent Component

btrie (system).

ASDF Systems

btrie.

Packages

nu.composed.btrie.system.


3.1.2 btrie/btrie.lisp

Source

btrie.asd.

Parent Component

btrie (system).

Packages

nu.composed.btrie.

Public Interface
Internals

4 Packages

Packages are listed by definition order.


4.1 nu.composed.btrie

Branch trie – an implementation of tries with branch widths.

Source

btrie.lisp.

Nickname

btrie

Use List
  • common-lisp.
  • it.bese.arnesi.
  • lift.
Public Interface
Internals

4.2 nu.composed.btrie.system

Source

btrie.asd.

Use List
  • asdf/interface.
  • common-lisp.

5 Definitions

Definitions are sorted by export status, category, package, and then by lexicographic order.


5.1 Public Interface


5.1.1 Special variables

Special Variable: +word-marker+
Package

nu.composed.btrie.

Source

btrie.lisp.


5.1.2 Ordinary functions

Function: leafp (node)

Predicate to tell if there are no branches for a node.

Package

nu.composed.btrie.

Source

btrie.lisp.

Function: make-leaf (&key width)
Package

nu.composed.btrie.

Source

btrie.lisp.

Function: make-node (&key key width branches leaf)

Utility function to make a trie instance.

Package

nu.composed.btrie.

Source

btrie.lisp.

Function: make-trie (&optional seqs)

Make a trie with letters as keys.

Package

nu.composed.btrie.

Source

btrie.lisp.

Function: make-word-trie (seqs)

Make a test trie with words as keys.

Package

nu.composed.btrie.

Source

btrie.lisp.

Function: nodes-equalp (a b)
Package

nu.composed.btrie.

Source

btrie.lisp.

Function: only-terminal-p (node)

This predicate tells if node has only terminal as a child.

Package

nu.composed.btrie.

Source

btrie.lisp.

Function: print-words (trie &optional stream prefix)

Prints words from the trie, one per line. Returns total word count.

Options:
* with-count: Prints word counts after tab when over one.

TODO:
* Use keyword arguments?
* Implement start, end
* Allow to specify separator instead of newline

Package

nu.composed.btrie.

Source

btrie.lisp.

Function: sort-trie (trie predicate &rest args)

Sort a trie recursively with a predicate function.

Package

nu.composed.btrie.

Source

btrie.lisp.

Function: sort-trie-branch (trie predicate &key key stable)

Sort a trie node’s branches with a predicate function.

Package

nu.composed.btrie.

Source

btrie.lisp.

Function: wordp (node)

Predicate to tell whether this node ends any words.

Package

nu.composed.btrie.

Source

btrie.lisp.


5.1.3 Generic functions

Generic Function: add (trie seq &optional count)
Package

nu.composed.btrie.

Methods
Method: add ((trie trie) (seq sequence) &optional count)

Add a branch to the trie count times. Modifies trie in-place. If branch already exists, increase it’s width.
A count below one is changed to one.

Source

btrie.lisp.

Generic Function: add-seqs (trie seqs &optional count)
Package

nu.composed.btrie.

Methods
Method: add-seqs ((trie trie) (seqs list) &optional count)
Source

btrie.lisp.

Generic Function: add-seqs-as-keys (trie seqs &optional count)
Package

nu.composed.btrie.

Methods
Method: add-seqs-as-keys ((trie trie) (seqs sequence) &optional count)
Source

btrie.lisp.

Generic Function: add-subseqs (trie seq len)
Package

nu.composed.btrie.

Methods
Method: add-subseqs ((trie trie) (seq sequence) (len integer))
Source

btrie.lisp.

Generic Reader: branches (object)
Package

nu.composed.btrie.

Methods
Reader Method: branches ((trie trie))

automatically generated reader method

Source

btrie.lisp.

Target Slot

branches.

Generic Writer: (setf branches) (object)
Package

nu.composed.btrie.

Methods
Writer Method: (setf branches) ((trie trie))

automatically generated writer method

Source

btrie.lisp.

Target Slot

branches.

Generic Function: find-key (trie key)
Package

nu.composed.btrie.

Methods
Method: find-key ((trie trie) key)

Get a symbol matching key from trie’s branches.

Source

btrie.lisp.

Generic Reader: key (object)
Package

nu.composed.btrie.

Methods
Reader Method: key ((trie trie))

Can be any type for generality.

Source

btrie.lisp.

Target Slot

key.

Generic Function: obtain-seq (trie seq)
Package

nu.composed.btrie.

Methods
Method: obtain-seq ((trie trie) (seq sequence))

Get a sequence from trie by following the keys in the sequence.

Source

btrie.lisp.

Generic Function: traverse (trie fun &key do-leafs)
Package

nu.composed.btrie.

Methods
Method: traverse ((trie trie) (fun function) &key do-leafs)

Traverse the trie perfoming a function on each node.

Source

btrie.lisp.

Generic Function: trie-prob (root suffix)
Package

nu.composed.btrie.

Methods
Method: trie-prob ((root trie) suffix)

Returns probability of suffix on given trie.

Source

btrie.lisp.

Generic Reader: width (object)
Package

nu.composed.btrie.

Methods
Reader Method: width ((trie trie))

automatically generated reader method

Source

btrie.lisp.

Target Slot

width.

Generic Writer: (setf width) (object)
Package

nu.composed.btrie.

Methods
Writer Method: (setf width) ((trie trie))

automatically generated writer method

Source

btrie.lisp.

Target Slot

width.


5.1.4 Standalone methods

Method: print-object ((trie trie) stream)
Source

btrie.lisp.


5.1.5 Classes

Class: trie

Trie data structure, see package documentation for more info.

Package

nu.composed.btrie.

Source

btrie.lisp.

Direct methods
Direct slots
Slot: key

Can be any type for generality.

Type

atom

Initform

""

Initargs

:key

Readers

key.

Writers

This slot is read-only.

Slot: width
Type

(integer 0 *)

Initform

0

Initargs

:width

Readers

width.

Writers

(setf width).

Slot: branches
Type

list

Initargs

:branches

Readers

branches.

Writers

(setf branches).


5.2 Internals


5.2.1 Special variables

Special Variable: *debug*
Package

nu.composed.btrie.

Source

btrie.lisp.


5.2.2 Ordinary functions

Function: cut-sequence (seq times)
Package

nu.composed.btrie.

Source

btrie.lisp.

Function: interleave (seq num-parts)
Package

nu.composed.btrie.

Source

btrie.lisp.

Function: make-trie-with-fn (&optional fn seqs)

Simple utility function to build a trie from a sequence.

Package

nu.composed.btrie.

Source

btrie.lisp.

Function: print-trie-simple (trie &optional stream depth indent)

## Traverse tries printing out nodes

Package

nu.composed.btrie.

Source

btrie.lisp.

Function: subseqs (seq length)
Package

nu.composed.btrie.

Source

btrie.lisp.


5.2.3 Generic functions

Generic Function: add-key (trie key &optional count)
Package

nu.composed.btrie.

Methods
Method: add-key ((trie trie) key &optional count)

Add a node to trie. If node exists, increases it’s width.

Source

btrie.lisp.

Generic Function: create-node (trie key &optional count)
Package

nu.composed.btrie.

Methods
Method: create-node ((trie trie) key &optional count)

Destructively adds node to trie

Source

btrie.lisp.

Generic Function: print-trie-to-stream (trie stream &optional depth compact)
Package

nu.composed.btrie.

Methods
Method: print-trie-to-stream ((trie trie) stream &optional depth compact)

Pretty print the trie.

Source

btrie.lisp.

Generic Function: remove-key (trie key &optional count)
Package

nu.composed.btrie.

Methods
Method: remove-key ((trie trie) key &optional count)

### Remove a node from trie. If node exists, decrease it’s width.

Source

btrie.lisp.

Generic Function: remove-node (trie key)
Package

nu.composed.btrie.

Methods
Method: remove-node ((trie trie) key)
Source

btrie.lisp.

Generic Function: sym-interval (trie key)
Package

nu.composed.btrie.

Methods
Method: sym-interval ((trie trie) key)

Return interval limits for a symbol matching key. Nil if key not found.

Source

btrie.lisp.

Generic Function: sym-low (trie key)
Package

nu.composed.btrie.

Methods
Method: sym-low ((trie trie) key)

Return a cumulative lower limit for a symbol matching key. Nil if key not found.

Source

btrie.lisp.


Appendix A Indexes


A.1 Concepts


A.2 Functions

Jump to:   (  
A   B   C   F   G   I   K   L   M   N   O   P   R   S   T   W  
Index Entry  Section

(
(setf branches): Public generic functions
(setf branches): Public generic functions
(setf width): Public generic functions
(setf width): Public generic functions

A
add: Public generic functions
add: Public generic functions
add-key: Private generic functions
add-key: Private generic functions
add-seqs: Public generic functions
add-seqs: Public generic functions
add-seqs-as-keys: Public generic functions
add-seqs-as-keys: Public generic functions
add-subseqs: Public generic functions
add-subseqs: Public generic functions

B
branches: Public generic functions
branches: Public generic functions

C
create-node: Private generic functions
create-node: Private generic functions
cut-sequence: Private ordinary functions

F
find-key: Public generic functions
find-key: Public generic functions
Function, cut-sequence: Private ordinary functions
Function, interleave: Private ordinary functions
Function, leafp: Public ordinary functions
Function, make-leaf: Public ordinary functions
Function, make-node: Public ordinary functions
Function, make-trie: Public ordinary functions
Function, make-trie-with-fn: Private ordinary functions
Function, make-word-trie: Public ordinary functions
Function, nodes-equalp: Public ordinary functions
Function, only-terminal-p: Public ordinary functions
Function, print-trie-simple: Private ordinary functions
Function, print-words: Public ordinary functions
Function, sort-trie: Public ordinary functions
Function, sort-trie-branch: Public ordinary functions
Function, subseqs: Private ordinary functions
Function, wordp: Public ordinary functions

G
Generic Function, (setf branches): Public generic functions
Generic Function, (setf width): Public generic functions
Generic Function, add: Public generic functions
Generic Function, add-key: Private generic functions
Generic Function, add-seqs: Public generic functions
Generic Function, add-seqs-as-keys: Public generic functions
Generic Function, add-subseqs: Public generic functions
Generic Function, branches: Public generic functions
Generic Function, create-node: Private generic functions
Generic Function, find-key: Public generic functions
Generic Function, key: Public generic functions
Generic Function, obtain-seq: Public generic functions
Generic Function, print-trie-to-stream: Private generic functions
Generic Function, remove-key: Private generic functions
Generic Function, remove-node: Private generic functions
Generic Function, sym-interval: Private generic functions
Generic Function, sym-low: Private generic functions
Generic Function, traverse: Public generic functions
Generic Function, trie-prob: Public generic functions
Generic Function, width: Public generic functions

I
interleave: Private ordinary functions

K
key: Public generic functions
key: Public generic functions

L
leafp: Public ordinary functions

M
make-leaf: Public ordinary functions
make-node: Public ordinary functions
make-trie: Public ordinary functions
make-trie-with-fn: Private ordinary functions
make-word-trie: Public ordinary functions
Method, (setf branches): Public generic functions
Method, (setf width): Public generic functions
Method, add: Public generic functions
Method, add-key: Private generic functions
Method, add-seqs: Public generic functions
Method, add-seqs-as-keys: Public generic functions
Method, add-subseqs: Public generic functions
Method, branches: Public generic functions
Method, create-node: Private generic functions
Method, find-key: Public generic functions
Method, key: Public generic functions
Method, obtain-seq: Public generic functions
Method, print-object: Public standalone methods
Method, print-trie-to-stream: Private generic functions
Method, remove-key: Private generic functions
Method, remove-node: Private generic functions
Method, sym-interval: Private generic functions
Method, sym-low: Private generic functions
Method, traverse: Public generic functions
Method, trie-prob: Public generic functions
Method, width: Public generic functions

N
nodes-equalp: Public ordinary functions

O
obtain-seq: Public generic functions
obtain-seq: Public generic functions
only-terminal-p: Public ordinary functions

P
print-object: Public standalone methods
print-trie-simple: Private ordinary functions
print-trie-to-stream: Private generic functions
print-trie-to-stream: Private generic functions
print-words: Public ordinary functions

R
remove-key: Private generic functions
remove-key: Private generic functions
remove-node: Private generic functions
remove-node: Private generic functions

S
sort-trie: Public ordinary functions
sort-trie-branch: Public ordinary functions
subseqs: Private ordinary functions
sym-interval: Private generic functions
sym-interval: Private generic functions
sym-low: Private generic functions
sym-low: Private generic functions

T
traverse: Public generic functions
traverse: Public generic functions
trie-prob: Public generic functions
trie-prob: Public generic functions

W
width: Public generic functions
width: Public generic functions
wordp: Public ordinary functions