Skip to main content
Login | Suomeksi | På svenska | In English

Purely Functional Compressed Bit Vectors with Applications and Implementations

Show full item record

Title: Purely Functional Compressed Bit Vectors with Applications and Implementations
Author(s): Kaasinen, Joel
Contributor: University of Helsinki, Faculty of Science, Department of Computer Science
Language: English
Acceptance year: 2011
Abstract:
The study of compressed data structures strives to represent information on a computer concisely — using as little space as possible. Compressed bit vectors are the simplest compressed data structure. They are used as a basis for more complex data structures with applications in, for example, computational biology. Functional programming is a programming paradigm that represents computation using functions without side-effects (such as mutation). Data structures that are representable in and suitable for functional programming are termed functional data structures. Functional data structures are also persistent: operations on them do not destroy previous versions. This thesis provides implementations of functional compressed bit vectors in the purely functional programming language Haskell. The implemented structures are analyzed and benchmarked against established imperative (C++) implementations. Applications of compressed bit vectors are also surveyed. This includes compressed wavelet trees, an implementation of which is also presented.


Files in this item

Files Size Format View
purelyfu.pdf 765.2Kb PDF

This item appears in the following Collection(s)

Show full item record