|
 www.compression-links.info: Find, download & compress! 
|
| SuffixTrees area, SourceCode content | libstree is a generic suffix tree implementation, written in C. It can handle arbitrary data structures as elements of a string. libstree is using the BSD license. Created: 22/09/2007 |
| SuffixTrees area, Papers content |
Two papers in which it is show how to combine the BWT with the suffix array
data structure, in order to build a sort of compressed suffix array.
In the first paper it is proven that
the space occupancy of the compressed suffix array can be bounded in
terms of the entropy of the input string. In the second paper it is
proposed and tested a practical implementation of this data structure.\
The first paper will appear in the Proc. of 41st IEEE Symposium on Foundations of Computer Science; the second one in the Proc. of the 12th SIAM-ACM Symposium on Discrete Algorithms. Created: 23/09/2000 by Mark Nelson |
| SuffixTrees area, Papers content | By Jesper Larsson, Published in Proceedings of the IEEE Data Compression Conference 1996. Hey Jesper, how about putting a PDF version online? Created: 26/04/2003 by Mark Nelson |
| Tutorials content, SuffixTrees area | A short and sweet tutorial on suffix trees. What they are and how to construct them. Created: 05/12/2000 by Mark Nelson |
| SuffixTrees area, Papers content | "The Context Trees of Block Sorting Compression" - paper By Jesper Larsson. Published in Proceedings of the IEEE Data Compression Conference 1998, PDF version of the paper. Created: 26/04/2003 by Mark Nelson |
| SuffixTrees area, SourceCode content |
A collection of C programs that do string matching and pattern discovery. This appears to be free code by D. Gusfield, who also has a book called "Algorithms on Strings, Trees and Sequences: Computer Science and Computational Biology".
One DCL reader commented The strmat package is wonderful. Created: 23/01/2000 by Mark Nelson |
| SuffixTrees area, SourceCode content | Links to a documented implementation of a suffix sort. This may not be a compression topic per se, but suffix trees are useful for compressing data. Created: 07/11/1999 by Mark Nelson |
| Tutorials content, Huffman area, SuffixTrees area, BWT area, SourceCode content, NonCommercialProgs content |
bwtzip is an ongoing project, distributed under the GNU General Public License, to implement a Burrows-Wheeler compressor in standard, portable C++. It is research-grade in that it is highly modularized and abstracted, so that it is simple to swap out parts of the compressor without affecting anything else. This makes it easy to experiment with different algorithms at different stages of compression.
Looks like Steven T. Lavavej released a new version of bwtzip in early February, 2003. A wide variety of improvements, most of them in implementation - not visible to the end user. A description of recent changes is found here Created: 11/12/2002 by Mark Nelson |
| SuffixTrees area, NonCommercialProgs content | An Open Source Suffx Tree implementation. Looks as though this might be oriented towards teaching applications, as it is an interactive application, not just an implementation of the data structure. Created: 07/09/2003 by Mark Nelson |
| SuffixTrees area, SourceCode content, NonCommercialLibs content | A C implementation of a Suffix Tree. This project also includes a Perl module that can use the C code. Created: 07/09/2003 by Mark Nelson |
| SuffixTrees area, Papers content | By Jesper Larsson. Published in Proceedings of the IEEE Data Compression Conference 1998, a PDF version of the paper. Created: 26/04/2003 by Mark Nelson |
| SuffixTrees area, Papers content | by Jesper Larsson. Technical report. LU-CS-TR:98-204, LUNFD6/(NFCS-3134)/1-6/(1998). A PDF version of the paper. Created: 26/04/2003 by Mark Nelson |
| SuffixTrees area, Papers content | By Jesper Larsson, Arne Andersson and Kurt Swanson. Technical report. LU-CS-TR:95-158, LUNFD6/(NFCS-3107)/1-14/(1995). Early version of a paper published in Proceedings of the 7th Annual Symposium on Combinatorial Pattern Matching 1996; to appear in Algotrithmica Created: 26/04/2003 by Mark Nelson |
| SuffixTrees area, Links content | I am a graduate student (doktorand) in algorithms and data structures at the Department of Computer Science at Lund University. Special interests are text searching and data compression. I use the links on this page to papers, but don't index the page itself Created: 26/04/2003 by Mark Nelson |
| SuffixTrees area, People content, Papers content | Jesper Larsson spent a fair amount of his years in academia studying Suffix Trees. His home page has links to his thesis and a few other papers on suffix trees and other string matching/Data Compression topics. Created: 23/04/2003 by Mark Nelson |
| Tutorials content, SuffixTrees area, Links content | The definition from the NIST Dictionary of Algorithms and Data Structures. Created: 05/04/2003 by Mark Nelson |
| Tutorials content, SuffixTrees area, Links content | The definition from the NIST Dictionary of Algorithms and Data Structures. Created: 05/04/2003 by Mark Nelson |
| SuffixTrees area, Papers content | 1997, Robert Giegerich, Stefan Kurtz. We review the linear time suffix tree constructions by Weiner, McCreight, and Ukkonen. We use the terminology of the most recent algorithm, Ukkonen's online construction, to explain its historic predecessors. The submitter of this paper indicates that it has user-friendly terminology, always welcome in Journal papers. Created: 16/11/2002 by Mark Nelson |
| SuffixTrees area, Papers content | R. Grossi and J. S. Vitter. ``Compressed Suffix Arrays and Suffix Trees, with Applications to Text Indexing and String Matching,'' Proceedings of the 32nd Annual ACM Symposium on Theory of Computing (STOC '00), Portland, OR, May 2000, 397-406. Created: 08/04/2002 by Mark Nelson |
| SuffixTrees area, Courses content, Papers content |
Notes on suffix tree construction, some course notes for COMP 612: Graduate Seminar in Compiler Construction, includes some pointers to important papers.
DataCompression.info user David D. had this complaint: None of the links work on this page, all there is is a short paragraph on suffix trees. I have to agree, it's a rather strange page. Created: 07/11/1999 by Mark Nelson |
| SuffixTrees area, Esoterica area | bsdiff and bspatch are tools for building and applying patches to binary files. By using suffix sorting (specifically, Larsson and Sadakane's qsufsort) and taking advantage of how executable files change, bsdiff routinely produces binary patches 50-80% smaller than those produced by Xdelta, and 15% smaller than those produced by .RTPatch (a $2750/seat commercial patch tool). Created: 01/01/1970 by Mark Nelson |
