[Subject home], [FAQ], [progress],   Bib', Alg's,  C , Java - L.A., Friday, 29-Mar-2024 07:30:32 AEDT
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

Definitions,   given txt[1..n]

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

(or maybe ``Woolloomooloo'')
T1  = mississippi = txt
T2  = ississippi
T3  = ssissippi
T4  = sissippi
T5  = issippi
T6  = ssippi
T7  = sippi
T8  = ippi
T9  = ppi
T10 = pi
T11 = i

Could sort (pointers to) suffixes

T11 = i
T8  = ippi
T5  = issippi
T2  = ississippi
T1  = mississippi
T10 = pi
T9  = ppi
T7  = sippi
T4  = sissippi
T6  = ssippi
T3  = ssissippi
Sort at least O(n.log(n))-time,   search at least O(log(n))-time. Question: What would be worst case?

Suffix Tree

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
©
L
.
A
l
l
i
s
o
n
[lecturer: consider building an ST for a different string e.g. ``Woolloomooloo'']

How to build a Suffix Tree?

           tree1

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

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

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

Next `mis'

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

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

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

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

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

tree-->|---missi...                     -- tree5
       |
       |---issi...
       |
       |---s-->|---si...
               |
               |---i...
[etc. . . .]
[lecturer: demonstrate uses; class: take notes!]

Uses of Suffix Tree

String Searching:   Suffix Tree:   Summary

© L.Allison, Friday, 29-Mar-2024 07:30:32 AEDT users.monash.edu.au/~lloyd/tilde/CSC2/CSE2304/Notes/19suffix.shtml
Computer Science, Software Engineering, Science (Computer Science).