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 Apr 28 11:21:54 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:

• Prefix trie
• Suffix tree

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:

• Project home page
• Also take a look at the project Wiki
• A mirror on SourceForge

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

• alexandria
• babel

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

• package.lisp (file)
• utils.lisp (file)
• brute-force.lisp (file)
• boyer-moore.lisp (file)
• boyer-moore-horspool.lisp (file)
• rabin-karp.lisp (file)
• knuth-morris-pratt.lisp (file)
• shift-or.lisp (file)
• aho-corasick.lisp (file)
• compiled-aho-corasick.lisp (file)
• suffix-tree.lisp (file)
• pre.lisp (file)
• doc.lisp (file)

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

• *standard-debug-settings* (special variable)
• *standard-optimize-settings* (special variable)
• format-name (function)

4.1.4 cl-string-match/src/utils.lisp

Dependency

package.lisp (file)

Parent

src (module)

Location

src/utils.lisp

Exported Definitions

• prefixed-with (function)
• suffixed-with (function)

4.1.5 cl-string-match/src/brute-force.lisp

Dependency

utils.lisp (file)

Parent

src (module)

Location

src/brute-force.lisp

Exported Definitions

• @brute-force-section (special variable)
• define-brute-matcher (macro)
• string-contains-brute (function)
• string-contains-brute-ub (function)

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

• @boyer-moore-section (special variable)
• initialize-bm (function)
• search-bm (function)
• string-contains-bm (function)

Internal Definitions

• bm (structure)
• bm-bad-char (function)
• (setf bm-bad-char) (function)
• bm-good-suffix (function)
• (setf bm-good-suffix) (function)
• bm-p (function)
• bm-pat (function)
• (setf bm-pat) (function)
• bm-suffixes (function)
• copy-bm (function)
• hash-bm (function)
• initialize-bad-char (function)
• initialize-good-suffix (function)
• make-bm (function)

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

• @boyer-moore-horspool-section (special variable)
• bmh8 (structure)
• bmh8-p (function)
• bmh8-pat (function)
• (setf bmh8-pat) (function)
• define-bmh-matcher (macro)
• initialize-bmh (function)
• initialize-bmh8 (function)
• search-bmh (function)
• search-bmh8 (function)
• string-contains-bmh (function)
• string-contains-bmh8 (function)

Internal Definitions

• bmh (structure)
• bmh-bad-char-skip (function)
• (setf bmh-bad-char-skip) (function)
• bmh-p (function)
• bmh-pat (function)
• (setf bmh-pat) (function)
• bmh-pat-len (function)
• (setf bmh-pat-len) (function)
• bmh8-bad-char-skip (function)
• (setf bmh8-bad-char-skip) (function)
• bmh8-pat-len (function)
• (setf bmh8-pat-len) (function)
• copy-bmh (function)
• copy-bmh8 (function)
• make-bmh (function)
• make-bmh8 (function)

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

• @rabin-karp-section (special variable)
• initialize-rk (function)
• search-rk (function)
• string-contains-rk (function)

Internal Definitions

• +alph-size+ (constant)
• +big-prime+ (constant)
• check-rk-lv (function)
• check-rk-mk (function)
• copy-rk (function)
• horner-hash (function)
• make-rk (function)
• rk (structure)
• rk-alph-size (function)
• (setf rk-alph-size) (function)
• rk-p (function)
• rk-pat (function)
• (setf rk-pat) (function)
• rk-pat-hash (function)
• (setf rk-pat-hash) (function)
• rk-pat-len (function)
• (setf rk-pat-len) (function)
• rk-rm (function)
• (setf rk-rm) (function)
• rk-ub32 (type)

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

• @knuth-morris-pratt-section (special variable)
• initialize-kmp (function)
• search-kmp (function)
• string-contains-kmp (function)

Internal Definitions

• copy-kmp (function)
• kmp (structure)
• kmp-p (function)
• kmp-pat (function)
• (setf kmp-pat) (function)
• kmp-pat-len (function)
• (setf kmp-pat-len) (function)
• kmp-table (function)
• (setf kmp-table) (function)
• make-kmp (function)

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

• @shift-or-section (special variable)
• initialize-sor (function)
• search-sor (function)
• string-contains-sor (function)

Internal Definitions

• +sor-alphabet+ (constant)
• copy-sor (function)
• make-sor (function)
• sor (structure)
• sor-cidx (function)
• (setf sor-cidx) (function)
• sor-lim (function)
• (setf sor-lim) (function)
• sor-p (function)
• sor-pat-len (function)
• (setf sor-pat-len) (function)
• sor-printer (function)
• sor-ub32 (type)

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

• @aho-corasick-section (special variable)
• empty-trie (function)
• initialize-ac (function)
• initialize-tabac (function)
• search-ac (function)
• search-tabac (function)
• string-contains-ac (function)
• string-contains-tabac (function)
• trie->tabular-ac (function)
• trie-add-keyword (function)
• trie-build (function)
• trie-contains (function)
• trie-contains-prefix (function)
• trie-node (structure)
• trie-pprint (function)
• trie-traverse-bfo (function)
• trie-traverse-dfo (function)

Internal Definitions

• +ac-alphabet+ (constant)
• compute-failure-function (function)
• copy-tabac (function)
• copy-trie-node (function)
• make-tabac (function)
• make-trie-node (function)
• map-trie-children (macro)
• tabac (structure)
• tabac-final (function)
• (setf tabac-final) (function)
• tabac-match-len (function)
• (setf tabac-match-len) (function)
• tabac-p (function)
• tabac-start (function)
• (setf tabac-start) (function)
• tabac-trans (function)
• (setf tabac-trans) (function)
• tabac-transition (function)
• trie-add-child (function)
• trie-dump-dot (function)
• trie-dump-dot-file (function)
• trie-find-child (function)
• trie-node-children (function)
• (setf trie-node-children) (function)
• trie-node-depth (function)
• (setf trie-node-depth) (function)
• trie-node-fail (function)
• (setf trie-node-fail) (function)
• trie-node-id (function)
• (setf trie-node-id) (function)
• trie-node-label (function)
• (setf trie-node-label) (function)
• trie-node-mark (function)
• (setf trie-node-mark) (function)
• trie-node-p (function)
• trie-node-printer (function)

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

• search-compiled-ac (function)
• trie->compiled-ac (function)

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

• +infinity+ (constant)
• build-suffix-tree-simple (function)
• build-suffix-tree-ukkonen (function)
• make-suffix-node (function)
• make-suffix-tree (function)
• make-ukk-node (function)
• suffix-node (structure)
• suffix-node-add-child (function)
• suffix-node-children (function)
• (setf suffix-node-children) (function)
• suffix-node-end (function)
• (setf suffix-node-end) (function)
• suffix-node-equals (function)
• suffix-node-leafp (function)
• suffix-node-map-over-children (function)
• suffix-node-start (function)
• (setf suffix-node-start) (function)
• suffix-node-str (function)
• suffix-tree (structure)
• suffix-tree-build-from-sexp (function)
• suffix-tree-char (function)
• suffix-tree-equals (function)
• suffix-tree-root (function)
• (setf suffix-tree-root) (function)
• suffix-tree-str (function)
• (setf suffix-tree-str) (function)
• suffix-tree-walk (function)
• ukk-node (structure)
• ukk-node-suffix (function)
• (setf ukk-node-suffix) (function)

Internal Definitions

• add-suffix-simple (function)
• branch (function)
• build-suffix-tree-mccreight (function)
• canonize (function)
• copy-suffix-node (function)
• copy-suffix-tree (function)
• copy-ukk-node (function)
• print-suffix-tree-for-gv (function)
• print-suffix-tree-for-gv-pretty (function)
• print-suffix-tree-in-file (function)
• ref-length (function)
• split-node (function)
• stbstr (function)
• str-length (function)
• suffix-node-get-child (function)
• suffix-node-id (function)
• (setf suffix-node-id) (function)
• suffix-node-insert-child (function)
• suffix-node-p (function)
• suffix-node-parent (function)
• (setf suffix-node-parent) (function)
• suffix-node-printer (function)
• suffix-tree-nodes-count (function)
• (setf suffix-tree-nodes-count) (function)
• suffix-tree-p (function)
• suffix-tree-printer (function)
• ukk-node-children (function)
• (setf ukk-node-children) (function)
• ukk-node-end (function)
• (setf ukk-node-end) (function)
• ukk-node-id (function)
• (setf ukk-node-id) (function)
• ukk-node-p (function)
• ukk-node-parent (function)
• (setf ukk-node-parent) (function)
• ukk-node-start (function)
• (setf ukk-node-start) (function)
• ukkonen-update (function)

4.1.14 cl-string-match/src/pre.lisp

Dependency

suffix-tree.lisp (file)

Parent

src (module)

Location

src/pre.lisp

Exported Definitions

• @pre-basic-matching-section (special variable)
• @pre-compiling-patterns-section (special variable)
• @pre-groups-section (special variable)
• @pre-pattern-replacing-section (special variable)
• @pre-pattern-scanning-section (special variable)
• @pre-pattern-splitting-section (special variable)
• @pre-regexp-section (special variable)
• @pre-with-re-match-section (special variable)
• compile-re (function)
• find-re (function)
• match-groups (method)
• match-pos-end (method)
• match-pos-start (method)
• match-re (function)
• match-string (method)
• re (class)
• re-match (class)
• replace-re (function)
• split-re (function)
• with-re (macro)
• with-re-match (macro)

Internal Definitions

• *expression-parser* (special variable)
• *set-parser* (special variable)
• compile-set (function)
• copy-re-thread (function)
• escape (function)
• hex-char-p (function)
• make-re-thread (function)
• newline-p (function)
• punctuation-p (function)
• re-expression (method)
• re-pattern (method)
• re-thread (structure)
• re-thread-groups (function)
• (setf re-thread-groups) (function)
• re-thread-p (function)
• re-thread-pc (function)
• (setf re-thread-pc) (function)
• re-thread-sp (function)
• (setf re-thread-sp) (function)
• re-thread-stack (function)
• (setf re-thread-stack) (function)
• run (function)
• space-p (function)
• tab-p (function)
• word-char-p (function)

4.1.15 cl-string-match/src/doc.lisp

Dependency

pre.lisp (file)

Parent

src (module)

Location

src/doc.lisp

Exported Definitions

• @cl-string-match-manual (special variable)
• @multi-pattern-search (special variable)
• @regexp-pattern-search (special variable)
• @single-pattern-search (special variable)

Internal Definitions

• print-markdown-footer (function)
• update-md (function)

4.1.16 ascii-strings/contrib/ascii-strings.lisp

Parent

contrib (module)

Location

contrib/ascii-strings.lisp

Packages

ascii-strings

Exported Definitions

• ascii-char-code (function)
• make-substitution-table (function)
• make-ub-buffer (function)
• make-ub-line-reader (function)
• make-ub-string (function)
• octets-to-ub (function)
• string-to-ub (function)
• ub-alpha-char-p (function)
• ub-alphanumericp (function)
• ub-both-case-p (function)
• ub-buffer (type)
• ub-char (function)
• ub-char (type)
• ub-char-code (function)
• ub-char-code-limit (constant)
• ub-char-downcase (function)
• ub-char-equal (function)
• ub-char-greaterp (function)
• ub-char-int (function)
• ub-char-lessp (function)
• ub-char-name (function)
• ub-char-not-equal (function)
• ub-char-not-greaterp (function)
• ub-char-not-lessp (function)
• ub-char-upcase (function)
• ub-char/= (function)
• ub-char< (function)
• ub-char<= (function)
• ub-char= (function)
• ub-char> (function)
• ub-char>= (function)
• ub-code-char (function)
• ub-digit-char (function)
• ub-digit-char-p (function)
• ub-graphic-char-p (function)
• ub-line-reader-close (function)
• ub-line-reader-file-position (function)
• ub-lower-case-p (function)
• ub-name-char (function)
• ub-nstring-capitalize (function)
• ub-nstring-downcase (function)
• ub-nstring-upcase (function)
• ub-read-line (function)
• ub-read-line-raw (function)
• ub-read-line-string (function)
• ub-standard-char-p (function)
• ub-string (type)
• ub-string-capitalize (function)
• ub-string-downcase (function)
• ub-string-equal (function)
• ub-string-greaterp (function)
• ub-string-left-trim (function)
• ub-string-lessp (function)
• ub-string-not-equal (function)
• ub-string-not-greaterp (function)
• ub-string-not-lessp (function)
• ub-string-right-trim (function)
• ub-string-trim (function)
• ub-string-upcase (function)
• ub-string/= (function)
• ub-string< (function)
• ub-string<= (function)
• ub-string= (function)
• ub-string> (function)
• ub-string>= (function)
• ub-subseq (function)
• ub-to-string (function)
• ub-upper-case-p (function)

Internal Definitions

• %ub-string-compare (function)
• *default-substitution-table* (special variable)
• +newline+ (constant)
• +ub-line-reader-buffer-size+ (constant)
• copy-ub-line-reader (function)
• ub-line-reader (structure)
• ub-line-reader-buffer (function)
• (setf ub-line-reader-buffer) (function)
• ub-line-reader-eof (function)
• (setf ub-line-reader-eof) (function)
• ub-line-reader-fill (function)
• (setf ub-line-reader-fill) (function)
• ub-line-reader-p (function)
• ub-line-reader-pos (function)
• (setf ub-line-reader-pos) (function)
• ub-line-reader-stream (function)
• (setf ub-line-reader-stream) (function)
• ub-schar (function)
• ub-string<>=*-body (macro)

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

• mgl-pax
• ascii-strings
• iterate
• alexandria
• common-lisp

Exported Definitions

• +infinity+ (constant)
• @aho-corasick-section (special variable)
• @boyer-moore-horspool-section (special variable)
• @boyer-moore-section (special variable)
• @brute-force-section (special variable)
• @cl-string-match-manual (special variable)
• @knuth-morris-pratt-section (special variable)
• @multi-pattern-search (special variable)
• @pre-basic-matching-section (special variable)
• @pre-compiling-patterns-section (special variable)
• @pre-groups-section (special variable)
• @pre-pattern-replacing-section (special variable)
• @pre-pattern-scanning-section (special variable)
• @pre-pattern-splitting-section (special variable)
• @pre-regexp-section (special variable)
• @pre-with-re-match-section (special variable)
• @rabin-karp-section (special variable)
• @regexp-pattern-search (special variable)
• @shift-or-section (special variable)
• @single-pattern-search (special variable)
• bmh8 (structure)
• bmh8-p (function)
• bmh8-pat (function)
• (setf bmh8-pat) (function)
• build-suffix-tree-simple (function)
• build-suffix-tree-ukkonen (function)
• compile-re (function)
• define-bmh-matcher (macro)
• define-brute-matcher (macro)
• empty-trie (function)
• find-re (function)
• initialize-ac (function)
• initialize-bm (function)
• initialize-bmh (function)
• initialize-bmh8 (function)
• initialize-kmp (function)
• initialize-rk (function)
• initialize-sor (function)
• initialize-tabac (function)
• make-suffix-node (function)
• make-suffix-tree (function)
• make-ukk-node (function)
• match-groups (generic function)
• match-groups (method)
• match-pos-end (generic function)
• match-pos-end (method)
• match-pos-start (generic function)
• match-pos-start (method)
• match-re (function)
• match-string (generic function)
• match-string (method)
• prefixed-with (function)
• re (class)
• re-match (class)
• replace-re (function)
• search-ac (function)
• search-bm (function)
• search-bmh (function)
• search-bmh8 (function)
• search-compiled-ac (function)
• search-kmp (function)
• search-rk (function)
• search-sor (function)
• search-tabac (function)
• split-re (function)
• string-contains-ac (function)
• string-contains-bm (function)
• string-contains-bmh (function)
• string-contains-bmh8 (function)
• string-contains-brute (function)
• string-contains-brute-ub (function)
• string-contains-kmp (function)
• string-contains-rk (function)
• string-contains-sor (function)
• string-contains-tabac (function)
• suffix-node (structure)
• suffix-node-add-child (function)
• suffix-node-children (function)
• (setf suffix-node-children) (function)
• suffix-node-end (function)
• (setf suffix-node-end) (function)
• suffix-node-equals (function)
• suffix-node-leafp (function)
• suffix-node-map-over-children (function)
• suffix-node-start (function)
• (setf suffix-node-start) (function)
• suffix-node-str (function)
• suffix-tree (structure)
• suffix-tree-build-from-sexp (function)
• suffix-tree-char (function)
• suffix-tree-equals (function)
• suffix-tree-root (function)
• (setf suffix-tree-root) (function)
• suffix-tree-str (function)
• (setf suffix-tree-str) (function)
• suffix-tree-walk (function)
• suffixed-with (function)
• trie->compiled-ac (function)
• trie->tabular-ac (function)
• trie-add-keyword (function)
• trie-build (function)
• trie-contains (function)
• trie-contains-prefix (function)
• trie-node (structure)
• trie-pprint (function)
• trie-traverse-bfo (function)
• trie-traverse-dfo (function)
• ukk-node (structure)
• ukk-node-suffix (function)
• (setf ukk-node-suffix) (function)
• with-re (macro)
• with-re-match (macro)

Internal Definitions

• *expression-parser* (special variable)
• *set-parser* (special variable)
• *standard-debug-settings* (special variable)
• *standard-optimize-settings* (special variable)
• +ac-alphabet+ (constant)
• +alph-size+ (constant)
• +big-prime+ (constant)
• +sor-alphabet+ (constant)
• add-suffix-simple (function)
• bm (structure)
• bm-bad-char (function)
• (setf bm-bad-char) (function)
• bm-good-suffix (function)
• (setf bm-good-suffix) (function)
• bm-p (function)
• bm-pat (function)
• (setf bm-pat) (function)
• bm-suffixes (function)
• bmh (structure)
• bmh-bad-char-skip (function)
• (setf bmh-bad-char-skip) (function)
• bmh-p (function)
• bmh-pat (function)
• (setf bmh-pat) (function)
• bmh-pat-len (function)
• (setf bmh-pat-len) (function)
• bmh8-bad-char-skip (function)
• (setf bmh8-bad-char-skip) (function)
• bmh8-pat-len (function)
• (setf bmh8-pat-len) (function)
• branch (function)
• build-suffix-tree-mccreight (function)
• canonize (function)
• check-rk-lv (function)
• check-rk-mk (function)
• compile-set (function)
• compute-failure-function (function)
• copy-bm (function)
• copy-bmh (function)
• copy-bmh8 (function)
• copy-kmp (function)
• copy-re-thread (function)
• copy-rk (function)
• copy-sor (function)
• copy-suffix-node (function)
• copy-suffix-tree (function)
• copy-tabac (function)
• copy-trie-node (function)
• copy-ukk-node (function)
• escape (function)
• format-name (function)
• hash-bm (function)
• hex-char-p (function)
• horner-hash (function)
• initialize-bad-char (function)
• initialize-good-suffix (function)
• kmp (structure)
• kmp-p (function)
• kmp-pat (function)
• (setf kmp-pat) (function)
• kmp-pat-len (function)
• (setf kmp-pat-len) (function)
• kmp-table (function)
• (setf kmp-table) (function)
• make-bm (function)
• make-bmh (function)
• make-bmh8 (function)
• make-kmp (function)
• make-lambda-ac (function)
• make-re-thread (function)
• make-rk (function)
• make-sor (function)
• make-tabac (function)
• make-trie-node (function)
• map-trie-children (macro)
• newline-p (function)
• print-markdown-footer (function)
• print-suffix-tree-for-gv (function)
• print-suffix-tree-for-gv-pretty (function)
• print-suffix-tree-in-file (function)
• punctuation-p (function)
• re-expression (generic function)
• re-expression (method)
• re-pattern (generic function)
• re-pattern (method)
• re-thread (structure)
• re-thread-groups (function)
• (setf re-thread-groups) (function)
• re-thread-p (function)
• re-thread-pc (function)
• (setf re-thread-pc) (function)
• re-thread-sp (function)
• (setf re-thread-sp) (function)
• re-thread-stack (function)
• (setf re-thread-stack) (function)
• ref-length (function)
• rk (structure)
• rk-alph-size (function)
• (setf rk-alph-size) (function)
• rk-p (function)
• rk-pat (function)
• (setf rk-pat) (function)
• rk-pat-hash (function)
• (setf rk-pat-hash) (function)
• rk-pat-len (function)
• (setf rk-pat-len) (function)
• rk-rm (function)
• (setf rk-rm) (function)
• rk-ub32 (type)
• run (function)
• sor (structure)
• sor-cidx (function)
• (setf sor-cidx) (function)
• sor-lim (function)
• (setf sor-lim) (function)
• sor-p (function)
• sor-pat-len (function)
• (setf sor-pat-len) (function)
• sor-printer (function)
• sor-ub32 (type)
• space-p (function)
• split-node (function)
• stbstr (function)
• str-length (function)
• suffix-node-get-child (function)
• suffix-node-id (function)
• (setf suffix-node-id) (function)
• suffix-node-insert-child (function)
• suffix-node-p (function)
• suffix-node-parent (function)
• (setf suffix-node-parent) (function)
• suffix-node-printer (function)
• suffix-tree-nodes-count (function)
• (setf suffix-tree-nodes-count) (function)
• suffix-tree-p (function)
• suffix-tree-printer (function)
• tab-p (function)
• tabac (structure)
• tabac-final (function)
• (setf tabac-final) (function)
• tabac-match-len (function)
• (setf tabac-match-len) (function)
• tabac-p (function)
• tabac-start (function)
• (setf tabac-start) (function)
• tabac-trans (function)
• (setf tabac-trans) (function)
• tabac-transition (function)
• trie-add-child (function)
• trie-dump-dot (function)
• trie-dump-dot-file (function)
• trie-find-child (function)
• trie-node-children (function)
• (setf trie-node-children) (function)
• trie-node-depth (function)
• (setf trie-node-depth) (function)
• trie-node-fail (function)
• (setf trie-node-fail) (function)
• trie-node-id (function)
• (setf trie-node-id) (function)
• trie-node-label (function)
• (setf trie-node-label) (function)
• trie-node-mark (function)
• (setf trie-node-mark) (function)
• trie-node-p (function)
• trie-node-printer (function)
• ukk-node-children (function)
• (setf ukk-node-children) (function)
• ukk-node-end (function)
• (setf ukk-node-end) (function)
• ukk-node-id (function)
• (setf ukk-node-id) (function)
• ukk-node-p (function)
• ukk-node-parent (function)
• (setf ukk-node-parent) (function)
• ukk-node-start (function)
• (setf ukk-node-start) (function)
• ukkonen-update (function)
• update-md (function)
• word-char-p (function)

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

• alexandria
• common-lisp

Used By List

cl-string-match

Exported Definitions

• ascii-char-code (function)
• make-substitution-table (function)
• make-ub-buffer (function)
• make-ub-line-reader (function)
• make-ub-string (function)
• octets-to-ub (function)
• string-to-ub (function)
• ub-alpha-char-p (function)
• ub-alphanumericp (function)
• ub-both-case-p (function)
• ub-buffer (type)
• ub-char (function)
• ub-char (type)
• ub-char-code (function)
• ub-char-code-limit (constant)
• ub-char-downcase (function)
• ub-char-equal (function)
• ub-char-greaterp (function)
• ub-char-int (function)
• ub-char-lessp (function)
• ub-char-name (function)
• ub-char-not-equal (function)
• ub-char-not-greaterp (function)
• ub-char-not-lessp (function)
• ub-char-upcase (function)
• ub-char/= (function)
• ub-char< (function)
• ub-char<= (function)
• ub-char= (function)
• ub-char> (function)
• ub-char>= (function)
• ub-code-char (function)
• ub-digit-char (function)
• ub-digit-char-p (function)
• ub-graphic-char-p (function)
• ub-line-reader-close (function)
• ub-line-reader-file-position (function)
• ub-lower-case-p (function)
• ub-name-char (function)
• ub-nstring-capitalize (function)
• ub-nstring-downcase (function)
• ub-nstring-upcase (function)
• ub-read-line (function)
• ub-read-line-raw (function)
• ub-read-line-string (function)
• ub-standard-char-p (function)
• ub-string (type)
• ub-string-capitalize (function)
• ub-string-downcase (function)
• ub-string-equal (function)
• ub-string-greaterp (function)
• ub-string-left-trim (function)
• ub-string-lessp (function)
• ub-string-not-equal (function)
• ub-string-not-greaterp (function)
• ub-string-not-lessp (function)
• ub-string-right-trim (function)
• ub-string-trim (function)
• ub-string-upcase (function)
• ub-string/= (function)
• ub-string< (function)
• ub-string<= (function)
• ub-string= (function)
• ub-string> (function)
• ub-string>= (function)
• ub-subseq (function)
• ub-to-string (function)
• ub-upper-case-p (function)

Internal Definitions

• %ub-string-compare (function)
• *default-substitution-table* (special variable)
• +newline+ (constant)
• +ub-line-reader-buffer-size+ (constant)
• copy-ub-line-reader (function)
• ub-line-reader (structure)
• ub-line-reader-buffer (function)
• (setf ub-line-reader-buffer) (function)
• ub-line-reader-eof (function)
• (setf ub-line-reader-eof) (function)
• ub-line-reader-fill (function)
• (setf ub-line-reader-fill) (function)
• ub-line-reader-p (function)
• ub-line-reader-pos (function)
• (setf ub-line-reader-pos) (function)
• ub-line-reader-stream (function)
• (setf ub-line-reader-stream) (function)
• ub-schar (function)
• ub-string<>=*-body (macro)

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

• make-load-form (method)
• print-object (method)
• re-expression (method)
• re-pattern (method)

Direct slots

Slot: pattern

Initargs

:pattern

Readers

re-pattern (generic function)

Slot: expr

Initargs

:expression

Readers

re-expression (generic function)