Compact Data Structures
A Practical Approach
Compact data structures help represent data in reduced space while allowingquerying, navigating, and operating it in compressed form. They are essential toolsfor efficiently handling massive amounts of data by exploiting the memory hierarchy.They also reduce the resources needed in distributed deployments and make betteruse of the limited memory in low-end devices.
The field has developed rapidly, reaching a level of maturity that allowspractitioners and researchers in application areas to benefit from the use of compactdata structures. This first comprehensive book on the topic focuses on the structuresthat are most relevant for practical use. Readers will learn how the structures work,how to choose the right ones for their application scenario, and how to implementthem. Researchers and students in the area will find in the book a definitive guideto the state of the art in compact data structures.
Gonzalo Navarro is Professor of Computer Science at the University of Chile. He hasworked for 20 years on the relation between compression and data structures. Hehas directed or participated in numerous large projects on web research, informationretrieval, compressed data structures, and bioinformatics. He is the Editor in Chiefof the ACM Journal of Experimental Algorithmics and also a member of theeditorial board of the journals Information Retrieval and Information Systems .His publications include the book Flexible Pattern Matching in Strings (with M.Raffinot), 20 book chapters, more than 100 journal papers and 200 conferencepapers; he has also chaired eight international conferences.
Compact Data Structures
A Practical Approach
Gonzalo NavarroDepartment of Computer Science, University of Chile
OneLibertyPlaza,20thFloor,NewYork,NY10006,USA
CambridgeUniversityPressispartoftheUniversityofCambridge.
ItfurtherstheUniversitysmissionbydisseminatingknowledgeinthepursuitofeducation,learning,andresearchatthehighestinternationallevelsofexcellence.
www.cambridge.org
Informationonthistitle:www.cambridge.org/9781107152380
GonzaloNavarro2016
Thispublicationisincopyright.Subjecttostatutoryexceptionandtotheprovisionsofrelevantcollectivelicensingagreements,noreproductionofanypartmaytakeplacewithoutthewrittenpermissionofCambridgeUniversityPress.
Firstpublished2016
PrintedintheUnitedStatesofAmericabySheridanBooks,Inc.
AcataloguerecordforthispublicationisavailablefromtheBritishLibrary.
LibraryofCongressCataloging-in-PublicationData
Names:Navarro,Gonzalo,1969author.
Title:Compactdatastructures:apracticalapproach/GonzaloNavarro,
UniversidaddeChile.
Description:NewYork,NY:UniversityofCambridge,[2016]|Includes
bibliographicalreferencesandindex.
Identifiers:LCCN2016023641|ISBN9781107152380(hardback:alk.paper)
Subjects:LCSH:Datastructures(Computerscience)|Computeralgorithms.
Classification:LCCQA76.9.D35N382016|DDC005.7/3dc23
LCrecordavailableathttps://lccn.loc.gov/2016023641
ISBN 978-1-107-15238-0Hardback
CambridgeUniversityPresshasnoresponsibilityforthepersistenceoraccuracyofURLsforexternalorthird-partyInternetWebsitesreferredtointhispublicationanddoesnotguaranteethatanycontentonsuchWebsitesis,orwillremain,accurateorappropriate.
AAyln,FacundoyMartina,queanmecreen.
ABetina,queanmesoporta.
Amipadre,amihermana,yalamemoriademimadre.
Contents
1.1
1.2
1.3
1.4
1.5
1.6
2.1
2.2
2.3
2.3.1
2.3.2
2.4
2.5
2.6
2.6.1
2.6.2
2.6.3
2.6.4
2.7
2.8
2.9
2.10
2.11
3.1
3.2
3.2.1
3.2.2
3.3
3.4
3.4.1
3.4.2
3.4.3
3.4.4
3.4.5
3.5
3.6
4.1
4.1.1
4.1.2
4.2
4.2.1
4.2.2
4.2.3
4.3
4.3.1
4.3.2
4.3.3
4.4
4.4.1
4.4.2
4.4.3
4.5
4.5.1
4.5.2
4.5.3
4.6
4.7
5.1
5.2
5.3
5.4
5.4.1
5.4.2
5.5
5.6
6.1
6.1.1
6.1.2
6.1.3
6.1.4
6.2
6.2.1
6.2.2
6.2.3
6.2.4
6.2.5
6.3
6.4
6.4.1
6.4.2
6.4.3
6.4.4
6.4.5
6.5
6.6
7.1
7.1.1
7.1.2
7.1.3
7.1.4
7.2
7.2.1
7.2.2
7.2.3
7.2.4
7.3
7.3.1
7.4
7.4.1
7.4.2
7.5
7.6
8.1
8.1.1
8.2
8.2.1
8.3
8.3.1
8.4
8.5
8.5.1
8.5.2
8.5.3
8.5.4
8.5.5
8.5.6
8.5.7
8.6
8.7
9.1
9.1.1
9.1.2
9.1.3
9.1.4
9.1.5
9.2
9.2.1
9.2.2
9.2.3
9.2.4
9.3
9.3.1
9.3.2
9.3.3
9.4
9.4.1
9.4.2
9.4.3
9.5
9.5.1
9.5.2
9.5.3
9.5.4
9.6
9.7
10.1
10.1.1
10.1.2
10.1.3
10.2
10.2.1
10.3
10.3.1
10.3.2
10.4
10.5
10.5.1
10.5.2
10.5.3
10.5.4
10.5.5
10.5.6
10.6
10.7
11.1
11.1.1
11.1.2
11.1.3
11.1.4
11.2
11.3
11.3.1
11.3.2
11.3.3
11.3.4
11.4
11.4.1
11.4.2
11.4.3
11.5
11.5.1
11.5.2
11.5.3
11.5.4
11.6
11.6.1
11.6.2
11.6.3
11.6.4
11.7
11.8
12.1
12.1.1
12.1.2
12.1.3
12.2
12.3
12.4
12.4.1
12.4.2
12.4.3
12.4.4
12.4.5
12.5
12.5.1
12.5.2
12.6
12.6.1
12.6.2
12.6.3
12.6.4
12.7
12.8
12.9
13.1
13.1.1
13.1.2
13.1.3
13.1.4
13.2
13.2.1
13.2.2
13.2.3
13.2.4
13.3
13.3.1
13.3.2
13.3.3
13.3.4
13.3.5
List of Algorithms
Foreword
This is a delightful book on data structures that are both time and spaceefficient. Space as well as time efficiency is crucial in modern informationsystems. Even if we have extra space somewhere, it is unlikely to be close to theprocessors. The space used by most such systems is overwhelmingly for structuralindexing, such as B-trees, hash tables, and various cross-references, rather thanfor raw data. Indeed data, such as text, take far too much space in raw formand must be compressed. A system that keeps both data and indices in acompact form has a major advantage.