title: Dictionary-based keyword detection
body: <p>I'd like to identify keywords from scanned documents with possible OCR errors. Based on a list of keywords and confidence values for each character and its alternatives of the scanned document, how can I develop an algorithm for reliable identifying keywords?</p>
  
  <p>For OCR I am using Tesseract, which provides confidence values for each character and its best alternatives. So for every word I have a list like this:</p>
  
  <pre><code> Word=order
   [0] o (93%) [alts: 0 (90%), c (83%), e (82%)]
   [1] r (96%)
   [2] d (96%)
   [3] e (90%) [alts: a (75%)]
   [4] r (95%) 
  </code></pre>
  
  <p>another example including OCR errors: </p>
  
  <pre><code> Word=PaYmeHI (Payment would be correct)
   [0] P (81%) [alts: p (78%), D (68%)]
   [1] a (76%) [alts: 3 (73%), e (63%), ö (61%)]
   [2] Y (87%) [alts: V (86%)]
   [3] m (83%) 
   [4] E (71%) [alts: € (79%), 9 (72%), % (67%), e (65%), B (64%), G (64%)]
   [5] H (76%) [alts: n (83%), D (74%), N (70%), ü (69%)]
   [6] I (75%) [alts: t (69%), { (67%), 1 (65%), i (61%)]
  </code></pre>
  
  <p>As you can see, tesseract doensn't always choose the result with the highest percentage (4, 5). </p>
  
  <p>From skimming through the result it appears, that most characters having a value above 90% are correct. However, bad results don't necessarily contain the correct character in the list of alternatives (see [2], which should be a lower case <code>y</code>. </p>
  
  <p>Currently I am getting a list of candidates by using Levenshtein distance and String length. Furthermore, I am excluding keywords where <code>lev2 &gt; 3</code>. This is just hardcoded, as I am still looking for a good way to determine a threshold. </p>
  
  <pre><code>      int lev = getLevenshteinDistance(keyword, s);
        int lev2 = getLevenshteinDistance(keyword.toLower(), s.toLower());
        int len = Math.abs(keyword.length - s.length); 
        int x = lev + lev2 + len;
  </code></pre>
  
  <p>I am sorting the list of keywords by <code>x</code>, to get the most likely results. </p>
  
  <p>So first, I am looking for a way to determine a good threshold based on the OCR result and string length. A short string will require a lower threshold than a larger one and a solid OCR result too. Take the example from above: For the word order <code>lev2 &lt;= 1</code>, would be sufficient, whereas for <code>payment</code> at least <code>lev2 &lt;= 3</code> should be calculated. </p>
  
  <p>Second, how can I decide if one of the candidates left actually matches the word? In case <code>lev == 0</code> and when the confidence values of all characters are <code>&gt;= 90</code> it is obvious. But considering bad OCR results, what algorithm can I develop that also includes alternative OCR choices?</p>