This page contains literature used to implement algorithms in this package and some suggested reading on the subject of this package: string matching, substring search, pattern matching and subset search.
- Computing Patterns in Strings - Bill Smyth. Pearson/Addison Wesley, 2003.
- Algorithms - Sedgewick, Wayne. Addison-Wesley, 4th ed., 2011.
- Flexible Pattern Matching in Strings: Practical On-Line Search Algorithms for Texts and Biological Sequences - Gonzalo Navarro, Matthieu Raffinot, Cambridge University Press, 2002.
- Christian Charras and Thierry Lecroq, Exact String Matching Algorithms
- The Prague Stringology Club
- Liu Xinyu, Suffix Tree with Functional and imperative implementation
- A chapter from the book "Information Retrieval: Data Structures & Algorithms" edited by William B. Frakes and Ricardo Baeza-Yates. Ricardo A. Baeza-Yates, CHAPTER 10: STRING SEARCHING ALGORITHMS. Contains BMH algorithm implementation with Hume and Sunday improvements
- Regular Expression Matching: the Virtual Machine Approach by Russ Cox and Regular Expression Matching Can Be Simple And Fast by the same author explaining the Thompson NFA approach to regular expressions
Might be useful
- Mike Haertel, why GNU grep is fast
Relevant Common Lisp packages
Following packages and libraries implement substring search, string search, pattern matching and regular engine implementations on Lisp.
- CL-DAWG: Direct Acyclic Word Graph implementation
- BK-TREE: implements a derivative of BK-Tree data structure
- info.read-eval-print.trie: provides in-memory and on-disk Trie implementations
- cl-trie: CLOS-based Trie implementation, available as a Quicklisp package
- proc-parse: procedural string parser. Parses strings and octets, wraps multiple patterns dispatcher into macros making them more readable.
- mk-string-metrics: implements efficient algorithms that calculate various string metrics in Common Lisp: Damerau-Levenshtein distance, Hamming distance, Jaccard similarity coefficient, Jaro distance, Jaro-Winkler distance, Levenshtein distance, Normalized Damerau-Levenshtein distance, Normalized Levenshtein distance, Overlap coefficient.
- Text packages listed on Cliki.
Other articles on this Wiki
- Regular expressions in Common Lisp lists known regexp engine implementations in Common Lisp and provides some brief information about them.