Timeline for Match dictionary to misspelled word, corner cases
Current License: CC BY-SA 3.0
14 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Feb 2, 2017 at 21:10 | comment | added | paparazzo | I don't know how to say it any it any clearer. As it processes a match the distance goes up and down so you can't just just give up at a threshold. | |
| Feb 2, 2017 at 21:07 | comment | added | D.W.♦ | @Paparazzi, I understand that, but as I said, I don't see why that is a problem. Perhaps I don't understand what you are trying to say in your comment. | |
| Feb 2, 2017 at 21:06 | comment | added | paparazzo | I am commenting on "early out" version. | |
| Feb 2, 2017 at 21:01 | comment | added | D.W.♦ | @Paparazzi, I don't see why that is a problem. Each time you compute an edit distance for some pair of words (using the Wagner-Fischer algorithm), you know what value of $k$ to use. It doesn't need to be the same for every pair of words -- you can dynamically adjust. | |
| Feb 2, 2017 at 20:44 | comment | added | Nyfiken Gul | @ Paparazzi, Yea exactly, I think it can only change +/-1 between adjacent matrix positions but that makes it hard enough to eliminate any redundancy.. | |
| Feb 2, 2017 at 20:37 | comment | added | paparazzo | I have tired a > k but the problem I had is the distance can come down as it processes the comparison so you don't really know until the end. | |
| Feb 2, 2017 at 19:46 | comment | added | Nyfiken Gul | Hard to explain since I'm on mobile but I'm making use of the fact that the matrix of L(x, y) and L(x, z) share the same first P rows if the first P letters of y and z match | |
| Feb 2, 2017 at 19:44 | comment | added | Nyfiken Gul | I wonder if I maybe could make use of the 'triangle property' somehow? I.e. L(x, y) <= L(z, y) + L(z, x). Maybe I can run that against the least-distance-matches of the previous w to get an upper bound for L(x, di)? | |
| Feb 2, 2017 at 19:43 | comment | added | D.W.♦ | @NyfikenGul, I don't understand what your last comment is saying or what you are responding to or how that relates to my answer. I'm not seeing a clash with the second trick in my answer. | |
| Feb 2, 2017 at 19:30 | comment | added | Nyfiken Gul | "For a given word w1, find the all matches with the least editing distance from it in the dictionary D (Levenshtein distance).". Yea, I've played around with that thought aswell - though I'm afraid it'll clash with one of the other 'mechanisms' I've implemented, ehich is that if two words D[i] and D[i+1] share the same first P letters I only need to build the matrix for D[i+1] from the (P+1)th row down (meaning I can 'reuse' the old one to some extent). Hmm, this is a really tricky one.. | |
| Feb 2, 2017 at 19:14 | comment | added | D.W.♦ | @NyfikenGul, huh, I didn't see that anywhere in the question. Anyway, see edited answer for another trick (which is compatible with finding all words at the same distance). | |
| Feb 2, 2017 at 19:14 | history | edited | D.W.♦ | CC BY-SA 3.0 |
added 520 characters in body
|
| Feb 2, 2017 at 19:10 | comment | added | Nyfiken Gul | Thanks for your answer. Yes, I know, although my approach to edit-distances of 1 is as I wrote above (I generate all of them). The problem with just jumping out of the loop when I've found a one-distamce word is that I need to output all one-distance words. Thanks for the tips, have tried looking up stuff online bit will definitely try harder then! :) | |
| Feb 2, 2017 at 17:37 | history | answered | D.W.♦ | CC BY-SA 3.0 |