uu.seUppsala universitets publikationer
Ändra sökning
RefereraExporteraLänk till posten
Permanent länk

Direktlänk
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association
  • vancouver
  • Annat format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annat språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf
Suffix trees on words
Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi. Teknisk-naturvetenskapliga fakulteten, Biologiska sektionen, Institutionen för ekologi och evolution, Datalogi.
1999 (Engelska)Ingår i: Algorithmica, Vol. 23Artikel i tidskrift (Refereegranskat) Published
Abstract [en]

We discuss an intrinsic generalization of the suffix tree, designed to index a string of length n which has a natural partitioning into m multi-character substrings or words. This word suffix tree represents only the m suffixes that start at word boundaries. These boundaries are determined by delimiters, whose definition depends on the application.

Since traditional suffix tree construction algorithms rely heavily on the fact that all suffixes are inserted, construction of a word suffix tree is nontrivial, in particular when only O(m) construction space is allowed. We solve this problem, presenting an algorithm with O(n) expected running time. In general, construction cost is Omega(n) due to the need of scanning the entire input. In applications that require strict node ordering, an additional cost of sorting O(m') characters arises, where m' is the number of distinct words. In either case, this is a significant improvement over previously known solutions.

Furthermore, when the alphabet is small, we may assume that the $n$ characters in the input string occupy o(n) machine words. We illustrate that this can allow a word suffix tree to be built in sublinear time.

Ort, förlag, år, upplaga, sidor
1999. Vol. 23
Nyckelord [en]
suffix trees, algorithms. data structures
Identifikatorer
URN: urn:nbn:se:uu:diva-25787OAI: oai:DiVA.org:uu-25787DiVA, id: diva2:53561
Tillgänglig från: 2007-02-13 Skapad: 2007-02-13 Senast uppdaterad: 2011-01-14

Open Access i DiVA

Fulltext saknas i DiVA

Personposter BETA

Andersson, Arne

Sök vidare i DiVA

Av författaren/redaktören
Andersson, Arne
Av organisationen
Institutionen för informationsteknologiDatalogi

Sök vidare utanför DiVA

GoogleGoogle Scholar

urn-nbn

Altmetricpoäng

urn-nbn
Totalt: 1080 träffar
RefereraExporteraLänk till posten
Permanent länk

Direktlänk
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association
  • vancouver
  • Annat format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annat språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf