title: Real world typo statistics?
body: <p>Where can I find some real world typo statistics?  </p>
  
  <p>I'm trying to match people's input text to internal objects, and people tend to make spelling mistakes.<br>
  There are 2 kinds of mistakes:  </p>
  
  <ol>
  <li><code>typos</code> - "Helllo" instead of "Hello" / "Satudray" instead of "Saturday" etc.  </li>
  <li><code>Spelling</code> - "Shikago" instead of "Chicago" </li>
  </ol>
  
  <p>I use  <a href="http://en.wikipedia.org/wiki/Damerau%E2%80%93Levenshtein_distance" rel="noreferrer">Damerau-Levenshtein distance</a> for the typos and <a href="http://en.wikipedia.org/wiki/Double_Metaphone" rel="noreferrer">Double Metaphone</a> for spelling (Python implementations <a href="http://mwh.geek.nz/2009/04/26/python-damerau-levenshtein-distance/" rel="noreferrer">here</a> and <a href="http://atomboy.isa-geek.com/plone/Members/acoil/programing/double-metaphone/metaphone.py/view" rel="noreferrer">here</a>).</p>
  
  <p>I want to focus on the Damerau-Levenshtein (or simply <code>edit-distance</code>). The textbook implementations always use '1' for the weight of deletions, insertions substitutions and transpositions. While this is simple and allows for nice algorithms it doesn't match "reality" / "real-world probabilities".  </p>
  
  <p>Examples:   </p>
  
  <ul>
  <li>I'm sure the likelihood of "Helllo" ("Hello") is greater than "Helzlo", yet they are both 1 edit distance away.</li>
  <li>"Gello" is closer than "Qello" to "Hello" on a QWERTY keyboard.</li>
  <li>Unicode transliterations: What is the "real" distance between "München" and "Munchen"?</li>
  </ul>
  
  <p>What should the "real world" weights be for deletions, insertions, substitutions, and transpositions?  </p>
  
  <p>Even <a href="http://norvig.com/spell-correct.html" rel="noreferrer">Norvig's very cool spell corrector</a> uses non-weighted edit distance.</p>
  
  <p>BTW- I'm sure the weights need to be functions and not simple floats (per the above 
  examples)...</p>
  
  <p>I can adjust the algorithm, but where can I "learn" these weights? I don't have access to <a href="http://www.google.com/jobs/britney.html" rel="noreferrer">Google-scale data</a>...  </p>
  
  <p>Should I just guess them?</p>
  
  <p><strong>EDIT - trying to answer user questions:</strong></p>
  
  <ul>
  <li>My current non-weighted algorithm fails often when faced with typos for the above reasons. "Return on Tursday": every "real person" can easily tell Thursday is more likely than Tuesday, yet they are both 1-edit-distance away! (Yes, I do log and measure my performance).</li>
  <li>I'm developing an NLP Travel Search engine, so my dictionary contains ~25K destinations (expected to grow to 100K), Time Expressions ~200 (expected 1K), People expressions ~100 (expected 300), Money Expressions ~100 (expected 500), "glue logic words" ("from", "beautiful", "apartment") ~2K (expected 10K) and so on...</li>
  <li>Usage of the edit distance is different for each of the above word-groups. I try to "auto-correct when obvious", e.g. 1 edit distance away from only 1 other word in the dictionary. I have <strong>many</strong> other hand-tuned rules, e.g. Double Metaphone fix which is not more than 2 edit distance away from a dictionary word with a length > 4... The list of rules continues to grow as I learn from real world input.</li>
  <li>"How many pairs of dictionary entries are within your threshold?": well, that depends on the "fancy weighting system" and on real world (future) input, doesn't it? Anyway, I have extensive unit tests so that every change I make to the system only makes it better (based on past inputs, of course). Most sub-6 letter words are within 1 edit distance from a word that is 1 edit distance away from another dictionary entry.</li>
  <li>Today when there are 2 dictionary entries at the same distance from the input I try to apply various statistics to better guess which the user meant (e.g. Paris, France is more likely to show up in my search than Pārīz, Iran).</li>
  <li>The cost of choosing a wrong word is returning semi-random (often ridiculous) results  to the end-user and potentially losing a customer. The cost of not understanding is slightly less expensive: the user will be asked to rephrase.</li>
  <li>Is the cost of complexity worth it? Yes, I'm sure it is. You would not believe the amount of typos people throw at the system and expect it to understand, and I could sure use the boost in <a href="http://en.wikipedia.org/wiki/Precision_and_recall" rel="noreferrer">Precision and Recall</a>.</li>
  </ul>