# Multiset-Trie Data Structure
## 3 Multiset-Trie Operations
### Sub-Multiset and Super-Multiset Existence  
The functions submsetExistence and supermsetExistence are symmetrical in the following sense. Let a multiset \(m\) represent the borderline in \(\mathcal{M}\) defined by a path from the root to a leaf following the elements from \(m\). The operation submsetExistence searches the left part of \(\mathcal{M}\) and the operation supermsetExistence the right part of \(\mathcal{M}\).  
The function submsetExistence(\(\mathcal{M},m,dev\)) checks if there exists a multiset \(x\) in \(\mathcal{M}\), that satisfies the condition \(x\subseteq m\) and \(|x[i]-m[i]|\leq dev\), where \(1\leq i\leq\sigma\). The function starts with searching for an exact match \(x=m\) in \(\mathcal{M}\), since \(m\subseteq m\) by definition of submultiset inclusion. If an exact match is not found in \(\mathcal{M}\), the function uses multiset-trie to find the closest (the largest) sub-multiset of \(m\) in \(\mathcal{M}\) by decreasing the multiplicity of elements in \(m\). The parameter \(dev\) is used to limit a maximal deviation of multiplicity for a particular element in \(x\) with respect to \(m\). At every level, the function tries to proceed with the largest possible multiplicity of an element that is provided by \(m\). However, when the function reaches some level where it meets a _Null_ node and cannot go further using the path provided by \(m\), it decreases the multiplicity of an element that corresponds to a current level with respect to the specified maximal deviation. Thus, the function can decrease the multiplicity of an element or eventually skip it in order to find the closest \(x\subseteq m\). The function submsetExistence is presented in Algorithm 4.  
```
1:functionsubmsetExistence(\(\mathcal{M},m,dev\))
2:\(currentNode\leftarrow\mathcal{M}\)
3:if\(currentNode\) is acceptingthen
4:return True
5:for\(i=m[1]\) down to \(\max(0,m[1]-dev)\)do
6:if child \(c_{i}\) of \(currentNode\) is not Nullthen
7:if\(\textsc{submsetExistence}(c_{i},m[2:],dev)\)then
8:return True
9:return False
```  
**Algorithm 4** Function submsetExistence  
The function supermsetExistence(\(\mathcal{M},m,dev\)) checks if there exists super-multiset \(x\) of a given multiset \(m\) in \(\mathcal{M}\), such that condition \(|x[i]-m[i]|\leq dev\) is satisfied, where \(1\leq i\leq\sigma\). Symmetrically to the function submsetExistence, the function supermsetExistence searches first for an exact match \(x=m\) in \(\mathcal{M}\). If such \(x\) does not exist in \(\mathcal{M}\), then the function searches on the right side of the borderline representing an exact match of in \(\mathcal{M}\). Since we would like to find the closest (the smallest) super-multiset, we increase the multiplicity of elements in \(m\) at every level of \((M)\) starting with the multiplicities of \(m\). The function supermsetExistence is presented in Algorithm 5.  
```
1:functionsupermsetExistence(\(\mathcal{M},m,dev\))
2:\(currentNode\leftarrow\mathcal{M}\)
3:if\(currentNode\) is acceptingthen
4:return True
5:for\(i=m[1]\) to min(\(n-1,m[1]+dev\)) do
6:if child \(c_{i}\) of \(currentNode\) is not Nullthen
7:ifsupermsetExistence(\(c_{i}\), \(m[2:]\), \(dev\)) then
8:return True
9:return False
```  
**Algorithm 5** Function supermsetExistence