title: Efficient sub-string search over large dataset
body: <p>I have a large dataset <code>tPro1</code> (~500k points).  Seen below, the variable of interest is <code>tPro1$Path</code>.</p>
  
  <pre><code>      Path                                  Row      rm                                              
  1  &gt;root&gt;aaaa&gt;bbbb&gt;cccc&gt;dddd&gt;hello         1        TRUE
  2  &gt;root&gt;aaaa&gt;bbbb&gt;cccc&gt;dddd&gt;greetings     2        TRUE
  3  &gt;root&gt;aaaa&gt;bbbb&gt;cccc&gt;dddd&gt;example       3        TRUE
  4  &gt;root&gt;iiii&gt;jjjj&gt;kkkk&gt;llll&gt;mmmm          4        TRUE
  5  &gt;root&gt;iiii&gt;jjjj&gt;kkkk&gt;nnnn&gt;testing       5        TRUE
  </code></pre>
  
  <p>I also have a smaller dataset, let's call it <code>Sub1</code>, of a couple dozen or so dataponts.  It has higher level paths than <code>tPro1</code>.      </p>
  
  <pre><code>     [1] "&gt;root&gt;aaaa&gt;bbbb&gt;cccc&gt;dddd"
       [2] "&gt;root&gt;aaaa&gt;bbbb&gt;eeee&gt;ffff"
       [3] "&gt;root&gt;aaaa&gt;bbbb&gt;gggg&gt;hhhh" 
       [4] "&gt;root&gt;iiii&gt;jjjj&gt;kkkk&gt;llll&gt;mmmm"
       [5] "&gt;root&gt;iiii&gt;jjjj&gt;kkkk&gt;nnnn" 
       [6] "&gt;root&gt;oooo&gt;pppp&gt;qqqq"
  </code></pre>
  
  <p>What I am trying to do is associate the longer paths in <code>tPro1</code> with the shorter ones in <code>Sub1</code>. <code>tPro1</code> is a copy of some key info from <code>Pro0</code>.  Output <code>Pro0</code> would be</p>
  
  <pre><code>          Path                                  Short_path                                                    
  1  &gt;root&gt;aaaa&gt;bbbb&gt;cccc&gt;dddd&gt;hello         &gt;root&gt;aaaa&gt;bbbb&gt;cccc&gt;dddd
  2  &gt;root&gt;aaaa&gt;bbbb&gt;cccc&gt;dddd&gt;greetings     &gt;root&gt;aaaa&gt;bbbb&gt;cccc&gt;dddd
  3  &gt;root&gt;aaaa&gt;bbbb&gt;cccc&gt;dddd&gt;example       &gt;root&gt;aaaa&gt;bbbb&gt;cccc&gt;dddd
  4  &gt;root&gt;iiii&gt;jjjj&gt;kkkk&gt;llll&gt;mmmm          &gt;root&gt;iiii&gt;jjjj&gt;kkkk&gt;llll&gt;mmmm
  5  &gt;root&gt;iiii&gt;jjjj&gt;kkkk&gt;nnnn&gt;testing       &gt;root&gt;iiii&gt;jjjj&gt;kkkk&gt;nnnn
  </code></pre>
  
  <p>I've written a loop that for each path in <code>Sub1</code>, grepl's each <code>tPro1</code> to see if it is a substring.  For 500k*24 points, this would be a very inefficient process, so I've tried some optimizations:</p>
  
  <ol>
  <li>Note <code>tPro1$rm</code>.  When a substring is found, this is set to false.  They are removed/skipped afterwards to save pointless recheck time. 
  
  <ol start="2">
  <li>A Path s may appear multiple times in <code>tPro1</code>.  Thus when a valid substring p is found for s, instead of continuing to grepl, the algorithm goes through the dataset and looks for all unchecked instances of s.</li>
  </ol></li>
  </ol>
  
  <p>My code is </p>
  
  <pre><code>start.time &lt;- Sys.time()
  
  for (p in Sub1$Path) {
    for (i in 1:NROW(tPro1)) {
      if (tPro1[i,3]) {
        if (grepl(p, tPro1[i,1], fixed=TRUE)) {
          # Replace all of subpath 
          for (j in i:NROW(tPro1)) {
            if (tPro1[j,1] == tPro1[i,1]) {
              Pro0[tPro1[j,2],2] &lt;- p
              tPro1[j,3] &lt;- FALSE
            }
          }
        }
      }
    }
    v &lt;- unlist(tPro1[,3])
    tPro1 &lt;- tPro1[v,]
  }
  
  end.time &lt;- Sys.time()
  time.taken &lt;- end.time - start.time
  time.taken
  </code></pre>
  
  <p>Processing the full dataset does not halt in human time (on my machine at least).  For illustrative purposes, doing batches of 1000 at a time (reduced <code>tPro1</code>) takes 46secs. 2000 takes 1 mins, 3000:1.4mins.  </p>
  
  <p>Any glaring improvements that could be made, or is it just the nature of the problem?</p>
  
  <p>EDIT: There are around 54k unique long paths, and also not all of the long paths have a corresponding short path (eg in <code>tPro1</code> there is <code>&gt;root&gt;strange&gt;path</code>, whereas in <code>sub1</code> there is no path of the form <code>&gt;root&gt;strange</code>)</p>
  
  <p>EDIT2: Following <a href="https://stackoverflow.com/users/4731848/rosscova">rosscova</a>'s answer below, the time was taken down from possibly eternity, to 279.75 seconds!</p>