{'fraction_non_alphanumeric': 0.056247802820202336, 'fraction_numerical': 0.012694816608726222, 'mean_word_length': 3.638883855770973, 'pattern_counts': {'":': 0, '<': 3, '<?xml version=': 0, '>': 0, 'https://': 1, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 27, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
LZRR: LZ77 Parsing with Right Reference

Lossless data compression has been widely studied in computer science. One of the most widely used lossless data compressions is Lempel-Zip(LZ) 77 parsing, which achieves a high compression ratio. Bidirectional (a.k.a. macro) parsing is a lossless data compression and computes a sequence of phrases copied from another substring (target phrase) on either the left or the right position in an input string. Gagie et al.(LATIN 2018) recently showed that a large gap exists between the number of smallest bidirectional phrases of a given string and that of LZ77 phrases. In addition, finding the smallest bidirectional parse of a given text is NP-complete. Several variants of bidirectional parsing have been proposed thus far, but no prior work for bidirectional parsing has achieved high compression that is smaller than that of LZ77 phrasing for any string. In this paper, we present the first practical bidirectional parsing named LZ77 parsing with right reference (LZRR), in which the number of LZRR phrases is theoretically guaranteed to be smaller than the number of LZ77 phrases. Experimental results using benchmark strings show the number of LZRR phrases is approximately five percent smaller than that of LZ77 phrases.


Introduction
Lossless data compression has been widely studied in computer science. One of the most widely used lossless data compressions is Lempel-Zip (LZ) 77 parsing [8], which compresses a given string by computing a sequence of phrases copied from the longest substring on the left position in an input string. LZ77 parsing has a long research history, with the first paper on it published in 1976 [8]. Many LZ77's extensions have since been proposed (e.g., [7,3,10]), and LZ77 parsing achieves the smallest compression ratio among them.
Bidirectional (a.k.a. macro) parsing [11] is a lossless data compression and computes a sequence of phrases copied from another substring (target phrase) on either the left or right position in an input string. Each set of LZ77 phrases is convertible into a set of bidirectional phrases, and the number of phrases in the smallest bidirectional parsing is less than that of LZ77 phrases. Gagie et al. [2] recently showed the number of LZ77 phrases z representing an input string of length n can be tightly bounded by the smallest number of bidirectional phrases b * representing the same string as z = O(b * log(n/b * )), which suggests that a large gap exists between b * and z. In addition, finding the smallest bidirectional parse of a given text is NP-complete [11]. Thus, an important open challenge is to develop a polynomial time bidirectional parsing such that the number of bidirectional phrases is smaller than that of LZ77 phrases.
Several variants of bidirectional parsing have been proposed thus far. Lex-parsing [9] is a bidirectional parsing that computes a sequence of bidirectional phrases that each occurred previously on a suffix array of a string. The number of phrases v in the lex-parsing is bounded by v = O(b * log(n/b * )) [2]. Although the lex-parsing is effective for most benchmark strings (i.e., phrases v is very close to z) in practice, it can fail to compress some strings (i.e., v is much larger than z) [9]. Lcpcomp [1] and a bidirectional parsing using Burrows-Wheeler transform (BWT) [2] have also been proposed, and they never have fewer phrases than lex-parse [9]. Kempa and Prezza proposed a parsing algorithm for computing the bidirectional parse of an input string for a given string attractor of the string [6]. The number of the bidirectional phrases is bounded by O(γ log(n/γ)), where γ is the size of the string attractor. Let γ * be the size of the smallest string attractor for a given string. Then b * = O(γ * log(n/γ * )) holds [6]. In addition, finding the smallest string attractor of a given string is also NP-complete [6]. In summary, no prior bidirectional parsing achieves high compression that is smaller than that of LZ77 phrasing for any string.
In this paper, we present the first practical bidirectional parsing named LZ77 parsing with right reference (LZRR) in which the number of LZRR phrases is always smaller than the number of LZ77 phrases by a large margin. LZRR is a polynomial time algorithm that greedily computes phrases from a string in the left-to-right order the same as LZ77. The main difference between LZRR and LZ77 is the way to compute their phrases. Whereas LZ77 parsing chooses the longest substring occurring previously as a phrase, LZRR parsing uses not only previous occurrences of each phrase but also subsequent occurrences (i.e., it chooses the longest substring occurring previously or subsequently as a phrase). For this reason, the number of LZRR phrases is theoretically guaranteed to be no more than that of LZ77 phrases. Experimental results using benchmark datasets show the number of LZRR phrases is approximately five percent smaller than that of LZ77 phrases.

Preliminaries
Let Σ be an ordered alphabet of size σ, T be a string of length n over Σ and |T | be the length of T .
For two strings x and y, x ≺ y represents that x is lexicographically smaller than y, we write x ≺ y. Similarly, for a string z, x z y represents that the LCP of x and z is equal to or longer than that of y and z. For example, aab aac ab.
Our model of computation is a unit-cost word RAM with a machine word size of Ω(log 2 n) bits. We evaluate the space complexity in terms of the number of machine words. A bitwise evaluation of space complexity can be obtained with a log 2 n multiplicative factor.

Arrays
Suffix array SA, inverse suffix array ISA, LCP array LCP, longest previous factor array LPF, and sorted suffix array SA i are integer arrays of length n for a string T , respectively. SA is the permutation of [1..n] such that T [SA [1] ..]. SA k is not unique when there exist two positions i and j such that lcp(k, i) = lcp(k, j).

Union-find data structure
Union-find is a data structure for disjoint sets and supports the following operations for disjoint set D: MakeSet, Union, Find . MakeSet adds element {m + 1} into D and returns the integer where m is the cardinality of D. Union(x, y) merges two sets X, Y ∈ D containing x and y, respectively; it adds a new set X ∪ Y into D; it removes X and Y from D. The Find (x) returns the id of the set containing x in D. The union-find data structure performs MakeSet, Union, Find operations in O(m + p + qα p+q (p)) time, while using O(m) space [12], where p and q are the numbers of Union and Find operations, respectively, and α k is the inverse of the k-th row of Ackermann function. The original string T can be recovered from BP B by referring to a finite number of phrases from each f i in B. If an infinite loop of phrases referred from any f i exists, the original string T cannot be recovered from B. If T can be recovered from B, B is said to be a valid BP of T ; otherwise, B is said to be invalid BP of T .

Bidirectional phrases and partial bidirectional phrases
The value of the phrase reached from position x in k iterations of references is formally defined as where p is the integer such that s p ≤ x < s p+1 holds for s b+1 = n + 1. For k ≥ 1, we define g k (x) as follows: If g n [x] ∈ Σ holds, then there are no infinite loops of references containing x. Therefore, B is valid BP of T if B has no infinite loops of references, i.e., g n [x] ∈ Σ holds for all x.
LZ77 phrases [8] of string T are a specialization of BP and defined as the bidirectional phrases that are all selected from previously seen substrings. Since there is no infinite loops of references on phrases, LZ77 phrases of T are always valid BP of T . Formally, let LZRR parsing gradually builds the valid BP from the start position of T in the left-to-right order. A subsequence of the valid BP is called partial bidirectional phrases (PBP) and is defined as a BP P = f 1 , f 2 , . . . , f k for a prefix of T that can be copied from any substring of T , i.e., t i ∈ {1, . . . , n} \ {s i } for all i ∈ {1, . . . , k} for a target phrase f i , which avoids a self copy.
The concatenation of such PBP P and every character phrase referred from P can recover the prefix of T with a finite number of references. Such PBP are called valid PBP, and other PBP are called invalid PBP. Formally, let B P = P · f 1 , f 2 , . . . , f k be the concatenation of PBP P and the remaining character The original string of a PBP can be recovered by iteratively referring to phrases starting from each target phrase in a finite number of times until the character phrase is found. Thus, the position of each character phrase can be seen as the source for positions of target/character phrases. Formally, for a PBP P and position x ∈ {1, . . . , n} on T , source(P, x) returns source y ∈ N of x in B P , i.e., position y satisfying either (i) g k (x) = y and g k+1 (x) ∈ Σ for an integer k or (ii) x = y and g 0 (x) ∈ Σ. For the above example, the source of the position 1 is the position 6 in P since g 0 (1) = 3, g 1 (1) = 6 and g 2 (1) = a.

LZRR
A key idea of LZRR parsing is to compute the valid BP from an input text T by gradually computing the valid PBP from the head of T in the left-to-right order. LZRR parsing computes whole LZRR phrases initialized as zero phrase for an input string in two steps: (i) it computes candidates of the reference positions of the longest valid phrase following the current LZRR phrase; and (ii) it computes the valid (possibly character) phrase with the maximum length among extensions starting from those candidates. Steps (i) and (ii) are iterated until whole LZRR phrases are computed.
LZRR parsing uses two major functions of LP and LF for steps (i) and (ii), respectively. Given a valid PBP P of T , LP function LP(P ) returns the longest valid phrase following P , i.e., the longest phrase f such that P · f is a valid PBP of T . Given a valid PBP P of T and reference position j ∈ {1, . . . , n}, LF function LF(P, j) returns the length of the longest valid phrase having reference position j and following P , i.e., LF(P, j) = max({0} ∪ { | ∈ {1, 2, . . . , lcp(i, j)}, P · j, is valid}) where i is the starting position of the phrase following P . LZRR parsing computes LZRR phrases as the valid BP LZRR(T ) = LP(P 0 ), . . . , LP(P b−1 ) of T where P p is the first p LZRR phrases for each p ∈ {0, 1, . . . , b} and b is the number of LZRR phrases of T . The LZRR phrases of T are not unique.

Algorithm 1:
The LP algorithm.
The LZRR parsing algorithm is presented in Section 3. Theorems 1 and 2 are shown in Section 4.

LP algorithm
A straight forward computation of LP(P ) is to compute reference position j max such that LF(P, j max ) = max{LF(P, 1), . . . , LF(P, n)} and then compute max = LF(P, j max ), which results in LZRR phrase  Proof. See Appendix.
Algorithm 1 shows the algorithm for computing LP(P ) function and computes each LF function from the head of SA i . When Algorithm 1 finds k max , it returns the current longest valid phrase.

LF algorithm
LF algorithm LF(P, j) finds the longest valid target phrase with reference position j and following the PBP P of T by gradually extending the target phrase of length 1 until it cannot find any reference string copying the target phrase. When PBP P · j, for P and the target phrase j, is computed one-by-one, it can include an infinite loop of references by a mutual reference of phrases. This is because PBP as a target phrase can be copied from the left and right reference strings. This can happen when for computing the extension P · j, the position of a target phrase in P and j, can be mutually reached with a finite number of references. The LP algorithm avoids such cases by using the union-find data structure built from PBP P .
Each disjoint set in the union-find data structure includes string positions with the same source (character phrase) for PBP P . The union-find data structure is initialized as n disjoint sets that all contain the unique position of the input string of length n. If the union-find data structure for PBP P · j, − 1 for P and the target phrase j, exists, the data structure for P · j, − 1 can be updated by Union(i + − 1, j + − 1) operation.
The infinite loops of references can be detected using the find operation in the union-find data structure. When P · j, − 1 is a valid and the extension of starting position i + − 1 next to the PBP Algorithm 2: The LF algorithm.
Input: PBP P , union-find data structure for disjoint sets of P , reference position j; Output: LF(P, j); return − 1; and reference position j + − 1 is computed, if Find (i + − 1) is equal to Find (j + − 1) if and only if infinite loops of references exist. LF algorithm checks this condition each time. Formally, the following corollary holds. Algorithm 2 shows the algorithm for computing LF(P, j) function using Corollary 4 and the algorithm stated previously. Thus, we can compute the length max of the longest valid target phrase with reference position j and following the PBP P by O( max ) union and find operations on the given union-find data structure for D P .
Note that we need to modify Algorithm 2 for LP(P ) algorithm. This is because LF algorithms in our LP(P ) algorithm need the same union-find data structure determined by the PBP P . On the other hand, the given union-find data structure is changed by union operations in Algorithm 2. By modifying Algorithm 2 using an additional union-find data structure, we can compute LF(P, j) without updating the given union-find data structure. Formally, the following lemma holds.
Lemma 5. Given the union-found data structure L for D P , we can compute LF(P, j) in O(n) working space by O( max ) Find operations on L and O( max ) union and find operations on an additional unionfind data structure L for O( max ) disjoint sets. L is disposed after LF(P, j) is computed.
Proof. See Appendix.

Computation of LZRR(T )
Since LF(P p , j) algorithm for each p ∈ {0, . . . , b − 1} uses the union-find data structure for disjoint sets of the current LZRR phrases (i.e., P p ), we update the union-find data structure when the (p + 1)-th LZRR phrase is selected. This needs at most |LP(P p+1 )| Union operations by Corollary 4. We show that the working space of LZRR parsing is O(n) space. LZRR parsing needs two data structures: (1) the union-find data structures for LF algorithm and (2) the data structure to compute the sequence W p = SA sp [1], lcp(s p , SA sp [1]), . . . , SA sp [k p ], lcp(i, SA i [k p ]) for LP(P p−1 ) algorithm, where k p is k max in LP(P p−1 ) algorithm and s p is the starting position of p-th LZRR phrase.
We can compute W p [1.
.k] in O(k) time in an online manner using arrays of SA, ISA, and LCP for two integers p and k (See Appendix).
SA, ISA, and LCP of a given a string T can be constructed in O(n) time and working space [4,5]. Therefore, the second data structure can be constructed in O(n) time and space, and the LZRR parsing algorithm runs in O(n) working space.
Next, we show that the running time of LZRR parsing is O(n 2 α n 2 (n 2 )). Let G be the sequence of operations on disjoint-sets executed by LZRR parsing and W be the sequence of W 1 · · · W b , where b is the number of phrases in LZRR(T ). Then the running time is the sum of the computation time for executing G and computing W , and the prepossessing time of SA, ISA and LCP, which is O(n).
We show that W can be computed in O(n 2 ) time. For an integer p ∈ {1, . . . , b}, W p can be computed in O(k p ) = O(n) time. This is because k p = |Occ(T, f p )| ≤ n holds since T [SA i [y]..] has f p as a prefix for all y ∈ {1, . . . , k p }, where f p is the string represented by the p-th LZRR phrase. Thus, |W | = O(n 2 ) since b ≤ n. Hence W can be computed in O(n 2 ) time using the above online algorithm.
As a result, we can compute LZRR(T ) in O(n 2 α n 2 (n 2 )) time and O(n) working space.

The proof of Theorem 2
We . . , f k parses greedily T in the right-to-left order such that each phrase is the longest substring occurring previously (left) in T .
A key idea of this proof is that if LZ (T ) chooses a substring as an LZ phrase, then there exists an LZ phrase starting at a position on the LZ phrase and including the ending position of the LZ phrase. This is because the LZ phrase occurs previously in T and the LZ phrase is the longest substring occurring previously in T . Since the fact holds for every LZ phrase, |LZ(T )| ≤ |LZ (T )| holds. Conversely, if LZ(T ) chooses a substring as an LZ phrase, then there exists an LZ phrase starting at a position on the LZ phrase and including the starting position of the LZ phrase. This is because the LZ phrase occurs previously in T and the LZ phrase is the longest substring occurring previously in T . Since this fact holds for every LZ phrase, |LZ (T )| ≤ |LZ(T )| holds. Therefore, |LZ (T )| = |LZ(T )| holds. The proof of |LZRR(T )| ≤ |LZOR(T )|. LZOR(T ) = f 1 , . . . , f k parses T in the left-to-right order such that each phrase is the longest substring occurring subsequently in T .
A key idea of this proof is that if LZOR(T ) can choose a substring at a position as an LZOR phrase then LZRR(T ) also can choose the substring as an LZRR phrase. This is because candidate phrases with right reference positions are always valid phrases in LZRR parsing. Since the fact holds for every position on T , |LZRR(T )| ≤ |LZOR(T )| holds. The proof of |LZOR(T )| = |LZ (T R )|. Parsing a string in the left-to-right order using the longest substring occurring subsequently in the string is equal to parsing the reversed string in the right-toleft order using the longest substring occurring previously in the reversed string. Thus, |LZOR(T )| = |LZ (T R )| holds.

Experiments
In this section, we demonstrate the effectiveness of LZRR parsing with benchmark strings. We used two types of strings of pseudo-real and real repetitive collections in the Pizza & Chili corpus downloadable from http://pizzachili.dcc.uchile.cl. We compared our LZRR parsing with LZ77 parsing and lex-parse. We used execution time, memory, and number of phrases as evaluation measures for each method. The C++ programming language was used for implementing all the parsing algorithms. The implementations used in this experiment are available at https://github.com/TNishimoto/lzrr. LZ77 and lex-parse were implemented in the standard manner and work in time and space linear to string length using SA, ISA, and LCP arrays. For each method, we computed two sets of phrases for original string T and reverse string T R , respectively, and we took the set with the smaller number of phrases. We denote numbers of phrases as |LZ77|, |LEX|, and |LZRR| for parsing algorithms of LZ77, lexparse (LEX), and LZRR, respectively. We performed all the experiments on one core of a quad-core Intel(R) Xeon(R) E5-2680 v2 (2.80 GHz) CPU with 256 GB of memory. Table 1 shows the number of phrases for each method. The number of LZRR phrases was smaller than that of LZ77 phrases for all benchmark strings. Specifically, the number of LZRR phrases was approximately five percent smaller than that of LZ77 for all the strings except for fib41, rs.13, and tm29. The number of LZRR phrases was smaller that of lex-parse phrases for most of the strings.   Table 2 shows execution time and memory on limited benchmark strings for each method. The table for all the strings is presented in Appendix. Although our LZRR parsing needs O(n 2 α n 2 (n 2 )) time, the execution time was at most four times slower than that of LZ77 parsing. This is because the number of while-loops in Algorithm 1 is much smaller than n in practice. The memory for LZRR parsing was at most two times larger than that for LZ77 parsing. This is because the proposed algorithm needs the data structure for LF along with SA, ISA, and LCP arrays.  Figure 1: This figure represents the change of sources when a new target phrase is appended into a PBP. The "t" and "c" in rectangles mean target phrases and character phrases, respectively.

Results
To compute LF(P, j) without changing the union-find data structure L for D P , we create an additional union-find data structure L and we emulate find operations on D P · j, using union-find data structures L and L for D P . Since union operations are performed on L , L is not changed in LF algorithm.
A key idea is that sources on the last phrase j, are only changed by extending P · j, . See Figure 1. The left figure represents sources of positions on target phrases. The right figure represents the change of sources by appending new target phrase j, to the target phrases. The new target phrase changes only sources on the phrase and these sources are determined by the phrase. This suggests that sources not on the target phrase j, can be computed using L, and the other sources can be computed using L and the additional union-find data structure L that manages sources of positions on the phrase j, . In addition, disjoint sets managed by L can be updated by union operations as Corollary 4.
Formally, let U (P · j, ) be the set of positions on the phrase j, and sources of those positions (i.e., U (P · j, ) = {i, . . . , i + − 1} ∪ {source(P · j, , x) | x ∈ {i, . . . , i + − 1}}) and let D P · j, be disjoint sets on U (P · j, ) such that each set consists of all positions of the same source, where i is the position following P . Let MakeSet (x) be the operation on disjoint-sets D that adds {x} into D if D does not contain x. Then the following lemma and corollary hold.
Proof. T [r] is a character phrase on B P for each position r ∈ {i, i+1, . . . , i+ −1}. If the source x of x on B P is not a position in {i, i+1, . . . , i+ −1}, then x does not reach any position in {i, . . . , i+ −1}. When a phrase is appended into P , the source x is changed if and only if the character phrase on x is changed. Thus, the source of x is not changed by appending j, into P , i.e., source(P, x) = source(P · j, , x).
Otherwise, the source x is in {i, . . . , i + − 1} on B P and x has a source x on B P · j, because T [x ] is not a character phrase on B P · j, . Since the source of x is that of x on B P · j, , Lemma 6 holds. We compute the source of a given position on {1, . . . , n} by O(1) find queries on D P and D P · j, using Lemma 6 and Corollary 7. Note that we need to compute the position on the character phrase in a given set to obtain the source of a given position. For this reason, we use the position on a character phrase as the id of the set that contains the position. We can maintain such id using an additional array of length m with the same time complexity, where m is the cardinality of disjoint-sets.
We also note that we need to convert integers in D P · j, to consecutive integers. This is because disjoint sets of L are on consecutive integers since MakeSet creates the element {m + 1}. Thus, we use an array W of size n, where W [x] stores the integer in L that corresponds to x if x ∈ U (P · j, ); otherwise W [x] = −1. This array also enables us to emulate MakeSet operations. Since the size of W is n, we reuse W during the LZRR parsing algorithm, and the algorithm creates the array in advance. It takes O(n) time and space. W can be initialized in O(m) time, where m is the number of positive integers in W .
Algorithm 3 shows the modified algorithm for computing LF(P, j) function using Lemma 6 and Corollary 7. Algorithm 3 computes LF(P, j) by O( max ) union and find operations and does not perform union operations on D P , where max is the length of the longest valid phrase following P with reference position j. As a result, Lemma 5 holds.
Note that Algorithms 2 and 3 can fail if there exists an invalid PBP P · j, for an integer ∈ {1, 2, . . . , max }. If such an integer exists, then algorithms return − 1 and fail. However, such cases do not occur because we cannot remove infinite loops of references from an invalid PBP by appending phrases into the PBP.
Appendix C: The proof of the upper bound of LZRR phrases 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21   a b a b a b a a b b b a b b a a b a b 14 15 16 17 18 19 20 21   a b a b a b a a b b b a b b a a b a b 14 15 16 17 18 19 20 21   a b a b a b a a b b b a b b a a b a b  We show three formulas using injective functions; for two BPs F = f 1 , f 2 , . . . , f k and F = f 1 , f 2 , . . . , f k of T , if there exists an injective function w that maps phrases in F into distinct phrases in F , then k ≤ k holds. In the remaining section, let s x and e x (resp. s x and e x ) be starting and ending positions of x-th phrase in F (resp. F ).  . . , f k , we define the function w(x ) that returns the integer x such that f x contains e x (i.e., s x ≤ e x ≤ e x holds). w is injective if the starting position of each LZ phrase is not larger than that of the LZ phrase containing the ending position of the LZ phrase, i.e., s x ≤ s w(x ) holds for all x ∈ {1, 2, . . . , k − 1}. This is because no LZ phrases contain two ending positions in LZ phrases, i.e., no integer exists y such that w(y ) = w(y + 1) holds if s x ≤ s w(x ) holds for all x .
We show s x ≤ s w(  For LZRR(T ) = f 1 , f 2 , . . . , f k and LZOR(T ) = f 1 , f 2 , . . . , f k , let w(x) be the function that returns the integer x such that f x contains s x . Then w is injective if w(x) < w(x+1) holds for all x ∈ {1, 2, . . . , k−1}. We use the following lemma.
w(x) < w(x + 1) holds if max{1, LNF[s x ]} ≤ |f x | holds for all x ∈ {1, 2, . . . k}. Recall that LP function returns the valid longest bidirectional phrase. The LNF array and Lemma 8 suggest that the length of