2 ms·
Thanks for doing the legwork! Sadly, it turns out our genius idea doesn't work so well - the infamous cholecystoduodenostomy/duodenocholecystostomy is in joint
by twic 10y ago
Thanks for doing the legwork!
Sadly, it turns out our genius idea doesn't work so well - the infamous cholecystoduodenostomy/duodenocholecystostomy is in joint fourth place, and the scarcely any better duodenopancreatectomy/pancreatoduodenectomy is joint second.
mjd's key insight was that good anagrams are ones where all the letters are thoroughly scrambled; both of the cases above are ones where large blocks of letters remain intact. I don't know if you've had scrambled eggs where large lumps of white or yolk remain intact, but i have, and they're vile.
So, anyway, perhaps a better edit distance metric is one which allows cut-and-paste of whole blocks as an edit, since it would give those words much lower scores. My years of DNA-hunching immediately led me to think of sequence alignment algorithms, because that kind of cut-and-paste is exactly what happens in DNA:
https://en.wikipedia.org/wiki/Smith%E2%80%93Waterman_algorithm https://en.wikipedia.org/wiki/Smith%E2%80%93Waterman_algorit...
https://en.wikipedia.org/wiki/BLAST https://en.wikipedia.org/wiki/BLAST
But i'm not sure those algorithms are much good, because they model the editing as deleting, inserting, and modifying runs of letters, rather than moving them around.
Next, i thought of compression, because that often works by finding repeated runs of characters, and also i don't really know any other areas of string algorithms. What if you concatenated two strings, compressed them using LZ77, and measured the amount of compression? Or what if you did it with something simpler and more local, like Predictor [1]? Could you use the Burrows–Wheeler transform?
[1] https://tools.ietf.org/html/rfc1978 https://tools.ietf.org/html/rfc1978 - your daily obscure blast from the past!
- tyingq 10y agoI had the best luck with "Anagrams by percent of string not part of longest common substring, then length" The top-to-bottom ranking isn't quite right...need some better way to push down short words, but it does seem to put most of the good stuff near the top. https://gist.github.com/anonymous/ec28b75fb6c841b56def8eefec813656 https://gist.github.com/anonymous/ec28b75fb6c841b56def8eefec...