Suffix Tree Revision

Question 1

Suffix Tree resembles to

Answer 1

Search Tries or Tries

Question 2

Trie

Answer 2

The tree-like data structure which have nodes and edges corresponding to a particular character.

Question 3

Suffix Tree

Answer 3

Also tree like DS which have edge labels as the intervals and not the characters only. Each edge label have arbitrary length string carrying over it.

Question 4

Algorithm proceeds with

Answer 4

Phases or steps which constitute extension among them.

Question 5

Number of phases

Answer 5

O(n) ; n: length of the string. For each character, we have a phase to go through and for each of the phases, we have the extensions corresponding to it.

Question 6

Number of extensions or the individual steps in the phase

Answer 6

The upper bound is O(n) which is the worst case in which we have to go through the steps of O(n) times for completing a single phase.

Question 7

Edge carries

Answer 7

Intervals : [start, end] which shows how much string length we are talking about with a single edge.

Start of the string will say about the starting index of the suffix of the present phase and ending index for the ending index of the present phase.

Question 8

The space complexity of the edge

Answer 8

For each edge two variables have to be maintained and not the overall string at once. Therefore two variable will constitute to O(1) complexity for each of the edge.

Question 9

What about end index ?

Answer 9

Usually for the better implementation we tend to label th end index by some common variable like end for all the leaves due to which it gets automatically consistent with the suffixes of the next phase as well.

ex. [1, #]

Question 10

Tree is correct suffix tree upto in each step

Answer 10

Current character ofcourse

Question 11

Steps in the algorithm

Answer 11

n : length of the string (number of characters)

Question 12

Work at each step

Answer 12

O(1) where n is the length of the string; other than this the updating process of the suffix tree can be accomplished by using the end index updating at the same time.

Question 13

First Extensions

Answer 13

Simple Repetition

Question 14

Active Point

Answer 14

Three tuples: (active_point, active_node, active_length)

Question 15

Remainder

Answer 15

An integer indicating how many new suffices we need to insert.

Question 16

What happens when the suffix do already exist in the suffix tree before hand. Ex. if abc do already have the suffix tree corresponding to them then after the abca .

Answer 16

The suffix tree is not updated, rather the additional variables are updated,

1. Active Point
2. Remainder

So with the upcoming suffix like abca “the last a” will be updating the active point and remainders.

Question 17

Is the tree complete in First extension when the repeating suffix is found?

Answer 17

No, it has not been updated yet since we have updated the active points but not the tree.

Question 18

Do the tree contains the all the suffixes at a point of time?

Answer 18

Yes, either implicitly or explicitly the tree do contain the suffices of the tree at a point of algorithm or phase.

Question 19

What are the ways to update the suffix tree ?

Answer 19

There are two ways to update the suffix tree:

1. Explicit updating
2. Implicit updating

Explicit updating comes from the updation of the tree on its own adding a new edge or updating the end index of the suffixes do chaange the tree explicitly

Implicit updating will update the tree by updating the variables namely : Active point and remainder.

Question 20

Describe remainder variable

Answer 20

Number of suffixes we need to add yet, which aren’t been added into the suffix tree presently.

Example : consider the example abcabx then after reaching x we will be having the abx, bx, and x as our remainder.

Question 21

How the active points are updated ?

Answer 21

They correspond to tuple having :

1. Active node
2. Active Edge
3. Active Length