The btrie Reference Manual

Next: , Previous: , Up: (dir)   [Contents][Index]

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 Tue Nov 15 04:21:09 2022 GMT+0.

Table of Contents


1 Introduction

-------------------------------------------------------------------------
Branch trie - a generic trie implementation with branch widths
-------------------------------------------------------------------------
Version:  0.2.1
Initial Common Lisp version:  2010-08-01

Features:

  This trie implementation has an original idea of “branch width”
  invented by Peter Hillerström on 14 of November 2008. Branch width
  of a trie node tells how many branches go through that node.
  Widths can be used to calculate probabilites for different suffixes.

Notes about this implementation

  * The trie is implemented recursively, so 'trie' can mean the whole
    tree or a single node on a trie.
  * Generic: Keys can be sequences of any type.
  * IMPORTANT: All functions are destructive, for efficiently handling
    large data sets. There will be non-destructive versions of functions.

About tries generally:

  Trie, or prefix tree, is an ordered tree data structure that is used
  to store an associative array where the keys are usually strings.

  Unlike a binary search tree, no node in the tree stores the whole key
  associated with that node instead, its position in the tree shows
  what key it is associated with.

  All the descendants of a node have a common prefix of the string
  associated with that node, and the root is associated with the empty
  string. Looking up a key of length m takes worst case O(m) time.

  More information about tries:
  http://en.wikipedia.org/wiki/Trie

Todo:

  - Removal of sequences
  - Merging (union) of several tries and other set operations like intersection
  - Sliding window to keep at most n sequences in the trie
  - Bit tries using bit-vectors

2 Systems

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


Previous: , Up: Systems   [Contents][Index]

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 <peter.hillerstrom@gmail.com>

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.


Previous: , Up: Files   [Contents][Index]

3.1 Lisp


Next: , Previous: , Up: Lisp   [Contents][Index]

3.1.1 btrie/btrie.asd

Source

btrie.asd.

Parent Component

btrie (system).

ASDF Systems

btrie.

Packages

nu.composed.btrie.system.


Previous: , Up: Lisp   [Contents][Index]

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.


Next: , Previous: , Up: Packages   [Contents][Index]

4.1 nu.composed.btrie.system

Source

btrie.asd.

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

4.2 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

5 Definitions

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


Next: , Previous: , Up: Definitions   [Contents][Index]

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


Next: , Previous: , Up: Internals   [Contents][Index]

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


Next: , Previous: , Up: Indexes   [Contents][Index]

A.1 Concepts


Next: , Previous: , Up: Indexes   [Contents][Index]

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

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