Examples

This page shows a variety of small examples which show how to use libsdsl in your code and how to compile a program using libsdsl.

Example 1: Uncompressed bitvectors

The following example shows how to create and modify an uncompressed bitvector.

#include <stdlib.h>
#include <sdsl/int_vector.hpp>
#include <sdsl/util.hpp>

using namespace sdsl;

int main(int argc,char** argv)
{
	bit_vector::size_type n = 12345678;
	bit_vector bv(n); // create bit vector of size n
	// set random bits 
	for(bit_vector::size_type i=0;i<n;i++) {
		if(rand() % 5 == 0) bv[i] = 1;
	}
	// count the number of bits set
	size_t count = 0;
	for(bit_vector::size_type i=0;i<n;i++) {
		if( bv[i] == 1) count++;
	}
	std::cout << "bv contains " << count << " one bits." << std::endl;
	std::cout << "bv uses " << util::get_size_in_mega_bytes(bv) << " MB space." << std::endl;

	return EXIT_SUCCESS;
}

You can compile the program using the following command:

	g++ -O3 -funroll-loops -I${HOME}/include -L${HOME}/lib bitvec.cpp -o bitvec -lsdsl

Example 2: Serializing and Loading compressed bitvector

The following example demonstrates how to create, serialize and load a compressed bitvector.

#include <stdlib.h>
#include <sdsl/rrr_vector.hpp>
#include <sdsl/util.hpp>

using namespace sdsl;

int main(int argc,char** argv)
{
	// create an uncompressed bitvector first
	bit_vector::size_type n = 12345678;
	bit_vector::size_type max_num_ones = n*0.005; 
	bit_vector bv(n);
	// set random bits 
	for(bit_vector::size_type i=0;i<max_num_ones;i++) {
		bv[rand()%n] = 1;
	}
	// construct compressed representation 
	rrr_vector<> cbv(bv);
	// store compressed bv to file
	util::store_to_file(cbv,"cbv.out");

	// load cbv from file 
	rrr_vector<> cbv_load;
	util::load_from_file(cbv_load,"cbv.out");

	// check if they are the same
	for(bit_vector::size_type i=0;i<bv.size();i++) {
		if(bv[i] != cbv[i] || bv[i] != cbv_load[i]) std::cout << "ERROR!" << std::endl;
	}

	std::cout << "bv uses " << util::get_size_in_mega_bytes(bv) << " MB space." << std::endl;
	std::cout << "cbv uses " << util::get_size_in_mega_bytes(cbv) << " MB space." << std::endl;

	return EXIT_SUCCESS;
}

You can compile the program using the following command:

	g++ -O3 -funroll-loops -I${HOME}/include -L${HOME}/lib bitvec.cpp -o bitvec -lsdsl

Example 3: Creating a compressed suffix array over a text

The following example demonstrates how to create, serialize and load a compressed suffix array (csa).

#include <sdsl/int_vector.hpp>
#include <sdsl/suffixarrays.hpp>
#include <sdsl/algorithms_for_string_matching.hpp>
#include <sdsl/util.hpp>

using namespace sdsl;

int main(int argc,char** argv)
{
	// load text from disk
	const char* text_file = "/usr/share/dict/words";

	// create csa 
	csa_wt<> csa;
	if(! construct_csa(text_file,csa) ) std::cout << "ERROR!" << std::endl;

	// store csa on disk
	util::store_to_file(csa,"words_csa.out");

	// load csa from disk
	csa_wt<> csa_load;
	util::load_from_file(csa_load,"words_csa.out");

	// perform pattern matching
	csa_wt<>::size_type c;
	c = algorithm::count(csa_load,(const unsigned char*)"house",5);
	std::cout << "pattern 'house' occurs " << c << " times." << std::endl;

	int_vector<> occs;
	algorithm::locate(csa_load,(const unsigned char*)"house",5,occs);
	std::cout << "pattern 'house' occurs " << occs.size() << " times at positions ";
	for(int_vector<>::size_type i=0;i<occs.size();i++) {
		std::cout << occs[i] << ",";
	}
	std::cout << std::endl;

	std::cout << "csa uses " << util::get_size_in_mega_bytes(csa_load) << " MB space." << std::endl;

	return EXIT_SUCCESS;
}

You can compile the program using the following command:

	g++ -O3 -funroll-loops -DNDEBUG -I${HOME}/include -L${HOME}/lib csa.cpp -o csa -lsdsl -ldivsufsort -ldivsufsort64

Note:

make sure that {HOME}/lib is in your LD_LIBRARY_PATH

For more complex examples see the Tutorials section of the wiki.