# Concurrent vs. Exclusive Reading in Parallel Decoding of LZ-Compressed Files +
## 3 Decoding LZC-Compressed Files in Parallel
### The CREW PRAM Algorithm  
A special mark occurs in the sequence of pointers of the LZC encoding when the dictionary is cleared out, so that the decoder does not have to monitor the compression ratio. The positions of the special mark are detected by parallel prefix. Each subsequence \(q_{1}\cdots q_{m}\) of pointers between two consecutive marks can be decoded in parallel. The parallel algorithm is based on the fact that the target of the pointer \(q_{i}\) in the subsequence is the concatenation of the target of the pointer in position \(q_{i}-\alpha\) with the first character of the target of the pointer in position \(q_{i}-\alpha+1\), and employs concurrent reading [9]. Let \(Q_{1}\cdots Q_{N}\) be the LZC encoding of a string \(S\), drawn over an alphabet \(A\) of cardinality \(\alpha\), with \(Q_{h}\) sequence of pointers between two consecutive reset operations, for \(1\leq h\leq N\). Each \(Q_{h}\) can be decoded independently. Let \(q_{1}\cdots q_{m}\) be the sequence of pointers \(Q_{h}\) encoding the substring \(S^{\prime}\) of \(S\). The decoding of \(Q_{h}\) requires on a CREW PRAM \(\mathrm{O}((log(L))\) time with \(\mathrm{O}(|S^{\prime}|)\) processors, where \(L\) is the maximum length of a pointer target. The dictionary size is a theoretical upper bound to \(L\) that is tight for unary strings. The algorithm computes an \(m\times d\)_matrix of prefix pointers_\(M\), initially null with \(d=2^{16}\), as it follows:  
input: sequence of pointers \(q_{1}\ldots q_{m}\);  
output: matrix \(M\) of prefix pointers;  
\(1\). \(k:=1\);  
\(2\). **in parallel for \(1\leq i\leq m\)do**  
\(3\). \(M[i,j]:=q_{i}\);  
\(last[i]:=1\);  
\(value[i]:=M[i,j]-d\);  
\(6\). **while \(value[i]>0\)do**  
\(7\). **in parallel for \(1\leq j\leq k\)do**  
\(8\). **if \(j\leq last[value[i]]\)then**  
\(M[last[i]+j.i]=M[j,value[i]\);  
\(last[i]:=last[i]+last[value[i]]\);  
\(value[i]:=value[value[i]]\);  
\(k:=2k\);  
At each step, \(last[i]\) is the last nonnull component on the \(i^{th}\) column considered (line 10 after the initialization at line 4). The nonnull components of the \(value(i)^{th}\) column are copied on the \(i^{th}\) column in the positions after \(last[i]\) (lines 7-9). Note that \(value(i)\) is strictly less than \(i\). Then, \(value(i)\) is updatedby setting \(value(i):=value(value(i))\) (line 11). The loop stops on column \(i\) when \(value(i)\) is less or equal to zero. This procedure takes \(\mathrm{O}(|S^{\prime}|)\) processors and \(\mathrm{O}(log(L))\) time on a CREW PRAM, since the number of nonnull components on a column doubles at each step. The target of the pointer \(q_{i}\) is the concatenation of the target of the pointer in position \(q_{i}-\alpha\) with the first character of the target of the pointer in position \(q_{i}-\alpha+1\), since the dictionary initially contains the alphabet characters. At the end of the procedure, \(M[last[i],i]\) is the pointer representing the first character of the target of \(q_{i}\) and \(last[i]\) is the target length. Then, we conclude that \(M[last[M[j,i]-d+1],M[j,i]-d+1]\), for \(1\leq j\leq last[i]-1\), is the pointer representing the \((last[i]-j+1)^{th}\) character of the target of \(q_{i}\). That is, we have to look at the pointer values written on column \(i\) and consider the last nonnull components of the columns in the positions given by such values decreased by \(\alpha-1\). Such components must be concatenated according to the bottom-up order of the respective values on column \(i\). By mapping each component into the correspondent alphabet character, we obtain the suffix following the first character of the target of \(q_{i}\), and the pointers are therefore decoded (see [9] for further clarifications). The sequence of pointers can be seen as a parent pointer representation of a forest, where each pointer \(q\) with a value greater than \(\alpha\) represents a link from a node associated with \(q\) to its parent node associated with the pointer in position \(q-\alpha\).