Fundamentals of Stringology IV: The Burrows-Wheeler Transform

on YouTube ↗01h 07m

" summary

Defines the LCP array (longest common prefix) and gives a linear-time two-finger skip trick to compute each H[k] by skipping H[k]−1 characters when possible, so LCP builds in O(n) without a suffix tree. Defines the Burrows–Wheeler transform as the last column of the matrix of sorted rotations, shows equivalence with suffix arrays, describes invertibility via LF pointers, and explains practical benefits: strong run‑length grouping, much smaller on small alphabets (2 bits per base) and searchable in compressed form (FM‑index/BW back‑search).

AI-written summary · about

" chapters (4)

1. 0:00Intro
2. 0:30The LCP array
3. 23:50Introduction
4. 46:15Example

" related talks

• 24mString Comparison in Real LifeNaomi Kriger · Conf42 Python 2021
• 26mA Fast Algorithm for Computing the Maximum Weight Base in a Linear MatroidHuy Nguyen · Randomized Numerical Linear Algebra and Applications 2018
• 44mScalable Algorithmic Primitives for Data ScienceRichard Peng · Randomized Numerical Linear Algebra and Applications 2018
• 32mAdventures with Randomized Algebra for Extreme-Scale Signal ProcessingAnshumali Shrivastava · Randomized Numerical Linear Algebra and Applications 2018
• 30mMatrix-free Construction of HSS Representations Using Adaptive Randomized SamplingXiaoye S. Li · Randomized Numerical Linear Algebra and Applications 2018
• 43mTopological data analysis: How to quantify "holes" in your data and why?Ondrej Draganov · PyCon DE & PyData 2025
• 07mTamara Kolda, Distinguished Member of Technical Staff, Sandia National Laboratories @ MLconf SF PartTamara Kolda · MLconf SF 2014
• 24mHighlights from Current Programs part 2:Siddhartha Banerjee, Avishay Tal, Christian Borgs · Eighth Annual Industry Day