This tutorial will present a practical introduction to the most important succinct data structures, tools, and applications with the intent of providing the researchers with a jump-start into this domain. The focus of this tutorial will be efficient text processing utilising space efficient representations of suffix arrays, suffix trees and searchable integer compression schemes with specific applications of succinct data structures to common NLP tasks such as n-gram language modelling.
It will be held on Monday 9am-12pm, the 12th of December 2016, in Osaka, Japan in conjunction with COLING 2016.
The practical, “hands-on” parts of this tutorial will be based on the popular Succinct Data Structure Library (SDSL). The library contains highly optimised implementations of most practical succinct structures. You can install the library on Mac and Linux operating systems using the following commands:
The library requires the following software packages:
After installing the library you can test if your setup works correctly buy compiling on of the sample programs included in the library:
The three tutorial is organised as follows:
In the first session we motivate the need for succinct structures. We discuss existing applications and examples in IR and NLP, and benefits of succinct structures when facing terabyte scale text processing problems.
In the second session we give a brief introduction into the theoretical foundation of succinct data structures. We discuss the concept of bitvectors, data compression and basic RANK and SELECT on bitvectors which are at the core of most succinct data structures. Next we introduce several simple succinct structures such as a succinct tree representation (LOUDS) and variable size, constant access time, integer representations (DAC).
In the next session we start the tutorial by briefly revisiting several classical search indexes such as Suffix Arrays and Suffix Trees which can provide search functionality used in many NLP applications. We then introduce the notation of a Compressed Suffix Array (CSA), which substantially reduces the space requirement of a Suffix Array while providing the same functionality.
This session covers the underlying technical principals of compressed suffix arrays. This includes concepts such as the Burrows-Wheeler Transform, backward search and wavelet trees. We further extend the concept of compressed suffix arrays to compressed suffix trees (CST). This includes additional structures to represent the shape of the tree as well as additional operations supported by the CST which are important for several NLP applications.
This session will cover our line of research on unlimited order language modelling with modified Kneser-Ney smoothing. Efficient methods for storing and querying language models are critical for scaling to large corpora and high Markov orders. At its core, our approach uses a compressed suffix tree of text which provides near optimal compression while supporting efficient search. We present algorithms for on-the-fly computation of probabilities under a Kneser-Ney and Modified Kneser-Ney language models. Our approach is exact and on par with leading language modelling toolkits in terms of speed while being several order of magnitudes smaller.
The last session briefly touch on advanced succinct structures consisting of Range Minimum / Maximum Queries, Succinct Tries, Treaps and 2D-range query structures.
Gonzalo Navarro. Compact Data Structures – A practical approach. Cambridge University Press, 570 pages, 2016 (website)
Giuseppe Ottaviano. Succinct – Alternative Succinct Data structure library (website)
Ehsan Shareghi, Matthias Petri, Gholamreza Haffari and Trevor Cohn – Fast, Small and Exact: Infinite-order Language Modelling with Compressed Suffix Trees TACL 2016 - Code: repo
Ehsan Shareghi, Matthias Petri, Gholamreza Haffari and Trevor Cohn – Compact, Efficient and Unlimited Capacity: Language Modeling with Compressed Suffix Trees EMNLP 2015