Hello Doug,<br><br>*putting llvmdev in copy since they are concerned too*<br><br>I've finally got around to finish a working implementation of the typical Levenshtein Distance with the diagonal optimization.<br><br>I've tested it against the original llvm implementation and checked it on a set of ~18k by randomly generating a variation of each word and checking that both implementations would return the same result... took me some time to patch the diagonal version, but they now do.<br>
<br>I have left the older method in place, especially because I saw that it was used in FileCheck and was a bit wary of any side-effect I might introduce there.<br><br>I have thus created a new method: unsigned StringRef::levenshtein_distance(StringRef other, unsigned maxEditDistance) and replace the two uses of edit_distance in Sema\SemaLookup.cpp with it.<br>
<br>I have ditched the "AllowReplace" argument since it further complicated the logic of an already ~150 lines method for no obvious gain (as far as I could see) and I have also explicited the computations a bit by using named temporaries.<br>
<br>Unfortunately I have only a Windows machine at hand for the moment and the tests don't work that well... so I'd appreciate if anyone could check my changes.<br><br>I have done two separate patches: one for llvm (stringref-path.diff) and one for clang (sema-patch.diff), the llvm patch should be applied first of course.<br>
<br>Since it is my first time proposing a patch, I hope I have done things right :)<br><br>Regards,<br>Matthieu.<br><br><br><div class="gmail_quote">2010/12/1 Douglas Gregor <span dir="ltr"><<a href="mailto:dgregor@apple.com">dgregor@apple.com</a>></span><br>
<blockquote class="gmail_quote" style="margin: 0pt 0pt 0pt 0.8ex; border-left: 1px solid rgb(204, 204, 204); padding-left: 1ex;"><div style="word-wrap: break-word;"><br><div><div><div></div><div class="h5"><div>On Nov 21, 2010, at 11:58 AM, Matthieu Monrocq wrote:</div>
<br><blockquote type="cite">Hi Doug,<br><br><div class="gmail_quote">2010/11/9 Douglas Gregor <span dir="ltr"><<a href="mailto:dgregor@apple.com" target="_blank">dgregor@apple.com</a>></span><br><blockquote class="gmail_quote" style="margin: 0pt 0pt 0pt 0.8ex; border-left: 1px solid rgb(204, 204, 204); padding-left: 1ex;">
<div style="word-wrap: break-word;">Hi Matthieu,<div><div></div><div><div><br><div><div>On Nov 8, 2010, at 3:05 PM, Matthieu Monrocq wrote:</div><br><blockquote type="cite">Hi Doug,<br><br>We had a discussion a month ago I think about the Spell Correction algorithm which was used in CLang, notably for auto-completion, based on the Levenstein distance.<br>
<br>It turns out I just came upon this link today: <a href="http://nlp.stanford.edu/IR-book/html/htmledition/k-gram-indexes-for-spelling-correction-1.html" target="_blank">http://nlp.stanford.edu/IR-book/html/htmledition/k-gram-indexes-for-spelling-correction-1.html</a><br>
<br>The idea is to use bigrams (2-letters parts of a word) to build an index of the form (bigram > all words containing this bigram), then use this index to retrieve all the words with enough bigrams in common with the word you are currently trying to approximate.<br>
<br>This drastically reduces the set of identifiers on which computing the Levenstein distance, especially if we directly trim those which have a length incompatible anyway from the beginning. Furthermore, the result may be ordered by the number of common bigrams, and thus the Levenstein distance may be computed first on the most promising candidates in order to have the maximum edit distance drop quickly.<br>
<br>I have implemented a quick algorithm in python (~70 lines, few comments though), to test it out, and I find the results quite promising.<br><br>I have used the following corpus: <a href="http://norvig.com/big.txt" target="_blank">http://norvig.com/big.txt</a> (~6 MB) which can be found on Peter Norvig's page: <a href="http://norvig.com/spell-correct.html" target="_blank">http://norvig.com/spell-correct.html</a><br>
<br>For example, looking for the word "neaer":<br><br>Number of distinct Words from the corpus: 48911<br>Number of distinct Bigrams from the corpus: 1528<br>Number of results: [(1, 34), (2, 1133)]<br>Most promising results: (1, ['Kearney', 'NEAR', 'nearing', 'linear', 'learner', 'uneasy', 'nearest', 'neat', 'lineage', 'leaned', 'Nearer', 'Learned', 'Nearly', 'cleaner', 'cleaned', 'neatly', 'nearer', 'earned', 'n<br>
eared', 'nearly', 'learned', 'nearby', 'Nearest', 'near', 'meanest', 'earnest', 'Near', 'beneath', 'gleaned', 'Beneath', 'kneaded', 'weaned', 'Freneau', 'guineas'])<br>
<br>Or for the word "sppose":<br><br>Number of distinct Words from the corpus: 48911<br>Number of distinct Bigrams from the corpus: 1528<br>Number of results: [(1, 14), (2, 136), (3, 991)]<br>Most promising results: (1, ['disposal', 'opposed', 'opposing', 'Oppose', 'suppose', 'Dispose', 'dispose', 'apposed', 'disposed', 'oppose', 'supposed', 'opposite', 'supposes', 'Suppose'])<br>
<br><br>Do you think the method worth investigating ?<br></blockquote></div><br></div></div></div><div>Yes, I do. Typo correction performance is very important (and has historically been very poor). </div><div><br></div>
<div>Note that there are also more-efficient algorithms for computing the Levenstein distance (e.g., d*min(m, n) rather than m*n). We should also consider those.</div><div><br></div><div><span style="white-space: pre-wrap;"> </span>- Doug</div>
</div></blockquote></div><br>The diagonal optimization you are talking about seems to bring a *2 to *3 speed-up, which is quite nice, however the algorithm is tricky and I am not sure yet that I have the correct distance in every case. I am going to settle and implement some fuzzy testers this week to help find bugs in the various algorithms.<br>
</blockquote><div><br></div></div></div>Okay. Replacing our current implementation with one of the faster algorithms would be great, since that would not require any infrastructure changes at all. Just replace the existing StringRef::edit_distance and we're done.</div>
<div><div class="im"><br><blockquote type="cite">Anyway I've been exploring a few options regarding typo correction these past weeks and I now have a little ecosystem of various solutions, however I currently lack 3 things:<br>
- a real lexicon (mine is about ~18k words) --> I would appreciate if someone pointed me to a more representative lexicon, otherwise I may try and index a subset of the boost library and see what I can come up with<br>
</blockquote><div><br></div></div><div>I tend to use Cocoa.h on Mac OS, which is great for Objective-C. Boost is reasonable for C++ code.</div><div class="im"><br><blockquote type="cite">
- a real benchmark: I have no idea how to "select" good (typo-ed) words for testing / benchmarking the typo correction algorithms. I have started by always using the same word (at a distance of 1) but it clearly isn't representative and my knowledge of statistics is rather lacking so if you have an approach to suggest...<br>
</blockquote><div><br></div></div><div>Random permutations of randomly-selected words from the lexicon would be fine, I think.</div><div class="im"><br><blockquote type="cite">
- a good Trie implementation, or hints in how to implement one. A Trie seems to be the best index (quite compact yet ordered), however I only have a naive implementation at the moment.<br><br>My best concurrent so far seems to be based on CS Language theory and involves extracting the set of words recognized by two automatons, one being the Trie, which recognize all the known words, and one being crafted for the word we are looking for, and recognize all words in a certain distance. However for maximal efficiency, this requires some structures to be precomputed, and this structure grows exponentially with the distance. It works for distance 1 to 3, is already 2.8MB for distance 4 (and takes about 70s to be computed on my machine, though I suppose it would be faster to deserialize a precomputed version), and I haven't dared trying further as it seems to be a geometrical serie with a factor of ~28 !<br>
</blockquote><div><br></div></div><div>The issue with using a trie is that you have to actually build the trie. It can't be something that is maintained online, because typo correction must be zero cost unless it is needed (since most compilation runs never need typo correction). Also, performance in the presence of precompiled headers is also important: we don't want to have to construct the trie when building the precompiled header, for example.</div>
<div class="im"><br><blockquote type="cite">Would it be considered a loss to limit ourselves to words within distance min(word.length()/4+1, 3) ?<br></blockquote><div><br></div></div>I could live with that. Clang already has limits on the maximum edit distance it will accept for a typo correction.</div>
<div class="im"><div><br><blockquote type="cite">It occured to me that one transformation (the transposition of adjacent characters) was quite a common typo. I have toyed with the Damereau-Levenshtein distance but this is quite harder to implement the optmizations with it. Without it a simple transposition costs 2 transformations (one addition and one deletion) so in this case 3 is rather limiting, but still I don't know if looking much further is very interesting.<br>
</blockquote></div><div><br></div></div><div>Making transposition a 1-unit transformation would be an improvement. It can be added to the current implementation or come in with a new implementation.</div><br><div><span style="white-space: pre-wrap;"> </span>- Doug</div>
</div></blockquote></div><br>