Consider a voice recording split into it's phonemes as our sample $S=(s_1,...,s_k) \in \Omega = P^k$. The number of phonemes is $|P| = 40$. Then I have a word $w = (w_1,...,w_n) \in P^n$. I want to analyze with what chance I can reconstruct $w$ by just cutting out parts of the sample and chaining them together in the right order. I assume that $p(s_i=p) = x_p$ for $i=1,..,n$ and $p \in P$, i.e. that each sample symbol $s_i$ is chosen independently from the others and the distribution of the phonemes is given by $x_j$.
First, I wanted to know what the probability is that one can reconstruct a word "in principle" by taking single phonemes from the sample and chaining them in the right order. One can easily calculate this by naively iterating through all possible samples. This is obviously not feasable for larger k. Instead, I take the set $X = \{w_i : 1 \leq i \leq n\}$ of all required phonemes. Let $R_A^k$ be all the samples of length k where all phonemes in $A \subseteq X$ are contained in the sample (i.e. $A$ is reconstructable). Note that $p(S \in R_X^k)$ is my answer. The states $Q=\{R_A : A \subseteq X\}$ form a Bayesian Network where the transitions represent going from $k$ to $k+1$. For instance, if one is in state $R_A$ one ends up in $R_{A \cup \{p\}}$ with probability $x_p$ for $p \in X \setminus A$. Now I can iteratively calculate the probability of $w$ being reconstructable in $O(k \cdot 2^{|X|})$ and this suffices for my data (in one dataset, the biggest $n$ is $10$).
Now, I want to know the probability for reconstructing the word using $c$ substrings in $S$. For instance, if I want to reconstruct the word $w=$ACEG and I have the sample $S=$CEGBAF then I can reconstruct $w$ as A+CEG using 2 substrings. I try to group all samples into relevant states so that I can iteratively compute over k like before. My idea is to save the longest available substring in each position of w, as well as the start position and length of the longest streak in S (the largest substring at the end of $S$ that is in $w$), so $q=((q_1,...,q_n),a,l)$.
For example: $w=$ABCDE and the state $q=((2,1,2,1,0),3,1)$. This means we gathered two substrings "AB" and "CD", the last streak in S was "C".
Naively there are $n! \cdot \frac{n \cdot (n+1)}{2}$ such states. One can cut down this number by observing constraints in $q$: $(a=0 \wedge l=0) \vee (0 \lt l \leq q_a \lt n-a)$)
I implemented this in python (Note that string indexing starts at zero here):
#!/usr/bin/python
import itertools
def enum_states(n):
states = [(i,) for i in xrange(0,n+1)]
for i in xrange(n-1):
states = [q + (x,) for q in states for x in xrange(max(0, q[-1]-1), n - i)]
states = [(q, a, l) for q in states for a in xrange(0, n) for l in xrange(0, n-a+1) if (a==0 and l==0) or (l > 0 and l <= q[a] and q[a] < n-a)]
return states
def print_states(states):
i = 0
for q in states:
tup = q[0]
a = q[1]
l = q[2]
tup = [str(e) for e in tup]
if l == 0:
print ''.join(tup) + " ",
else:
print ''.join(tup[:a]) + "<" + ''.join(tup[a:a+l]) + ">" + ''.join(tup[a+l:]),
i += 1
if i%8 == 0:
print
states = enum_states(10)
#print_states(states)
print len(states)
For $n=10$ there are $|Q|=978926$ states! My original goal was to compute the transition matrix from the bayesian network. There are at most $(n+1)$ transitions from each state (one for each phoneme in $w$ and one for all phonemes not in $w$). The transition matrix $M$ would therefore be very sparse and could be stored efficiently in a CSR Matrix. However iterating over k going one step at a time would be too slow for large k. Instead one can calculate $M^k$ using fast exponentiation. But the resulting matrix would not be sparse any more and just be too big to work with.
I hope I could articulate my problem clearly. To sum up: How can I compute the probability of a word being reconstructable using $c$ substrings from a sample of length $k$ efficiently? Am I missing something? Maybe there's a smarter way of doing this.
