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
- The SMART tool with implementations of up to 86 exact string matching algorithms. Created by Simone Faro and Thierry Lecroq. Authors also maintain a comprehensive list of papers where these algorithms were defined.
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.