## 3 Positional Inverted Self-Index
```
1:functiondecompress(\(f\), \(t\))
2:\(\textit{fpointer}\leftarrow\textsc{getFPointer}(f)\);
3:while\(f\leq t\)do
4:repeat
5:\(w\leftarrow\) [PERSON] decode at position \(F[\textit{fPointer}]\) using \(T_{c}\);
6:\(\textit{fPointer}\leftarrow\textit{fPointer}+\) [PERSON] codeword length;
7:\(\textsc{output}(w)\);
8:until\(w\
eq\langle\textit{STOP}\rangle\)
9:\(s\leftarrow\textsc{getStem}(f)\);
10:\(f\gets f+\) SCDC codeword length;
11:if\(T_{s}\).size\(>1\)then
12:\(w\leftarrow\) [PERSON] decode at position \(F[\textit{fPointer}]\) using \(T_{s}\);
13:\(\textit{fPointer}\leftarrow\textit{fPointer}+\) [PERSON] codeword length;
14:else
15:\(w\leftarrow\) the only word with the stem \(s\);
16:\(\textsc{output}(w)\);
17:functiongetStem(\(i\))
18:whileTRUE do
19:if\(I[i]=1\)then
20:\(i\gets i+1\); \(s\leftarrow\) SCDC decode at position \(i\); return\(s\);
21:else
22:\(p\leftarrow\) SCDC decode at position \(i\);
23:\(i\gets i+\) SCDC codeword length;
24:if\(I[i]=0\)then
25:\(i\gets i+1\); \(s\leftarrow\) SCDC decode at position \(i\); return\(s\);
26:\(i\gets i+p\);
27:functiongetFPointer(\(i\))
28:\(f\leftarrow i\) / \(\beta\); \(j\gets 0\);
29:\(\textit{fPointer}\gets 0\);
30:while\(j\leq f\)do
31:\(\textit{fPointer}\leftarrow\textit{fPointer}+\textit{FP}[j]\); \(j\gets j+1\);
32:\(f\gets f\times\beta\);
33:while\(f<i\)do
34:repeat
35:\(w\leftarrow\) [PERSON] decode at position \(F[\textit{fPointer}]\) using \(T_{c}\);
36:\(\textit{fPointer}\leftarrow\textit{fPointer}+\) [PERSON] codeword length;
37:until\(w\
eq\langle\textit{STOP}\rangle\)
38:\(s\leftarrow\textsc{getStem}(f)\); \(f\gets f+\) SCDC codeword length;
39:if\(T_{s}\).size\(>1\)then
40:\(w\leftarrow\) [PERSON] decode at position \(F[\textit{fPointer}]\) using \(T_{s}\);
41:\(\textit{fPointer}\leftarrow\textit{fPointer}+\) [PERSON] codeword length;
42:return\(\textit{fPointer}\);
```  
**Algorithm 1**pist Decompression from Byte Position \(f\)  
The function getFpointer is necessary to find a position in the presentation layer \(F\) corresponding to the position \(i\) in the inverted list \(I\). The algorithm finds the first stored _fPointer_ preceding the position \(i\) (see line 28). Next, the algorithm sums up offsets stored in \(\textit{FP}\) (see rows 30-31). In the next while cycle (line 33), the algorithm traverses the inverted list \(I\) and correspondingly the presentation layer \(F\). The next repeat-until cycle (see line 34) traverses all the non-alphanumeric words and stop words preceding the word at position \(f\). Next, the algorithm finds a stem \(s\) corresponding to the word at position \(f\) (see line 38) and decodes the word variant of the stem \(s\) (see line 40). Finally, when the actual position \(f\) in the inverted list \(I\) corresponds to \(i\), the corresponding position in the presentation layer \(F\) is stored in _fPointer_. The function decompress performs the decompression starting at position \(f\) and processing next \(t\) words. The function exactly mimics the behaviour of getFpointer function (starting from line 33). The only difference is that the function decompress outputs the decoded non-alphanumeric words and stop words of the presentation layer (see line 7) and it outputs the stem variants (see line 16). The condition at line 11 decides, whether the algorithm decodes the stem variant or it outputs the only existing stem variant. We provide the following theorems defining the space and time complexity of PISI data structure. Theorem 1 defines the upper bound of space needed for PISI inverted list. Theorem 2 defines the upper bound of space needed for PISI presentation layer. Finally, Theorem 3 defines the upper bound of time needed to locate all occurrences of a queried term. **Theorem 1**.