# Text Indexing for Regular Expression Matching
## 3 A Regular Expression Index
### Solution Graphs: Pattern Matching via Reachability  
We take a slightly unorthodox view of regular expressions in this section. This viewpoint will make it easier to precompute solutions to small regular expression queries and then merge them with other solutions to answer the query. Essentially, we will view the solution for a regular expression query with regular expression \(p\) as a directed graph \(G\) where we are mainly concerned with the reachability from vertices in a set \(V_{1}\) to vertices in another set \(V_{2}\). A solution graph for a given text \(T\) and regular expression \(p\) is defined as follows:  
**Definition 1** (Solution Graph). : _For a text \(T\) and regular expression \(p\), a solution graph \(G\) is a directed graph that contains two distinguished sets of vertices \(V_{1}=\{v^{1}_{1},\dots,v^{1}_{|T|+1}\}\) and \(V_{2}=\{v^{2}_{1},\dots,v^{2}_{|T|+1}\}\), called the start and end vertices, respectively. In \(G\) there exists a path from \(v^{1}_{i}\in V_{1}\) to a vertex \(v^{2}_{j+1}\in V_{2}\) if and only if the substring \(T[i,j]\) matches the regular expression \(p\). Correspondingly, we will say that the regular expression given by the empty string matches the substring \(T[i,i-1]\)._  
Solution graphs for a text and pattern are not unique. Moreover, there will typically be many additional vertices lying on the paths between the \(V_{1}\) and \(V_{2}\), but we ultimately only care about the reachability between these two sets. Note also that this representation may require much more information than our final solution, which itself must only provide a list of starting positions and ending positions. We will demonstrate how these graphs can be merged together at every step while only using \(O(|T|)\) time for each vertex of the parse tree. Merging Solution Graphs  
We now describe how solution graphs for subexpressions can be merged based on the operators used. We use this procedure both in the construction and in the query phase. It forms the key component of our technique. Illustrations are provided in Figures 2 and 3. If the regular expression is only a single symbol, the solution graph is easily obtained as a bipartite graph, e.g., the top row of Figure 2.  
First we consider the **or** operator \({}^{\prime}|^{\prime}\). Let \(p_{1}\) be one regular expression with solution graph \(G_{1}\) that has start and end vertex sets \(V_{1}\) and \(V_{2}\). Let \(p_{2}\) be a regular expression with solution graph \(G_{2}\) that has start and end vertex sets \(U_{1}\) and \(U_{2}\). To compute the graph \(G\) corresponding to \(p_{1}|p_{2}\), do the following:  
1. Graph \(G\) is initially equal to the two disconnected graphs \(G_{1}\) and \(G_{2}\). 2. Add two sets of new vertices \(W_{1}=\{w^{1}_{1},\dots,w^{1}_{|T|+1}\}\) and \(W_{2}=\{w^{2}_{1},\dots,w^{2}_{|T|+1}\}\). These will be the new start and end vertex sets, respectively, of \(G\). 3. Add the directed edges: \(\{(w^{1}_{i},v^{1}_{i})\mid 1\leq i\leq|T|+1\}\), \(\{(w^{1}_{i},u^{1}_{i})\mid 1\leq i\leq|T|+1\}\), \(\{(v^{2}_{i},w^{2}_{i})\mid 1\leq i\leq|T|+1\}\), and \(\{(u^{2}_{i},w^{2}_{i})\mid 1\leq i\leq|T|+1\}\). For the **concatenation** operator \({}^{\prime}\circ\)' we again take \(G_{1}\) as the solution graph for pattern \(p_{1}\) with start and end vertex sets \(V_{1}\) and \(V_{2}\), respectively, and \(G_{2}\) as the solution graph for pattern \(p_{2}\) with start and end vertex sets \(U_{1}=\{u^{1}_{1},\dots,u^{1}_{|T|+1}\}\) and \(U_{2}=\{u^{2}_{1},\dots,u^{2}_{|T|+1}\}\). To create the solution graph \(G\) for \(p_{1}\circ p_{2}\), do the following:  
1. Graph \(G\) is initially equal to the two disconnected graphs \(G_{1}\) and \(G_{2}\). 2. Make \(V_{1}\) the start vertex set of \(G\) and \(U_{2}\) the end vertex set of \(G\). 3. Add the directed edges: \(\{(v^{2}_{i},u^{1}_{i})\mid 1\leq i<|T|+1\}\). Figure 2: Solution graphs for the text \(T=aabbab\). (**Top**): solution graphs for regular expressions \(a\) and \(b\). Second from top: solution graphs for the regular expressions \(a^{*}\) and \(b^{*}\).