Succinct Data structures and Algorithms for Practicing Engineers

Most Datastructure and Algorithm books either focus on helping engineers pass coding interviews at FAANG, or they are too complex and advanced, focusing on Computer Scientists in Academia. As a result of this focus, they spend more time teaching engineers how to implement datastructures, instead of teaching why the datastructure is useful, and how it should be used, and when it should be used.

This is important because, in the real world, developers almost never have to implement any new datastructures, since there would usually be libraries in their host languages that implement these datastructures. Developers need to have a toolbox of powerful datastructures and algorithms that they will actually use in problem solving.

This book is a short practical introduction to the beautiful world of Succint datastructures. 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.

In simple terms, you can build datastructures that can encode huge amounts of data into a tiny fraction of the data size, while still allowing you to perform queries and calculations on them.

For example, they allow a data representation which would otherwise need to be written to disk to instead be fit into main memory which improves access time.

There exist a range of real-world applications that can utilize this space-efficient storage method, most centered around information retrieval:

Search Engines - Search engines can index billions of web pages and respond to queries about those pages in real-time. Therefore, it is crucial to decrease the space used by their index while still allowing efficient queries.

Mobile applications - Mobile applications have a limited amount of storage available on the device and efficient storage allows for added functionality.

DNA representation - Medical databases are massive and contain sequences that contain patterns and need to be queried quickly. One can successfully represent DNA in a succinct manner.

Streaming environments - In a streaming environment, the next frame(s) need to be accessed quickly and efficiently. The smaller the size of the content, the faster it can be processed, and at a smaller cost.

This book will skip the maths and focus on giving you a practical intuition about Succint Data Structures, when you should use them, how you should use them, and the class of problems they solve, You won't learn how to implement these datastructures, but you will understand what they do, and when to use them. Code examples in Golang by default.

Content chapters:

• 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