Suffix Tree - History

History

The concept was first introduced as a position tree by Weiner (1973), which Donald Knuth subsequently characterized as "Algorithm of the Year 1973". The construction was greatly simplified by McCreight (1976), and also by Ukkonen (1995). Ukkonen provided the first online-construction of suffix trees, now known as Ukkonen's algorithm, with running time that matched the then fastest algorithms. These algorithms are all linear-time for a constant-size alphabet, and have worst-case running time of in general.

Farach (1997) gave the first suffix tree construction algorithm that is optimal for all alphabets. In particular, this is the first linear-time algorithm for strings drawn from an alphabet of integers in a polynomial range. Farach's algorithm has become the basis for new algorithms for constructing both suffix trees and suffix arrays, for example, in external memory, compressed, succinct, etc.

Read more about this topic:  Suffix Tree

Famous quotes containing the word history:

    “The best history is but like the art of Rembrandt; it casts a vivid light on certain selected causes, on those which were best and greatest; it leaves all the rest in shadow and unseen.”
    —Walter Bagehot (1826–1877)

    “No one is ahead of his time, it is only that the particular variety of creating his time is the one that his contemporaries who are also creating their own time refuse to accept.... For a very long time everybody refuses and then almost without a pause almost everybody accepts. In the history of the refused in the arts and literature the rapidity of the change is always startling.”
    —Gertrude Stein (1874–1946)

    “No matter how vital experience might be while you lived it, no sooner was it ended and dead than it became as lifeless as the piles of dry dust in a school history book.”
    —Ellen Glasgow (1874–1945)