This HTML5 document contains 25 embedded RDF statements represented using HTML+Microdata notation.

The embedded RDF content will be recognized by any processor of HTML5 Microdata.

Namespace Prefixes

Prefix	IRI
dct	http://purl.org/dc/terms/
yago-res	http://yago-knowledge.org/resource/
dbo	http://dbpedia.org/ontology/
foaf	http://xmlns.com/foaf/0.1/
dbt	http://dbpedia.org/resource/Template:
rdfs	http://www.w3.org/2000/01/rdf-schema#
freebase	http://rdf.freebase.com/ns/
rdf	http://www.w3.org/1999/02/22-rdf-syntax-ns#
owl	http://www.w3.org/2002/07/owl#
n9	http://en.wikipedia.org/wiki/
dbp	http://dbpedia.org/property/
dbc	http://dbpedia.org/resource/Category:
prov	http://www.w3.org/ns/prov#
xsdh	http://www.w3.org/2001/XMLSchema#
dbr	http://dbpedia.org/resource/

Statements

Subject Item

dbr:Suffix_array

rdfs:label

Suffix array

rdfs:comment

In computer science, a suffix array is a sorted array of all suffixes of a string. It is a data structure used in, among others, full text indices, data compression algorithms, and the field of bibliometrics. Suffix arrays were introduced by as a simple, space efficient alternative to suffix trees. They had independently been discovered by Gaston Gonnet in 1987 under the name PAT array.

owl:sameAs

yago-res:Suffix_array freebase:m.04rbjc

dbp:wikiPageUsesTemplate

dbt:Harv dbt:Sfn dbt:Harvtxt dbt:Reflist dbt:Commons_category dbt:Cite_conference dbt:Infobox dbt:Cite_journal dbt:Citation_needed dbt:Aligned_table dbt:Strings

dct:subject

dbc:Substring_indices dbc:Arrays dbc:Computer_science_suffixes dbc:String_data_structures

prov:wasDerivedFrom

n9:Suffix_array?oldid=1071919073&ns=0

dbo:wikiPageID

1303494

dbo:wikiPageLength

29891

dbo:wikiPageRevisionID

1071919073

dbo:abstract

In computer science, a suffix array is a sorted array of all suffixes of a string. It is a data structure used in, among others, full text indices, data compression algorithms, and the field of bibliometrics. Suffix arrays were introduced by as a simple, space efficient alternative to suffix trees. They had independently been discovered by Gaston Gonnet in 1987 under the name PAT array. gave the first in-place time suffix array construction algorithm that is optimal both in time and space, where in-place means that the algorithm only needs additional space beyond the input string and the output suffix array. Enhanced suffix arrays (ESAs) are suffix arrays with additional tables that reproduce the full functionality of suffix trees preserving the same time and memory complexity.The suffix array for a subset of all suffixes of a string is called . Multiple probabilistic algorithms have been developed to minimize the additional memory usage including an optimal time and memory algorithm.

foaf:isPrimaryTopicOf

n9:Suffix_array