A multidimensional analog to the Burrows-Wheeler transform
Abhinav Nellore, Austin Nguyen, Reid F. Thompson · arXiv (Cornell University) · 2019
We show how to perform multidimensional pattern matching over an $n$-dimensional grid of text spanning a total of $s$ characters with nength, an analog to the Burrows-Wheeler transform. Nength exploits a Fourier duality between two kinds of grid products to map a search problem that naively takes $\mathcal{O}(s^2)$ arithmetic operations to an equivalent problem that takes $\mathcal{O}(s \log s)$ arithmetic operations.