title: Efficient string similarity grouping
body: <p><strong>Setting</strong>:
  I have data  on people, and their parent's names, and I want to find siblings (people with identical parent names).</p>
  
  <pre><code> pdata&lt;-data.frame(parents_name=c("peter pan + marta steward",
                                   "pieter pan + marta steward",
                                   "armin dolgner + jane johanna dough",
                                   "jack jackson + sombody else"))
  </code></pre>
  
  <p>The expected output here would be a column indicating that the first two observations belong to family X, while the third and fourth columns are each in a separate family. E.g:</p>
  
  <pre><code>person_id    parents_name                           family_id
  1            "peter pan + marta steward",           1
  2            "pieter pan + marta steward",          1
  3            "armin dolgner + jane johanna dough",  2
  4            "jack jackson + sombody else"          3
  </code></pre>
  
  <p><strong>Current approach</strong>:
  I am flexible regarding the distance metric. Currently, I use Levenshtein edit-distance to match obs, allowing for two-character differences. But other variants such as "largest common sub string" would be fine if they run faster.</p>
  
  <p>For smaller subsamples I use <code>stringdist::stringdist</code> in a loop or <code>stringdist::stringdistmatrix</code>, but this is getting increasingly inefficient as sample size increases.</p>
  
  <p>The matrix version explodes once a certain sample size is used. My terribly inefficient attempt at looping is here:</p>
  
  <pre><code>#create data of the same complexity using random last-names
  #(4mio obs and ~1-3 kids per parents) 
  pdata&lt;-data.frame(parents_name=paste0(rep(c("peter pan + marta ",
                                  "pieter pan + marta ",
                                  "armin dolgner + jane johanna ",
                                  "jack jackson + sombody "),1e6),stringi::stri_rand_strings(4e6, 5)))
  
  for (i in 1:nrow(pdata)) {
    similar_fatersname0&lt;-stringdist::stringdist(pdata$parents_name[i],pdata$parents_name[i:nrow(pdata)],nthread=4)&lt;2
    #[create grouping indicator]
  }
  </code></pre>
  
  <p><strong>My question</strong>: There should be substantial efficiency gains, e.g. because I could stop comparing strings once I found them to sufficiently different in something that is easier to assess, eg. string length, or first word. The string length variant already works and reduces complexity by a factor ~3. But thats by far too little. Any suggestions to reduce computation time are appreciated.</p>
  
  <p><strong>Remarks</strong>:</p>
  
  <ul>
  <li>The strings are actually in unicode and not in the Latin alphabet (Devnagari)</li>
  <li>Pre-processing to drop unused characters etc is done</li>
  </ul>