Algorithms and Data Structures: String Searching, Suffix Tree

[CSE2304], [FAQ], [progress] & [plan], Bib', Alg's, C - L.A., Sem'1, 2006, FIT, Monash, .au
Instructions: Topics discussed in these lecture notes are examinable unless otherwise indicated. You need to follow instructions, take more notes & draw diagrams especially as [indicated] or as done in lectures, work through examples, and do extra reading. Hyper-links not in [square brackets] are mainly for revision, for further reading, and for lecturers of the subject.

String Searching: Suffix Tree: Introduction

Recall String searching for a `pattern' in a `text'.
Good algorithms take O( | text | )-time.
It turns out that we can do search in O( | pattern | )-time if we spend some pre-processing time to build an index of some kind,
e.g. a suffix tree . . .

Definitions, given txt[1..n]

A prefix is a substring txt[1..j]
A suffix is a substring txt[i..n]
A substring is txt[i..j], so
a substring is a prefix of a suffix (or equivalently a [________] of a [________].)
There are n * (n+1) / 2 non-empty substrings of txt but
an "index" of the n suffices is enough to find any substring

e.g. Consider the suffices of txt[1..n] = ``mississippi'' :

(or maybe ``Woolloomooloo'')

T₁  = mississippi = txt
T₂  = ississippi
T₃  = ssissippi
T₄  = sissippi
T₅  = issippi
T₆  = ssippi
T₇  = sippi
T₈  = ippi
T₉  = ppi
T₁₀ = pi
T₁₁ = i

Could sort (pointers to) suffixes

T₁₁ = i
T₈  = ippi
T₅  = issippi
T₂  = ississippi
T₁  = mississippi
T₁₀ = pi
T₉  = ppi
T₇  = sippi
T₄  = sissippi
T₆  = ssippi
T₃  = ssissippi

Sort at least O(n.log(n))-time, search at least O(log(n))-time. Question: What would be worst case?

Suffix Tree

is a special data structure
- a tree, edges labelled with substrings
is related to Trie and PATRICIA
can be built, right to left, in O(n)-time (Weiner 1973, McCreight 1976) and
left to right, in O(n)-time (Ukkonen 1992, 1995)
- which is good because [________________________________]
O(n)-space, but a large constant, so research into variations and alternatives is still current.

suffix tree for mississippi [lecturer: do a search; class: take notes!]

tree-->|---mississippi
       |
       |---i-->|---ssi-->|---ssippi
       |       |         |
       |       |         |---ppi
       |       |
       |       |---ppi
       |
       |---s-->|----si-->|---ssippi
       |       |         |
       |       |         |---ppi
       |       |
       |       |----i--->|---ssippi
       |                 |
       |                 |---ppi
       |--p-->|---pi
              |
              |---i

[lecturer: consider building an ST for a different string e.g. ``Woolloomooloo'']

How to build a Suffix Tree?

           tree₁

tree-->----m...

Adding the second character to get `mi' there are now suffixes `mi' and `i':

           tree₂

tree-->|---mi...
       |
       |---i...

Next `mis'

tree-->|---mis...                       -- tree₃
       |
       |---is...
       |
       |---s...

There is no need to add any more splits for `miss' because `s' is part of `ss'.

tree-->|---miss...                      -- tree₄
       |
       |---iss...
       |
       |---ss...

However, with `missi' there must be a split . . .

. . . split because one `s' is followed by `i', the other by `s'

tree-->|---missi...                     -- tree₅
       |
       |---issi...
       |
       |---s-->|---si...
               |
               |---i...

[etc. . . .]

[lecturer: demonstrate uses; class: take notes!]

Uses of Suffix Tree

Search for pat[1..m] in txt[1..n]
- preprocessing O(n)-time
- search O(m)-time
Longest repeated substring in txt.
Longest common substring of txt₁ and txt₂.
Longest palindrome in txt.

String Searching: Suffix Tree: Summary

Can be built in O(n)-time (Weiner 1973, McCreight 1976, Ukkonen 1992, 1995; see bib')
search for pat[1..m] then takes only O(m)-time.
Compare with other String Search methods.
NB. Algorithm to build a S.T. in O(n)-time is not examinable

(but to build a S.T. as above "by hand", and applications of S.T. are examinable).