title: fast way to create a transition frequency table
body: <p>I have a table showing sequences of patterns, represented with the id of the sequence, and the ordered value of the consecutive patterns over several rows. patterns have all the same length but sequences have different lengths)</p>
  <pre><code>patterns_seq_a &lt;- c(&quot;ABC&quot;, &quot;BCD&quot;, &quot;ABC&quot;, &quot;CBA&quot;)
  patterns_seq_b &lt;- c(&quot;BCD&quot;, &quot;BCC&quot;, &quot;BAC&quot;, &quot;ABC&quot;, &quot;BCD&quot;)
  patterns_seq_c &lt;- c(&quot;ABC&quot;, &quot;ABC&quot;)
  sequence_df &lt;- data.frame(sequence_id = c(rep(&quot;a&quot;, length(patterns_seq_a)),
                           rep(&quot;b&quot;, length(patterns_seq_b)),
                           rep(&quot;c&quot;, length(patterns_seq_c))),
                    pattern = c(patterns_seq_a, patterns_seq_b, patterns_seq_c))
  </code></pre>
  <p>and I'm trying to count the frequency from one pattern to another over all the sequences.
  (and ultimately will build a probability of transitions from the frequency table)
  so for example looking at the transition from &quot;CBA&quot; to &quot;BCD&quot; its frequency over all sequences would be 0 (NB the row 4 and 5 don't belong to the same sequence).<br />
  The end result would have the form of:</p>
  <pre><code>unique_patterns &lt;- unique(sequence_df$pattern)
  result &lt;- data.frame(matrix(0, ncol = length(unique_patterns), nrow = length(unique_patterns)))
  colnames(result) &lt;- unique_patterns
  rownames(result) &lt;- unique_patterns
  </code></pre>
  <p>(but could also be a hash pattern -&gt; pattern -&gt; frequency if it has to)</p>
  <p>On the web I've found a solution based on concatenations of sequences then greps but I it's unusable as it's too slow (profvis blames the greps). Something on the lines of this:</p>
  <pre><code>freq_table &lt;- c()
  
  for (start_pattern in unique_patterns) {
    for (end_pattern in unique_patterns) {
      transition_pattern &lt;- paste0(start_pattern, ',', end_pattern)
      sequence_holding_transition &lt;- concat_sequence_df[grep(transition_pattern, concat_sequence_df$patterns_sequence),]
      if (nrow(sequence_holding_transition) &lt; 1) {
        transition_frequency &lt;- c(transition_pattern, 0)
      } else {
        concat_sequence_holding_transition &lt;-  paste0(sequence_holding_transition$patterns_sequence, collapse = &quot;,&quot;, sep=&quot;/&quot;)
        transition_pattern_positions &lt;- gregexpr(pattern = transition_pattern, text = concat_sequence_holding_transition)[[1]]
        transition_frequency &lt;- c(transition_pattern, length(transition_pattern_positions))
      }
      freq_table &lt;- rbind(freq_table, transition_frequency)
    }
  }
  
  
  frequency_table &lt;- data.frame(pattern_transition = freq_table[, 1], counts = freq_table[, 2])
  frequency_table$pattern.from &lt;- sapply(strsplit(as.character(frequency_table$pattern_transition), &quot;,&quot;), `[`, 1)
  frequency_table$pattern.to &lt;- sapply(strsplit(as.character(frequency_table$pattern_transition), &quot;,&quot;), `[`, 2)
  
  frequency_table &lt;- t(matrix(as.numeric(as.character(frequency_table$counts)), ncol=length(unique_patterns), nrow=length(unique_patterns)))
  colnames(frequency_table) &lt;- unique_patterns
  rownames(frequency_table) &lt;- unique_patterns
  </code></pre>
  <p>I haven't been able to vectorize it and those greps are really slow in any case. I tried parallelizing it but it's still too slow.<br />
  Would someone have a lightning fast solution of building this frequency table?<br />
  I don't really care about the code sample, it's just here to show an example of a - unusable- solution.</p>
  <p>Thanks!</p>
  <p>UPDATE:</p>
  <p>please find bellow the expected output if I know how to count.<br />
  To have lines with no transitions (such as &quot;CBA&quot; to &quot;XXX&quot;) dropped is acceptable, and ofc it doesn't matter the actual type of the structure:</p>
  <pre><code>structure(
    list(
      ABC = c(1, 1, 0, 1, 0),
      BAC = c(0, 0, 1, 0, 0),
      BCC = c(0, 0, 0, 1, 0),
      BCD = c(2, 0, 0, 0, 0),
      CBA = c(1, 0, 0, 0, 0)
    ),
    row.names = c(&quot;ABC&quot;, &quot;BAC&quot;, &quot;BCC&quot;, &quot;BCD&quot;, &quot;CBA&quot;),
    class = &quot;data.frame&quot;
  )
  </code></pre>