An invertible transform for efficient string matching in labeled digraphs

Abstract

Let $G=(V,E)$ be a digraph where each vertex is unlabeled, each edge is labeled by a character in some alphabet $\hat{I}\text{c◯}$, and any two edges with both the same head and the same tail have different labels. The powerset construction gives a transform of $G$ into a weakly connected digraph $G^{\prime }=(V^{\prime },E^{\prime })$ that enables solving the decision problem of whether there is a walk in $G$ matching an arbitrarily long query string $q$ in time linear in $|q|$ and independent of $|E|$ and $|V|$. We show $G$ is uniquely determined by $G^{\prime }$ when for every $v_{\ell }\in V$, there is some distinct string $s_{\ell }$ on $\hat{I}\text{c◯}$ such that $v_{\ell }$ is the origin of a closed walk in $G$ matching $s_{\ell }$, and no other walk in $G$ matches $s_{\ell }$ unless it starts and ends at $v_{\ell }$. We then exploit this invertibility condition to strategically alter any $G$ so its transform $G^{\prime }$ enables retrieval of all $t$ terminal vertices of walks in the unaltered $G$ matching $q$ in $O(|q|+t\log |V|)$ time. We conclude by proposing two defining properties of a class of transforms that includes the Burrows-Wheeler transform and the transform presented here.

13 pages, 3 figures; v7 is the content of the camera-ready copy for CPM 2021 incorporating reviewer feedback