## 3 Positional Inverted Self-Index
The vocabulary also stores the common Huffman tree \(T_{c}\) that is used to encode the non-alphanumeric words and the stop words. The next component of the vocabulary is the array \(FI\) storing the first word positions (in the array \(I\)) of the corresponding words in the vocabulary. **Example 1**. : _The dotted lines in Figure 1 describe an example of PISI search procedure. Suppose we search for the term course. First, we apply stemming on the searched term and obtain the stem course. Next, we look for the stem in the sorted vocabulary. Once the stem is found, the algorithm starts to scan the inverted list at position \(FI_{2}=4\) (see line 1). The algorithm jumps over the following occurrences (see lines 2 and 3). Finally, the last occurrence stores a back pointer to the vocabulary (line 4). The next steps depicted in Figure 1 are described also as procedure getFpointer in Algorithm 1. Suppose we want to decompress the neighbourhood of the last occurrence of the stem course at position \(11\) in the inverted list. It is necessary to synchronize the presentation layer with the occurrence in the inverted list. The previous synchronization point is at position \(\lfloor\frac{11}{F}\rfloor=\lfloor\frac{11}{3}\rfloor=3\). The algorithm sums up the offsets stored in \(FP\) array and it starts at position \(\sum_{i=1}^{3}FP_{i}=38\) in presentation layer that corresponds to the \(9\)-th entry (see lines 5 and 6). Finally, the algorithm performs decompression of the entries preceding the desired \(11\)-th entry (line 7). The entry decompression is basically composed of two steps. First, looking for the stem back pointer. Second, decompression of separators and the stem variant._  
Figure 2 depicts details of encoding process of the inverted list and the presentation layer. In the inverted list, we need to precede every back pointer by some reserved byte. PISI uses byte \(\langle 0\rangle\) for every \(\alpha\)-th occurrence that is not the last, and byte \(\langle 1\rangle\) for the last occurrence in the sequence. The byte \(\langle 0\rangle\) is preceded by a pointer to the next occurrence in the inverted list \(\langle\)offset\(\rangle\) and followed by a back pointer to the vocabulary \(\langle\)pointer to stem\(\rangle\). The byte \(\langle 1\rangle\) is followed only by the back pointer. In the presentation layer, it is necessary to mark the end of the sequence of non-alphanumeric words and stop words. PISI uses a reserved word \(\langle\)STOP\(\rangle\) that obtains the shortest Huffman code in the tree \(T_{c}\). PISI works in so-called _spaceless word model_ that expects the single space character _, as a default separator. PISI inverted list is encoded using a byte code, particularly _SCDC_[19]. For the sake of efficiency, it is practical to store byte instead of word position offsets in the inverted list. The word position offsets (presented in Figures 1 and 2) can be easily transformed into the byte offsets. This small change means only a negligible loss in compression ratio, however, it enables fast traversal of the inverted list of a chosen term without the need of previous preprocessing. This traversal is theoretically (not concerning the memory hierarchy of the computer) of the same speed as in the case of the standard positional inverted index. Before we give a formal definition of PISI data structure we need to introduce some other concepts. Suppose an input text \(T\) composed of single words. \(T\) is transformed into \(\hat{T}\) using stemming, stopping and case folding. Thus, \(\hat{T}\) is a vector of length \(N\) composed of single stems extracted from \(T\). The function \(\mathtt{rank}_{\hat{T}}(s,i)\) returns the number of occurrences of the stem \(s\) in the vector \(\hat{T}\) up to the position \(i\). The function \(\mathtt{select}_{\hat{T}}(s,i)\) returns the position of the \(i\)-th occurrence of the stem \(s\) in the vector \(\hat{T}\) and it returns \(0\) if there is no such a occurrence.