Suffix Arrays and Suffix Trees.avi

Suffix Arrays and Suffix Trees used to be different. But nowadays Suffix Arrays are just a way of implementing a Suffix Tree (or vice versa). See: Kim, Kim, and Park. Linearized suffix tree: an efficient index data structure with the capabilities of suffix trees and suffix arrays. Algorithmica, 2007. Most papers on Suffix trees/arrays use the word 'Mississippi' as an example. This video gives some other examples that could be used The trees used here are right branching because it was simpler to draw them that way and efficiency was not the main point.

Category:

Science & Technology

Tags:

• algorithm
• data structure

[lucasfibonacci1]

There's a very good, up to date (2011) lecture video on suffix arrays by Daniel Gusfield at ucdavis. Check it out!

But watch my video too, of course. And see also my video on suffix links. 

[lucasfibonacci1]

I said that suffix arrays coud be used to find gappy phrases. Here are a few examples from the 20 newsgroup corpus:

if you [care|refuse] to accept it

So "care" alternates "refuse" (easy to overlook)

without [any|offering one |the least] shred of (neg polarity item)

are you [|ever so gently|seriously] suggesting that (optional modifiers)

case you [hadn't|haven't] noticed (grammatical variation)

love your [brotherman|neighbor|neighbour­] as yourself (spell, lex choice)

[lucasfibonacci1]

Also, of course, phrase-based Machine Translation. Do you have other applications? If so, write them down here. Suffix arrays are needed also for winning programming contests. I'm afraid that my video is not so helpful, since it just gives a bunch of examples. But what kind of video really would be helpful?

[lucasfibonacci1]

Some nice things to do with suffix arrays. 1. Collect key phrases (like the statistically improbable phrases of Amazon. 2. Collect gappy phrases: from one ___ to the other. 3.. Collect reversible binomials: "towns and cities" "industry and academia" 4. Compare document collections: take a collection of documents concerned with South Dakota, how many of the phrases in this ccollection will be found in document collections for North Dakota or Nebraska? 5. Look for plagerism. 6. wrong terminology

[lucasfibonacci1]

The integer array is the longest common prefix table (lcp table), which is used with suffix arrays. Suppose our text is "Bananaland' 0.06. Looking at the bottom of the tree and read off the suffixes left to right. The 4th suffix is 'ananaland'. The lcp table should store the length of the longest common prefix of this suffix and its predecessor, which is 'analand'. The longest common prefix is 'ana', so the table stores a 3. The -1 at 0 is a sentinel (often useful). Position 1 always stores 0.