Table of Contents
Suffix Trees & Information Retrieval
Motivating Problem
Outline
Tries & Trees
Formalities & Definitions
Construction: Brute Force
Analysis
Searching
Suffix Links
Suffix Links – Example
Suffix Links: analysis
Searching with Suffix Links
Suffix Trees & Repeated Subsequences
Miscellany
Parameterized Suffix Trees
Definitions
More Definitions….
Brute-force Construction
P-Trees & Suffix Links
P-Strings & Suffix Links….
Fixes
Searching for a pattern
Chang & Lawler Search in p-suffix Trees
Finding parameterized duplications
Parameterized Duplications...
Parameterized Duplications, example
Parameterized Duplication in Software
References
PPT Slide
|