Re: Suffix trees versus prefix arrays

<almurph@xxxxxxxxxxxxx> ha scritto nel messaggio
news:12d19b6a-331b-40f2-abad-bbff88309238@xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
Hi everyone

Why do suffix trees/arrays _appear_ to be more commonly used then
prefix trees/arrays? Is it due to some property of language (like
script is read from the left to the right)? Or does it make no
difference at all? Is there some sort of advantage?

I would appreciate any comments that you may have on this.

Thanks,
Al.

From Wikipedia:
A trie, or prefix tree, is an ordered tree data structure that is used to
store an associative array where the keys are usually strings.
A suffix tree (also called suffix trie, PAT tree or, in an earlier form,
position tree) is a data structure that presents the suffixes of a given
string in a way that allows for a particularly fast implementation of many
important string operations, for instance locating a substring in S,
locating a substring if a certain number of mistakes are allowed, locating
matches for a regular expression pattern etc. Suffix trees also provided one
of the first linear-time solutions for the longest common substring problem.
These speedups come at a cost: storing a string's suffix tree typically
requires significantly more space than storing the string itself.


.

Relevant Pages

  • Re: RegExp as Finite State Machine
    ... That's a hard problem in general. ... "s + any suffix" is a regular language because it ... Whether an NFA accepts any string is solvable by a simple algorithm ...
    (comp.lang.javascript)
  • Re: GhostScript - syntax to convert all files in a folder
    ... and then write a script/batch file to run it 5000 times. ... % returns a new string the same length as string with the last ... % suffix-length bytes replaced with suffix. ... dup dup length 3 index length sub 4 -1 roll putinterval ...
    (comp.lang.postscript)
  • Re: Limiting Records with Null Only Once
    ... I used the allow zero length string on field B with the ... combined index on both fields and it worked like a gem. ... >suffix) so they sort correctly (i.e. you don't want to ...
    (microsoft.public.access.queries)
  • Re: [QUIZ] Longest Repeated Substring (#153)
    ... My hack at the substring problem is based on suffix ... in the original string. ... def initialize ...
    (comp.lang.ruby)
  • Re: Converting full Names from 1 cell to 2
    ... separate the 1 column in to 2 columns bases on table below. ... The hard part is determining the Suffix. ... Function ReExtr(str As String, ... Dim re As RegExp ...
    (microsoft.public.excel.misc)