# Pairs in a trace

Progress done between 2021-04-17 and 2021-04-22 by jgil@eso.org

## Some definitions

An *alphabet* $\Sigma$ is any finite set, and its elements are called *symbols*. A *trace* $T$ is any concatenation of symbols in $\Sigma$, written as $T \in \Sigma^{*}$. The symbols in $\Sigma$ that are also in a trace $T$ are written as $\Sigma(T)$

## Notion of a pair

In any trace we can precisely determine which of them appears in pairs by rewritting the trace as repetitions. For example in $T=ababab$, $T$ can be written as a repetition of the subtrace $ab$: $T= (ab)(ab)(ab) = 3 \times (ab)$. Note that if any other symbols exists in the trace, the pairing condition of $ab$ remains, for example $(ab)$ is paired in both $T_1=ababab$ and $T_2=abXabYab$.

Let be the set $\Sigma$ an alphabet, $T \in \Sigma^{*}$ a trace, and $a,b \in \Sigma; a \neq b$ a disjoint ordered pair. We say that $(a,b)$ is **paired in $T$** if exists $n \ge 0$ such that $T \cap \{a,b\} = n \times (ab)$, i.e. the symbols in $T$ restricted to $a$ and $b$ can be written as a repetition of the trace $(ab)$, possibly with $n=0$.



## Pair-cardinality

The pair-cardinality captures the repetitions of $ab$ in $T$. 

**Definition**: Given $T \in \Sigma^{*}$ and $a,b \in \Sigma$ we define the function $n_T(ab)$ as:

$$ 
\begin{align}
n_T: & \Sigma^2 \rightarrow \mathbb{N} \cup \{- \infty \} \\
n_T(ab) & = \left\{ 
  \begin{array}{rcl} n & \text{ if } a \neq b \text{ and } T \cap \{a,b\} = n \times (ab)   \\ 
  -\infty & \text{ otherwise } \end{array}\right. 
\end{align}
$$

Now we can define more precisely the notion of pairs. 

**Definition**: A pair $(a,b)$ is **paired in T** if $n_T(ab) \ge 0$, and $(a,b)$ is **unpaired in T** if $n_T(ab) \lt 0$.

**Definition**: The set of all pairs in $T$ is defined as $\mathcal{P}_T = \{ (ab) | (a,b) \text{ is paired in } T \}$

### Examples


```python
def pair_cardinality(x, y, T):
    '''
    Returns the cardinality if (x,y) is pair in T, otherwise it returns -1
    '''
    if x==y:
        return -1
    intersection=[a for a in T if a==x or a==y ]
    cardinality=int(len(intersection) / 2)
    return cardinality if [x,y]*cardinality==intersection else -1
```

Let be $\Sigma = \{a,b,x,y,m,n\}$ and $T=axbabyabyx$.


```python
T='axbabyabyx'
```

$(x,y)$ is unpaired in T because $T \cap \{x,y\} = xyyx$ cannot be written as repetitions of $(xy)$. Its cardinality $n_T(xy) = - \infty $


```python
[i for i in T if i in ('x', 'y')]
```




    ['x', 'y', 'y', 'x']




```python
pair_cardinality('x', 'y', T)
```




    -1



The pair $(a,b)$ is paired in $T$ and $n_T(ab)=3$, because $T \cap \{a,b\} = ababab = 3 \times (ab)$. 


```python
[i for i in T if i in ('a', 'b')]
```




    ['a', 'b', 'a', 'b', 'a', 'b']




```python
pair_cardinality('a', 'b', T)
```




    3



## Properties of pairs

**Property**: If $(a,b)$ is paired in $T$ then it is easy to prove that $(b,a)$ is unpaired in $T$ because there not exists any $n$ that verifies $T \cap \{b,a\} = n \times (ba)$


```python
pair_cardinality('b', 'a', T)
```




    -1



**Property**: If both $m$, $n$ are not in $\Sigma(T)$, then $T \cap \{m,n\} = 0 \times (mn)$ and its cardinality is equal to 0 which means that there is no evidence that $(m,n)$ be unpaired in T.


```python
pair_cardinality('m', 'n', T)
```




    0



**Property**: If $a \in \Sigma(T); x \in \Sigma \setminus \Sigma(T)$ i.e. the first symbol is in $T$ and the second not in $T$, then both $(a,x)$ and $(x,a)$ are unpaired in $T$.


```python
pair_cardinality('a', 'm', T)
```




    -1




```python

pair_cardinality('m', 'a', T)
```




    -1



## All pairs in T

Strategy: $\forall a,b \in \Sigma(T); a \neq b$ test if $n_T(ab) \ge 0$


```python
T='axbabyabyx'
```


```python
list( set( [x for x in T] ) )
```




    ['a', 'b', 'y', 'x']




```python
import pandas as pd
```


```python
def pairs_in_trace(T):
    Pairs_in_T = {}

    # The alphabet in T
    Sigma_T = list( set( [x for x in T] ) )
    for i in range( len(Sigma_T) -1 ):
        a = Sigma_T[i]
        # By def (a,a) is not paired in T
        Pairs_in_T[ (a,a) ] = -1 
        for b in Sigma_T[i+1:]:
            Pairs_in_T[ (a,b) ] = pair_cardinality(a, b, T)
            # asymmetric paired property: if (a,b) is paired in T the (b,a) is not
            if Pairs_in_T[ (a,b) ]>=0:
                Pairs_in_T[ (b,a) ] = -1  
            else: 
                Pairs_in_T[ (b,a) ] = pair_cardinality(b, a, T)
    return Pairs_in_T
```


```python
# Note that the sequence 1234 can be destroyed if a 4321 is added.
T='123abcabc44321'
```


```python
pairs = pairs_in_trace(T)
P=pd.DataFrame.from_dict( { a[0]+a[1]:b for a,b in pairs.items() }, orient='index', columns=['pairs'] )

# Show only pairs with n_T >= 0 
P[ P['pairs'] >= 0 ].T
```




<div>
<style scoped>
    .dataframe tbody tr th:only-of-type {
        vertical-align: middle;
    }

    .dataframe tbody tr th {
        vertical-align: top;
    }

    .dataframe thead th {
        text-align: right;
    }
</style>
<table border="1" class="dataframe">
  <thead>
    <tr style="text-align: right;">
      <th></th>
      <th>bc</th>
      <th>ac</th>
      <th>ab</th>
    </tr>
  </thead>
  <tbody>
    <tr>
      <th>pairs</th>
      <td>2</td>
      <td>2</td>
      <td>2</td>
    </tr>
  </tbody>
</table>
</div>




```python
P=pairs_in_trace(T)

# See how just (a,b) is pair and the rest has n_T=-1

pd.DataFrame.from_dict( { a[0]+a[1]:b for a,b in P.items() }, orient='index', columns=['pairs'] ).T
```




<div>
<style scoped>
    .dataframe tbody tr th:only-of-type {
        vertical-align: middle;
    }

    .dataframe tbody tr th {
        vertical-align: top;
    }

    .dataframe thead th {
        text-align: right;
    }
</style>
<table border="1" class="dataframe">
  <thead>
    <tr style="text-align: right;">
      <th></th>
      <th>33</th>
      <th>32</th>
      <th>23</th>
      <th>31</th>
      <th>13</th>
      <th>34</th>
      <th>43</th>
      <th>3c</th>
      <th>c3</th>
      <th>3b</th>
      <th>...</th>
      <th>4a</th>
      <th>a4</th>
      <th>cc</th>
      <th>cb</th>
      <th>bc</th>
      <th>ca</th>
      <th>ac</th>
      <th>bb</th>
      <th>ba</th>
      <th>ab</th>
    </tr>
  </thead>
  <tbody>
    <tr>
      <th>pairs</th>
      <td>-1</td>
      <td>-1</td>
      <td>-1</td>
      <td>-1</td>
      <td>-1</td>
      <td>-1</td>
      <td>-1</td>
      <td>-1</td>
      <td>-1</td>
      <td>-1</td>
      <td>...</td>
      <td>-1</td>
      <td>-1</td>
      <td>-1</td>
      <td>-1</td>
      <td>2</td>
      <td>-1</td>
      <td>2</td>
      <td>-1</td>
      <td>-1</td>
      <td>2</td>
    </tr>
  </tbody>
</table>
<p>1 rows × 48 columns</p>
</div>




```python
T='123abcabc4'
pairs = pairs_in_trace(T)
P=pd.DataFrame.from_dict( { a[0]+a[1]:b for a,b in pairs.items() }, orient='index', columns=['pairs'] )

# Show only pairs with n_T >= 0 
P[ P['pairs'] >= 0 ].T
```




<div>
<style scoped>
    .dataframe tbody tr th:only-of-type {
        vertical-align: middle;
    }

    .dataframe tbody tr th {
        vertical-align: top;
    }

    .dataframe thead th {
        text-align: right;
    }
</style>
<table border="1" class="dataframe">
  <thead>
    <tr style="text-align: right;">
      <th></th>
      <th>23</th>
      <th>13</th>
      <th>34</th>
      <th>12</th>
      <th>24</th>
      <th>14</th>
      <th>bc</th>
      <th>ac</th>
      <th>ab</th>
    </tr>
  </thead>
  <tbody>
    <tr>
      <th>pairs</th>
      <td>1</td>
      <td>1</td>
      <td>1</td>
      <td>1</td>
      <td>1</td>
      <td>1</td>
      <td>2</td>
      <td>2</td>
      <td>2</td>
    </tr>
  </tbody>
</table>
</div>



## Sequences

(Write here a discussion about notation, path, simple paths, sequences in literature, and be clear what a "sequence" is for us)

**Definition**: A sequence $S \in \Sigma^*$  is a trace whose symbols are different, $ s_i \neq s_j \forall i \neq j$. Similar to pairs, $S$ is a **sequence in $T$** if exists $n \ge 0$ such that $T \cap \Sigma(S) = n \times S$, i.e., the trace restricted to symbols of $S$ is a n-repetition of $S$. 

The cardinality of $S$ in $T$ is defined in the same way than for pairs, and extended to any trace: 

**Definition**: Let be $S$ any trace in $\Sigma^*$, then  $n_T(S) = n$ for some suitable $n$ if $S$ is a sequence in $T$, or $- \infty$ if $S$ is not a sequence in T. For completeness we also define $n_T( S=s_1 ) = n_T( \emptyset ) = -\infty$, the cases for one symbol and empty sequence.

**Definition**: The set of all sequences in $T$ is denoted as $\mathcal{S}_T = \{ S | S \text{ is sequence in } T \}$

Note that if $abcd$ is a sequence in $T$, then also $ab$, $abc$, $bcd$, $ad$ and all other subtraces are sequences in $T$. 

**Definition**: A sequence $S$ is called a **maximal sequence in $T$** if is not a combination of other sequences in $T$: $\nexists R, S' \in \mathcal{S}_T; S \neq R $ such that $\Sigma(S') = \Sigma(S) \cup \Sigma(R)$. 

**Definition**: The set of all maximal sequences in T is denoted as $\overline{ \mathcal{S}_T } = \{ S | S \text{ is maximal sequence in } T \}$

If $S=ab$ we recover the definitions of pairs: $n_T(S) = n_T(ab)$. Also, any sequence in T can be written in terms of its pairs. Therefore, all pairs properties inherits to sequences.


```python
def sequence_cardinality(S, T):
    '''
    Returns the cardinality if S=abc...z is a sequence in T, otherwise it returns -1
    '''
    # Force list
    if type(S)==type(''):
        S = list(S.strip())
        
    # two or more symbols only
    if len(S) < 2:
        return -1

    # Check all symbols are different
    if len(S) != len(set(S)):
        return -1

    intersection=[a for a in T if a in S ]
    cardinality=int(len(intersection) / len(S)  )
    return cardinality if S*cardinality==intersection else -1
```


```python
T='123abcabc4'
```


```python
sequence_cardinality('abc', T)
```




    2




```python
sequence_cardinality('ab', T)
```




    2




```python
sequence_cardinality('a', T)
```




    -1




```python
sequence_cardinality('ba', T)
```




    -1




```python
# This sequence has cardinality 0
sequence_cardinality('MNO', T)
```




    0



This sequence has $n_T(S) < 0$ because one of its symbols is not in T


```python
sequence_cardinality('abcM', T)
```




    -1




```python
sequence_cardinality('1234', T)
```




    1




```python
sequence_cardinality('abc', T)
```




    2




```python
sequence_cardinality('1234', T)
```




    1




```python
sequence_cardinality('abc', T)
```




    2



## Properties of sequences

If $S = s_1 ... s_m$ , $m \ge  2$ is a sequence in $T$, then the following properties can be verified.

**Property**: $(s_i, s_j)$ are paired in $T$ for $i \lt j$ and unpaired for $i \ge j$.

**Property**: the cardinality is equal for the sequence and its pairs. $n_T(S) = n_T(s_i,  s_j)$ for all $i \lt j$


```python
T='a1b2ca3bc4a5bc'
S='abc'
```


```python
print( "Cardinality of S in T: {}".format( sequence_cardinality(S,T) ) )
print( "Cardinality of ab in T: {}".format( pair_cardinality('a', 'b', T) ) )
print( "Cardinality of bc in T: {}".format( pair_cardinality('b', 'c', T) ) )
print( "Cardinality of ac in T: {}".format( pair_cardinality('a', 'c', T) ) )
print( "Cardinality of ba in T: {} (should be negative)".format( pair_cardinality('b', 'a', T) ) )
```

    Cardinality of S in T: 3
    Cardinality of ab in T: 3
    Cardinality of bc in T: 3
    Cardinality of ac in T: 3
    Cardinality of ba in T: -1 (should be negative)


## Lemma: Consecutive sequence order

When describing a sequence based on the pairs which lies in it, an interesting property emerges. Clearly there are exactly $m$ pairs in $S=s_1 ... s_m$ of the form $(s_i, s_m)$ because all its symbols are different bby definition. And this is applicable to any subtrace of $S$. A stronger claim can be proved, that there are no such pairs ending in $s_m$ in $T$ outside $S$ with the same cardinality.

**Lemma**: $s_j$ is the $j$-esim element of a sequence $S$ in $T$ $\iff$ there are exactly $j-1$ pairs $(x, s_j)$ paired in $T$ where $n_T(S) = n_T(x, s_j)$. All such $x$ lies inside $S$.

(proof easy but pending) **however, please study $aXYbaYXb$ before sing and dance**

Below are some examples of the lemma.


```python
T='a1b2ca3bc4a5bc'
S='abc'

pairs = pairs_in_trace(T)
```


```python
# Show all pairs in T

P=pd.DataFrame.from_dict( { a[0]+a[1]:b for a,b in pairs.items() }, orient='index', columns=['pairs'] )
P[ P['pairs'] >= 0 ].T
```




<div>
<style scoped>
    .dataframe tbody tr th:only-of-type {
        vertical-align: middle;
    }

    .dataframe tbody tr th {
        vertical-align: top;
    }

    .dataframe thead th {
        text-align: right;
    }
</style>
<table border="1" class="dataframe">
  <thead>
    <tr style="text-align: right;">
      <th></th>
      <th>23</th>
      <th>35</th>
      <th>13</th>
      <th>34</th>
      <th>25</th>
      <th>12</th>
      <th>24</th>
      <th>15</th>
      <th>45</th>
      <th>14</th>
      <th>bc</th>
      <th>ac</th>
      <th>ab</th>
    </tr>
  </thead>
  <tbody>
    <tr>
      <th>pairs</th>
      <td>1</td>
      <td>1</td>
      <td>1</td>
      <td>1</td>
      <td>1</td>
      <td>1</td>
      <td>1</td>
      <td>1</td>
      <td>1</td>
      <td>1</td>
      <td>3</td>
      <td>3</td>
      <td>3</td>
    </tr>
  </tbody>
</table>
</div>




```python
print( "Cardinality of S in T: {}".format( sequence_cardinality(S,T) ) )
```

    Cardinality of S in T: 3



```python
# All pairs ending in 'a' for S=abc
[ (x,sj,n) for (x,sj), n in pairs.items() 
 if sj == 'a' 
 and sequence_cardinality(S, T) == pair_cardinality(x, sj, T) ] 
```




    []




```python
# All pairs ending in 'b' for S=abc
[ (x,sj,n) for (x,sj), n in pairs.items() 
 if sj == 'b' 
 and sequence_cardinality(S, T) == pair_cardinality(x, sj, T) ] 
```




    [('a', 'b', 3)]




```python
# All pairs ending in 'c' for S=abc
[ (x,sj,n) for (x,sj), n in pairs.items() 
 if sj == 'c' 
 and sequence_cardinality(S, T) == pair_cardinality(x, sj, T) ] 
```




    [('b', 'c', 3), ('a', 'c', 3)]



## Complexity of getting all pairs in T

The time seems to be bounded by $O( |T|  2^{\Sigma(T)} )$ , it depends on the size of alphabet instead of the length of the traces.


```python
print('Extract all pairs: fixed length\n-------')
N=500
for i in range(1,6):
    T = list(range(100*i)) * int(N/(10*i) )
    print( "\nlength={}, symbols={}".format(len(T), 100*i))
    %time pairs_in_trace( T  )
```

    Extract all pairs: fixed length
    -------
    
    length=5000, symbols=100
    CPU times: user 1.32 s, sys: 7.27 ms, total: 1.33 s
    Wall time: 1.33 s
    
    length=5000, symbols=200
    CPU times: user 5.2 s, sys: 20.7 ms, total: 5.22 s
    Wall time: 5.24 s
    
    length=4800, symbols=300
    CPU times: user 11 s, sys: 17.8 ms, total: 11 s
    Wall time: 11 s
    
    length=4800, symbols=400
    CPU times: user 19.1 s, sys: 22.6 ms, total: 19.1 s
    Wall time: 19.1 s
    
    length=5000, symbols=500
    CPU times: user 30.8 s, sys: 22.2 ms, total: 30.8 s
    Wall time: 30.9 s



```python
print('\nExtract all pairs: fixed symbols\n-------')
S=100
for N in range(1,11):
    T = list(range(S)) * (N*10) 
    print( "\nlength={}, symbols={}".format(len(T), S))
    %time pairs_in_trace( T  )
```

    
    Extract all pairs: fixed symbols
    -------
    
    length=1000, symbols=100
    CPU times: user 268 ms, sys: 3.57 ms, total: 271 ms
    Wall time: 269 ms
    
    length=2000, symbols=100
    CPU times: user 503 ms, sys: 1.99 ms, total: 504 ms
    Wall time: 504 ms
    
    length=3000, symbols=100
    CPU times: user 752 ms, sys: 1.54 ms, total: 754 ms
    Wall time: 753 ms
    
    length=4000, symbols=100
    CPU times: user 1.02 s, sys: 2.78 ms, total: 1.03 s
    Wall time: 1.03 s
    
    length=5000, symbols=100
    CPU times: user 1.29 s, sys: 4.45 ms, total: 1.3 s
    Wall time: 1.3 s
    
    length=6000, symbols=100
    CPU times: user 1.54 s, sys: 4.27 ms, total: 1.54 s
    Wall time: 1.54 s
    
    length=7000, symbols=100
    CPU times: user 1.87 s, sys: 10.2 ms, total: 1.88 s
    Wall time: 1.89 s
    
    length=8000, symbols=100
    CPU times: user 2.07 s, sys: 6.73 ms, total: 2.08 s
    Wall time: 2.08 s
    
    length=9000, symbols=100
    CPU times: user 2.29 s, sys: 5.83 ms, total: 2.29 s
    Wall time: 2.3 s
    
    length=10000, symbols=100
    CPU times: user 2.51 s, sys: 3.94 ms, total: 2.52 s
    Wall time: 2.52 s



```python

```

e6ecc4f118faea2e1baab6ab28fd65dc3d96f6e7
ipynb
Jupyter Notebook
notebooks/2021-refactor/2021-04-21-Simplified pairs.ipynb
jpgil/logdelay
788e9402d63cecc732822ac49a39dd961b63219f
Apache-2.0
notebooks/2021-refactor/2021-04-21-Simplified pairs.ipynb
jpgil/logdelay
788e9402d63cecc732822ac49a39dd961b63219f
Apache-2.0
2020-03-24T18:06:50.000Z
2021-05-28T16:03:39.000Z
notebooks/2021-refactor/2021-04-21-Simplified pairs.ipynb
jpgil/logdelay
788e9402d63cecc732822ac49a39dd961b63219f
Apache-2.0
Qwen/Qwen-72B
1. YES
2. YES