Resources and Literature

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.

Literature

• 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.

Internet Resources

• 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

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
• proc-parse: procedural string parser. Parses strings and octets, wraps multiple patterns dispatcher into macros making them more readable.

Regular expression matchers:

• cl-irregsexp: offers fast text matching.
• CLAWK: AWK implementation embedded into Common Lisp.
• re: small, lightweight, and very fast, regular expression library for LispWorks. It is a non-recursive, backtracing VM. The syntax is similar to Lua-style pattern patching, but has added support for additional regex features.