title: How to calculate similarity between Chamber of Commerce numbers?
body: <p>I am working on an engine that does OCR post-processing, and currently I have a set of organizations in the database, including Chamber of Commerce Numbers.</p>
  
  <p>Also from the OCR output I have a list of possible Chamber of Commerce (COC) numbers.</p>
  
  <p>What would be the best way to search the most similar one? Currently I am using Levenshtein Distance, but the result range is simply too big and on big databases I really doubt it's feasibility. Currently it's implemented in Java, and the database is a MySQL database.</p>
  
  <p>Side note: A Chamber of Commerce number in The Netherlands is defined to be an 8-digit number for every company, an earlier version of this system used another 4 digits (0000, 0001, etc.) to indicate an establishment of an organization, nowadays totally new COC numbers are being given out for those.</p>
  
  <p>Example of COCNumbers:</p>
  
  <ul>
  <li>30209227</li>
  <li>02045251</li>
  <li>04087614</li>
  <li>01155720</li>
  <li>20081288</li>
  <li>020179310000</li>
  <li>09053023</li>
  <li>09103292</li>
  <li>30039925</li>
  <li>13041611</li>
  <li>01133910</li>
  <li>09063023</li>
  <li>34182B01</li>
  <li>27124701</li>
  </ul>
  
  <p>List of possible COCNumbers determined by post-processing:</p>
  
  <ul>
  <li>102537177</li>
  <li>000450093333</li>
  <li>465111338098</li>
  <li>NL90223l30416l</li>
  <li>NLﬂ0737D447B01</li>
  <li>12juni2013</li>
  <li>IBANNL32ABNA0242244777</li>
  <li>lncassantNL90223l30416l10000</li>
  <li>KvK13041611</li>
  <li>BtwNLﬂ0737D447B01</li>
  </ul>
  
  <p>A few extra notes:</p>
  
  <ul>
  <li>The post-processing picks up words and word groups from the invoice, and those word groups are being concatenated in one string. (A word group is at it says, a group of words, usually denoted by a space between them).</li>
  <li>The condition that the post-processing uses for it to be a COC number is the following: The length should be 8 or more, half of the content should be numbers and it should be alphanumerical.</li>
  <li>The amount of possible COCNumbers determined by post-processing is relatively small.</li>
  <li>The database itself can grow very big, up to 10.000s of records.</li>
  </ul>
  
  <p>How would I proceed to find the best match in general? (In this case (13041611, KvK13041611) is the best (and moreover correct) match)</p>