A multidimensional analog to the Burrows-Wheeler transform

05/09/2019

∙

by   Abhinav Nellore, et al.

∙

0

∙

share

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 O(s^2) arithmetic operations to an equivalent problem that takes O(s s) arithmetic operations.