# Tri-Partition Alphabet-Based State Prediction for Multivariate Time-Series
## 4 Algorithms
### Stage III  
Algorithm 4 discusses the details of Stage III. First, \(f_{j+1,i}\) is the label of attribute \(a_{i}\). The predicted symbol is the one with the maximal frequency. Second, the purpose of using the index to count is to improve the efficiency of this algorithm. In Line 6, Count\((\cdot)\) is a mapping function for the count matrix in which the size is \(g\times 2\). The \(l\)-th position stores the frequency of \(\gamma_{l}\) (\(l\in[1,g]\)). Generally, the matrix is denoted by \(\mathbf{M}=((\text{Count}(1),\,1)\), (Count(2), 2),..., (Count(\(g\)), \(g\))). For example, with Table 3, let the indices of H, M, and L be 0, 1, and 2, respectively, (\(g=3\)). Matrix ((3, 0), (2, 1), (4, 2)) means the frequencies of H, M, and L are 3, 2, and 4, respectively. Moreover, \(\mathbf{M}_{1,e}=(3,\,0)\), \(\mathbf{M}_{1,1}=3\), and \(\mathbf{M}_{1,2}=0\).  
In Line 9, the count matrices are listed in the count descending order. Generally, \(\mathbf{M}^{\prime}=(\mathbf{M}_{1,e},\mathbf{M}_{2,e},\ldots,\mathbf{M}_{g,e})\) are subject to (1) \(\forall i\in[1,g]\), \(\mathbf{M}_{i,e}\in\mathbf{M}\), and (2) \(\forall j\in[1,g]\), \(j\
eq i\), \(\mathbf{M}_{i,1}\geq\mathbf{M}_{j,1}\). For example, the matrix ((3, 0), (2, 1), (4, 2)) is transformed into ((4, 2), (3, 0), (2, 1)). In Lines 10-21, the algorithm searches for three symbols with the biggest count from the strong, medium, and weak regions each. There is no need to continue searching if all three symbols of the current variable are known. The time complexity of this stage is \(\Theta(mn)\).  
Finally, the RFS considers more information than the IFS, but their time and space complexities are the same, namely \(\Theta(nm)\). This way, we can obtain four kinds of states called the state, tri-state, IFS-based tri-state (IFS-tri-state), and RFS-based tri-state (RFS-tri-state).  
```
0:\(S^{\prime}=(T,A,V^{\prime},f^{\prime})\), \(S=(T,A,V,f)\), N and \(\Sigma=(\Gamma,\Lambda,\Omega)\);
0:\(P^{3\times n}=\begin{pmatrix}p_{1}^{\Gamma},&\dots,&p_{n}^{\Gamma}\\ p_{1}^{\Lambda},&\dots,&p_{n}^{\Lambda}\\ p_{1}^{\Omega},&\dots,&p_{n}^{\Omega}\end{pmatrix}\); Method: Prediction.
1: Initialize \(P^{3\times n}\) by filling with \(\phi\);
2:for(\(i\in[1,n]\)) do
3:\(\mathbf{M}=((\text{Count}(1),\,1),\,(\text{Count}(2),\,2),\,\dots,(\text{ Count}(g),\,g))\), \(\text{Count}(l)=0\) (\(l\in[1,g]\));
4:for (each neighbor \(O\in\mathbf{N}\)) do
5: Get its last time stamp, denoted by \(t_{j}\);
6: Obtain the index of \(f_{j+1,i}\) in \(V_{a_{i}}\), denoted by \(l\);
7:\(\text{Count}(l)++\);
8:endfor
9: Obtain \(\mathbf{M}^{\prime}\) by listing \(\mathbf{M}\) in the descending order of \(\text{Count}(\cdot)\);
10:for(\(j\in[1,g]\)) do
11: Let \(l=\mathbf{M}^{\prime}_{j,2}\);
12:if\((\gamma_{l}\in\Gamma\) and \(p_{i}^{\Gamma}\
eq\phi)\) then
13:\(p_{i}^{\Gamma}=\gamma_{l}\);
14:else if\((\gamma_{l}\in\Lambda)\) and \(p_{i}^{\Lambda}\
eq\phi\)then
15:\(p_{i}^{\Lambda}=\gamma_{l}\);
16:else if\((\gamma_{l}\in\Omega)\) and \(p_{i}^{\Omega}\
eq\phi\)then
17:\(p_{i}^{\Omega}=\gamma_{l}\);
18:else
19: break;
20:endif
21:endfor
22:endfor
23:return\(P^{3\times n}\);
```  
**Algorithm 4** Three-way state prediction.