Rooted LCP Queries

In this section we show Lemma 2. The idea in answering a rooted LCP query forx on T(C_i) is to find a string z in C_i that x follows longest. We identify the leaf of T(C_i) that corresponds tozand the distanceh=|maxpref(x, z)|. We can then use a weighted ancestor queryWA(z, h)to determine the location wherexdiverges fromz. This location is the answer to the rooted LCP queryLCP(x, i). See Figure 3.2 for an illustration.

We will use the longest prefix string forxinCi,lps_Ci(x), as the stringz. The distance h is then equal to h_Ci(x) = |maxpref(lps_Ci(x), x)|. In order to determine lps_Ci(x) and h_Ci(x), we uselps_C(x)andh_C(x), which are available thanks to the preprocessing ofx.

We findlps_Ci(x)using a number of important lemmas. First, Lemma 7 and Corollary 2 show that we can determine the distance thatxfollows a stringy∈C_i in constant time.

T(Ci)

z= lps_Ci(x) h=hC_i(x)

LCP(x, i)

x ^WA(z, h)

Figure 3.2:Illustrating how a rooted LCP query forxonT(Ci)is answered by a weighted ancestor query on a stringz∈Cithatxfollows longest.

19 Lemma 8 shows that we can identify two candidate strings in C_i in time O(log logn), at least one of which is a valid choice forlps_Ci(x). In Lemma 9, we use Corollary 2 to determine which of the candidate strings thatxfollows longest, thereby obtaining a valid choice forlps_Ci(x)as well ash_Ci(x).

Lemma 7 Given a suffixy∈Coft, the distancehthat a stringx∈Σ^∗ followsycan be determined in constant time as

h=|maxpref(x, y)|= min(|NCA(lps_C(x), y)|, h_C(x)) provided thatlps_C(x)andh_C(x)are available.

Proof By Lemma 5,lps_C(x)is lexicographically closest toxamong all strings inC, so either

1. xlps_C(x)yorylps_C(x)x. In this case, Corollary 1 yields

h=|maxpref(x, y)|= min |maxpref(lps_C(x), y)|,|maxpref(x,lps_C(x))|

.

2. yxlps_C(x)orlps_C(x)xy. In this case, Corollary 1 yields

|maxpref(y,lps_C(x))|= min |maxpref(y, x)|,|maxpref(x,lps_C(x))|

. By definition,|maxpref(x,lps_C(x))| ≥ |maxpref(y, x)|for anyy∈C, so

h=|maxpref(y, x)|=|maxpref(y,lps_C(x))|

= min |maxpref(lps_C(x), y)|,|maxpref(x,lps_C(x))|

.

For both of the above cases we have that

h= min |maxpref(lps_C(x), y)|,|maxpref(x,lps_C(x))|

.

By definition, |maxpref(x,lps_C(x))| =h_C(x), and since maxpref(lps_C(x), y) can be determined in constant time by a nearest common ancestor query on the leaves of T(C)corresponding tolps_C(x)andy, we have that

h= min |NCA(lps_C(x), y)|, h_C(x) . This concludes the proof.

We extend the lemma by showing that the distance thatxfollows a substring oftcan also be determined in constant time.

Corollary 2 Given a suffix y ∈ C of t, the distance h that a string x ∈ Σ^∗ follows pref_i(y), can be determined in constant time as

h=|maxpref(x,pref_i(y))|= min(i,|NCA(lps_C(x), y)|, h_C(x)) provided thatlps_C(x)andhC(x)are available.

20 THE LCP DATA STRUCTURE

Proof The distance that x follows pref_i(y) is at most |pref_i(y)| = i, and since x followsyat least as long asxfollowspref_i(y), the lemma follows from Lemma 7.

Using the predecessor data structure for orderset(Ci), we can in time O(log logn²) = O(log logn)determine the predecessor and successor string fory∈C in the lexicographic ordering ofC_i. We denote these strings asPRED_Ci(y) and SUCC_Ci(y) and the following lemma shows that fory= lps_C(x), at least one of these strings is a valid choice forlps_Ci(x).

Lemma 8 EitherPRED_Ci(lps_C(x))orSUCC_Ci(lps_C(x))is a valid choice forlps_Ci(x).

Proof We letx⁻ = PRED_Ci(lps_C(x))and x⁺ = SUCC_Ci(lps_C(x)). By definition, x⁻ andx⁺are the two strings inCi lexicographically closest tolps_C(x). We consider the following cases for the lexicographic ordering ofx.

1. x⁻ ≺ x ≺ x⁺. In this case x⁻ and x⁺ are also the two strings in C_i lexico-graphically closest to x, and by Lemma 5 one of them is a valid choice for lps_Ci(x).

2. xx⁻. We show thatx⁻is a valid choice forlps_Ci(x). To obtain a contradiction, assume thatx⁻ is not a valid choice forlps_Ci(x). Then there is a valid choice z ∈ C_i different fromx⁻ forlps_Ci(x). It must be the case thatz ≺ x⁻, since otherwisex⁻would be lexicographically closer toxthanz, contradicting thatz is a valid choice forlps_Ci(x). Sincex⁻is not a valid choice forlps_Ci(x), it must hold that either

a) xfollowszlonger thanx⁻, or

b) zis lexicographically closer toxthanx⁻, i.e.,xz≺x⁻.

Letz⁰ ∈Cdenote a suffix ofthavingzas a prefix. In the first case,xfollowsz⁰ longer thanx⁻, and thus also longer thanlps_C(x)because of the lexicographic ordering. In the second casez⁰ is lexicographically closer toxthanlps_C(x)since x z ≺x⁻ lps_C(x). Both cases contradict the definition of lps_C(x). This shows thatx⁻ must be a valid choice forlps_Ci(x).

3. xx⁺. In this casex⁺is a valid choice forlps_Ci(x). The argument is symmetri-cal to the previous.

The following lemma is obtained by combining the previously shown lemmas. The lemma provideslps_Ci(x)andhCi(x)which are needed in order to answer the rooted LCP query with a weighted ancestor query.

Lemma 9 Let C = suff(t) be the set of all suffixes of t. Given lps_C(x) and h_C(x), we can determinelps_Ci(x) andh_Ci(x)in timeO(log logn), provided that a nearest common ancestor data structure has been built for the suffix treeT(C).

21 Proof We first obtain the stringsx⁻=PRED_Ci(lps_C(x))andx⁺=SUCC_Ci(lps_C(x))in timeO(log logn). It follows from Lemma 8 that at least one ofx⁻andx⁺is a valid choice forlps_Ci(x). Lety⁻ andy⁺ denote suffixes inChavingx⁻andx⁺as a prefix, respectively.

From Lemma 7, the distance thatxfollows y⁻ andy⁺ is upper bounded by the distance thatlps_C(x)follows the strings. We can tell which of the stringsxfollows farthest by comparing the length of the maximum common prefix betweenlps_C(x)and y⁻ to that betweenlps_C(x)andy⁺as determined by two nearest common ancestor queries. From the lengths of the maximum common prefixes, we select the correct choice forlps_Ci(x)betweenx⁻andx⁺. Thus,

lps_Ci(x) =

(x⁻ if|NCA(lps_C(x), y⁻)| ≥ |NCA(lps_C(x), y⁺)|

x⁺ if|NCA(lps_C(x), y⁻)|<|NCA(lps_C(x), y⁺)| .

Note that in casey⁻andy⁺has an equally long maximum common prefix withlps_C(x), we selectx⁻. This is because x ≺x⁻ ≺lps_C(x) ≺x⁺ is a possible lexicographical ordering for the strings. This may happen if x⁻ ∈/ C is a prefix of lps_C(x), since a string is lexicographically ordered before any other string of which it is a prefix.

On the contrary,x⁻ ≺lps_C(x) ≺x⁺ ≺x is not a possible lexicographical ordering because there would be a string inChavingx⁺as a prefix, contradicting thatlps_C(x)is lexicographically closest toxinC. Thus,x⁻is always at least as close lexicographically toxasx⁺.

The maximum distance,h_Ci(x), thatxfollows a string inC_i equals the distance thatxfollowslps_Ci(x). Thus,hCi(x)is the maximum distance thatxfollows eitherx⁻ orx⁺since the maximum of these was the correct choice forlps_Ci(x). We determine the distances using Corollary 2 as

hCi(x) = max |maxpref(x, x⁻)|, |maxpref(x, x⁺)|

= max

min |NCA(lps_C(x), y⁻)|, h_C(x),|x⁻| , min |NCA(lps_C(x), y⁺)|, h_C(x),|x⁺|

.

Findingx⁺andx⁻can be done in timeO(log logn). The nearest ancestor queries can be answered in constant time. Hence the total time spent isO(log logn).

We now describe how to answer a rooted LCP query on T(C_i) in time O(log logn) for a suffix x⁰ of a string x, assuming that x has been preprocessed in time O(|x|). To answer a rooted LCP query LCP(x⁰, i), we first determine lps_C(x⁰) and h_C(x⁰) in time O(log logσ) =O(log logn)as described in Lemma 6 for use in the following lemmas. Then we determine the leaflps_Ci(x⁰)inT(Ci)andhCi(x⁰)in timeO(log logn)as described by Lemma 9. Knowing both of these parameters, the location wherex⁰ diverges fromT(C_i) can be found by a weighted ancestor query onT(C_i), determining the ancestor oflps_Ci(x⁰) having a depth (string length) equal tohCi(x), i.e.,WA(lps_Ci(x⁰), hCi(x))onT(Ci). Thus, a rooted LCP query can be answered in timeO(log logn), concluding the proof of Lemma 2.

22 THE LCP DATA STRUCTURE

3.5.1 Example of a Rooted LCP Query

In this section we illustrate and describe each of the steps necessary to answer a rooted LCP query for a small example. The goal is to answer a rooted LCP query for the string x = cacba on a compressed trie T(C_i). We assume that the LCP data struc-ture is built for the string t = bccbbccd, having the 28 unique substrings shown in Figure 3.3(a) with their lexicographic order number. The LCP data structure is built as previously described, producing the sorted suffix treeT(C)for all suffixesC= suff(t) = {bbccd,bccbbccd,bccd,cbbccd,ccbbccd,ccd,cd,d} of t. Furthermore, the suffixes in T(C) are labeled by their lexicographic order number and a nearest common ancestor data structure has been built forT(C).

First, we preprocess the query stringxto find the longest prefix string forxamong the suffixes oft,lps_C(x), and the length of the maximum common prefixhC(x). As shown in Figure 3.3(b), we find thatlps_C(x) =cbbccdwhich has order number19. The length of the maximum common prefix ish_C(x) = 1.

Next, we consider the compressed trieT(Ci)(see Figure 3.3(c)) storing the substrings Ci = pref₃(suff(t)) ={bbc,bcc,cbb,ccb,ccd,cd,d}. We assume thatT(Ci)is stored in the LCP data structure, and hence a weighted ancestor data structure has been built for T(Ci). Furthermore, a predecessor data structure has been prepared fororderset(Ci) = {3,7,16,21,26,27,28}, containing the lexicographic order numbers of the strings inCi.

We now describe how a rooted LCP queryLCP(x, i)for the stringxon the compressed trieT(Ci)is answered. First, we identify the longest prefix string forxinCi,lps_Ci(x)and the lengthhCi(x)as follows. The predecessor and successor oflps_C(x)(order number19) in the orderset ofC_i are the stringsx⁻ = cbb(order number16) and x⁺ = ccb(order number21). By Lemma 8 one of these strings is a valid choice forlps_Ci(x). To determine which, we use Corollary 2 to find the distance thatxfollowsx⁻andx⁺respectively. This step consists of performing two nearest common ancestor queriesNCA(y⁻,lps_C(x))and

NCA(y⁺,lps_C(x))on the suffix tree, wherey⁻andy⁺are suffixes ofthavingx⁻andx⁺as a prefix, respectively. In this way, we find thatxfollows bothx⁻andx⁺for a distance of1, and the longest prefix string inC_iforxisx⁻. The answer to the rooted LCP queryLCP(x, i) is the ancestor ofx⁻of depth1. This location can be found by a weighted ancestor query

WA(x⁻,1)onT(Ci)as shown in Figure 3.3(d).

3.6 Unrooted LCP Queries

In the following two subsections, we describe two different ways of answering an un-rooted LCP query LCP(x, i, `) on a trie T(Ci). The first method is the one stated by Cole et al. [13], which requires O(|C_i|log|C_i|) additional space to support unrooted queries in timeO(log logn)on a trieT(Ci). This method results in Lemma 3. The second method is a new solution that requiresO(|C_i|)additional space to add support for unrooted LCP queries in timeO(log|C_i|+ log logn)onT(C_i). This method results in Lemma 4.

23

(a) The 28 unique substrings of tand their lexicographic order number. The suffixes oftare marked in bold.

5

(b) The position of x = cacba in the suffix tree for t, i.e., T(C) withC = suff(t). The longest

(d) FindingLCP(x, i)by a weighted ancestor query on T(Ci), using thatlps_Ci(x) =x⁻andhC_i(x) = 1 has been determined.

Figure 3.3:Illustrating how to answer a rooted LCP queryLCP(x, i)on a compressed trieT(Ci)stored in the LCP data structure. The indexed text in this example ist=bccbbccdand the query string is x=cacba.

24 THE LCP DATA STRUCTURE

3.6.1 Prerequisites

Before describing the details of the two solutions, we first account for the prerequisites they share. We assume that the LCP data structure has been constructed as described in Section 3.3, i.e., in particular a nearest common ancestor data structure has been built for the suffix treeT(C).

Both the method by Cole et al. [13] and our new method rely on a heavy path de-compositionHofT(C_i)to add support for unrooted LCP queries onT(C_i). As described in Section 2.2.1, the top of each heavy pathH ∈ H is extended until every light edge contains exactly one single character. This implies that the root of a heavy pathH, which we denoteroot(H), is not necessarily an explicit vertex inT(Ci). To be able to index into a heavy pathH ∈ H, we store an array containing for each explicit vertexv∈H, the string length of the string starting inroot(H)and ending inv. By building a predecessor data structure for this array, we can find the location onH at string distance ifromroot(H) by a single predecessor query to determine the explicit parent vertex for the location.

Storing these predecessor data structures requires O(|C_i|) additional space, since each vertex inT(Ci) is contained in at most one heavy path. Indexing into the array forH can be done in constant time, and a predecessor query on the array can be answered in timeO(log log maxx∈C_i|x|) =O(log logn), since the size of the universe is bounded by the length of the longest string in Ci. Constructing the heavy path decomposition and the predecessor data structures takes timeO(|C_i|). We assume this is done when the LCP data structure is built.

For both methods of answering unrooted LCP queries, the following lemma is very central.

Lemma 10 Given a location`∈T(C<sub>i</sub>)on a heavy pathH ∈ Hand a stringx∈Σ<sup>∗</sup>, we lethdenote the distance thatxfollowsH starting in`. Provided thatxhas been preprocessed in timeO(|x|), we can determinehin constant time.

Proof Observe that the leaf of each heavy pathH ∈ H, leaf(H), corresponds to a substring oft, i.e., the string starting inroot(T(Ci))and ending inleaf(H). For each heavy pathH∈ H, we store the positionpos(y_H)of a suffixy_H ofthaving the string leaf(H)as a prefix. Sinceleaf(H)is a substring oft, there must be at least one suffix y_H ∈C. From the definition, any location`onH is a prefix of bothleaf(H)andy<sub>H</sub>. Let z<sub>`</sub> denote the substring of t starting in ` and ending in leaf(H) of length

|z<sub>`</sub>|=|leaf(H)| − |`|. We will use Corollary 2 to determine the distance thatxfollows z_{`</sub>, which requires us to identify a suffixz<sub>`}⁰ ofthavingz_` as a prefix.

To that end, note that leaf(H) = `·z<sub>`</sub> v_pref y_H, so z<sub>`</sub> is a prefix of the string obtained by removing the prefix ` from yH. Thus, we obtain z_{`</sub><sup>0</sup> as the suffix of t shifted |`|positions to the right from yH, effectively stripping ` off yH. That is, z<sub>`}⁰ = suff_pos(y

H)+|`|(t), so we have that z<sub>`</sub> = pref_{|z`|</sub> z<sub>`}⁰

= pref|leaf(H)|−|`| suff_pos(y

H)+|`|(t) .

25 Thus by Corollary 2 we can determine the distanceh that xfollows z_` in constant time as

Figure 3.4:Determininghby considering the possible cases in the suffix tree fort,T(C). Ifz`is a prefix of x(see Figure 3.4(a)), we haveh=|maxpref(x, z`)|=|z`|. In casez`is not a prefix ofx, there are two cases two consider. Eitherxdiverges fromz`on a path inC(see Figure 3.4(b)). In this caselps<sub>C</sub>(x)is located in the same off-path subtrie thatxbranches off into. Consequently, the maximum prefix betweenxandz`can be found by a nearest common ancestor query between lps_C(x)andz⁰<sub>`</sub>. Otherwise,xdiverges fromz`on a path not inC(or xis fully matched on z`). See Figure 3.4(c). In this case, the maximum common prefix betweenxandz`equals the maximum common prefix betweenxand any string inC, i.e.,h=hC(x).

3.6.2 The Solution by Cole et al.

The main idea in the method described by Cole et al. [13] for answering an unrooted LCP queryLCP(x, i, `)is to reduce the query to a rooted LCP query on a subtrie ofT(C<sub>i</sub>) included in the LCP data structure. A simple way to achieve this would be to includeevery subtrie ofT(Ci)in the LCP data structure. The unrooted LCP query LCP(x, i, `)could then be answered by performing a rooted LCP query on the subtrie ofT(C_i)rooted at location`.

Unfortunately, this approach could requireΘ(|C_i|n)space to store the additional subtries in the LCP data structure, since a stringy⁰ ∈Ci is present in|y⁰| ≤nsubtries.

To reduce this space usage, we will only include selected subtries ofT(C_i)in the LCP data structure. More precisely, for each heavy pathH in the heavy path decompositionH ofT(Ci), we add the subtrie ofT(Ci)rooted atroot(H)to the LCP data structure. The additional space required to store the predecessor and weighted ancestor data structures

26 THE LCP DATA STRUCTURE

for these subtries only amounts toO(|C_i|log|C_i|), since each of the|C_i|strings is contained in at mostlog|C_i|of these subtries. However, this only yields support for unrooted LCP queries starting in a location`, which is also the root of some heavy pathH ∈ H. For all other locations inT(C_i), we will reduce the unrooted LCP query forx to a rooted LCP query for a suffix ofx starting in the root of a another heavy path. More precisely, we preprocessT(C_i)as follows.

Preprocessing ofT(Ci):For all heavy pathsH∈ H,T_root(H)(Ci)is added to the LCP data structure to support unrooted LCP queries starting inroot(H).

Adding a subtrieT_root(H)(C_i)to the LCP data structure consists of constructing the pre-decessor data structure for the orderset over the strings starting inroot(H)and ending in a leaf. Additionally, a weighted ancestor data structure is constructed on the vertices ofT_root(H)(C_i). The additional preprocessing requiresO(|C_i|)additional space for each subtrie ofT(C_i)added to the LCP data structure.

We now describe how to answer an unrooted LCP queryLCP(x, i, `)when`is not a top location of a heavy path inT(C_i). LetHdenote the heavy path inHthat`is located on. The search forxfollowsH some string distanceh≤ |x|from`after which the search either stops (x is fully matched) or leavesH. Using Lemma 10 we can compute h in constant time. Knowingh, we can determine the answer toLCP(x, i, `)in timeO(log logn) as follows.

Using h to Find LCP(x, i, `) We first obtain the location`h on H at distanceh from ` by performing a predecessor query onH to obtain the explicit parent vertex of`_h. The answer can then be obtained as described below.

1. Ifh=|x|,xis fully matched onH and we have thatLCP(x, i, `) =`_h.

2. Ifh <|x|, the search forxleavesH at location`_h, and there are two possibilities to consider:

a) `<sub>h</sub>has an outgoing light edge(`_h, `<sup>0</sup><sub>h</sub>)labeled with the next unmatched character x[h+1]. Since`⁰_his the root of another heavy path inH, the answer toLCP(x, i, `) can be found by a rooted LCP query forx’s unmatched suffixsuff<sub>h+2</sub>(x)on the subtrieT<sub>`</sub>⁰

h(C_i). See Figure 3.5 for an illustration of this case.

b) `<sub>h</sub> has no outgoing edge labeledx[h+ 1], so the pattern cannot followT(C<sub>i</sub>) longer. In this case, we have thatLCP(x, i, `) =`h.

In any case,LCP(x, i, `)can be determined inO(log logn)time. This completes the proof of Lemma 3.

27

T(Ci)

root(H)

leaf(H)

` h

H

`h

`⁰_h

T_`0 h(Ci)

Figure 3.5:Illustrating how to answer an unrooted LCP query from the location`∈T(Ci)using the method described by Cole et al. [13]. The illustration shows the situation where the search forxleaves the heavy pathHon a light edge and proceeds in the subtrieT`⁰_h(Ci).

3.6.3 A New Solution

When performing a LCP query LCP(x, i, `), the search path forxstarting in`traverses a number of heavy paths inT(Ci)as shown in Figure 3.6. The solution by Cole et al. [13]

only considers the first of these heavy paths, and uses a rooted LCP query to complete the search. The main idea of our new solution is to follow all theO(log|C_i|)heavy paths that the search path passes through, thereby avoiding the need for a rooted LCP query and the additional space overhead caused by adding subtries ofT(Ci)to the LCP data structure.

Intuitively, for each heavy path intersected by the search path, the next heavy path can be identified in constant time using Lemma 10. On the final heavy path, a predecessor query is needed to determine the exact location where the search path stops.

For a heavy pathH, we lethdenote the distance which the search path forxstarting in`followsH. Referring to Figure 3.6, we can compute the answer to an unrooted LCP query recursively as follows. To answerLCP(x, i, `)we identify the heavy pathH ofT(Ci) that`is part of and compute the distancehin constant time as described by Lemma 10.

IfxleavesHon a light edge, indexing distancehintoH from`yields an explicit vertex v. Atv, a constant time lookup forx[h+ 1]determines the light edge on whichxleaves H. Since the light edge has a label of length one, the next location`⁰ on that edge is the root of the next heavy path. We continue the search for the remaining suffix ofxfrom`<sup>0</sup> recursively by a new unrooted LCP queryLCP(suff<sub>h+2</sub>(x), i, `⁰). IfH is the heavy path on which the search for xstops, the location at distanceh(i.e., the answer to the original LCP query) is not necessarily an explicit vertex, and may not be found by indexing into H. In that case a predecessor query forhis performed onH to determine the preceding explicit vertex and thereby the location LCP(x, i, `). Answering an unrooted LCP query entails at mostlog|C_i|recursive steps, each taking constant time. The final recursive step may require a predecessor query taking timeO(log logn). Consequently, an unrooted LCP

28 THE LCP DATA STRUCTURE

query can be answered in timeO(log|C_i|+ log logn) usingO(|C_i|) additional space to store the predecessor data structures for each heavy path. This completes the proof of Lemma 4.

T(Ci) ^h

H root(H)

leaf(H) v

`

`⁰

LCP(x, i, `)

At mostlog|Ci|heavy paths.

x

Figure 3.6:Illustrating how an unrooted LCP queryLCP(x, i, `)can be answered by recursively following at mostlog|Ci|heavy paths inT(Ci).

In document String Indexing for Patterns with Wildcards (Sider 24-35)