# Concurrent vs. Exclusive Reading in Parallel Decoding of LZ-Compressed Files +
## 3 Decoding LZC-Compressed Files in Parallel
### The EREW PRAM Algorithm  
The subsequence \(q_{1}\cdots q_{m}\) of pointers between two consecutive reset operations that we decoded on the CREW PRAM in the previous subsection is decoded on the EREW PRAM in two phases. In the first phase, since the pointers do not contain the information on the length of their targets, these lengths have to be computed. 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\), where \(\alpha\) is the alphabet cardinality. Then, in parallel for each \(i\), link pointer \(q_{i}\) to the pointer in position \(q_{i}-\alpha\) if \(q_{i}>\alpha\). Again, we obtain a forest where each tree is rooted in a pointer representing an alphabet character, and the length \(l_{i}\) of the target of a pointer \(q_{i}\) is equal to the level of the pointer in the tree plus \(1\). It is known from [1] that the largest number of distinct factors whose concatenation forms a given string of length \(\ell\) is \(\mathrm{O}(\ell/\log\ell)\). Since a factor of the LZW factorization of a string appears a number of times which is at most equal to the alphabet cardinality, it follows that \(m\) is \(\mathrm{O}(\ell/\log\ell)\) if \(\ell\) is the length of the substring encoded by the subsequence \(q_{1}\cdots q_{m}\). Then, building such a forest takes \(\mathrm{O}(log(|S^{\prime}|))\) time with \(\mathrm{O}(|S^{\prime}|)\) processors on a shared memory parallel machine without writing and reading conflicts. With the same parallel complexity, we can compute the trees of such forest and the level of each node in its own tree by means of the Euler tour technique. Therefore, we can compute the lengths \(l_{1},...,l_{m}\) of the targets. If \(s_{1},...,s_{m}\) are the partial sums, the target of \(q_{i}\) is the substring over the positions \(s_{i-1}+1\cdots s_{i}\) of the output string. For each \(q_{i}\) which does not correspond to an alphabet character, define \(first(i)=s_{q_{i}-\alpha-1}+1\) and \(last(i)=s_{q_{i}-\alpha}+1\). Since 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\), link the positions \(s_{i-1}+1\cdots s_{i}\) to the positions \(s_{first(i)}\cdots s_{last(i)}\), respectively. As in the sliding dictionary case, if the target of \(q_{i}\) is an alphabet character, the corresponding position in the output string is the root of a tree in a forest, and all the nodes in a tree correspond to positions of the decoded string where the character is the root. Since the number of children for each node is at most \(\alpha\), in \(\text{O}(log(|S^{\prime}|))\) time with \(\text{O}(|S^{\prime}|)\) processors, we can store the forest in a doubly linked structure and decode by means of the Euler tour technique on the EREW PRAM [14]. Differently from the CREW PRAM algorithm, the running time is obviously \(\text{O}(log(|S^{\prime}|))\), regardless of the factor maximum length.