Strings, Compression, and Orchestra
Here is most of the research work I did from 1995 to 1999, as a
postgraduate student and member of the algorithms research group at
the Department of Computer Science
at Lund University. It concerns data structures for
searching sequential data (particularly suffix trees) and reversible compression of
sequential data.
The work is all summed up in the Ph.D. thesis Structures of
String Matching and Data Compression, which contains the most accurate and
comprehensible versions of results contained in the other documents below. The other
documents serve the purpose of showing how results were originally published and giving
credit to the coauthors.
These documents, and the source code, were previously available via
my Lund University homepage. After that page was removed, I was kindly
offered a subdomain larsson.dogma.net by
Mark Nelson in order to keep the files available
online, and linked from his data compression
info site. Some time ago, I noticed that all of that had disappeared, because
Mark retired I suppose. (I know it was still up in March 2019, because that was when I
got an email from Richard M. Stallman himself asking me to update the copyright notice
of the C code to be compatible with GPL3, which I did.) Now, in August 2024, I got the
idea to put this back up under my private domain. I
don't know if it is of any use, most of this should be possible to find elsewhere
anyway, but why not! I just updated some of this information that wasn't true anymore.
From late 1999 to August 2010 I was out of academia, mostly working for a company called
Apptus Technologies (which has now turned into Voyado, and in a way also into Theca
Systems). 2010–2014 I was at the IT University of Copenhagen,
and since August 2014 I'm at Malmö University, teaching
mostly algorithms and database technology, and occasionally working a bit on research,
still in the stringology and data compression field.
Theses/Compilations
- Structures of String Matching and Data
Compression.
Doctoral dissertation, September 1999.
The material and much of the text of this dissertation is
taken primarily from the papers listed below, but with
numerous extensions, updates, and clarifications.
[PDF]
[Compressed PostScript]
[BibTeX entry]
Errata for the above, updated July 2000.
[PDF]
[Compressed PostScript]
- Attack of the Mutant Suffix Trees.
Licentiate thesis, January 1998.
Compilation of the first three papers below, with a short
introduction.
[PDF]
[Compressed PostScript]
[BibTeX entry]
Individual Papers
Significant material of the following papers is compiled, revised and
partly extended in the dissertation Structures of String Matching and Data Compression above.
Source Code
-
qsufsort.c and suftest.c
Suffix sorting implementation to accompany the paperFaster Suffix Sorting. The former file is included as
appendix B of Structures of String Matching and Data Compression.
- slide.c
Implementation of sliding window suffix tree. Given in
appendix A of Structures of String Matching and Data
Compression.