The cl-string-match Reference Manual
Table of Contents
The cl-string-match Reference Manual
This is the cl-string-match Reference Manual, version 2018.1.2,
generated automatically by Declt version 3.0 "Montgomery Scott"
on Tue Dec 22 12:51:23 2020 GMT+0.
1 Introduction
CL-STRING-MATCH
aims at providing robust implementations of string
matching algorithms. These algorithms are also called "substring
search"
or "subsequence search" algorithms.
Currently it provides implementations of the following string matching
algorithms (see wiki for details):
- Brute-force (also known as naïve algorithm)
- Boyer-Moore (with mismatched character heuristic and good suffix shift)
- Boyer-Moore-Horspool algorithm
- Knuth-Morris-Pratt algorithm
- Rabin-Karp algorithm
- Shift-OR algorithm (single pattern)
- Aho-Corasick algorithm (with finite set of patterns, forward
transition and fail function)
- A simple backtracking regular expressions engine
re similar to that of the Lua
programming language. At the moment it significantly underperforms
compared to the CL-PPCRE.
Some string processing algorithms are also implemented:
- Simple (naїve) suffix tree construction algorithm
- Ukkonen's suffix tree construction algorithm
Data structures:
Utilities:
- Testing whether a string has the given suffix or prefix (starts with
or ends with the pattern)
Some algorithms (Brute-force, Boyer-Moore-Horspool) have parametric
implementations (code templates) making it possible to declare
specific implementations for application-specific custom data types
and data structures.
This library is routinely tested on Steel Bank CL, Clozure CL,
Embeddable CL and Armed Bear CL. Chances are really high that it will
work on other platforms without problems (check its status on
CL-TEST-GRID).
Check the API Reference for more details.
Additional resources:
RATIONALE
Since the standard search
function is working fine, one might ask:
why do we need a yet another implementation? Answer is simple:
advanced algorithms offer different benefits compared to the standard
implementation that is based on the brute-force algorithm.
Benchmarks
show that depending on environment and pattern of application, a
Boyer-Moore-Horspool algorithm implementation can outperform standard
search function in SBCL by almost 18 times! Check the code in the
bench
folder for further details.
USAGE
CL-STRING-MATCH
is supported by Quicklisp and is known by its system name:
(ql:quickload :cl-string-match)
CL-STRING-MATCH exports functions in cl-string-match
package (that
is also nicknamed as sm
).
Shortcut functions search given pattern pat
in text txt
. They are
usually much slower (because they build index structures every time
they are called) but are easier to use:
string-contains-brute
pat txt — Brute-force
string-contains-bm
pat txt — Boyer-Moore
string-contains-bmh
pat txt — Boyer-Moore-Horspool
string-contains-kmp
pat txt — Knuth-Morris-Pratt
string-contains-ac
pat txt — Aho-Corasick
string-contains-rk
pat txt — Rabin-Karp
A more robust approach is to use pre-calculated index data that is
processed by a pair of initialize
and search
functions:
initialize-bm
pat and search-bm
bm txt
initialize-bmh
pat and search-bmh
bm txt
initialize-bmh8
pat and search-bmh8
bm txt
initialize-rk
pat and search-rk
rk txt
initialize-kmp
pat and search-kmp
kmp txt
initialize-ac
pat and search-ac
ac txt. initialize-ac
can accept a list of patterns that are compiled into a trie.
Brute-force algorithm does not use pre-calculated data and has no
"initialize" function.
Boyer-Moore-Horspool implementation (the -BMH
and -BMH8
functions)
also accepts :start2
and :end2
keywords for the "search" and
"contains" functions.
Following example looks for a given substring pat in a given line of
text txt using Boyer-Moore-Horspool algorithm implementation:
(let ((idx (initialize-bmh "abc")))
(search-bmh idx "ababcfbgsldkj"))
Counting all matches of a given pattern in a string:
(loop with str = "____abc____abc____ab"
with pat = "abc"
with idx = (sm:initialize-bmh8 pat)
with z = 0 with s = 0 while s do
(when (setf s (sm:search-bmh8 idx str :start2 s))
(incf z) (incf s (length pat)))
finally (return z))
It should be noted that Boyer-Moore-Horspool (bmh
) implementation
can offer an order of magnitude boost to performance compared to the
standard search
function.
However, some implementations create a "jump table" that can be the
size of the alphabet (over 1M CHAR-CODE-LIMIT on implementations
supporting Unicode) and thus consume a significant chunk of
memory. There are different solutions to this problem and at the
moment a version for the ASCII strings is offered: initialize-bmh8
pat and search-bmh8
bm txt as well as string-contains-bmh8
pat txt work for strings with characters inside the 256 char code
limit.
CONTRIB
This project also contains code that is not directly invloved with the
pattern search algorithms but nevertheless might be found useful for
text handling/processing. Check the contrib folder in the repository
for more details. Currently it contains:
-
ascii-strings.lisp
aims to provide single-byte strings
functionality for Unicode-enabled Common Lisp implementations. Another
goal is to reduce memory footprint and boost performance of the
string-processing tasks, i.e. read-line
.
-
simple-scanf
implements a subset of the original POSIX standard
scanf(3)
function features.
TODO
The project still lacks some important features and is under constant
development. Any kind of contributions or feedback are welcome.
Please take a look at the list of open issues or the Project Roadmap.
Visit project Wiki for additiona
2 Systems
The main system appears first, followed by any subsystem dependency.
2.1 cl-string-match
- Author
Vityok https://bitbucket.org/vityok
- Home Page
https://bitbucket.org/vityok/cl-string-match
- License
BSD
- Description
Provides implementations of the standard sub-string search (string
matching) algorithms: brute-force, Boyer-Moore, Rabin-Karp, etc.
- Version
2018.1.2
- Dependencies
- alexandria
- ascii-strings (system)
- yacc
- jpl-queues
- iterate
- mgl-pax
- Source
cl-string-match.asd (file)
- Component
src (module)
2.2 ascii-strings
- Author
Vityok https://bitbucket.org/vityok
- License
BSD
- Description
Operations on ASCII strings. Essentially this can be any kind of
single-byte encoded strings.
- Version
2015.9.16
- Dependencies
-
- Source
ascii-strings.asd (file)
- Component
contrib (module)
3 Modules
Modules are listed depth-first from the system components tree.
3.1 cl-string-match/src
- Parent
cl-string-match (system)
- Location
src/
- Components
-
3.2 ascii-strings/contrib
- Parent
ascii-strings (system)
- Location
contrib/
- Component
ascii-strings.lisp (file)
4 Files
Files are sorted by type and then listed depth-first from the systems
components trees.
4.1 Lisp
4.1.1 cl-string-match.asd
- Location
cl-string-match.asd
- Systems
cl-string-match (system)
- Packages
clstringmatch.system
4.1.2 ascii-strings.asd
- Location
ascii-strings.asd
- Systems
ascii-strings (system)
- Packages
ascii-strings.system
4.1.3 cl-string-match/src/package.lisp
- Parent
src (module)
- Location
src/package.lisp
- Packages
cl-string-match
- Internal Definitions
-
4.1.4 cl-string-match/src/utils.lisp
- Dependency
package.lisp (file)
- Parent
src (module)
- Location
src/utils.lisp
- Exported Definitions
-
4.1.5 cl-string-match/src/brute-force.lisp
- Dependency
utils.lisp (file)
- Parent
src (module)
- Location
src/brute-force.lisp
- Exported Definitions
-
4.1.6 cl-string-match/src/boyer-moore.lisp
- Dependency
brute-force.lisp (file)
- Parent
src (module)
- Location
src/boyer-moore.lisp
- Exported Definitions
-
- Internal Definitions
-
4.1.7 cl-string-match/src/boyer-moore-horspool.lisp
- Dependency
boyer-moore.lisp (file)
- Parent
src (module)
- Location
src/boyer-moore-horspool.lisp
- Exported Definitions
-
- Internal Definitions
-
4.1.8 cl-string-match/src/rabin-karp.lisp
- Dependency
boyer-moore-horspool.lisp (file)
- Parent
src (module)
- Location
src/rabin-karp.lisp
- Exported Definitions
-
- Internal Definitions
-
4.1.9 cl-string-match/src/knuth-morris-pratt.lisp
- Dependency
rabin-karp.lisp (file)
- Parent
src (module)
- Location
src/knuth-morris-pratt.lisp
- Exported Definitions
-
- Internal Definitions
-
4.1.10 cl-string-match/src/shift-or.lisp
- Dependency
knuth-morris-pratt.lisp (file)
- Parent
src (module)
- Location
src/shift-or.lisp
- Exported Definitions
-
- Internal Definitions
-
4.1.11 cl-string-match/src/aho-corasick.lisp
- Dependency
shift-or.lisp (file)
- Parent
src (module)
- Location
src/aho-corasick.lisp
- Exported Definitions
-
- Internal Definitions
-
4.1.12 cl-string-match/src/compiled-aho-corasick.lisp
- Dependency
aho-corasick.lisp (file)
- Parent
src (module)
- Location
src/compiled-aho-corasick.lisp
- Exported Definitions
-
- Internal Definitions
make-lambda-ac (function)
4.1.13 cl-string-match/src/suffix-tree.lisp
- Dependency
compiled-aho-corasick.lisp (file)
- Parent
src (module)
- Location
src/suffix-tree.lisp
- Exported Definitions
-
- Internal Definitions
-
4.1.14 cl-string-match/src/pre.lisp
- Dependency
suffix-tree.lisp (file)
- Parent
src (module)
- Location
src/pre.lisp
- Exported Definitions
-
- Internal Definitions
-
4.1.15 cl-string-match/src/doc.lisp
- Dependency
pre.lisp (file)
- Parent
src (module)
- Location
src/doc.lisp
- Exported Definitions
-
- Internal Definitions
-
4.1.16 ascii-strings/contrib/ascii-strings.lisp
- Parent
contrib (module)
- Location
contrib/ascii-strings.lisp
- Packages
ascii-strings
- Exported Definitions
-
- Internal Definitions
-
5 Packages
Packages are listed by definition order.
5.1 clstringmatch.system
- Source
cl-string-match.asd
- Use List
- asdf/interface
- common-lisp
5.2 cl-string-match
String matching functions and methods.
- Source
package.lisp (file)
- Nickname
sm
- Use List
-
- Exported Definitions
-
- Internal Definitions
-
5.3 ascii-strings.system
- Source
ascii-strings.asd
- Use List
- asdf/interface
- common-lisp
5.4 ascii-strings
This library implements functions and data types
similar to the standard Common Lisp functions and types but prefixed
with ub- to avoid naming conflicts.
This package aims at providing single-byte strings functionality
for Unicode-enabled Common Lisp implementations. Another aim is to
reduce memory footprint and boost performance of the
string-processing algorithms.
There are similar libraries/packages with slight differences. Check,
for instance, com.informatimago.common-lisp.cesarum.ascii.
This package also provides a faster alternative to the standard
read-line function. A line reader is created by the
make-ub-line-reader function, an ub-string is read by the
ub-read-line, and a standard line can be read by the
ub-read-line-string.
Please note, that while ASCII uses 7-bits per character, this library
works with octets, using 8-bits per character.
- Source
ascii-strings.lisp (file)
- Nickname
ascii
- Use List
-
- Used By List
cl-string-match
- Exported Definitions
-
- Internal Definitions
-
6 Definitions
Definitions are sorted by export status, category, package, and then by
lexicographic order.
6.1 Exported definitions
6.1.1 Constants
- Constant: +infinity+
-
- Package
cl-string-match
- Source
suffix-tree.lisp (file)
- Constant: ub-char-code-limit
-
Maximum number of UB-CHARs is limited by a single byte. That is:
just 256 characters are possible.
- Package
ascii-strings
- Source
ascii-strings.lisp (file)
6.1.2 Special variables
- Special Variable: @aho-corasick-section
-
- Package
cl-string-match
- Source
aho-corasick.lisp (file)
- Special Variable: @boyer-moore-horspool-section
-
- Package
cl-string-match
- Source
boyer-moore-horspool.lisp (file)
- Special Variable: @boyer-moore-section
-
- Package
cl-string-match
- Source
boyer-moore.lisp (file)
- Special Variable: @brute-force-section
-
- Package
cl-string-match
- Source
brute-force.lisp (file)
- Special Variable: @cl-string-match-manual
-
- Package
cl-string-match
- Source
doc.lisp (file)
- Special Variable: @knuth-morris-pratt-section
-
- Package
cl-string-match
- Source
knuth-morris-pratt.lisp (file)
- Special Variable: @multi-pattern-search
-
- Package
cl-string-match
- Source
doc.lisp (file)
- Special Variable: @pre-basic-matching-section
-
- Package
cl-string-match
- Source
pre.lisp (file)
- Special Variable: @pre-compiling-patterns-section
-
- Package
cl-string-match
- Source
pre.lisp (file)
- Special Variable: @pre-groups-section
-
- Package
cl-string-match
- Source
pre.lisp (file)
- Special Variable: @pre-pattern-replacing-section
-
- Package
cl-string-match
- Source
pre.lisp (file)
- Special Variable: @pre-pattern-scanning-section
-
- Package
cl-string-match
- Source
pre.lisp (file)
- Special Variable: @pre-pattern-splitting-section
-
- Package
cl-string-match
- Source
pre.lisp (file)
- Special Variable: @pre-regexp-section
-
- Package
cl-string-match
- Source
pre.lisp (file)
- Special Variable: @pre-with-re-match-section
-
- Package
cl-string-match
- Source
pre.lisp (file)
- Special Variable: @rabin-karp-section
-
- Package
cl-string-match
- Source
rabin-karp.lisp (file)
- Special Variable: @regexp-pattern-search
-
- Package
cl-string-match
- Source
doc.lisp (file)
- Special Variable: @shift-or-section
-
- Package
cl-string-match
- Source
shift-or.lisp (file)
- Special Variable: @single-pattern-search
-
- Package
cl-string-match
- Source
doc.lisp (file)
6.1.3 Macros
- Macro: define-bmh-matcher VARIANT-TAG &key KEY-GET KEY-CODE KEY-CMP= EMPTY-PAT ALPHABET-SIZE DATA-TYPE
-
- Package
cl-string-match
- Source
boyer-moore-horspool.lisp (file)
- Macro: define-brute-matcher VARIANT-TAG &key KEY-GET KEY-CMP/= DATA-TYPE
-
- Package
cl-string-match
- Source
brute-force.lisp (file)
- Macro: with-re (RE PATTERN) &body BODY
-
Compile pattern if it’s not a RE object and execute body.
- Package
cl-string-match
- Source
pre.lisp (file)
- Macro: with-re-match (MATCH MATCH-EXPR &key NO-MATCH) &body BODY
-
Intern match symbols to execute a body.
- Package
cl-string-match
- Source
pre.lisp (file)
6.1.4 Functions
- Function: ascii-char-code CHAR
-
This is like the standard CHAR-CODE but returns an octet.
- Package
ascii-strings
- Source
ascii-strings.lisp (file)
- Function: bmh8-p OBJECT
-
- Package
cl-string-match
- Source
boyer-moore-horspool.lisp (file)
- Function: bmh8-pat INSTANCE
-
- Function: (setf bmh8-pat) VALUE INSTANCE
-
- Package
cl-string-match
- Source
boyer-moore-horspool.lisp (file)
- Function: build-suffix-tree-simple STR
-
Build a Suffix tree for the given string STR using naive (brute-force) algorithm.
Naive algorithm takes O(m²) time to build a suffix tree where m is the
given string length.
Essentially it operates as follows:
while suffices remain:
add next shortest suffix to the tree
Algorithm first ads a suffix Str[1..m] (entire string) to the
tree. Then it proceeds adding suffices Str[i..m] (i=2..m) to the tree.
- Package
cl-string-match
- Source
suffix-tree.lisp (file)
- Function: build-suffix-tree-ukkonen STR
-
Build a Suffix tree for the given string STR using Ukkonen’s
algorithm.
Ukkonen’s algorithm takes O(m) time to build a suffix tree where m is
the given string length.
Ukkonen’s algorithm is an on-line algorithm and can operate on a
stream of characters, adding one character at a time.
- Package
cl-string-match
- Source
suffix-tree.lisp (file)
- Function: compile-re PATTERN
-
Create a regular expression from a pattern string.
- Package
cl-string-match
- Source
pre.lisp (file)
- Function: empty-trie ()
-
Creates a new instance and returns an empty trie.
- Package
cl-string-match
- Source
aho-corasick.lisp (file)
- Function: find-re PATTERN S &key START END OFFSET ALL
-
Find a regexp pattern match somewhere in a string. Run from an offset.
- Package
cl-string-match
- Source
pre.lisp (file)
- Function: initialize-ac ()
-
Returns a Trie that is used to look for the given patterns in the
text. It can deal either with a single pattern or a list of patterns.
- Package
cl-string-match
- Source
aho-corasick.lisp (file)
- Function: initialize-bm ()
-
- Package
cl-string-match
- Source
boyer-moore.lisp (file)
- Function: initialize-bmh ()
-
Preprocess the needle.
Initialize the table to default value.
- Package
cl-string-match
- Source
boyer-moore-horspool.lisp (file)
- Function: initialize-bmh8 ()
-
Preprocess the needle.
Initialize the table to default value.
- Package
cl-string-match
- Source
boyer-moore-horspool.lisp (file)
- Function: initialize-kmp ()
-
- Package
cl-string-match
- Source
knuth-morris-pratt.lisp (file)
- Function: initialize-rk ()
-
- Package
cl-string-match
- Source
rabin-karp.lisp (file)
- Function: initialize-sor ()
-
- Package
cl-string-match
- Source
shift-or.lisp (file)
- Function: initialize-tabac ()
-
Returns a tabular FDA that is used to look for the given patterns
in the text. It can deal either with a single pattern or a list of
patterns.
- Package
cl-string-match
- Source
aho-corasick.lisp (file)
- Function: make-substitution-table SUBST
-
- Package
ascii-strings
- Source
ascii-strings.lisp (file)
- Function: make-suffix-node &key (START START) (END END) (PARENT PARENT) (CHILDREN CHILDREN) (ID ID)
-
- Package
cl-string-match
- Source
suffix-tree.lisp (file)
- Function: make-suffix-tree &key (STR STR) (ROOT ROOT) (NODES-COUNT NODES-COUNT)
-
- Package
cl-string-match
- Source
suffix-tree.lisp (file)
- Function: make-ub-buffer SIZE
-
Allocate an ub-buffer of the given size.
- Package
ascii-strings
- Source
ascii-strings.lisp (file)
- Function: make-ub-line-reader &key (STREAM STREAM) (BUFFER BUFFER) (FILL FILL) (POS POS) (EOF EOF)
-
- Package
ascii-strings
- Source
ascii-strings.lisp (file)
- Function: make-ub-string SIZE
-
- Package
ascii-strings
- Source
ascii-strings.lisp (file)
- Function: make-ukk-node &key (START START) (END END) (PARENT PARENT) (CHILDREN CHILDREN) (ID ID) (SUFFIX SUFFIX)
-
- Package
cl-string-match
- Source
suffix-tree.lisp (file)
- Function: match-re PATTERN S &key START END OFFSET EXACT
-
Test a pattern re against a string.
- Package
cl-string-match
- Source
pre.lisp (file)
- Function: octets-to-ub VEC
-
Convert a simple vector into an octets vector (ub-string).
- Package
ascii-strings
- Source
ascii-strings.lisp (file)
- Function: prefixed-with TXT PREF
-
Returns T if the given string ‘TXT‘ is prefixed (starts with) the
given prefix ‘PREF‘.
- Package
cl-string-match
- Source
utils.lisp (file)
- Function: replace-re PATTERN WITH S &key START END OFFSET ALL
-
Replace patterns found within a string with a new value.
- Package
cl-string-match
- Source
pre.lisp (file)
- Function: search-ac ()
-
Looks for patterns that are indexed in the given trie and returns two values:
start position of the first matching pattern and its index.
- Package
cl-string-match
- Source
aho-corasick.lisp (file)
- Function: search-bm ()
-
Search for pattern bm in txt.
- Package
cl-string-match
- Source
boyer-moore.lisp (file)
- Function: search-bmh ()
-
Search for pattern defined in the IDX in TXT.
- Package
cl-string-match
- Source
boyer-moore-horspool.lisp (file)
- Function: search-bmh8 ()
-
Search for pattern defined in the IDX in TXT.
- Package
cl-string-match
- Source
boyer-moore-horspool.lisp (file)
- Function: search-compiled-ac SEARCH-FUNCTION TXT
-
- Package
cl-string-match
- Source
compiled-aho-corasick.lisp (file)
- Function: search-kmp ()
-
- Package
cl-string-match
- Source
knuth-morris-pratt.lisp (file)
- Function: search-rk ()
-
Implementation of the Rabin-Karp substring search algorithm.
- Package
cl-string-match
- Source
rabin-karp.lisp (file)
- Function: search-sor ()
-
- Package
cl-string-match
- Source
shift-or.lisp (file)
- Function: search-tabac ()
-
- Package
cl-string-match
- Source
aho-corasick.lisp (file)
- Function: split-re PATTERN S &key START END OFFSET ALL COALESCE-SEPS
-
Split a string into one or more strings by pattern match.
- Package
cl-string-match
- Source
pre.lisp (file)
- Function: string-contains-ac ()
-
Looks for the given pattern in the text and returns index of the
first occurence.
- Package
cl-string-match
- Source
aho-corasick.lisp (file)
- Function: string-contains-bm ()
-
- Package
cl-string-match
- Source
boyer-moore.lisp (file)
- Function: string-contains-bmh ()
-
- Package
cl-string-match
- Source
boyer-moore-horspool.lisp (file)
- Function: string-contains-bmh8 ()
-
- Package
cl-string-match
- Source
boyer-moore-horspool.lisp (file)
- Function: string-contains-brute ()
-
A Brute-force substring search implementation.
Brute-force substring search requires O(N x M) character compares to
search for a pattern of length M in a text of length N, in the worst
case.
Algorithm described in: Chapter 5, p. 760 in
’Algorithms’, Robert Sedgewick and Kevin Wayne. 4th
- Package
cl-string-match
- Source
brute-force.lisp (file)
- Function: string-contains-brute-ub ()
-
A Brute-force substring search implementation.
Brute-force substring search requires O(N x M) character compares to
search for a pattern of length M in a text of length N, in the worst
case.
Algorithm described in: Chapter 5, p. 760 in
’Algorithms’, Robert Sedgewick and Kevin Wayne. 4th
- Package
cl-string-match
- Source
brute-force.lisp (file)
- Function: string-contains-kmp ()
-
- Package
cl-string-match
- Source
knuth-morris-pratt.lisp (file)
- Function: string-contains-rk ()
-
- Package
cl-string-match
- Source
rabin-karp.lisp (file)
- Function: string-contains-sor ()
-
- Package
cl-string-match
- Source
shift-or.lisp (file)
- Function: string-contains-tabac ()
-
Looks for the given pattern in the text and returns index of the
first occurence.
- Package
cl-string-match
- Source
aho-corasick.lisp (file)
- Function: string-to-ub STR
-
Convert a standard Lisp String into an octets vector.
- Package
ascii-strings
- Source
ascii-strings.lisp (file)
- Function: suffix-node-add-child TREE NODE START END
-
Adds a child node to the given NODE. Depending on the type of the
given node creates either Ukkonens suffix tree or simple suffix tree
node.
- Package
cl-string-match
- Source
suffix-tree.lisp (file)
- Function: suffix-node-children INSTANCE
-
- Function: (setf suffix-node-children) VALUE INSTANCE
-
- Package
cl-string-match
- Source
suffix-tree.lisp (file)
- Function: suffix-node-end INSTANCE
-
- Function: (setf suffix-node-end) VALUE INSTANCE
-
- Package
cl-string-match
- Source
suffix-tree.lisp (file)
- Function: suffix-node-equals NODE-A NODE-B
-
- Package
cl-string-match
- Source
suffix-tree.lisp (file)
- Function: suffix-node-leafp NODE
-
Retruns T is the given node is a leaf (has no children), return NIL
otherwise.
- Package
cl-string-match
- Source
suffix-tree.lisp (file)
- Function: suffix-node-map-over-children NODE FUNCTION
-
Applies the given function to every child of the given node.
- Package
cl-string-match
- Source
suffix-tree.lisp (file)
- Function: suffix-node-start INSTANCE
-
- Function: (setf suffix-node-start) VALUE INSTANCE
-
- Package
cl-string-match
- Source
suffix-tree.lisp (file)
- Function: suffix-node-str TREE NODE
-
Returns the string that corresponds to the edge pointing to this
node.
- Package
cl-string-match
- Source
suffix-tree.lisp (file)
- Function: suffix-tree-build-from-sexp STR SEXP
-
Build the suffix tree from the given sexp representation. Sexp is
in form (begin end (children)).
- Package
cl-string-match
- Source
suffix-tree.lisp (file)
- Function: suffix-tree-char TREE I
-
- Package
cl-string-match
- Source
suffix-tree.lisp (file)
- Function: suffix-tree-equals TREE-A TREE-B
-
Checks all the nodes in the given trees and returns T if trees are
equal or NIL otherwise.
- Package
cl-string-match
- Source
suffix-tree.lisp (file)
- Function: suffix-tree-root INSTANCE
-
- Function: (setf suffix-tree-root) VALUE INSTANCE
-
- Package
cl-string-match
- Source
suffix-tree.lisp (file)
- Function: suffix-tree-str INSTANCE
-
- Function: (setf suffix-tree-str) VALUE INSTANCE
-
- Package
cl-string-match
- Source
suffix-tree.lisp (file)
- Function: suffix-tree-walk TREE FUNCTION
-
Applies the given FUNCTION to every node in the given TREE.
- Package
cl-string-match
- Source
suffix-tree.lisp (file)
- Function: suffixed-with TXT SUFF
-
Returns T if the given string ‘TXT‘ is suffixed (ends with) the
given suffix ‘SUFF‘.
- Package
cl-string-match
- Source
utils.lisp (file)
- Function: trie->compiled-ac TRIE
-
Returns a compiled function for the given Aho-Corasick trie.
- Package
cl-string-match
- Source
compiled-aho-corasick.lisp (file)
- Function: trie->tabular-ac TRIE
-
Given an Aho-Corasick trie and transforms it into a table-based DFA
for the Aho-Corasick automata.
- Package
cl-string-match
- Source
aho-corasick.lisp (file)
- Function: trie-add-keyword ()
-
Starting at the root, follow the path labeled by chars of Pi
If the path ends before Pi, continue it by adding new edges and nodes
for the remaining characters of Pi.
Store identifier i of Pi at the terminal node of the path.
- Package
cl-string-match
- Source
aho-corasick.lisp (file)
- Function: trie-build ()
-
Builds a Trie based on the given list of patterns.
- Package
cl-string-match
- Source
aho-corasick.lisp (file)
- Function: trie-contains ()
-
Returns T if the given TRIE contains the given string S.
- Package
cl-string-match
- Source
aho-corasick.lisp (file)
- Function: trie-contains-prefix ()
-
Checks if the given TRIE contains some prefix of the given string S.
Returns the length of the matched prefix.
- Package
cl-string-match
- Source
aho-corasick.lisp (file)
- Function: trie-pprint TRIE &key PADDING ROOT STREAM
-
Traverse the given trie and pretty-print it to the given stream.
ROOT is the root node (optional).
- Package
cl-string-match
- Source
aho-corasick.lisp (file)
- Function: trie-traverse-bfo TRIE HANDLER
-
Traverse the trie in the Breadth-First-Order and call the given
handler function on each node..
- Package
cl-string-match
- Source
aho-corasick.lisp (file)
- Function: trie-traverse-dfo TRIE HANDLER
-
Traverse the trie in the Depth-First-Order and call the given
handler function on each node.
- Package
cl-string-match
- Source
aho-corasick.lisp (file)
- Function: ub-alpha-char-p C
-
- Package
ascii-strings
- Source
ascii-strings.lisp (file)
- Function: ub-alphanumericp C
-
Returns true if character is an alphabetic character or a numeric
character; otherwise, returns false.
- Package
ascii-strings
- Source
ascii-strings.lisp (file)
- Function: ub-both-case-p ()
-
- Package
ascii-strings
- Source
ascii-strings.lisp (file)
- Function: ub-char STRING INDEX
-
- Package
ascii-strings
- Source
ascii-strings.lisp (file)
- Function: ub-char-code CHAR
-
Returns a code of the ub-char. Since ub-char is a number (an
octet), it is essentially an identity function.
- Package
ascii-strings
- Source
ascii-strings.lisp (file)
- Function: ub-char-downcase C
-
- Package
ascii-strings
- Source
ascii-strings.lisp (file)
- Function: ub-char-equal ()
-
- Package
ascii-strings
- Source
ascii-strings.lisp (file)
- Function: ub-char-greaterp ()
-
- Package
ascii-strings
- Source
ascii-strings.lisp (file)
- Function: ub-char-int CHAR
-
- Package
ascii-strings
- Source
ascii-strings.lisp (file)
- Function: ub-char-lessp ()
-
- Package
ascii-strings
- Source
ascii-strings.lisp (file)
- Function: ub-char-name ()
-
- Package
ascii-strings
- Source
ascii-strings.lisp (file)
- Function: ub-char-not-equal ()
-
- Package
ascii-strings
- Source
ascii-strings.lisp (file)
- Function: ub-char-not-greaterp ()
-
- Package
ascii-strings
- Source
ascii-strings.lisp (file)
- Function: ub-char-not-lessp ()
-
- Package
ascii-strings
- Source
ascii-strings.lisp (file)
- Function: ub-char-upcase C
-
- Package
ascii-strings
- Source
ascii-strings.lisp (file)
- Function: ub-char/= C1 C2
-
- Package
ascii-strings
- Source
ascii-strings.lisp (file)
- Function: ub-char< C1 C2
-
- Package
ascii-strings
- Source
ascii-strings.lisp (file)
- Function: ub-char<= C1 C2
-
- Package
ascii-strings
- Source
ascii-strings.lisp (file)
- Function: ub-char= C1 C2
-
- Package
ascii-strings
- Source
ascii-strings.lisp (file)
- Function: ub-char> C1 C2
-
- Package
ascii-strings
- Source
ascii-strings.lisp (file)
- Function: ub-char>= C1 C2
-
- Package
ascii-strings
- Source
ascii-strings.lisp (file)
- Function: ub-code-char ()
-
- Package
ascii-strings
- Source
ascii-strings.lisp (file)
- Function: ub-digit-char ()
-
- Package
ascii-strings
- Source
ascii-strings.lisp (file)
- Function: ub-digit-char-p C &optional R
-
Tests whether char is a digit in the specified radix (i.e., with a
weight less than radix). If it is a digit in that radix, its weight is
returned as an integer; otherwise nil is returned.
- Package
ascii-strings
- Source
ascii-strings.lisp (file)
- Function: ub-graphic-char-p ()
-
- Package
ascii-strings
- Source
ascii-strings.lisp (file)
- Function: ub-line-reader-close READER
-
Mimics a standard close function: closes the underlying stream and
resets the reader to its initial state.
- Package
ascii-strings
- Source
ascii-strings.lisp (file)
- Function: ub-line-reader-file-position READER &optional POSITION
-
Returns the current position within the stream according to the
amount of information really read.
When the buffer caches more information than was really read by one of
UB-READ-LINE function the standard FILE-POSITION function will return
position of the buffer that is larger than the position that was read
by the user.
Returned number can be used by the standard FILE-POSITION function to
adjust the position within a stream.
When optional argument POSITION is supplied, the file position is
adjusted accordingly in the underlying stream. The buffer is flushed.
- Package
ascii-strings
- Source
ascii-strings.lisp (file)
- Function: ub-lower-case-p C
-
- Package
ascii-strings
- Source
ascii-strings.lisp (file)
- Function: ub-name-char ()
-
- Package
ascii-strings
- Source
ascii-strings.lisp (file)
- Function: ub-nstring-capitalize ()
-
- Package
ascii-strings
- Source
ascii-strings.lisp (file)
- Function: ub-nstring-downcase ()
-
- Package
ascii-strings
- Source
ascii-strings.lisp (file)
- Function: ub-nstring-upcase ()
-
- Package
ascii-strings
- Source
ascii-strings.lisp (file)
- Function: ub-read-line READER
-
Reads data into a pre-allocated buffer in the reader structure and
returns an array displaced to the contents of the next line in that
buffer.
- Package
ascii-strings
- Source
ascii-strings.lisp (file)
- Function: ub-read-line-raw READER
-
Reads data into the pre-allocated buffer in the READER structure
and returns two values: start and end positions of the line within the
buffer that can be used to extract this line contents from the
buffer.
Please note, that unlike the standard read-line or the
liberal-read-line by jasonmelbye this function works with the
Unix-type of lines - sequence of characters delimited by the Newline
symbol.
- Package
ascii-strings
- Source
ascii-strings.lisp (file)
- Function: ub-read-line-string READER
-
Reads data into a pre-allocated buffer in the reader structure and
returns a standard Lisp string.
- Package
ascii-strings
- Source
ascii-strings.lisp (file)
- Function: ub-standard-char-p ()
-
- Package
ascii-strings
- Source
ascii-strings.lisp (file)
- Function: ub-string-capitalize ()
-
- Package
ascii-strings
- Source
ascii-strings.lisp (file)
- Function: ub-string-downcase ()
-
- Package
ascii-strings
- Source
ascii-strings.lisp (file)
- Function: ub-string-equal ()
-
- Package
ascii-strings
- Source
ascii-strings.lisp (file)
- Function: ub-string-greaterp ()
-
- Package
ascii-strings
- Source
ascii-strings.lisp (file)
- Function: ub-string-left-trim ()
-
- Package
ascii-strings
- Source
ascii-strings.lisp (file)
- Function: ub-string-lessp ()
-
- Package
ascii-strings
- Source
ascii-strings.lisp (file)
- Function: ub-string-not-equal ()
-
- Package
ascii-strings
- Source
ascii-strings.lisp (file)
- Function: ub-string-not-greaterp ()
-
- Package
ascii-strings
- Source
ascii-strings.lisp (file)
- Function: ub-string-not-lessp ()
-
- Package
ascii-strings
- Source
ascii-strings.lisp (file)
- Function: ub-string-right-trim ()
-
- Package
ascii-strings
- Source
ascii-strings.lisp (file)
- Function: ub-string-trim ()
-
- Package
ascii-strings
- Source
ascii-strings.lisp (file)
- Function: ub-string-upcase ()
-
- Package
ascii-strings
- Source
ascii-strings.lisp (file)
- Function: ub-string/= STRING1 STRING2 &key START1 END1 START2 END2
-
Returns true if the supplied substrings are different; otherwise it
is false.
- Package
ascii-strings
- Source
ascii-strings.lisp (file)
- Function: ub-string< STRING1 STRING2 &key START1 END1 START2 END2
-
Returns true if substring1 is less than substring2; otherwise it is
false.
- Package
ascii-strings
- Source
ascii-strings.lisp (file)
- Function: ub-string<= STRING1 STRING2 &key START1 END1 START2 END2
-
Returns true if substring1 is less than or equal to substring2;
otherwise it is false.
- Package
ascii-strings
- Source
ascii-strings.lisp (file)
- Function: ub-string= STRING1 STRING2 &key START1 END1 START2 END2
-
Returns true if the supplied substrings are of the same length and
contain the same characters in corresponding positions; otherwise it
returns false.
- Package
ascii-strings
- Source
ascii-strings.lisp (file)
- Function: ub-string> STRING1 STRING2 &key START1 END1 START2 END2
-
Returns true if substring1 is greater than substring2; otherwise it
is false.
- Package
ascii-strings
- Source
ascii-strings.lisp (file)
- Function: ub-string>= STRING1 STRING2 &key START1 END1 START2 END2
-
Returns true if substring1 is greater than or equal to substring2;
otherwise it is false.
- Package
ascii-strings
- Source
ascii-strings.lisp (file)
- Function: ub-subseq SEQUENCE START &optional END
-
Returns either the SEQUENCE itself, or a dispaced array to the
SEQUENCE. This is meant as a memory-efficient replacement for the
ordinary SUBSEQ that allocates a new sequence.
- Package
ascii-strings
- Source
ascii-strings.lisp (file)
- Function: ub-to-string USTR &key START END SUBST
-
Converts either an UB-STRING or UB-BUFFER into a standard Common
Lisp string.
START, END the start and end offsets within the given USTR to
translate into a standard string.
- Package
ascii-strings
- Source
ascii-strings.lisp (file)
- Function: ub-upper-case-p C
-
- Package
ascii-strings
- Source
ascii-strings.lisp (file)
- Function: ukk-node-suffix INSTANCE
-
- Function: (setf ukk-node-suffix) VALUE INSTANCE
-
- Package
cl-string-match
- Source
suffix-tree.lisp (file)
6.1.5 Generic functions
- Generic Function: match-groups OBJECT
-
- Package
cl-string-match
- Methods
- Method: match-groups (RE-MATCH re-match)
-
automatically generated reader method
- Source
pre.lisp (file)
- Generic Function: match-pos-end OBJECT
-
- Package
cl-string-match
- Methods
- Method: match-pos-end (RE-MATCH re-match)
-
automatically generated reader method
- Source
pre.lisp (file)
- Generic Function: match-pos-start OBJECT
-
- Package
cl-string-match
- Methods
- Method: match-pos-start (RE-MATCH re-match)
-
automatically generated reader method
- Source
pre.lisp (file)
- Generic Function: match-string OBJECT
-
- Package
cl-string-match
- Methods
- Method: match-string (RE-MATCH re-match)
-
automatically generated reader method
- Source
pre.lisp (file)
6.1.6 Structures
- Structure: bmh8 ()
-
- Package
cl-string-match
- Source
boyer-moore-horspool.lisp (file)
- Direct superclasses
structure-object (structure)
- Direct slots
- Slot: bad-char-skip
-
- Type
(simple-array fixnum (*))
- Initform
#()
- Readers
bmh8-bad-char-skip (function)
- Writers
(setf bmh8-bad-char-skip) (function)
- Slot: pat
-
- Type
simple-string
- Initform
""
- Readers
bmh8-pat (function)
- Writers
(setf bmh8-pat) (function)
- Slot: pat-len
-
- Type
fixnum
- Initform
0
- Readers
bmh8-pat-len (function)
- Writers
(setf bmh8-pat-len) (function)
- Structure: suffix-node ()
-
Documentation
- Package
cl-string-match
- Source
suffix-tree.lisp (file)
- Direct superclasses
structure-object (structure)
- Direct subclasses
ukk-node (structure)
- Direct methods
print-object (method)
- Direct slots
- Slot: start
-
- Type
fixnum
- Initform
0
- Readers
suffix-node-start (function)
- Writers
(setf suffix-node-start) (function)
- Slot: end
-
- Type
fixnum
- Initform
0
- Readers
suffix-node-end (function)
- Writers
(setf suffix-node-end) (function)
- Slot: parent
-
- Readers
suffix-node-parent (function)
- Writers
(setf suffix-node-parent) (function)
- Slot: children
-
- Readers
suffix-node-children (function)
- Writers
(setf suffix-node-children) (function)
- Slot: id
-
- Type
fixnum
- Initform
0
- Readers
suffix-node-id (function)
- Writers
(setf suffix-node-id) (function)
- Structure: suffix-tree ()
-
ROOT is a SUFFIX-NODE with default values. It is intended to keep
references to its children. ROOT is just a simple placeholder for the
actual nodes as its children.
- Package
cl-string-match
- Source
suffix-tree.lisp (file)
- Direct superclasses
structure-object (structure)
- Direct methods
print-object (method)
- Direct slots
- Slot: str
-
- Type
simple-string
- Initform
""
- Readers
suffix-tree-str (function)
- Writers
(setf suffix-tree-str) (function)
- Slot: root
-
- Readers
suffix-tree-root (function)
- Writers
(setf suffix-tree-root) (function)
- Slot: nodes-count
-
- Type
fixnum
- Initform
0
- Readers
suffix-tree-nodes-count (function)
- Writers
(setf suffix-tree-nodes-count) (function)
- Structure: trie-node ()
-
Each node of a trie contains a list of child nodes, a label (the
letter) and a mark (some value attributed to the matching string).
Trie root node is like all other nodes but its ‘ID‘ is used as an
increment to create ids for new nodes.
Slots:
* ‘id‘ - unique node identifier, root node has the largest id.
* ‘children‘ - a hash table with labels as keys, ‘trie-node‘ as
values.
* ‘mark‘ - output function, when not null marks the last character of a
keyword and is returned as the search result.
* ‘fail‘ - fail transition to another node.
* ‘depth‘ - number of nodes from the root node to this node.
- Package
cl-string-match
- Source
aho-corasick.lisp (file)
- Direct superclasses
structure-object (structure)
- Direct methods
print-object (method)
- Direct slots
- Slot: id
-
- Type
fixnum
- Initform
0
- Readers
trie-node-id (function)
- Writers
(setf trie-node-id) (function)
- Slot: children
-
- Readers
trie-node-children (function)
- Writers
(setf trie-node-children) (function)
- Slot: label
-
- Readers
trie-node-label (function)
- Writers
(setf trie-node-label) (function)
- Slot: mark
-
- Readers
trie-node-mark (function)
- Writers
(setf trie-node-mark) (function)
- Slot: fail
-
- Type
(or null cl-string-match:trie-node)
- Readers
trie-node-fail (function)
- Writers
(setf trie-node-fail) (function)
- Slot: depth
-
- Type
fixnum
- Initform
0
- Readers
trie-node-depth (function)
- Writers
(setf trie-node-depth) (function)
- Structure: ukk-node ()
-
Ukkonen’s algorithm relies on the suffix link technique. Some other
algorithms might also rely on it but the naive suffix tree algorithm
does not require it.
This structure extends the standard suffix tree node structure with
the suffix link slot.
- Package
cl-string-match
- Source
suffix-tree.lisp (file)
- Direct superclasses
suffix-node (structure)
- Direct slots
- Slot: suffix
-
- Readers
ukk-node-suffix (function)
- Writers
(setf ukk-node-suffix) (function)
6.1.7 Classes
- Class: re ()
-
Regular expression.
- Package
cl-string-match
- Source
pre.lisp (file)
- Direct superclasses
standard-object (class)
- Direct methods
-
- Direct slots
- Slot: pattern
-
- Initargs
:pattern
- Readers
re-pattern (generic function)
- Slot: expr
-
- Initargs
:expression
- Readers
re-expression (generic function)
- Class: re-match ()
-
Matched pattern.
- Package
cl-string-match
- Source
pre.lisp (file)
- Direct superclasses
standard-object (class)
- Direct methods
-
- Direct slots
- Slot: match
-
- Initargs
:match
- Readers
match-string (generic function)
- Slot: groups
-
- Initargs
:groups
- Readers
match-groups (generic function)
- Slot: start-pos
-
- Initargs
:start-pos
- Readers
match-pos-start (generic function)
- Slot: end-pos
-
- Initargs
:end-pos
- Readers
match-pos-end (generic function)
6.1.8 Types
- Type: ub-buffer ()
-
Buffer of octets is a simple array to allow compiler
optimizations.
- Package
ascii-strings
- Source
ascii-strings.lisp (file)
- Type: ub-char ()
-
An octet. A number equal to the char code.
- Package
ascii-strings
- Source
ascii-strings.lisp (file)
- Type: ub-string ()
-
Strings must be vectors to allow for fill pointers and
displacement. However, SBCL does a better job on optimizations when it
deals with simple arrays.
- Package
ascii-strings
- Source
ascii-strings.lisp (file)
6.2 Internal definitions
6.2.1 Constants
- Constant: +ac-alphabet+
-
- Package
cl-string-match
- Source
aho-corasick.lisp (file)
- Constant: +alph-size+
-
- Package
cl-string-match
- Source
rabin-karp.lisp (file)
- Constant: +big-prime+
-
- Package
cl-string-match
- Source
rabin-karp.lisp (file)
- Constant: +newline+
-
- Package
ascii-strings
- Source
ascii-strings.lisp (file)
- Constant: +sor-alphabet+
-
Size of the alphabet for the Shift-OR algorithm implementation.
- Package
cl-string-match
- Source
shift-or.lisp (file)
- Constant: +ub-line-reader-buffer-size+
-
Defines the size of the buffer used by the line
reader in bytes.
- Package
ascii-strings
- Source
ascii-strings.lisp (file)
6.2.2 Special variables
- Special Variable: *default-substitution-table*
-
Substitution table used to convert ub-strings to the standard
strings by default. Since character with code 0 is not very welcome in
the world of C, we are converting it to an ordinary character.
- Package
ascii-strings
- Source
ascii-strings.lisp (file)
- Special Variable: *expression-parser*
-
- Package
cl-string-match
- Source
pre.lisp (file)
- Special Variable: *set-parser*
-
- Package
cl-string-match
- Source
pre.lisp (file)
- Special Variable: *standard-debug-settings*
-
The standard debug settings to be used in functions under development.
- Package
cl-string-match
- Source
package.lisp (file)
- Special Variable: *standard-optimize-settings*
-
The standard optimize settings used by most declaration
expressions. Tuned for best performance by default, but when the
SM-DEBUG-ENABLED keyword is present in the *FEATURES* list, makes
debug and safety its priority at the expense of everything else.
- Package
cl-string-match
- Source
package.lisp (file)
6.2.3 Macros
- Macro: map-trie-children (PARENT CHILD) &body BODY
-
Perform the given BODY on the children of the given PARENT. The
child node is bound to the CHILD variable.
Example:
(map-trie-children (node child)
(push child stack))
- Package
cl-string-match
- Source
aho-corasick.lisp (file)
- Macro: ub-string<>=*-body LESSP EQUALP
-
Makes a body of the string comparison functions. Borrowed from the
string.lisp file of the SBCL sources.
- Package
ascii-strings
- Source
ascii-strings.lisp (file)
6.2.4 Functions
- Function: %ub-string-compare STRING1 START1 END1 STRING2 START2 END2
-
- Package
ascii-strings
- Source
ascii-strings.lisp (file)
- Function: add-suffix-simple TREE START END
-
Adds a suffix of a string STR designated by its START and END to
the suffix tree TREE.
- Package
cl-string-match
- Source
suffix-tree.lisp (file)
- Function: bm-bad-char INSTANCE
-
- Function: (setf bm-bad-char) VALUE INSTANCE
-
- Package
cl-string-match
- Source
boyer-moore.lisp (file)
- Function: bm-good-suffix INSTANCE
-
- Function: (setf bm-good-suffix) VALUE INSTANCE
-
- Package
cl-string-match
- Source
boyer-moore.lisp (file)
- Function: bm-p OBJECT
-
- Package
cl-string-match
- Source
boyer-moore.lisp (file)
- Function: bm-pat INSTANCE
-
- Function: (setf bm-pat) VALUE INSTANCE
-
- Package
cl-string-match
- Source
boyer-moore.lisp (file)
- Function: bm-suffixes PAT SUFFIXES
-
- Package
cl-string-match
- Source
boyer-moore.lisp (file)
- Function: bmh-bad-char-skip INSTANCE
-
- Function: (setf bmh-bad-char-skip) VALUE INSTANCE
-
- Package
cl-string-match
- Source
boyer-moore-horspool.lisp (file)
- Function: bmh-p OBJECT
-
- Package
cl-string-match
- Source
boyer-moore-horspool.lisp (file)
- Function: bmh-pat INSTANCE
-
- Function: (setf bmh-pat) VALUE INSTANCE
-
- Package
cl-string-match
- Source
boyer-moore-horspool.lisp (file)
- Function: bmh-pat-len INSTANCE
-
- Function: (setf bmh-pat-len) VALUE INSTANCE
-
- Package
cl-string-match
- Source
boyer-moore-horspool.lisp (file)
- Function: bmh8-bad-char-skip INSTANCE
-
- Function: (setf bmh8-bad-char-skip) VALUE INSTANCE
-
- Package
cl-string-match
- Source
boyer-moore-horspool.lisp (file)
- Function: bmh8-pat-len INSTANCE
-
- Function: (setf bmh8-pat-len) VALUE INSTANCE
-
- Package
cl-string-match
- Source
boyer-moore-horspool.lisp (file)
- Function: branch TREE NODE L R C
-
Function branch is used to test if a position is the end point
and turn the implicit node to explicit node if necessary. Because
sentinel node is not used, the special case is handled in the first
if-clause.
- Package
cl-string-match
- Source
suffix-tree.lisp (file)
- Function: build-suffix-tree-mccreight STR
-
Build a Suffix tree for the given string STR using McCreight’s
algorithm.
McCreight’s algorithm takes O(n) time to build a suffix tree where n
is the given string length.
TODO
- Package
cl-string-match
- Source
suffix-tree.lisp (file)
- Function: canonize TREE NODE L R
-
- Package
cl-string-match
- Source
suffix-tree.lisp (file)
- Function: check-rk-lv ()
-
Las Vegas version: does pat[] match txt[i..i-M+1] ?
- Package
cl-string-match
- Source
rabin-karp.lisp (file)
- Function: check-rk-mk I
-
Monte Carlo version: always return true
- Package
cl-string-match
- Source
rabin-karp.lisp (file)
- Function: compile-set S
-
Create a single satisfy predicate for a character set.
- Package
cl-string-match
- Source
pre.lisp (file)
- Function: compute-failure-function ()
-
Given a trie calculate failure transitions for its nodes.
Modifies nodes.
Traverses the trie in the breadth-first-order (BFO)
- Package
cl-string-match
- Source
aho-corasick.lisp (file)
- Function: copy-bm INSTANCE
-
- Package
cl-string-match
- Source
boyer-moore.lisp (file)
- Function: copy-bmh INSTANCE
-
- Package
cl-string-match
- Source
boyer-moore-horspool.lisp (file)
- Function: copy-bmh8 INSTANCE
-
- Package
cl-string-match
- Source
boyer-moore-horspool.lisp (file)
- Function: copy-kmp INSTANCE
-
- Package
cl-string-match
- Source
knuth-morris-pratt.lisp (file)
- Function: copy-re-thread INSTANCE
-
- Package
cl-string-match
- Source
pre.lisp (file)
- Function: copy-rk INSTANCE
-
- Package
cl-string-match
- Source
rabin-karp.lisp (file)
- Function: copy-sor INSTANCE
-
- Package
cl-string-match
- Source
shift-or.lisp (file)
- Function: copy-suffix-node INSTANCE
-
- Package
cl-string-match
- Source
suffix-tree.lisp (file)
- Function: copy-suffix-tree INSTANCE
-
- Package
cl-string-match
- Source
suffix-tree.lisp (file)
- Function: copy-tabac INSTANCE
-
- Package
cl-string-match
- Source
aho-corasick.lisp (file)
- Function: copy-trie-node INSTANCE
-
- Package
cl-string-match
- Source
aho-corasick.lisp (file)
- Function: copy-ub-line-reader INSTANCE
-
- Package
ascii-strings
- Source
ascii-strings.lisp (file)
- Function: copy-ukk-node INSTANCE
-
- Package
cl-string-match
- Source
suffix-tree.lisp (file)
- Function: escape C
-
Return the test and predicate for an escaped character.
- Package
cl-string-match
- Source
pre.lisp (file)
- Function: format-name FORMAT &rest ARGS
-
- Package
cl-string-match
- Source
package.lisp (file)
- Function: hash-bm ORDER
-
- Package
cl-string-match
- Source
boyer-moore.lisp (file)
- Function: hex-char-p C
-
T if c is a hexadecimal character.
- Package
cl-string-match
- Source
pre.lisp (file)
- Function: horner-hash ()
-
Horner hashing function implementation.
Computes the hash function for an END-digit base- +ALPH-SIZE+ number
represented as a char array in time proportional to END. (We pass END
as an argument so that we can use the function for both the pattern
and the text.)
- Package
cl-string-match
- Source
rabin-karp.lisp (file)
- Function: initialize-bad-char IDX
-
Initialize the bad character skip for the Boyer-Moore algorithm.
- Package
cl-string-match
- Source
boyer-moore.lisp (file)
- Function: initialize-good-suffix IDX
-
Initialize the good suffix skip function table for the
Boyer-Moore algorithm.
- Package
cl-string-match
- Source
boyer-moore.lisp (file)
- Function: kmp-p OBJECT
-
- Package
cl-string-match
- Source
knuth-morris-pratt.lisp (file)
- Function: kmp-pat INSTANCE
-
- Function: (setf kmp-pat) VALUE INSTANCE
-
- Package
cl-string-match
- Source
knuth-morris-pratt.lisp (file)
- Function: kmp-pat-len INSTANCE
-
- Function: (setf kmp-pat-len) VALUE INSTANCE
-
- Package
cl-string-match
- Source
knuth-morris-pratt.lisp (file)
- Function: kmp-table INSTANCE
-
- Function: (setf kmp-table) VALUE INSTANCE
-
- Package
cl-string-match
- Source
knuth-morris-pratt.lisp (file)
- Function: make-bm &key (BAD-CHAR BAD-CHAR) (GOOD-SUFFIX GOOD-SUFFIX) (PAT PAT)
-
- Package
cl-string-match
- Source
boyer-moore.lisp (file)
- Function: make-bmh &key (BAD-CHAR-SKIP BAD-CHAR-SKIP) (PAT PAT) (PAT-LEN PAT-LEN)
-
- Package
cl-string-match
- Source
boyer-moore-horspool.lisp (file)
- Function: make-bmh8 &key (BAD-CHAR-SKIP BAD-CHAR-SKIP) (PAT PAT) (PAT-LEN PAT-LEN)
-
- Package
cl-string-match
- Source
boyer-moore-horspool.lisp (file)
- Function: make-kmp &key (PAT PAT) (PAT-LEN PAT-LEN) (TABLE TABLE)
-
- Package
cl-string-match
- Source
knuth-morris-pratt.lisp (file)
- Function: make-lambda-ac TRIE
-
Writes lambda function performing search over the given trie.
That function can later be compiled into native code and
funcall-ed. The generated function accepts a single string and returns
matching mark from the given trie.
Generated function is essentially a giant tagbody with jumps
dispatched in case forms depending on the current character.
- Package
cl-string-match
- Source
compiled-aho-corasick.lisp (file)
- Function: make-re-thread PC SP GROUPS STACK
-
- Package
cl-string-match
- Source
pre.lisp (file)
- Function: make-rk &key (PAT PAT) (PAT-HASH PAT-HASH) (PAT-LEN PAT-LEN) (ALPH-SIZE ALPH-SIZE) (RM RM)
-
- Package
cl-string-match
- Source
rabin-karp.lisp (file)
- Function: make-sor &key (CIDX CIDX) (LIM LIM) (PAT-LEN PAT-LEN)
-
- Package
cl-string-match
- Source
shift-or.lisp (file)
- Function: make-tabac &key (START START) (TRANS TRANS) (FINAL FINAL) (MATCH-LEN MATCH-LEN)
-
- Package
cl-string-match
- Source
aho-corasick.lisp (file)
- Function: make-trie-node &key (ID ID) (CHILDREN CHILDREN) (LABEL LABEL) (MARK MARK) (FAIL FAIL) (DEPTH DEPTH)
-
- Package
cl-string-match
- Source
aho-corasick.lisp (file)
- Function: newline-p C
-
T if c is a newline character.
- Package
cl-string-match
- Source
pre.lisp (file)
-
- Package
cl-string-match
- Source
doc.lisp (file)
- Function: print-suffix-tree-for-gv TREE &key STREAM LABEL
-
Print the given suffix TREE for the Graphviz visualization in the
dot format.
- Package
cl-string-match
- Source
suffix-tree.lisp (file)
- Function: print-suffix-tree-for-gv-pretty TREE &key STREAM LABEL
-
Alternative representation of the suffix tree. Based on java
implementation from: http://pastie.org/5925812
- Package
cl-string-match
- Source
suffix-tree.lisp (file)
- Function: print-suffix-tree-in-file TREE FNAME &optional LABEL
-
- Package
cl-string-match
- Source
suffix-tree.lisp (file)
- Function: punctuation-p C
-
T if c is a punctuation character.
- Package
cl-string-match
- Source
pre.lisp (file)
- Function: re-thread-groups INSTANCE
-
- Function: (setf re-thread-groups) VALUE INSTANCE
-
- Package
cl-string-match
- Source
pre.lisp (file)
- Function: re-thread-p OBJECT
-
- Package
cl-string-match
- Source
pre.lisp (file)
- Function: re-thread-pc INSTANCE
-
- Function: (setf re-thread-pc) VALUE INSTANCE
-
- Package
cl-string-match
- Source
pre.lisp (file)
- Function: re-thread-sp INSTANCE
-
- Function: (setf re-thread-sp) VALUE INSTANCE
-
- Package
cl-string-match
- Source
pre.lisp (file)
- Function: re-thread-stack INSTANCE
-
- Function: (setf re-thread-stack) VALUE INSTANCE
-
- Package
cl-string-match
- Source
pre.lisp (file)
- Function: ref-length L R
-
- Package
cl-string-match
- Source
suffix-tree.lisp (file)
- Function: rk-alph-size INSTANCE
-
- Function: (setf rk-alph-size) VALUE INSTANCE
-
- Package
cl-string-match
- Source
rabin-karp.lisp (file)
- Function: rk-p OBJECT
-
- Package
cl-string-match
- Source
rabin-karp.lisp (file)
- Function: rk-pat INSTANCE
-
- Function: (setf rk-pat) VALUE INSTANCE
-
- Package
cl-string-match
- Source
rabin-karp.lisp (file)
- Function: rk-pat-hash INSTANCE
-
- Function: (setf rk-pat-hash) VALUE INSTANCE
-
- Package
cl-string-match
- Source
rabin-karp.lisp (file)
- Function: rk-pat-len INSTANCE
-
- Function: (setf rk-pat-len) VALUE INSTANCE
-
- Package
cl-string-match
- Source
rabin-karp.lisp (file)
- Function: rk-rm INSTANCE
-
- Function: (setf rk-rm) VALUE INSTANCE
-
- Package
cl-string-match
- Source
rabin-karp.lisp (file)
- Function: run ()
-
Execute a regular expression program.
- Package
cl-string-match
- Source
pre.lisp (file)
- Function: sor-cidx INSTANCE
-
- Function: (setf sor-cidx) VALUE INSTANCE
-
- Package
cl-string-match
- Source
shift-or.lisp (file)
- Function: sor-lim INSTANCE
-
- Function: (setf sor-lim) VALUE INSTANCE
-
- Package
cl-string-match
- Source
shift-or.lisp (file)
- Function: sor-p OBJECT
-
- Package
cl-string-match
- Source
shift-or.lisp (file)
- Function: sor-pat-len INSTANCE
-
- Function: (setf sor-pat-len) VALUE INSTANCE
-
- Package
cl-string-match
- Source
shift-or.lisp (file)
- Function: sor-printer OBJ STREAM DEPTH
-
Make dump of the SOR structure more human-readable: in the CIDX
print characters and their positions, decipher LIM.
- Package
cl-string-match
- Source
shift-or.lisp (file)
- Function: space-p C
-
T if c is a whitespace character.
- Package
cl-string-match
- Source
pre.lisp (file)
- Function: split-node TREE OLD-NODE START END POS
-
Split the given NODE at position POS within the node.
- Package
cl-string-match
- Source
suffix-tree.lisp (file)
- Function: stbstr STR L R
-
The +infinity+ is defined as the largest number (standard constant
MOST-POSITIVE-FIXNUM), if the right index exceed to the length of the
list, the result is from left to the end of the list.
- Package
cl-string-match
- Source
suffix-tree.lisp (file)
- Function: str-length NODE
-
Length of the substring in the arc.
- Package
cl-string-match
- Source
suffix-tree.lisp (file)
- Function: suffix-node-get-child TREE NODE C
-
Given the NODE lookup a child node that starts with the given char
C in the given suffix tree TREE.
- Package
cl-string-match
- Source
suffix-tree.lisp (file)
- Function: suffix-node-id INSTANCE
-
- Function: (setf suffix-node-id) VALUE INSTANCE
-
- Package
cl-string-match
- Source
suffix-tree.lisp (file)
- Function: suffix-node-insert-child TREE NODE CHILD-NODE
-
Adds a child node to the given NODE.
- Package
cl-string-match
- Source
suffix-tree.lisp (file)
- Function: suffix-node-p OBJECT
-
- Package
cl-string-match
- Source
suffix-tree.lisp (file)
- Function: suffix-node-parent INSTANCE
-
- Function: (setf suffix-node-parent) VALUE INSTANCE
-
- Package
cl-string-match
- Source
suffix-tree.lisp (file)
- Function: suffix-node-printer OBJ STREAM DEPTH
-
- Package
cl-string-match
- Source
suffix-tree.lisp (file)
- Function: suffix-tree-nodes-count INSTANCE
-
- Function: (setf suffix-tree-nodes-count) VALUE INSTANCE
-
- Package
cl-string-match
- Source
suffix-tree.lisp (file)
- Function: suffix-tree-p OBJECT
-
- Package
cl-string-match
- Source
suffix-tree.lisp (file)
- Function: suffix-tree-printer OBJ STREAM DEPTH
-
- Package
cl-string-match
- Source
suffix-tree.lisp (file)
- Function: tab-p C
-
T if c is a tab character.
- Package
cl-string-match
- Source
pre.lisp (file)
- Function: tabac-final INSTANCE
-
- Function: (setf tabac-final) VALUE INSTANCE
-
- Package
cl-string-match
- Source
aho-corasick.lisp (file)
- Function: tabac-match-len INSTANCE
-
- Function: (setf tabac-match-len) VALUE INSTANCE
-
- Package
cl-string-match
- Source
aho-corasick.lisp (file)
- Function: tabac-p OBJECT
-
- Package
cl-string-match
- Source
aho-corasick.lisp (file)
- Function: tabac-start INSTANCE
-
- Function: (setf tabac-start) VALUE INSTANCE
-
- Package
cl-string-match
- Source
aho-corasick.lisp (file)
- Function: tabac-trans INSTANCE
-
- Function: (setf tabac-trans) VALUE INSTANCE
-
- Package
cl-string-match
- Source
aho-corasick.lisp (file)
- Function: tabac-transition IDX STATE C
-
Returns a new state based on the given char from the current state.
- Package
cl-string-match
- Source
aho-corasick.lisp (file)
- Function: trie-add-child ()
-
Add a child node to the given node with the given label and mark.
Constructor can be either ‘MAKE-TRIE-NODE‘ or any other structure
constructor derieved from the ‘TRIE-NODE‘ struct.
- Package
cl-string-match
- Source
aho-corasick.lisp (file)
- Function: trie-dump-dot TRIE &key STREAM
-
Dumps a textual representation of the Trie useful for making a
graphical plot with Graphviz to the given stream.
- Package
cl-string-match
- Source
aho-corasick.lisp (file)
- Function: trie-dump-dot-file TRIE FNAME
-
Dumps output of the TRIE-DUMP-DOT function to the file with the
specified file name.
- Package
cl-string-match
- Source
aho-corasick.lisp (file)
- Function: trie-find-child ()
-
Looks for a child of the given node trie with the given label.
- Package
cl-string-match
- Source
aho-corasick.lisp (file)
- Function: trie-node-children INSTANCE
-
- Function: (setf trie-node-children) VALUE INSTANCE
-
- Package
cl-string-match
- Source
aho-corasick.lisp (file)
- Function: trie-node-depth INSTANCE
-
- Function: (setf trie-node-depth) VALUE INSTANCE
-
- Package
cl-string-match
- Source
aho-corasick.lisp (file)
- Function: trie-node-fail INSTANCE
-
- Function: (setf trie-node-fail) VALUE INSTANCE
-
- Package
cl-string-match
- Source
aho-corasick.lisp (file)
- Function: trie-node-id INSTANCE
-
- Function: (setf trie-node-id) VALUE INSTANCE
-
- Package
cl-string-match
- Source
aho-corasick.lisp (file)
- Function: trie-node-label INSTANCE
-
- Function: (setf trie-node-label) VALUE INSTANCE
-
- Package
cl-string-match
- Source
aho-corasick.lisp (file)
- Function: trie-node-mark INSTANCE
-
- Function: (setf trie-node-mark) VALUE INSTANCE
-
- Package
cl-string-match
- Source
aho-corasick.lisp (file)
- Function: trie-node-p OBJECT
-
- Package
cl-string-match
- Source
aho-corasick.lisp (file)
- Function: trie-node-printer OBJ STREAM DEPTH
-
We have to avoid standard Lisp printer because of the FAIL links
that turn our tree into a network with cycles, throwing the default
printer into an infinite loop.
- Package
cl-string-match
- Source
aho-corasick.lisp (file)
- Function: ub-line-reader-buffer INSTANCE
-
- Function: (setf ub-line-reader-buffer) VALUE INSTANCE
-
- Package
ascii-strings
- Source
ascii-strings.lisp (file)
- Function: ub-line-reader-eof INSTANCE
-
- Function: (setf ub-line-reader-eof) VALUE INSTANCE
-
- Package
ascii-strings
- Source
ascii-strings.lisp (file)
- Function: ub-line-reader-fill INSTANCE
-
- Function: (setf ub-line-reader-fill) VALUE INSTANCE
-
- Package
ascii-strings
- Source
ascii-strings.lisp (file)
- Function: ub-line-reader-p OBJECT
-
- Package
ascii-strings
- Source
ascii-strings.lisp (file)
- Function: ub-line-reader-pos INSTANCE
-
- Function: (setf ub-line-reader-pos) VALUE INSTANCE
-
- Package
ascii-strings
- Source
ascii-strings.lisp (file)
- Function: ub-line-reader-stream INSTANCE
-
- Function: (setf ub-line-reader-stream) VALUE INSTANCE
-
- Package
ascii-strings
- Source
ascii-strings.lisp (file)
- Function: ub-schar STRING INDEX
-
- Package
ascii-strings
- Source
ascii-strings.lisp (file)
- Function: ukk-node-children INSTANCE
-
- Function: (setf ukk-node-children) VALUE INSTANCE
-
- Package
cl-string-match
- Source
suffix-tree.lisp (file)
- Function: ukk-node-end INSTANCE
-
- Function: (setf ukk-node-end) VALUE INSTANCE
-
- Package
cl-string-match
- Source
suffix-tree.lisp (file)
- Function: ukk-node-id INSTANCE
-
- Function: (setf ukk-node-id) VALUE INSTANCE
-
- Package
cl-string-match
- Source
suffix-tree.lisp (file)
- Function: ukk-node-p OBJECT
-
- Package
cl-string-match
- Source
suffix-tree.lisp (file)
- Function: ukk-node-parent INSTANCE
-
- Function: (setf ukk-node-parent) VALUE INSTANCE
-
- Package
cl-string-match
- Source
suffix-tree.lisp (file)
- Function: ukk-node-start INSTANCE
-
- Function: (setf ukk-node-start) VALUE INSTANCE
-
- Package
cl-string-match
- Source
suffix-tree.lisp (file)
- Function: ukkonen-update TREE NODE L I
-
- Package
cl-string-match
- Source
suffix-tree.lisp (file)
- Function: update-md ()
-
- Package
cl-string-match
- Source
doc.lisp (file)
- Function: word-char-p C
-
T if is alphanumeric or an underscore.
- Package
cl-string-match
- Source
pre.lisp (file)
6.2.5 Generic functions
- Generic Function: re-expression OBJECT
-
- Package
cl-string-match
- Methods
- Method: re-expression (RE re)
-
automatically generated reader method
- Source
pre.lisp (file)
- Generic Function: re-pattern OBJECT
-
- Package
cl-string-match
- Methods
- Method: re-pattern (RE re)
-
automatically generated reader method
- Source
pre.lisp (file)
6.2.6 Structures
- Structure: bm ()
-
- Package
cl-string-match
- Source
boyer-moore.lisp (file)
- Direct superclasses
structure-object (structure)
- Direct slots
- Slot: bad-char
-
- Type
(simple-array fixnum)
- Initform
(make-array 0 :element-type (quote fixnum))
- Readers
bm-bad-char (function)
- Writers
(setf bm-bad-char) (function)
- Slot: good-suffix
-
- Type
(simple-array fixnum)
- Initform
(make-array 0 :element-type (quote fixnum))
- Readers
bm-good-suffix (function)
- Writers
(setf bm-good-suffix) (function)
- Slot: pat
-
- Type
simple-string
- Initform
""
- Readers
bm-pat (function)
- Writers
(setf bm-pat) (function)
- Structure: bmh ()
-
- Package
cl-string-match
- Source
boyer-moore-horspool.lisp (file)
- Direct superclasses
structure-object (structure)
- Direct slots
- Slot: bad-char-skip
-
- Type
(simple-array fixnum (*))
- Initform
#()
- Readers
bmh-bad-char-skip (function)
- Writers
(setf bmh-bad-char-skip) (function)
- Slot: pat
-
- Type
simple-string
- Initform
""
- Readers
bmh-pat (function)
- Writers
(setf bmh-pat) (function)
- Slot: pat-len
-
- Type
fixnum
- Initform
0
- Readers
bmh-pat-len (function)
- Writers
(setf bmh-pat-len) (function)
- Structure: kmp ()
-
- Package
cl-string-match
- Source
knuth-morris-pratt.lisp (file)
- Direct superclasses
structure-object (structure)
- Direct slots
- Slot: pat
-
- Type
simple-string
- Initform
""
- Readers
kmp-pat (function)
- Writers
(setf kmp-pat) (function)
- Slot: pat-len
-
- Type
fixnum
- Initform
0
- Readers
kmp-pat-len (function)
- Writers
(setf kmp-pat-len) (function)
- Slot: table
-
- Type
(simple-array fixnum)
- Initform
(make-array 0 :element-type (quote fixnum))
- Readers
kmp-table (function)
- Writers
(setf kmp-table) (function)
- Structure: re-thread ()
-
- Package
cl-string-match
- Source
pre.lisp (file)
- Direct superclasses
structure-object (structure)
- Direct slots
- Slot: pc
-
- Readers
re-thread-pc (function)
- Writers
(setf re-thread-pc) (function)
- Slot: sp
-
- Readers
re-thread-sp (function)
- Writers
(setf re-thread-sp) (function)
- Slot: groups
-
- Readers
re-thread-groups (function)
- Writers
(setf re-thread-groups) (function)
- Slot: stack
-
- Readers
re-thread-stack (function)
- Writers
(setf re-thread-stack) (function)
- Structure: rk ()
-
- Package
cl-string-match
- Source
rabin-karp.lisp (file)
- Direct superclasses
structure-object (structure)
- Direct slots
- Slot: pat
-
- Type
simple-string
- Initform
""
- Readers
rk-pat (function)
- Writers
(setf rk-pat) (function)
- Slot: pat-hash
-
- Type
cl-string-match::rk-ub32
- Initform
0
- Readers
rk-pat-hash (function)
- Writers
(setf rk-pat-hash) (function)
- Slot: pat-len
-
- Type
cl-string-match::rk-ub32
- Initform
0
- Readers
rk-pat-len (function)
- Writers
(setf rk-pat-len) (function)
- Slot: alph-size
-
- Type
cl-string-match::rk-ub32
- Initform
cl-string-match::+alph-size+
- Readers
rk-alph-size (function)
- Writers
(setf rk-alph-size) (function)
- Slot: rm
-
- Type
cl-string-match::rk-ub32
- Initform
1
- Readers
rk-rm (function)
- Writers
(setf rk-rm) (function)
- Structure: sor ()
-
Index for the Shift-OR search operation.
- Package
cl-string-match
- Source
shift-or.lisp (file)
- Direct superclasses
structure-object (structure)
- Direct methods
print-object (method)
- Direct slots
- Slot: cidx
-
- Readers
sor-cidx (function)
- Writers
(setf sor-cidx) (function)
- Slot: lim
-
- Type
cl-string-match::sor-ub32
- Initform
0
- Readers
sor-lim (function)
- Writers
(setf sor-lim) (function)
- Slot: pat-len
-
- Type
fixnum
- Initform
0
- Readers
sor-pat-len (function)
- Writers
(setf sor-pat-len) (function)
- Structure: tabac ()
-
Defines an Aho-Corasick DFA based on tables.
Slots:
* ‘start‘ - initial state
* ‘trans‘ - a table of transition tables
* ‘final‘ - marks final states
* ‘match-len‘ - stores length of the keyword corresponding to the final state
- Package
cl-string-match
- Source
aho-corasick.lisp (file)
- Direct superclasses
structure-object (structure)
- Direct slots
- Slot: start
-
- Type
fixnum
- Initform
-1
- Readers
tabac-start (function)
- Writers
(setf tabac-start) (function)
- Slot: trans
-
- Type
(or null (simple-array (or null (simple-array fixnum))))
- Readers
tabac-trans (function)
- Writers
(setf tabac-trans) (function)
- Slot: final
-
- Type
(simple-array fixnum)
- Initform
(make-array 0 :element-type (quote fixnum))
- Readers
tabac-final (function)
- Writers
(setf tabac-final) (function)
- Slot: match-len
-
- Type
(simple-array fixnum)
- Initform
(make-array 0 :element-type (quote fixnum))
- Readers
tabac-match-len (function)
- Writers
(setf tabac-match-len) (function)
- Structure: ub-line-reader ()
-
Encapsulates a buffer and the state of the line reader. Created by
the make-ub-line-reader function, and the every next line is obtained
by one of the ub-read-line-* functions.
You should not forget to close the underlying stream using either a
standard close function or the ub-line-reader-close function.
It is anticipated that the underlying stream is an input stream with
element-type set to ub-char.
- Package
ascii-strings
- Source
ascii-strings.lisp (file)
- Direct superclasses
structure-object (structure)
- Direct slots
- Slot: stream
-
- Type
(or null stream)
- Readers
ub-line-reader-stream (function)
- Writers
(setf ub-line-reader-stream) (function)
- Slot: buffer
-
- Type
ascii-strings:ub-buffer
- Initform
(make-array ascii-strings::+ub-line-reader-buffer-size+ :element-type (quote ascii-strings:ub-char))
- Readers
ub-line-reader-buffer (function)
- Writers
(setf ub-line-reader-buffer) (function)
- Slot: fill
-
- Type
fixnum
- Initform
0
- Readers
ub-line-reader-fill (function)
- Writers
(setf ub-line-reader-fill) (function)
- Slot: pos
-
- Type
fixnum
- Initform
0
- Readers
ub-line-reader-pos (function)
- Writers
(setf ub-line-reader-pos) (function)
- Slot: eof
-
- Type
boolean
- Readers
ub-line-reader-eof (function)
- Writers
(setf ub-line-reader-eof) (function)
6.2.7 Types
- Type: rk-ub32 ()
-
- Package
cl-string-match
- Source
rabin-karp.lisp (file)
- Type: sor-ub32 ()
-
- Package
cl-string-match
- Source
shift-or.lisp (file)
Appendix A Indexes
A.1 Concepts
| Index Entry | | Section |
|
A | | |
| ascii-strings.asd: | | The ascii-strings․asd file |
| ascii-strings/contrib: | | The ascii-strings/contrib module |
| ascii-strings/contrib/ascii-strings.lisp: | | The ascii-strings/contrib/ascii-strings․lisp file |
|
C | | |
| cl-string-match.asd: | | The cl-string-match․asd file |
| cl-string-match/src: | | The cl-string-match/src module |
| cl-string-match/src/aho-corasick.lisp: | | The cl-string-match/src/aho-corasick․lisp file |
| cl-string-match/src/boyer-moore-horspool.lisp: | | The cl-string-match/src/boyer-moore-horspool․lisp file |
| cl-string-match/src/boyer-moore.lisp: | | The cl-string-match/src/boyer-moore․lisp file |
| cl-string-match/src/brute-force.lisp: | | The cl-string-match/src/brute-force․lisp file |
| cl-string-match/src/compiled-aho-corasick.lisp: | | The cl-string-match/src/compiled-aho-corasick․lisp file |
| cl-string-match/src/doc.lisp: | | The cl-string-match/src/doc․lisp file |
| cl-string-match/src/knuth-morris-pratt.lisp: | | The cl-string-match/src/knuth-morris-pratt․lisp file |
| cl-string-match/src/package.lisp: | | The cl-string-match/src/package․lisp file |
| cl-string-match/src/pre.lisp: | | The cl-string-match/src/pre․lisp file |
| cl-string-match/src/rabin-karp.lisp: | | The cl-string-match/src/rabin-karp․lisp file |
| cl-string-match/src/shift-or.lisp: | | The cl-string-match/src/shift-or․lisp file |
| cl-string-match/src/suffix-tree.lisp: | | The cl-string-match/src/suffix-tree․lisp file |
| cl-string-match/src/utils.lisp: | | The cl-string-match/src/utils․lisp file |
|
F | | |
| File, Lisp, ascii-strings.asd: | | The ascii-strings․asd file |
| File, Lisp, ascii-strings/contrib/ascii-strings.lisp: | | The ascii-strings/contrib/ascii-strings․lisp file |
| File, Lisp, cl-string-match.asd: | | The cl-string-match․asd file |
| File, Lisp, cl-string-match/src/aho-corasick.lisp: | | The cl-string-match/src/aho-corasick․lisp file |
| File, Lisp, cl-string-match/src/boyer-moore-horspool.lisp: | | The cl-string-match/src/boyer-moore-horspool․lisp file |
| File, Lisp, cl-string-match/src/boyer-moore.lisp: | | The cl-string-match/src/boyer-moore․lisp file |
| File, Lisp, cl-string-match/src/brute-force.lisp: | | The cl-string-match/src/brute-force․lisp file |
| File, Lisp, cl-string-match/src/compiled-aho-corasick.lisp: | | The cl-string-match/src/compiled-aho-corasick․lisp file |
| File, Lisp, cl-string-match/src/doc.lisp: | | The cl-string-match/src/doc․lisp file |
| File, Lisp, cl-string-match/src/knuth-morris-pratt.lisp: | | The cl-string-match/src/knuth-morris-pratt․lisp file |
| File, Lisp, cl-string-match/src/package.lisp: | | The cl-string-match/src/package․lisp file |
| File, Lisp, cl-string-match/src/pre.lisp: | | The cl-string-match/src/pre․lisp file |
| File, Lisp, cl-string-match/src/rabin-karp.lisp: | | The cl-string-match/src/rabin-karp․lisp file |
| File, Lisp, cl-string-match/src/shift-or.lisp: | | The cl-string-match/src/shift-or․lisp file |
| File, Lisp, cl-string-match/src/suffix-tree.lisp: | | The cl-string-match/src/suffix-tree․lisp file |
| File, Lisp, cl-string-match/src/utils.lisp: | | The cl-string-match/src/utils․lisp file |
|
L | | |
| Lisp File, ascii-strings.asd: | | The ascii-strings․asd file |
| Lisp File, ascii-strings/contrib/ascii-strings.lisp: | | The ascii-strings/contrib/ascii-strings․lisp file |
| Lisp File, cl-string-match.asd: | | The cl-string-match․asd file |
| Lisp File, cl-string-match/src/aho-corasick.lisp: | | The cl-string-match/src/aho-corasick․lisp file |
| Lisp File, cl-string-match/src/boyer-moore-horspool.lisp: | | The cl-string-match/src/boyer-moore-horspool․lisp file |
| Lisp File, cl-string-match/src/boyer-moore.lisp: | | The cl-string-match/src/boyer-moore․lisp file |
| Lisp File, cl-string-match/src/brute-force.lisp: | | The cl-string-match/src/brute-force․lisp file |
| Lisp File, cl-string-match/src/compiled-aho-corasick.lisp: | | The cl-string-match/src/compiled-aho-corasick․lisp file |
| Lisp File, cl-string-match/src/doc.lisp: | | The cl-string-match/src/doc․lisp file |
| Lisp File, cl-string-match/src/knuth-morris-pratt.lisp: | | The cl-string-match/src/knuth-morris-pratt․lisp file |
| Lisp File, cl-string-match/src/package.lisp: | | The cl-string-match/src/package․lisp file |
| Lisp File, cl-string-match/src/pre.lisp: | | The cl-string-match/src/pre․lisp file |
| Lisp File, cl-string-match/src/rabin-karp.lisp: | | The cl-string-match/src/rabin-karp․lisp file |
| Lisp File, cl-string-match/src/shift-or.lisp: | | The cl-string-match/src/shift-or․lisp file |
| Lisp File, cl-string-match/src/suffix-tree.lisp: | | The cl-string-match/src/suffix-tree․lisp file |
| Lisp File, cl-string-match/src/utils.lisp: | | The cl-string-match/src/utils․lisp file |
|
M | | |
| Module, ascii-strings/contrib: | | The ascii-strings/contrib module |
| Module, cl-string-match/src: | | The cl-string-match/src module |
|
A.2 Functions
| Index Entry | | Section |
|
% | | |
| %ub-string-compare : | | Internal functions |
|
( | | |
| (setf bm-bad-char) : | | Internal functions |
| (setf bm-good-suffix) : | | Internal functions |
| (setf bm-pat) : | | Internal functions |
| (setf bmh-bad-char-skip) : | | Internal functions |
| (setf bmh-pat) : | | Internal functions |
| (setf bmh-pat-len) : | | Internal functions |
| (setf bmh8-bad-char-skip) : | | Internal functions |
| (setf bmh8-pat) : | | Exported functions |
| (setf bmh8-pat-len) : | | Internal functions |
| (setf kmp-pat) : | | Internal functions |
| (setf kmp-pat-len) : | | Internal functions |
| (setf kmp-table) : | | Internal functions |
| (setf re-thread-groups) : | | Internal functions |
| (setf re-thread-pc) : | | Internal functions |
| (setf re-thread-sp) : | | Internal functions |
| (setf re-thread-stack) : | | Internal functions |
| (setf rk-alph-size) : | | Internal functions |
| (setf rk-pat) : | | Internal functions |
| (setf rk-pat-hash) : | | Internal functions |
| (setf rk-pat-len) : | | Internal functions |
| (setf rk-rm) : | | Internal functions |
| (setf sor-cidx) : | | Internal functions |
| (setf sor-lim) : | | Internal functions |
| (setf sor-pat-len) : | | Internal functions |
| (setf suffix-node-children) : | | Exported functions |
| (setf suffix-node-end) : | | Exported functions |
| (setf suffix-node-id) : | | Internal functions |
| (setf suffix-node-parent) : | | Internal functions |
| (setf suffix-node-start) : | | Exported functions |
| (setf suffix-tree-nodes-count) : | | Internal functions |
| (setf suffix-tree-root) : | | Exported functions |
| (setf suffix-tree-str) : | | Exported functions |
| (setf tabac-final) : | | Internal functions |
| (setf tabac-match-len) : | | Internal functions |
| (setf tabac-start) : | | Internal functions |
| (setf tabac-trans) : | | Internal functions |
| (setf trie-node-children) : | | Internal functions |
| (setf trie-node-depth) : | | Internal functions |
| (setf trie-node-fail) : | | Internal functions |
| (setf trie-node-id) : | | Internal functions |
| (setf trie-node-label) : | | Internal functions |
| (setf trie-node-mark) : | | Internal functions |
| (setf ub-line-reader-buffer) : | | Internal functions |
| (setf ub-line-reader-eof) : | | Internal functions |
| (setf ub-line-reader-fill) : | | Internal functions |
| (setf ub-line-reader-pos) : | | Internal functions |
| (setf ub-line-reader-stream) : | | Internal functions |
| (setf ukk-node-children) : | | Internal functions |
| (setf ukk-node-end) : | | Internal functions |
| (setf ukk-node-id) : | | Internal functions |
| (setf ukk-node-parent) : | | Internal functions |
| (setf ukk-node-start) : | | Internal functions |
| (setf ukk-node-suffix) : | | Exported functions |
|
A | | |
| add-suffix-simple : | | Internal functions |
| ascii-char-code : | | Exported functions |
|
B | | |
| bm-bad-char : | | Internal functions |
| bm-good-suffix : | | Internal functions |
| bm-p : | | Internal functions |
| bm-pat : | | Internal functions |
| bm-suffixes : | | Internal functions |
| bmh-bad-char-skip : | | Internal functions |
| bmh-p : | | Internal functions |
| bmh-pat : | | Internal functions |
| bmh-pat-len : | | Internal functions |
| bmh8-bad-char-skip : | | Internal functions |
| bmh8-p : | | Exported functions |
| bmh8-pat : | | Exported functions |
| bmh8-pat-len : | | Internal functions |
| branch : | | Internal functions |
| build-suffix-tree-mccreight : | | Internal functions |
| build-suffix-tree-simple : | | Exported functions |
| build-suffix-tree-ukkonen : | | Exported functions |
|
C | | |
| canonize : | | Internal functions |
| check-rk-lv : | | Internal functions |
| check-rk-mk : | | Internal functions |
| compile-re : | | Exported functions |
| compile-set : | | Internal functions |
| compute-failure-function : | | Internal functions |
| copy-bm : | | Internal functions |
| copy-bmh : | | Internal functions |
| copy-bmh8 : | | Internal functions |
| copy-kmp : | | Internal functions |
| copy-re-thread : | | Internal functions |
| copy-rk : | | Internal functions |
| copy-sor : | | Internal functions |
| copy-suffix-node : | | Internal functions |
| copy-suffix-tree : | | Internal functions |
| copy-tabac : | | Internal functions |
| copy-trie-node : | | Internal functions |
| copy-ub-line-reader : | | Internal functions |
| copy-ukk-node : | | Internal functions |
|
D | | |
| define-bmh-matcher : | | Exported macros |
| define-brute-matcher : | | Exported macros |
|
E | | |
| empty-trie : | | Exported functions |
| escape : | | Internal functions |
|
F | | |
| find-re : | | Exported functions |
| format-name : | | Internal functions |
| Function, %ub-string-compare : | | Internal functions |
| Function, (setf bm-bad-char) : | | Internal functions |
| Function, (setf bm-good-suffix) : | | Internal functions |
| Function, (setf bm-pat) : | | Internal functions |
| Function, (setf bmh-bad-char-skip) : | | Internal functions |
| Function, (setf bmh-pat) : | | Internal functions |
| Function, (setf bmh-pat-len) : | | Internal functions |
| Function, (setf bmh8-bad-char-skip) : | | Internal functions |
| Function, (setf bmh8-pat) : | | Exported functions |
| Function, (setf bmh8-pat-len) : | | Internal functions |
| Function, (setf kmp-pat) : | | Internal functions |
| Function, (setf kmp-pat-len) : | | Internal functions |
| Function, (setf kmp-table) : | | Internal functions |
| Function, (setf re-thread-groups) : | | Internal functions |
| Function, (setf re-thread-pc) : | | Internal functions |
| Function, (setf re-thread-sp) : | | Internal functions |
| Function, (setf re-thread-stack) : | | Internal functions |
| Function, (setf rk-alph-size) : | | Internal functions |
| Function, (setf rk-pat) : | | Internal functions |
| Function, (setf rk-pat-hash) : | | Internal functions |
| Function, (setf rk-pat-len) : | | Internal functions |
| Function, (setf rk-rm) : | | Internal functions |
| Function, (setf sor-cidx) : | | Internal functions |
| Function, (setf sor-lim) : | | Internal functions |
| Function, (setf sor-pat-len) : | | Internal functions |
| Function, (setf suffix-node-children) : | | Exported functions |
| Function, (setf suffix-node-end) : | | Exported functions |
| Function, (setf suffix-node-id) : | | Internal functions |
| Function, (setf suffix-node-parent) : | | Internal functions |
| Function, (setf suffix-node-start) : | | Exported functions |
| Function, (setf suffix-tree-nodes-count) : | | Internal functions |
| Function, (setf suffix-tree-root) : | | Exported functions |
| Function, (setf suffix-tree-str) : | | Exported functions |
| Function, (setf tabac-final) : | | Internal functions |
| Function, (setf tabac-match-len) : | | Internal functions |
| Function, (setf tabac-start) : | | Internal functions |
| Function, (setf tabac-trans) : | | Internal functions |
| Function, (setf trie-node-children) : | | Internal functions |
| Function, (setf trie-node-depth) : | | Internal functions |
| Function, (setf trie-node-fail) : | | Internal functions |
| Function, (setf trie-node-id) : | | Internal functions |
| Function, (setf trie-node-label) : | | Internal functions |
| Function, (setf trie-node-mark) : | | Internal functions |
| Function, (setf ub-line-reader-buffer) : | | Internal functions |
| Function, (setf ub-line-reader-eof) : | | Internal functions |
| Function, (setf ub-line-reader-fill) : | | Internal functions |
| Function, (setf ub-line-reader-pos) : | | Internal functions |
| Function, (setf ub-line-reader-stream) : | | Internal functions |
| Function, (setf ukk-node-children) : | | Internal functions |
| Function, (setf ukk-node-end) : | | Internal functions |
| Function, (setf ukk-node-id) : | | Internal functions |
| Function, (setf ukk-node-parent) : | | Internal functions |
| Function, (setf ukk-node-start) : | | Internal functions |
| Function, (setf ukk-node-suffix) : | | Exported functions |
| Function, add-suffix-simple : | | Internal functions |
| Function, ascii-char-code : | | Exported functions |
| Function, bm-bad-char : | | Internal functions |
| Function, bm-good-suffix : | | Internal functions |
| Function, bm-p : | | Internal functions |
| Function, bm-pat : | | Internal functions |
| Function, bm-suffixes : | | Internal functions |
| Function, bmh-bad-char-skip : | | Internal functions |
| Function, bmh-p : | | Internal functions |
| Function, bmh-pat : | | Internal functions |
| Function, bmh-pat-len : | | Internal functions |
| Function, bmh8-bad-char-skip : | | Internal functions |
| Function, bmh8-p : | | Exported functions |
| Function, bmh8-pat : | | Exported functions |
| Function, bmh8-pat-len : | | Internal functions |
| Function, branch : | | Internal functions |
| Function, build-suffix-tree-mccreight : | | Internal functions |
| Function, build-suffix-tree-simple : | | Exported functions |
| Function, build-suffix-tree-ukkonen : | | Exported functions |
| Function, canonize : | | Internal functions |
| Function, check-rk-lv : | | Internal functions |
| Function, check-rk-mk : | | Internal functions |
| Function, compile-re : | | Exported functions |
| Function, compile-set : | | Internal functions |
| Function, compute-failure-function : | | Internal functions |
| Function, copy-bm : | | Internal functions |
| Function, copy-bmh : | | Internal functions |
| Function, copy-bmh8 : | | Internal functions |
| Function, copy-kmp : | | Internal functions |
| Function, copy-re-thread : | | Internal functions |
| Function, copy-rk : | | Internal functions |
| Function, copy-sor : | | Internal functions |
| Function, copy-suffix-node : | | Internal functions |
| Function, copy-suffix-tree : | | Internal functions |
| Function, copy-tabac : | | Internal functions |
| Function, copy-trie-node : | | Internal functions |
| Function, copy-ub-line-reader : | | Internal functions |
| Function, copy-ukk-node : | | Internal functions |
| Function, empty-trie : | | Exported functions |
| Function, escape : | | Internal functions |
| Function, find-re : | | Exported functions |
| Function, format-name : | | Internal functions |
| Function, hash-bm : | | Internal functions |
| Function, hex-char-p : | | Internal functions |
| Function, horner-hash : | | Internal functions |
| Function, initialize-ac : | | Exported functions |
| Function, initialize-bad-char : | | Internal functions |
| Function, initialize-bm : | | Exported functions |
| Function, initialize-bmh : | | Exported functions |
| Function, initialize-bmh8 : | | Exported functions |
| Function, initialize-good-suffix : | | Internal functions |
| Function, initialize-kmp : | | Exported functions |
| Function, initialize-rk : | | Exported functions |
| Function, initialize-sor : | | Exported functions |
| Function, initialize-tabac : | | Exported functions |
| Function, kmp-p : | | Internal functions |
| Function, kmp-pat : | | Internal functions |
| Function, kmp-pat-len : | | Internal functions |
| Function, kmp-table : | | Internal functions |
| Function, make-bm : | | Internal functions |
| Function, make-bmh : | | Internal functions |
| Function, make-bmh8 : | | Internal functions |
| Function, make-kmp : | | Internal functions |
| Function, make-lambda-ac : | | Internal functions |
| Function, make-re-thread : | | Internal functions |
| Function, make-rk : | | Internal functions |
| Function, make-sor : | | Internal functions |
| Function, make-substitution-table : | | Exported functions |
| Function, make-suffix-node : | | Exported functions |
| Function, make-suffix-tree : | | Exported functions |
| Function, make-tabac : | | Internal functions |
| Function, make-trie-node : | | Internal functions |
| Function, make-ub-buffer : | | Exported functions |
| Function, make-ub-line-reader : | | Exported functions |
| Function, make-ub-string : | | Exported functions |
| Function, make-ukk-node : | | Exported functions |
| Function, match-re : | | Exported functions |
| Function, newline-p : | | Internal functions |
| Function, octets-to-ub : | | Exported functions |
| Function, prefixed-with : | | Exported functions |
| Function, print-markdown-footer : | | Internal functions |
| Function, print-suffix-tree-for-gv : | | Internal functions |
| Function, print-suffix-tree-for-gv-pretty : | | Internal functions |
| Function, print-suffix-tree-in-file : | | Internal functions |
| Function, punctuation-p : | | Internal functions |
| Function, re-thread-groups : | | Internal functions |
| Function, re-thread-p : | | Internal functions |
| Function, re-thread-pc : | | Internal functions |
| Function, re-thread-sp : | | Internal functions |
| Function, re-thread-stack : | | Internal functions |
| Function, ref-length : | | Internal functions |
| Function, replace-re : | | Exported functions |
| Function, rk-alph-size : | | Internal functions |
| Function, rk-p : | | Internal functions |
| Function, rk-pat : | | Internal functions |
| Function, rk-pat-hash : | | Internal functions |
| Function, rk-pat-len : | | Internal functions |
| Function, rk-rm : | | Internal functions |
| Function, run : | | Internal functions |
| Function, search-ac : | | Exported functions |
| Function, search-bm : | | Exported functions |
| Function, search-bmh : | | Exported functions |
| Function, search-bmh8 : | | Exported functions |
| Function, search-compiled-ac : | | Exported functions |
| Function, search-kmp : | | Exported functions |
| Function, search-rk : | | Exported functions |
| Function, search-sor : | | Exported functions |
| Function, search-tabac : | | Exported functions |
| Function, sor-cidx : | | Internal functions |
| Function, sor-lim : | | Internal functions |
| Function, sor-p : | | Internal functions |
| Function, sor-pat-len : | | Internal functions |
| Function, sor-printer : | | Internal functions |
| Function, space-p : | | Internal functions |
| Function, split-node : | | Internal functions |
| Function, split-re : | | Exported functions |
| Function, stbstr : | | Internal functions |
| Function, str-length : | | Internal functions |
| Function, string-contains-ac : | | Exported functions |
| Function, string-contains-bm : | | Exported functions |
| Function, string-contains-bmh : | | Exported functions |
| Function, string-contains-bmh8 : | | Exported functions |
| Function, string-contains-brute : | | Exported functions |
| Function, string-contains-brute-ub : | | Exported functions |
| Function, string-contains-kmp : | | Exported functions |
| Function, string-contains-rk : | | Exported functions |
| Function, string-contains-sor : | | Exported functions |
| Function, string-contains-tabac : | | Exported functions |
| Function, string-to-ub : | | Exported functions |
| Function, suffix-node-add-child : | | Exported functions |
| Function, suffix-node-children : | | Exported functions |
| Function, suffix-node-end : | | Exported functions |
| Function, suffix-node-equals : | | Exported functions |
| Function, suffix-node-get-child : | | Internal functions |
| Function, suffix-node-id : | | Internal functions |
| Function, suffix-node-insert-child : | | Internal functions |
| Function, suffix-node-leafp : | | Exported functions |
| Function, suffix-node-map-over-children : | | Exported functions |
| Function, suffix-node-p : | | Internal functions |
| Function, suffix-node-parent : | | Internal functions |
| Function, suffix-node-printer : | | Internal functions |
| Function, suffix-node-start : | | Exported functions |
| Function, suffix-node-str : | | Exported functions |
| Function, suffix-tree-build-from-sexp : | | Exported functions |
| Function, suffix-tree-char : | | Exported functions |
| Function, suffix-tree-equals : | | Exported functions |
| Function, suffix-tree-nodes-count : | | Internal functions |
| Function, suffix-tree-p : | | Internal functions |
| Function, suffix-tree-printer : | | Internal functions |
| Function, suffix-tree-root : | | Exported functions |
| Function, suffix-tree-str : | | Exported functions |
| Function, suffix-tree-walk : | | Exported functions |
| Function, suffixed-with : | | Exported functions |
| Function, tab-p : | | Internal functions |
| Function, tabac-final : | | Internal functions |
| Function, tabac-match-len : | | Internal functions |
| Function, tabac-p : | | Internal functions |
| Function, tabac-start : | | Internal functions |
| Function, tabac-trans : | | Internal functions |
| Function, tabac-transition : | | Internal functions |
| Function, trie->compiled-ac : | | Exported functions |
| Function, trie->tabular-ac : | | Exported functions |
| Function, trie-add-child : | | Internal functions |
| Function, trie-add-keyword : | | Exported functions |
| Function, trie-build : | | Exported functions |
| Function, trie-contains : | | Exported functions |
| Function, trie-contains-prefix : | | Exported functions |
| Function, trie-dump-dot : | | Internal functions |
| Function, trie-dump-dot-file : | | Internal functions |
| Function, trie-find-child : | | Internal functions |
| Function, trie-node-children : | | Internal functions |
| Function, trie-node-depth : | | Internal functions |
| Function, trie-node-fail : | | Internal functions |
| Function, trie-node-id : | | Internal functions |
| Function, trie-node-label : | | Internal functions |
| Function, trie-node-mark : | | Internal functions |
| Function, trie-node-p : | | Internal functions |
| Function, trie-node-printer : | | Internal functions |
| Function, trie-pprint : | | Exported functions |
| Function, trie-traverse-bfo : | | Exported functions |
| Function, trie-traverse-dfo : | | Exported functions |
| Function, ub-alpha-char-p : | | Exported functions |
| Function, ub-alphanumericp : | | Exported functions |
| Function, ub-both-case-p : | | Exported functions |
| Function, ub-char : | | Exported functions |
| Function, ub-char-code : | | Exported functions |
| Function, ub-char-downcase : | | Exported functions |
| Function, ub-char-equal : | | Exported functions |
| Function, ub-char-greaterp : | | Exported functions |
| Function, ub-char-int : | | Exported functions |
| Function, ub-char-lessp : | | Exported functions |
| Function, ub-char-name : | | Exported functions |
| Function, ub-char-not-equal : | | Exported functions |
| Function, ub-char-not-greaterp : | | Exported functions |
| Function, ub-char-not-lessp : | | Exported functions |
| Function, ub-char-upcase : | | Exported functions |
| Function, ub-char/= : | | Exported functions |
| Function, ub-char< : | | Exported functions |
| Function, ub-char<= : | | Exported functions |
| Function, ub-char= : | | Exported functions |
| Function, ub-char> : | | Exported functions |
| Function, ub-char>= : | | Exported functions |
| Function, ub-code-char : | | Exported functions |
| Function, ub-digit-char : | | Exported functions |
| Function, ub-digit-char-p : | | Exported functions |
| Function, ub-graphic-char-p : | | Exported functions |
| Function, ub-line-reader-buffer : | | Internal functions |
| Function, ub-line-reader-close : | | Exported functions |
| Function, ub-line-reader-eof : | | Internal functions |
| Function, ub-line-reader-file-position : | | Exported functions |
| Function, ub-line-reader-fill : | | Internal functions |
| Function, ub-line-reader-p : | | Internal functions |
| Function, ub-line-reader-pos : | | Internal functions |
| Function, ub-line-reader-stream : | | Internal functions |
| Function, ub-lower-case-p : | | Exported functions |
| Function, ub-name-char : | | Exported functions |
| Function, ub-nstring-capitalize : | | Exported functions |
| Function, ub-nstring-downcase : | | Exported functions |
| Function, ub-nstring-upcase : | | Exported functions |
| Function, ub-read-line : | | Exported functions |
| Function, ub-read-line-raw : | | Exported functions |
| Function, ub-read-line-string : | | Exported functions |
| Function, ub-schar : | | Internal functions |
| Function, ub-standard-char-p : | | Exported functions |
| Function, ub-string-capitalize : | | Exported functions |
| Function, ub-string-downcase : | | Exported functions |
| Function, ub-string-equal : | | Exported functions |
| Function, ub-string-greaterp : | | Exported functions |
| Function, ub-string-left-trim : | | Exported functions |
| Function, ub-string-lessp : | | Exported functions |
| Function, ub-string-not-equal : | | Exported functions |
| Function, ub-string-not-greaterp : | | Exported functions |
| Function, ub-string-not-lessp : | | Exported functions |
| Function, ub-string-right-trim : | | Exported functions |
| Function, ub-string-trim : | | Exported functions |
| Function, ub-string-upcase : | | Exported functions |
| Function, ub-string/= : | | Exported functions |
| Function, ub-string< : | | Exported functions |
| Function, ub-string<= : | | Exported functions |
| Function, ub-string= : | | Exported functions |
| Function, ub-string> : | | Exported functions |
| Function, ub-string>= : | | Exported functions |
| Function, ub-subseq : | | Exported functions |
| Function, ub-to-string : | | Exported functions |
| Function, ub-upper-case-p : | | Exported functions |
| Function, ukk-node-children : | | Internal functions |
| Function, ukk-node-end : | | Internal functions |
| Function, ukk-node-id : | | Internal functions |
| Function, ukk-node-p : | | Internal functions |
| Function, ukk-node-parent : | | Internal functions |
| Function, ukk-node-start : | | Internal functions |
| Function, ukk-node-suffix : | | Exported functions |
| Function, ukkonen-update : | | Internal functions |
| Function, update-md : | | Internal functions |
| Function, word-char-p : | | Internal functions |
|
G | | |
| Generic Function, match-groups : | | Exported generic functions |
| Generic Function, match-pos-end : | | Exported generic functions |
| Generic Function, match-pos-start : | | Exported generic functions |
| Generic Function, match-string : | | Exported generic functions |
| Generic Function, re-expression : | | Internal generic functions |
| Generic Function, re-pattern : | | Internal generic functions |
|
H | | |
| hash-bm : | | Internal functions |
| hex-char-p : | | Internal functions |
| horner-hash : | | Internal functions |
|
I | | |
| initialize-ac : | | Exported functions |
| initialize-bad-char : | | Internal functions |
| initialize-bm : | | Exported functions |
| initialize-bmh : | | Exported functions |
| initialize-bmh8 : | | Exported functions |
| initialize-good-suffix : | | Internal functions |
| initialize-kmp : | | Exported functions |
| initialize-rk : | | Exported functions |
| initialize-sor : | | Exported functions |
| initialize-tabac : | | Exported functions |
|
K | | |
| kmp-p : | | Internal functions |
| kmp-pat : | | Internal functions |
| kmp-pat-len : | | Internal functions |
| kmp-table : | | Internal functions |
|
M | | |
| Macro, define-bmh-matcher : | | Exported macros |
| Macro, define-brute-matcher : | | Exported macros |
| Macro, map-trie-children : | | Internal macros |
| Macro, ub-string<>=*-body : | | Internal macros |
| Macro, with-re : | | Exported macros |
| Macro, with-re-match : | | Exported macros |
| make-bm : | | Internal functions |
| make-bmh : | | Internal functions |
| make-bmh8 : | | Internal functions |
| make-kmp : | | Internal functions |
| make-lambda-ac : | | Internal functions |
| make-re-thread : | | Internal functions |
| make-rk : | | Internal functions |
| make-sor : | | Internal functions |
| make-substitution-table : | | Exported functions |
| make-suffix-node : | | Exported functions |
| make-suffix-tree : | | Exported functions |
| make-tabac : | | Internal functions |
| make-trie-node : | | Internal functions |
| make-ub-buffer : | | Exported functions |
| make-ub-line-reader : | | Exported functions |
| make-ub-string : | | Exported functions |
| make-ukk-node : | | Exported functions |
| map-trie-children : | | Internal macros |
| match-groups : | | Exported generic functions |
| match-groups : | | Exported generic functions |
| match-pos-end : | | Exported generic functions |
| match-pos-end : | | Exported generic functions |
| match-pos-start : | | Exported generic functions |
| match-pos-start : | | Exported generic functions |
| match-re : | | Exported functions |
| match-string : | | Exported generic functions |
| match-string : | | Exported generic functions |
| Method, match-groups : | | Exported generic functions |
| Method, match-pos-end : | | Exported generic functions |
| Method, match-pos-start : | | Exported generic functions |
| Method, match-string : | | Exported generic functions |
| Method, re-expression : | | Internal generic functions |
| Method, re-pattern : | | Internal generic functions |
|
N | | |
| newline-p : | | Internal functions |
|
O | | |
| octets-to-ub : | | Exported functions |
|
P | | |
| prefixed-with : | | Exported functions |
| print-markdown-footer : | | Internal functions |
| print-suffix-tree-for-gv : | | Internal functions |
| print-suffix-tree-for-gv-pretty : | | Internal functions |
| print-suffix-tree-in-file : | | Internal functions |
| punctuation-p : | | Internal functions |
|
R | | |
| re-expression : | | Internal generic functions |
| re-expression : | | Internal generic functions |
| re-pattern : | | Internal generic functions |
| re-pattern : | | Internal generic functions |
| re-thread-groups : | | Internal functions |
| re-thread-p : | | Internal functions |
| re-thread-pc : | | Internal functions |
| re-thread-sp : | | Internal functions |
| re-thread-stack : | | Internal functions |
| ref-length : | | Internal functions |
| replace-re : | | Exported functions |
| rk-alph-size : | | Internal functions |
| rk-p : | | Internal functions |
| rk-pat : | | Internal functions |
| rk-pat-hash : | | Internal functions |
| rk-pat-len : | | Internal functions |
| rk-rm : | | Internal functions |
| run : | | Internal functions |
|
S | | |
| search-ac : | | Exported functions |
| search-bm : | | Exported functions |
| search-bmh : | | Exported functions |
| search-bmh8 : | | Exported functions |
| search-compiled-ac : | | Exported functions |
| search-kmp : | | Exported functions |
| search-rk : | | Exported functions |
| search-sor : | | Exported functions |
| search-tabac : | | Exported functions |
| sor-cidx : | | Internal functions |
| sor-lim : | | Internal functions |
| sor-p : | | Internal functions |
| sor-pat-len : | | Internal functions |
| sor-printer : | | Internal functions |
| space-p : | | Internal functions |
| split-node : | | Internal functions |
| split-re : | | Exported functions |
| stbstr : | | Internal functions |
| str-length : | | Internal functions |
| string-contains-ac : | | Exported functions |
| string-contains-bm : | | Exported functions |
| string-contains-bmh : | | Exported functions |
| string-contains-bmh8 : | | Exported functions |
| string-contains-brute : | | Exported functions |
| string-contains-brute-ub : | | Exported functions |
| string-contains-kmp : | | Exported functions |
| string-contains-rk : | | Exported functions |
| string-contains-sor : | | Exported functions |
| string-contains-tabac : | | Exported functions |
| string-to-ub : | | Exported functions |
| suffix-node-add-child : | | Exported functions |
| suffix-node-children : | | Exported functions |
| suffix-node-end : | | Exported functions |
| suffix-node-equals : | | Exported functions |
| suffix-node-get-child : | | Internal functions |
| suffix-node-id : | | Internal functions |
| suffix-node-insert-child : | | Internal functions |
| suffix-node-leafp : | | Exported functions |
| suffix-node-map-over-children : | | Exported functions |
| suffix-node-p : | | Internal functions |
| suffix-node-parent : | | Internal functions |
| suffix-node-printer : | | Internal functions |
| suffix-node-start : | | Exported functions |
| suffix-node-str : | | Exported functions |
| suffix-tree-build-from-sexp : | | Exported functions |
| suffix-tree-char : | | Exported functions |
| suffix-tree-equals : | | Exported functions |
| suffix-tree-nodes-count : | | Internal functions |
| suffix-tree-p : | | Internal functions |
| suffix-tree-printer : | | Internal functions |
| suffix-tree-root : | | Exported functions |
| suffix-tree-str : | | Exported functions |
| suffix-tree-walk : | | Exported functions |
| suffixed-with : | | Exported functions |
|
T | | |
| tab-p : | | Internal functions |
| tabac-final : | | Internal functions |
| tabac-match-len : | | Internal functions |
| tabac-p : | | Internal functions |
| tabac-start : | | Internal functions |
| tabac-trans : | | Internal functions |
| tabac-transition : | | Internal functions |
| trie->compiled-ac : | | Exported functions |
| trie->tabular-ac : | | Exported functions |
| trie-add-child : | | Internal functions |
| trie-add-keyword : | | Exported functions |
| trie-build : | | Exported functions |
| trie-contains : | | Exported functions |
| trie-contains-prefix : | | Exported functions |
| trie-dump-dot : | | Internal functions |
| trie-dump-dot-file : | | Internal functions |
| trie-find-child : | | Internal functions |
| trie-node-children : | | Internal functions |
| trie-node-depth : | | Internal functions |
| trie-node-fail : | | Internal functions |
| trie-node-id : | | Internal functions |
| trie-node-label : | | Internal functions |
| trie-node-mark : | | Internal functions |
| trie-node-p : | | Internal functions |
| trie-node-printer : | | Internal functions |
| trie-pprint : | | Exported functions |
| trie-traverse-bfo : | | Exported functions |
| trie-traverse-dfo : | | Exported functions |
|
U | | |
| ub-alpha-char-p : | | Exported functions |
| ub-alphanumericp : | | Exported functions |
| ub-both-case-p : | | Exported functions |
| ub-char : | | Exported functions |
| ub-char-code : | | Exported functions |
| ub-char-downcase : | | Exported functions |
| ub-char-equal : | | Exported functions |
| ub-char-greaterp : | | Exported functions |
| ub-char-int : | | Exported functions |
| ub-char-lessp : | | Exported functions |
| ub-char-name : | | Exported functions |
| ub-char-not-equal : | | Exported functions |
| ub-char-not-greaterp : | | Exported functions |
| ub-char-not-lessp : | | Exported functions |
| ub-char-upcase : | | Exported functions |
| ub-char/= : | | Exported functions |
| ub-char< : | | Exported functions |
| ub-char<= : | | Exported functions |
| ub-char= : | | Exported functions |
| ub-char> : | | Exported functions |
| ub-char>= : | | Exported functions |
| ub-code-char : | | Exported functions |
| ub-digit-char : | | Exported functions |
| ub-digit-char-p : | | Exported functions |
| ub-graphic-char-p : | | Exported functions |
| ub-line-reader-buffer : | | Internal functions |
| ub-line-reader-close : | | Exported functions |
| ub-line-reader-eof : | | Internal functions |
| ub-line-reader-file-position : | | Exported functions |
| ub-line-reader-fill : | | Internal functions |
| ub-line-reader-p : | | Internal functions |
| ub-line-reader-pos : | | Internal functions |
| ub-line-reader-stream : | | Internal functions |
| ub-lower-case-p : | | Exported functions |
| ub-name-char : | | Exported functions |
| ub-nstring-capitalize : | | Exported functions |
| ub-nstring-downcase : | | Exported functions |
| ub-nstring-upcase : | | Exported functions |
| ub-read-line : | | Exported functions |
| ub-read-line-raw : | | Exported functions |
| ub-read-line-string : | | Exported functions |
| ub-schar : | | Internal functions |
| ub-standard-char-p : | | Exported functions |
| ub-string-capitalize : | | Exported functions |
| ub-string-downcase : | | Exported functions |
| ub-string-equal : | | Exported functions |
| ub-string-greaterp : | | Exported functions |
| ub-string-left-trim : | | Exported functions |
| ub-string-lessp : | | Exported functions |
| ub-string-not-equal : | | Exported functions |
| ub-string-not-greaterp : | | Exported functions |
| ub-string-not-lessp : | | Exported functions |
| ub-string-right-trim : | | Exported functions |
| ub-string-trim : | | Exported functions |
| ub-string-upcase : | | Exported functions |
| ub-string/= : | | Exported functions |
| ub-string< : | | Exported functions |
| ub-string<= : | | Exported functions |
| ub-string<>=*-body : | | Internal macros |
| ub-string= : | | Exported functions |
| ub-string> : | | Exported functions |
| ub-string>= : | | Exported functions |
| ub-subseq : | | Exported functions |
| ub-to-string : | | Exported functions |
| ub-upper-case-p : | | Exported functions |
| ukk-node-children : | | Internal functions |
| ukk-node-end : | | Internal functions |
| ukk-node-id : | | Internal functions |
| ukk-node-p : | | Internal functions |
| ukk-node-parent : | | Internal functions |
| ukk-node-start : | | Internal functions |
| ukk-node-suffix : | | Exported functions |
| ukkonen-update : | | Internal functions |
| update-md : | | Internal functions |
|
W | | |
| with-re : | | Exported macros |
| with-re-match : | | Exported macros |
| word-char-p : | | Internal functions |
|
A.3 Variables
| Index Entry | | Section |
|
* | | |
| *default-substitution-table* : | | Internal special variables |
| *expression-parser* : | | Internal special variables |
| *set-parser* : | | Internal special variables |
| *standard-debug-settings* : | | Internal special variables |
| *standard-optimize-settings* : | | Internal special variables |
|
+ | | |
| +ac-alphabet+ : | | Internal constants |
| +alph-size+ : | | Internal constants |
| +big-prime+ : | | Internal constants |
| +infinity+ : | | Exported constants |
| +newline+ : | | Internal constants |
| +sor-alphabet+ : | | Internal constants |
| +ub-line-reader-buffer-size+ : | | Internal constants |
|
@ | | |
| @aho-corasick-section : | | Exported special variables |
| @boyer-moore-horspool-section : | | Exported special variables |
| @boyer-moore-section : | | Exported special variables |
| @brute-force-section : | | Exported special variables |
| @cl-string-match-manual : | | Exported special variables |
| @knuth-morris-pratt-section : | | Exported special variables |
| @multi-pattern-search : | | Exported special variables |
| @pre-basic-matching-section : | | Exported special variables |
| @pre-compiling-patterns-section : | | Exported special variables |
| @pre-groups-section : | | Exported special variables |
| @pre-pattern-replacing-section : | | Exported special variables |
| @pre-pattern-scanning-section : | | Exported special variables |
| @pre-pattern-splitting-section : | | Exported special variables |
| @pre-regexp-section : | | Exported special variables |
| @pre-with-re-match-section : | | Exported special variables |
| @rabin-karp-section : | | Exported special variables |
| @regexp-pattern-search : | | Exported special variables |
| @shift-or-section : | | Exported special variables |
| @single-pattern-search : | | Exported special variables |
|
A | | |
| alph-size : | | Internal structures |
|
B | | |
| bad-char : | | Internal structures |
| bad-char-skip : | | Exported structures |
| bad-char-skip : | | Internal structures |
| buffer : | | Internal structures |
|
C | | |
| children : | | Exported structures |
| children : | | Exported structures |
| cidx : | | Internal structures |
| Constant, +ac-alphabet+ : | | Internal constants |
| Constant, +alph-size+ : | | Internal constants |
| Constant, +big-prime+ : | | Internal constants |
| Constant, +infinity+ : | | Exported constants |
| Constant, +newline+ : | | Internal constants |
| Constant, +sor-alphabet+ : | | Internal constants |
| Constant, +ub-line-reader-buffer-size+ : | | Internal constants |
| Constant, ub-char-code-limit : | | Exported constants |
|
D | | |
| depth : | | Exported structures |
|
E | | |
| end : | | Exported structures |
| end-pos : | | Exported classes |
| eof : | | Internal structures |
| expr : | | Exported classes |
|
F | | |
| fail : | | Exported structures |
| fill : | | Internal structures |
| final : | | Internal structures |
|
G | | |
| good-suffix : | | Internal structures |
| groups : | | Exported classes |
| groups : | | Internal structures |
|
I | | |
| id : | | Exported structures |
| id : | | Exported structures |
|
L | | |
| label : | | Exported structures |
| lim : | | Internal structures |
|
M | | |
| mark : | | Exported structures |
| match : | | Exported classes |
| match-len : | | Internal structures |
|
N | | |
| nodes-count : | | Exported structures |
|
P | | |
| parent : | | Exported structures |
| pat : | | Exported structures |
| pat : | | Internal structures |
| pat : | | Internal structures |
| pat : | | Internal structures |
| pat : | | Internal structures |
| pat-hash : | | Internal structures |
| pat-len : | | Exported structures |
| pat-len : | | Internal structures |
| pat-len : | | Internal structures |
| pat-len : | | Internal structures |
| pat-len : | | Internal structures |
| pattern : | | Exported classes |
| pc : | | Internal structures |
| pos : | | Internal structures |
|
R | | |
| rm : | | Internal structures |
| root : | | Exported structures |
|
S | | |
| Slot, alph-size : | | Internal structures |
| Slot, bad-char : | | Internal structures |
| Slot, bad-char-skip : | | Exported structures |
| Slot, bad-char-skip : | | Internal structures |
| Slot, buffer : | | Internal structures |
| Slot, children : | | Exported structures |
| Slot, children : | | Exported structures |
| Slot, cidx : | | Internal structures |
| Slot, depth : | | Exported structures |
| Slot, end : | | Exported structures |
| Slot, end-pos : | | Exported classes |
| Slot, eof : | | Internal structures |
| Slot, expr : | | Exported classes |
| Slot, fail : | | Exported structures |
| Slot, fill : | | Internal structures |
| Slot, final : | | Internal structures |
| Slot, good-suffix : | | Internal structures |
| Slot, groups : | | Exported classes |
| Slot, groups : | | Internal structures |
| Slot, id : | | Exported structures |
| Slot, id : | | Exported structures |
| Slot, label : | | Exported structures |
| Slot, lim : | | Internal structures |
| Slot, mark : | | Exported structures |
| Slot, match : | | Exported classes |
| Slot, match-len : | | Internal structures |
| Slot, nodes-count : | | Exported structures |
| Slot, parent : | | Exported structures |
| Slot, pat : | | Exported structures |
| Slot, pat : | | Internal structures |
| Slot, pat : | | Internal structures |
| Slot, pat : | | Internal structures |
| Slot, pat : | | Internal structures |
| Slot, pat-hash : | | Internal structures |
| Slot, pat-len : | | Exported structures |
| Slot, pat-len : | | Internal structures |
| Slot, pat-len : | | Internal structures |
| Slot, pat-len : | | Internal structures |
| Slot, pat-len : | | Internal structures |
| Slot, pattern : | | Exported classes |
| Slot, pc : | | Internal structures |
| Slot, pos : | | Internal structures |
| Slot, rm : | | Internal structures |
| Slot, root : | | Exported structures |
| Slot, sp : | | Internal structures |
| Slot, stack : | | Internal structures |
| Slot, start : | | Exported structures |
| Slot, start : | | Internal structures |
| Slot, start-pos : | | Exported classes |
| Slot, str : | | Exported structures |
| Slot, stream : | | Internal structures |
| Slot, suffix : | | Exported structures |
| Slot, table : | | Internal structures |
| Slot, trans : | | Internal structures |
| sp : | | Internal structures |
| Special Variable, *default-substitution-table* : | | Internal special variables |
| Special Variable, *expression-parser* : | | Internal special variables |
| Special Variable, *set-parser* : | | Internal special variables |
| Special Variable, *standard-debug-settings* : | | Internal special variables |
| Special Variable, *standard-optimize-settings* : | | Internal special variables |
| Special Variable, @aho-corasick-section : | | Exported special variables |
| Special Variable, @boyer-moore-horspool-section : | | Exported special variables |
| Special Variable, @boyer-moore-section : | | Exported special variables |
| Special Variable, @brute-force-section : | | Exported special variables |
| Special Variable, @cl-string-match-manual : | | Exported special variables |
| Special Variable, @knuth-morris-pratt-section : | | Exported special variables |
| Special Variable, @multi-pattern-search : | | Exported special variables |
| Special Variable, @pre-basic-matching-section : | | Exported special variables |
| Special Variable, @pre-compiling-patterns-section : | | Exported special variables |
| Special Variable, @pre-groups-section : | | Exported special variables |
| Special Variable, @pre-pattern-replacing-section : | | Exported special variables |
| Special Variable, @pre-pattern-scanning-section : | | Exported special variables |
| Special Variable, @pre-pattern-splitting-section : | | Exported special variables |
| Special Variable, @pre-regexp-section : | | Exported special variables |
| Special Variable, @pre-with-re-match-section : | | Exported special variables |
| Special Variable, @rabin-karp-section : | | Exported special variables |
| Special Variable, @regexp-pattern-search : | | Exported special variables |
| Special Variable, @shift-or-section : | | Exported special variables |
| Special Variable, @single-pattern-search : | | Exported special variables |
| stack : | | Internal structures |
| start : | | Exported structures |
| start : | | Internal structures |
| start-pos : | | Exported classes |
| str : | | Exported structures |
| stream : | | Internal structures |
| suffix : | | Exported structures |
|
T | | |
| table : | | Internal structures |
| trans : | | Internal structures |
|
U | | |
| ub-char-code-limit : | | Exported constants |
|
A.4 Data types
| Index Entry | | Section |
|
A | | |
| ascii-strings : | | The ascii-strings system |
| ascii-strings : | | The ascii-strings package |
| ascii-strings.system : | | The ascii-strings․system package |
|
B | | |
| bm : | | Internal structures |
| bmh : | | Internal structures |
| bmh8 : | | Exported structures |
|
C | | |
| cl-string-match : | | The cl-string-match system |
| cl-string-match : | | The cl-string-match package |
| Class, re : | | Exported classes |
| Class, re-match : | | Exported classes |
| clstringmatch.system : | | The clstringmatch․system package |
|
K | | |
| kmp : | | Internal structures |
|
P | | |
| Package, ascii-strings : | | The ascii-strings package |
| Package, ascii-strings.system : | | The ascii-strings․system package |
| Package, cl-string-match : | | The cl-string-match package |
| Package, clstringmatch.system : | | The clstringmatch․system package |
|
R | | |
| re : | | Exported classes |
| re-match : | | Exported classes |
| re-thread : | | Internal structures |
| rk : | | Internal structures |
| rk-ub32 : | | Internal types |
|
S | | |
| sor : | | Internal structures |
| sor-ub32 : | | Internal types |
| Structure, bm : | | Internal structures |
| Structure, bmh : | | Internal structures |
| Structure, bmh8 : | | Exported structures |
| Structure, kmp : | | Internal structures |
| Structure, re-thread : | | Internal structures |
| Structure, rk : | | Internal structures |
| Structure, sor : | | Internal structures |
| Structure, suffix-node : | | Exported structures |
| Structure, suffix-tree : | | Exported structures |
| Structure, tabac : | | Internal structures |
| Structure, trie-node : | | Exported structures |
| Structure, ub-line-reader : | | Internal structures |
| Structure, ukk-node : | | Exported structures |
| suffix-node : | | Exported structures |
| suffix-tree : | | Exported structures |
| System, ascii-strings : | | The ascii-strings system |
| System, cl-string-match : | | The cl-string-match system |
|
T | | |
| tabac : | | Internal structures |
| trie-node : | | Exported structures |
| Type, rk-ub32 : | | Internal types |
| Type, sor-ub32 : | | Internal types |
| Type, ub-buffer : | | Exported types |
| Type, ub-char : | | Exported types |
| Type, ub-string : | | Exported types |
|
U | | |
| ub-buffer : | | Exported types |
| ub-char : | | Exported types |
| ub-line-reader : | | Internal structures |
| ub-string : | | Exported types |
| ukk-node : | | Exported structures |
|