https://github.com/simongog/sdsl-lite Skip to content Sign up * Product + Features + Mobile + Actions + Codespaces + Copilot + Packages + Security + Code review + Issues + Discussions + Integrations + GitHub Sponsors + Customer stories * Team * Enterprise * Explore + Explore GitHub + Learn and contribute + Topics + Collections + Trending + Skills + GitHub Sponsors + Open source guides + Connect with others + The ReadME Project + Events + Community forum + GitHub Education + GitHub Stars program * Marketplace * Pricing + Plans + Compare plans + Contact Sales + Education [ ] * # In this repository All GitHub | Jump to | * No suggested jump to results * # In this repository All GitHub | Jump to | * # In this user All GitHub | Jump to | * # In this repository All GitHub | Jump to | Sign in Sign up {{ message }} simongog / sdsl-lite Public * Notifications * Fork 324 * Star 2k Succinct Data Structure Library 2.0 License View license 2k stars 324 forks Star Notifications * Code * Issues 59 * Pull requests 24 * Actions * Projects 0 * Wiki * Security * Insights More * Code * Issues * Pull requests * Actions * Projects * Wiki * Security * Insights simongog/sdsl-lite This commit does not belong to any branch on this repository, and may belong to a fork outside of the repository. master Switch branches/tags [ ] Branches Tags Could not load branches Nothing to show {{ refName }} default View all branches Could not load tags Nothing to show {{ refName }} default View all tags 61 branches 9 tags Code * Clone HTTPS GitHub CLI [https://github.com/s] Use Git or checkout with SVN using the web URL. [gh repo clone simong] Work fast with our official CLI. Learn more. * Open with GitHub Desktop * Download ZIP Launching GitHub Desktop If nothing happens, download GitHub Desktop and try again. Launching GitHub Desktop If nothing happens, download GitHub Desktop and try again. Launching Xcode If nothing happens, download Xcode and try again. Launching Visual Studio Code Your codespace will open once ready. There was a problem preparing your codespace, please try again. Latest commit @simongog simongog Merge pull request #414 from chrisbarber/master ... c32874c Dec 11, 2019 Merge pull request #414 from chrisbarber/master delete double semi-colon c32874c Git stats * 1,969 commits Files Permalink Failed to load latest commit information. Type Name Latest commit message Commit time CMakeModules allow portable build Dec 11, 2017 benchmark Fixed some typos Feb 26, 2017 build fix build for bash 4.3 Mar 19, 2014 examples Fixed a few missing std:: in examples/storage-visualization.cpp. Nov 18, 2016 external update googletest submodule url Jun 21, 2017 extras Fix issue #370 May 15, 2017 include delete double semi-colon Mar 26, 2019 lib const correctness Aug 15, 2017 test added range query support to k2 tree Oct 2, 2017 tutorial add LDFLAGS to tutorial makefile Mar 7, 2016 .gitignore Restructured tests Apr 9, 2013 .gitmodules update googletest submodule url Jun 21, 2017 .travis.yml Do not install cmake in new travis config Sep 26, 2016 CMakeLists.txt allow portable build Dec 11, 2017 COPYING Added link to arxiv version. Mar 29, 2014 Make.helper.cmake Included code coverage options and adjusted cheatsheet. Sep 17, 2013 README.md Update README.md May 11, 2018 VERSION Update VERSION Jul 4, 2016 install.bat Add install script for windows Sep 24, 2015 install.sh Default to a verbose install Dec 9, 2019 sdsl-lite.pc.cmake Correct paths in pkg-config template Nov 8, 2016 uninstall.sh only attempt make uninstall-sdsl if makefile exists Dec 3, 2015 View code [ ] SDSL - Succinct Data Structure Library What is it? Why SDSL? Documentation Requirements Installation Getting Started Test Benchmarks Bug Reporting The Latest Version Licensing External Resources used in SDSL Authors Contribute README.md SDSL - Succinct Data Structure Library Build Status What is it? The Succinct Data Structure Library (SDSL) is a powerful and flexible C++11 library implementing succinct data structures. In total, the library contains the highlights of 40 research publications. Succinct data structures can represent an object (such as a bitvector or a tree) in space close to the information-theoretic lower bound of the object while supporting operations of the original object efficiently. The theoretical time complexity of an operation performed on the classical data structure and the equivalent succinct data structure are (most of the time) identical. Why SDSL? Succinct data structures have very attractive theoretical properties. However, in practice implementing succinct data structures is non-trivial as they are often composed of complex operations on bitvectors. The SDSL Library provides high quality, open source implementations of many succinct data structures proposed in literature. Specifically, the aim of the library is to provide basic and complex succinct data structure which are * Easy and intuitive to use (like the STL, which provides classical data structures), * Faithful to the original theoretical results, * Capable of handling large inputs (yes, we support 64-bit), * Provide efficient construction of all implemented succinct data structures, while at the same time enable good run-time performance. [space-vis] In addition we provide additional functionality which can help you use succinct data structure to their full potential. * Each data structure can easily be serialized and loaded to/from disk. * We provide functionality which helps you analyze the storage requirements of any SDSL based data structure (see right) * We support features such as hugepages and tracking the memory usage of each SDSL data structure. * Complex structures can be configured by template parameters and therefore easily be composed. There exists one simple method which constructs all complex structures. * We maintain an extensive collection of examples which help you use the different features provided by the library. * All data structures are tested for correctness using a unit-testing framework. * We provide a large collection of supporting documentation consisting of examples, cheat sheet, tutorial slides and walk-through. The library contains many succinct data structures from the following categories: * Bitvectors supporting Rank and Select * Integer Vectors * Wavelet Trees * Compressed Suffix Arrays (CSA) * Balanced Parentheses Representations * Longest Common Prefix (LCP) Arrays * Compressed Suffix Trees (CST) * Range Minimum/Maximum Query (RMQ) Structures For a complete overview including theoretical bounds see the cheat sheet or the wiki. Documentation We provide an extensive set of documentation describing all data structures and features provided by the library. Specifically we provide * A cheat sheet which succinctly describes the usage of the library. * An doxygen generated API reference which lists all types and functions of the library. * A set of example programs demonstrating how different features of the library are used. * A tutorial presentation with the example code using in the sides demonstrating all features of the library in a step-by-step walk-through. * Unit Tests which contain small code snippets used to test each library feature. Requirements The SDSL library requires: * A modern, C++11 ready compiler such as g++ version 4.9 or higher or clang version 3.2 or higher. * The cmake build system. * A 64-bit operating system. Either Mac OS X or Linux are currently supported. * For increased performance the processor of the system should support fast bit operations available in SSE4.2 Installation To download and install the library use the following commands. git clone https://github.com/simongog/sdsl-lite.git cd sdsl-lite ./install.sh This installs the sdsl library into the include and lib directories in your home directory. A different location prefix can be specified as a parameter of the install.sh script: ./install.sh /usr/local/ To build a portable sdsl library without using SSE4.2 and AVX2 instructions, set BUILD_PORTABLE at build time, e.g. BUILD_PORTABLE=1 ./install.sh or mkdir build && BUILD_PORTABLE=1 cmake ... These instructions are enabled by default if the processor of the build system supports them. To remove the library from your system use the provided uninstall script: ./uninstall.sh There is also a Gentoo Ebuild for SDSL by Mathias Weller. Getting Started To get you started with the library you can start by compiling the following sample program which constructs a compressed suffix array (a FM-Index) over the text mississippi!, counts the number of occurrences of pattern si and stores the data structure, and a space usage visualization to the files fm_index-file.sdsl and fm_index-file.sdsl.html: #include #include using namespace sdsl; int main() { csa_wt<> fm_index; construct_im(fm_index, "mississippi!", 1); std::cout << "'si' occurs " << count(fm_index,"si") << " times.\n"; store_to_file(fm_index,"fm_index-file.sdsl"); std::ofstream out("fm_index-file.sdsl.html"); write_structure(fm_index,out); } To compile the program using g++ run: g++ -std=c++11 -O3 -DNDEBUG -I ~/include -L ~/lib program.cpp -o program -lsdsl -ldivsufsort -ldivsufsort64 Next we suggest you look at the comprehensive tutorial which describes all major features of the library or look at some of the provided examples. Test Implementing succinct data structures can be tricky. To ensure that all data structures behave as expected, we created a large collection of unit tests which can be used to check the correctness of the library on your computer. The test directory contains test code. We use googletest framework and make to run the tests. See the README file in the directory for details. To simply run all unit tests after installing the library type cd sdsl-lite/build make test-sdsl Note: Running the tests requires several sample files to be downloaded from the web and can take up to 2 hours on slow machines. Benchmarks To ensure the library runs efficiently on your system we suggest you run our benchmark suite. The benchmark suite recreates a popular experimental study which you can directly compare to the results of your benchmark run. Bug Reporting While we use an extensive set of unit tests and test coverage tools you might still find bugs in the library. We encourage you to report any problems with the library via the github issue tracking system of the project. The Latest Version The latest version can be found on the SDSL github project page https://github.com/simongog/sdsl-lite . If you are running experiments in an academic settings we suggest you use the most recent released version of the library. This allows others to reproduce your experiments exactly. Licensing The SDSL library is free software provided under the GNU General Public License (GPLv3). For more information see the COPYING file in the library directory. We distribute this library freely to foster the use and development of advanced data structure. If you use the library in an academic setting please cite the following paper: @inproceedings{gbmp2014sea, title = {From Theory to Practice: Plug and Play with Succinct Data Structures}, author = {Gog, Simon and Beller, Timo and Moffat, Alistair and Petri, Matthias}, booktitle = {13th International Symposium on Experimental Algorithms, (SEA 2014)}, year = {2014}, pages = {326-337}, ee = {http://dx.doi.org/10.1007/978-3-319-07959-2_28} } A preliminary version is available here on arxiv. External Resources used in SDSL We have included the code of two excellent suffix array construction algorithms. * Yuta Mori's incredible fast suffix libdivsufsort algorithm for byte-alphabets. * An adapted version of Jesper Larsson's implementation of suffix array sorting on integer-alphabets (description of Larsson and Sadakane). Additionally, we use the googletest framework to provide unit tests. Our visualizations are implemented using the d3js-library. Authors The main contributors to the library are: * Johannes Bader * Timo Beller * Simon Gog (Creator) * Matthias Petri This project is also supported by code contributions from other researchers. E.g. Juha Karkkainen, Dominik Kempa, and Simon Puglisi contributed a compressed bitvector implementation (hyb_vector). This project further profited from excellent input of our students Markus Brenner, Alexander Diehm, Christian Ocker, and Maike Zwerger. Stefan Arnold helped us with tricky template questions. We are also grateful to Diego Caro, Travis Gagie, Kalle Karhu, Bruce Kuo, Jan Kurrus, Shanika Kuruppu, Jouni Siren, and Julio Vizcaino for bug reports. Contribute Are you working on a new or improved implementation of a succinct data structure? We encourage you to contribute your implementation to the SDSL library to make your work accessible to the community within the existing library framework. Feel free to contact any of the authors or create an issue on the issue tracking system. About Succinct Data Structure Library 2.0 Resources Readme License View license Stars 2k stars Watchers 119 watching Forks 324 forks Releases 8 SDSL 2.1.1 Latest Jul 4, 2016 + 7 releases Packages 0 No packages published Contributors 38 * @simongog * @tb38 * @mpetri * @fmontoto * @xosh * @olydis * @niklasb * @ekg * @fermeise * @farruggia * @rkonow + 27 contributors Languages * C++ 90.2% * TeX 2.9% * Makefile 2.5% * R 2.0% * CMake 1.6% * C 0.4% * Other 0.4% Footer (c) 2022 GitHub, Inc. Footer navigation * Terms * Privacy * Security * Status * Docs * Contact GitHub * Pricing * API * Training * Blog * About You can't perform that action at this time. You signed in with another tab or window. Reload to refresh your session. You signed out in another tab or window. Reload to refresh your session.