Suffix Array


In computer science, a suffix array is a sorted array of all suffixes of a string. It is a simple, yet powerful data structure which is used, among others, in full text indices, data compression algorithms and within the field of bioinformatics.

Suffix arrays were introduced by Manber & Myers (1990) as a simple, space efficient alternative to suffix trees. They have independently been discovered by Gonnet, Baeza-Yates & Snider (1992) under the name PAT array.

Read more about Suffix Array:  Definition, Example, Correspondence To Suffix Trees, Space Efficiency, Construction Algorithms, Applications

Other articles related to "suffix array, suffix":

Suffix Array - Applications
... The suffix array of a string can be used as an index to quickly locate every occurrence of a substring pattern within the string ... of the pattern is equivalent to finding every suffix that begins with the substring ... ordering, these suffixes will be grouped together in the suffix array and can be found efficiently with two binary searches ...

Famous quotes containing the word array:

    Any one who knows what the worth of family affection is among the lower classes, and who has seen the array of little portraits stuck over a labourer’s fireplace ... will perhaps feel with me that in counteracting the tendencies, social and industrial, which every day are sapping the healthier family affections, the sixpenny photograph is doing more for the poor than all the philanthropists in the world.
    Macmillan’s Magazine (London, September 1871)