COLLECTED BY
Organization:
Internet Archive
These crawls are part of an effort to archive pages as they are created and archive the pages that they refer to. That way, as the pages that are referenced are changed or taken from the web, a link to the version that was live when the page was written will be preserved.
Then the Internet Archive hopes that references to these archived pages will be put in place of a link that would be otherwise be broken, or a companion link to allow people to see what was originally intended by a page's authors.
The goal is to
fix all broken links on the web.
Crawls of supported "No More 404" sites.
This is a collection of web page captures from links added to, or changed on, Wikipedia pages. The idea is to bring a reliability to Wikipedia outlinks so that if the pages referenced by Wikipedia articles are changed, or go away, a reader can permanently find what was originally referred to.
This is part of the Internet Archive's attempt to
rid the web of broken links.
The Wayback Machine - https://web.archive.org/web/20161104005610/https://xlinux.nist.gov/dads/HTML/suffixtree.html
suffix tree
(data structure)
Definition:
A compact representation of a trie corresponding to the suffixes of a given string where all nodes with one child are merged with their parents.
Generalization (I am a kind of ...)
Patricia tree, trie.
Specialization (... is a kind of me.)
multi suffix tree.
See also
suffix array, directed acyclic word graph.
Note:
A suffix tree is a Patricia tree corresponding to the suffixes of a given string. A directed acyclic word graph (DAWG) is a more compact form.
The newer suffix array has replaced the suffix tree as the data structure of choice in many applications.
Author: SE
Implementation
Strmat - a variety of string matching and pattern discovery algorithms (C). Christian Kreibich's libstree (C) including depth- and breadth-first traversal, string update, and examples like LCS. Mark Nelson's great Fast String Searching With Suffix Trees (C++) explains Ukkonen's linear-time algorithm. Dr. Dobb's Journal, August, 1996. (C++ and Pascal).
More information
Edward M. McCreight, A space-economical suffix tree construction algorithm, Journal of the ACM, 23:262-272, 1976.
Esko Ukkonen, On-line construction of suffix trees, Algorithmica, 14(3):249-260, September 1995.
A linear time, forward construction algorithm. See Wikipedia entry for links to PDF of Ukkonen's paper.
Go to the
Dictionary of Algorithms and Data
Structures home page.
If you have suggestions, corrections, or comments, please get in touch
with Paul Black.
Entry modified 2 September 2014.
HTML page formatted Mon Oct 3 15:05:18 2016.
Cite this as:
Stefan Edelkamp, "suffix tree", in
Dictionary of Algorithms and Data Structures [online], Vreda Pieterse and Paul E. Black, eds. 2 September 2014. (accessed TODAY)
Available from: https://www.nist.gov/dads/HTML/suffixtree.html
