title: How do I group similar strings in R?
body: <p>I have a database with ~5,000 locality names, most of which are repetitions with typos, permutations, abreviations, etc. I would like to group them by similarity, to speed up further processing. The best would be to convert each variation into a "platonic form", and put two columns side by side, with the original and platonic forms. I've read about <a href="http://en.wikipedia.org/wiki/Multiple_sequence_alignment" rel="nofollow">Multiple sequence alignment</a>, but this seems to be mostly used in bioinformatics, for sequences of DNA/RNA/Peptides. I'm not sure it will work well with names of places. <del>Anyone knows of a library that helps me to do it in R? Or which of the many algorithm variations might be easier to adapt?</del></p>
  
  <p>EDIT: How do I do that in R? Up to now, I'm using adist() function, which gave me a matrix of distances between each pair of strings (although it don't treat translocations the way I think it should, see comment below). The next step I'm working right now is to turn this matrix into a grouping/clustering of similar enough values. Thanks in advance!</p>
  
  <p>EDIT: To solve the translocations problem, I did a small function that gets all the words with more than 2 characters, sort them, removes any punctuation left, and paste them again into a string.</p>
  
  <pre><code>sep &lt;- function(linha) {
      resp &lt;- strsplit(linha," |/|-")
      resp &lt;- unlist(resp)
      resp &lt;- gsub(",|;|\\.","",resp)
      resp &lt;- sort(resp[which(nchar(resp) &gt; 2)])
      paste0(resp,collapse=" ")
  }
  </code></pre>
  
  <p>Then I apply this over all lines of my table</p>
  
  <pre><code>locs[,9] &lt;- apply(locs,1,function(x) sep(x[1])) # 1=original data; 9=new data
  </code></pre>
  
  <p>and finally apply adist() to create the similarity table.</p>