The btrie Reference Manual

Table of Contents

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 2.3 "Robert April" on Wed Mar 14 03:00:15 2018 GMT+0.


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

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

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

2 Systems

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


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

2.1 btrie

Author

Peter Hillerström <peter.hillerstrom@gmail.com>

License

Simplified BSD license.

Description

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.

Version

0.2.1

Dependencies
Source

btrie.asd (file)

Component

btrie.lisp (file)


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

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 files   [Contents][Index]

3.1.1 btrie.asd

Location

btrie.asd

Systems

btrie (system)

Packages

nu.composed.btrie.system


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

3.1.2 btrie/btrie.lisp

Parent

btrie (system)

Location

btrie.lisp

Packages

nu.composed.btrie

Exported Definitions
Internal Definitions

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

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

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

4.2 nu.composed.btrie

Branch trie – an implementation of tries with branch widths.

Source

btrie.lisp (file)

Nickname

btrie

Use List
Exported Definitions
Internal Definitions

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

5 Definitions

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


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

5.1 Exported definitions


Next: , Previous: , Up: Exported definitions   [Contents][Index]

5.1.1 Special variables

Special Variable: +word-marker+
Package

nu.composed.btrie

Source

btrie.lisp (file)


Next: , Previous: , Up: Exported definitions   [Contents][Index]

5.1.2 Functions

Function: leafp NODE

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

Package

nu.composed.btrie

Source

btrie.lisp (file)

Function: make-leaf &key WIDTH
Package

nu.composed.btrie

Source

btrie.lisp (file)

Function: make-node &key KEY WIDTH BRANCHES LEAF

Utility function to make a trie instance.

Package

nu.composed.btrie

Source

btrie.lisp (file)

Function: make-trie &optional SEQS

Make a trie with letters as keys.

Package

nu.composed.btrie

Source

btrie.lisp (file)

Function: make-word-trie SEQS

Make a test trie with words as keys.

Package

nu.composed.btrie

Source

btrie.lisp (file)

Function: nodes-equalp A B
Package

nu.composed.btrie

Source

btrie.lisp (file)

Function: only-terminal-p NODE

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

Package

nu.composed.btrie

Source

btrie.lisp (file)

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 (file)

Function: sort-trie TRIE PREDICATE &rest ARGS

Sort a trie recursively with a predicate function.

Package

nu.composed.btrie

Source

btrie.lisp (file)

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 (file)

Function: wordp NODE

Predicate to tell whether this node ends any words.

Package

nu.composed.btrie

Source

btrie.lisp (file)


Next: , Previous: , Up: Exported definitions   [Contents][Index]

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 (file)

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 (file)

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 (file)

Generic Function: add-subseqs TRIE SEQ LEN
Package

nu.composed.btrie

Methods
Method: add-subseqs (TRIE trie) (SEQ sequence) (LEN integer)
Source

btrie.lisp (file)

Generic Function: branches OBJECT
Generic Function: (setf branches) NEW-VALUE OBJECT
Package

nu.composed.btrie

Methods
Method: branches (TRIE trie)

automatically generated reader method

Source

btrie.lisp (file)

Method: (setf branches) NEW-VALUE (TRIE trie)

automatically generated writer method

Source

btrie.lisp (file)

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 (file)

Generic Function: key OBJECT
Package

nu.composed.btrie

Methods
Method: key (TRIE trie)

Can be any type for generality.

Source

btrie.lisp (file)

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 (file)

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 (file)

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 (file)

Generic Function: width OBJECT
Generic Function: (setf width) NEW-VALUE OBJECT
Package

nu.composed.btrie

Methods
Method: width (TRIE trie)

automatically generated reader method

Source

btrie.lisp (file)

Method: (setf width) NEW-VALUE (TRIE trie)

automatically generated writer method

Source

btrie.lisp (file)


Previous: , Up: Exported definitions   [Contents][Index]

5.1.4 Classes

Class: trie ()

Trie data structure, see package documentation for more info.

Package

nu.composed.btrie

Source

btrie.lisp (file)

Direct superclasses

standard-object (class)

Direct methods
Direct slots
Slot: key

Can be any type for generality.

Type

atom

Initargs

:key

Initform

""

Readers

key (generic function)

Slot: width
Type

(integer 0 *)

Initargs

:width

Initform

0

Readers

width (generic function)

Writers

(setf width) (generic function)

Slot: branches
Type

list

Initargs

:branches

Readers

branches (generic function)

Writers

(setf branches) (generic function)


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

5.2 Internal definitions


Next: , Previous: , Up: Internal definitions   [Contents][Index]

5.2.1 Special variables

Special Variable: *debug*
Package

nu.composed.btrie

Source

btrie.lisp (file)


Next: , Previous: , Up: Internal definitions   [Contents][Index]

5.2.2 Functions

Function: cut-sequence SEQ TIMES
Package

nu.composed.btrie

Source

btrie.lisp (file)

Function: interleave SEQ NUM-PARTS
Package

nu.composed.btrie

Source

btrie.lisp (file)

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 (file)

Function: print-trie-simple TRIE &optional STREAM DEPTH INDENT

## Traverse tries printing out nodes

Package

nu.composed.btrie

Source

btrie.lisp (file)

Function: subseqs SEQ LENGTH
Package

nu.composed.btrie

Source

btrie.lisp (file)


Previous: , Up: Internal definitions   [Contents][Index]

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 (file)

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 (file)

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 (file)

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 (file)

Generic Function: remove-node TRIE KEY
Package

nu.composed.btrie

Methods
Method: remove-node (TRIE trie) KEY
Source

btrie.lisp (file)

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 (file)

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 (file)


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

Appendix A Indexes


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

A.1 Concepts

Jump to:   B   F   L  
Index Entry  Section

B
btrie.asd: The btrie<dot>asd file
btrie/btrie.lisp: The btrie/btrie<dot>lisp file

F
File, Lisp, btrie.asd: The btrie<dot>asd file
File, Lisp, btrie/btrie.lisp: The btrie/btrie<dot>lisp file

L
Lisp File, btrie.asd: The btrie<dot>asd file
Lisp File, btrie/btrie.lisp: The btrie/btrie<dot>lisp file

Jump to:   B   F   L  

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): Exported generic functions
(setf branches): Exported generic functions
(setf width): Exported generic functions
(setf width): Exported generic functions

A
add: Exported generic functions
add: Exported generic functions
add-key: Internal generic functions
add-key: Internal generic functions
add-seqs: Exported generic functions
add-seqs: Exported generic functions
add-seqs-as-keys: Exported generic functions
add-seqs-as-keys: Exported generic functions
add-subseqs: Exported generic functions
add-subseqs: Exported generic functions

B
branches: Exported generic functions
branches: Exported generic functions

C
create-node: Internal generic functions
create-node: Internal generic functions
cut-sequence: Internal functions

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

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

I
interleave: Internal functions

K
key: Exported generic functions
key: Exported generic functions

L
leafp: Exported functions

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

N
nodes-equalp: Exported functions

O
obtain-seq: Exported generic functions
obtain-seq: Exported generic functions
only-terminal-p: Exported functions

P
print-trie-simple: Internal functions
print-trie-to-stream: Internal generic functions
print-trie-to-stream: Internal generic functions
print-words: Exported functions

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

S
sort-trie: Exported functions
sort-trie-branch: Exported functions
subseqs: Internal functions
sym-interval: Internal generic functions
sym-interval: Internal generic functions
sym-low: Internal generic functions
sym-low: Internal generic functions

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

W
width: Exported generic functions
width: Exported generic functions
wordp: Exported functions

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

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

A.3 Variables

Jump to:   *   +  
B   K   S   W  
Index Entry  Section

*
*debug*: Internal special variables

+
+word-marker+: Exported special variables

B
branches: Exported classes

K
key: Exported classes

S
Slot, branches: Exported classes
Slot, key: Exported classes
Slot, width: Exported classes
Special Variable, *debug*: Internal special variables
Special Variable, +word-marker+: Exported special variables

W
width: Exported classes

Jump to:   *   +  
B   K   S   W  

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

A.4 Data types

Jump to:   B   C   N   P   S   T  
Index Entry  Section

B
btrie: The btrie system

C
Class, trie: Exported classes

N
nu.composed.btrie: The nu<dot>composed<dot>btrie package
nu.composed.btrie.system: The nu<dot>composed<dot>btrie<dot>system package

P
Package, nu.composed.btrie: The nu<dot>composed<dot>btrie package
Package, nu.composed.btrie.system: The nu<dot>composed<dot>btrie<dot>system package

S
System, btrie: The btrie system

T
trie: Exported classes

Jump to:   B   C   N   P   S   T