6CCS3TSP/7CCSMTSP - Text Searching and Processing

Visualization of algorithms

• String searching (C. Charras, T. Lecroq)
• Alignment (C. Charras, T. Lecroq)

Tutorials by Robert Mercas

Documents

• Abstract. This lecture introduces the basic notions and properties of strings, also called words or texts.
• Lecture
• Content. Alphabet and strings, factors and their positions, subsequences, powers, Primitivity Lemma, root and conjugates.

• Abstract. The lecture describes several methods used to build text searching facilities inside various software like text editors, search engines on the Internet, or gene finders on biological sequences. The emphasis is put on the design of time and space efficient algorithms. It contains the latest results on the subject.
• Lecture
• Content. Pattern matching, sliding window strategy, naive search, Karp-Rabin string searching, complexity of the problem and known bounds, types of searching strategies.

• Abstract. The lecture focuses on sequential string matching for which the search processes the text on-line (Knuth, Morris, and Pratt algorithm, and variants). The buffer on the text is limited to only one symbol. On-line searching algorithms are based on automata, borders of strings, and their properties.
• Lecture
• Content. Left-to-right scan, periods and borders, MP algorithm, interrupted periods and strict borders, KMP algorithm, Periodicity Lemma, String-Matching Automaton and its significant arcs.
• SMA construction by Thierry Lecroq

• Abstract. The Table of prefixes of a string stores for each position the longest prefix of the string starting there. It contains information analogous to the Border table and can be used as well to design efficient String-Matching algorithms.
• Reference (not for the exam)
• Content. Table of prefixes, property, linear-time computation, relation between borders and prefixes.

• Abstract. The lecture deals with searching a text for a dictionary of patterns. The solution that is presented relies on the design of a Dictionary Matching Automaton, sometimes called the Aho-Corasick machine. It is an extension of the String-Matching Automaton discussed for sequential String Matching.
• Lecture
• Content. Matching several strings, trie of the dictionary, Dictionary Matching Automaton, failure function, search with failure function, computing failure links, optimization of the delay.

• Abstract. The lecture considers practically-efficient string-matching algorithms. (Boyer and Moore algorithm, and variants). They are based a backward scanning of the sliding window and on combinatorial properties of strings.
• Lecture (Pages 12 to 21 are not for the exam)
• Content. Right-to-left scan, match shift, BM algorithm, occurrence shift, turbo-BM algorithm, AG algorithm, table of suffixes.

• Abstract. The lecture presents the binary search technique used to search for a string in a list of ordered strings. The technique is based on combinatorial properties of longest common prefixes of elements of the list.
• Lecture
• Content. Searching, interval, longest common prefixes (LCP's), improved binary search, preprocessing the list.

• Abstract. Indexes on texts are used to access part of them efficiently. The Suffix Array technique provides an efficient implementation based on the method used for searching an ordered list of strings. The list comprises the non-empty suffixes of the text. The lecture describes how to create a suffix array, that is, sorting and computing LCP's of suffixes.
• Lecture
• Content. Indexes and their implementation, Suffix Array, sorting suffixes, ranks of suffixes, doubling technique, linear-time sorting, computing LCP's.

• Abstract. A Suffix Tree is a data structure used to implement the index of a text. It stores all the suffixes of the text in linear space and provide a direct access to all factors of the text. The lecture introduces the notions and properties of Suffix Trees and describes an efficient construction.
• Lecture
• Content. Trie of suffixes, forks, suffix link, Suffix Tree, slow find, fast find, complete construction algorithm.

• Abstract. The Suffix Automaton is an alternative data structure to implement indexes. It is the minimized version of the suffix trie. The lecture sketches the notion and the linear-time construction, as well as the notion of compact suffix automaton.
• Lecture
• Content. Suffix Automaton and its size, sketch of construction, compact suffix automaton.

• Abstract. Regular expressions are powerful tools to describe patterns and motifs. They are used in many software concerned with file management (searching, editing, compiling, ...). The lecture presents the standard algorithm used to match regular patterns. The generic solution is based on the generation of an automaton which serves for analysing files.
• Lecture
• Content. Grammar of regular expressions, syntactic analysis of regular expressions, translation into an automaton, generation of automata, acceptation procedure, searching procedure, determinisation of automata, time-space tradeoffs.

Past BSc exams