4 ms·

Sorting by edit distance might be interesting, too.

twic 10y ago
I also immediately thought of edit distance as the obvious metric, and it has a reasonably simple and efficient algorithm too: https://en.wikipedia.org/wiki/Levenshtein_distance https://en.wikipedia.org/wiki/Levenshtein_distance But then i realised that it was only obvious to me because i spent years hunched over a computer crunching DNA sequences. I'd also be interested in normalising edit distance by length somehow. It's no coincidence that higher-scoring words tend to be longer.
- tyingq 10y ago
  I was curious, so I rescored his list using Levenshtein. No normalization for long words though: https://gist.github.com/anonymous/431b163b2a2d532bfd0a3bdcc711f7b3 https://gist.github.com/anonymous/431b163b2a2d532bfd0a3bdcc7... I sorted it reverse so that the interesting pairs would be on top. Compare to his original scored list, here: http://pic.blog.plover.com/lang/anagram-scoring/anagrams-scored.txt http://pic.blog.plover.com/lang/anagram-scoring/anagrams-sco...
  - deleted 10y ago
    [deleted]
  - 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 ago
      I 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...

twic 10y ago

I also immediately thought of edit distance as the obvious metric, and it has a reasonably simple and efficient algorithm too: https://en.wikipedia.org/wiki/Levenshtein_distance https://en.wikipedia.org/wiki/Levenshtein_distance But then i realised that it was only obvious to me because i spent years hunched over a computer crunching DNA sequences. I'd also be interested in normalising edit distance by length somehow. It's no coincidence that higher-scoring words tend to be longer.

tyingq 10y ago
I was curious, so I rescored his list using Levenshtein. No normalization for long words though: https://gist.github.com/anonymous/431b163b2a2d532bfd0a3bdcc711f7b3 https://gist.github.com/anonymous/431b163b2a2d532bfd0a3bdcc7... I sorted it reverse so that the interesting pairs would be on top. Compare to his original scored list, here: http://pic.blog.plover.com/lang/anagram-scoring/anagrams-scored.txt http://pic.blog.plover.com/lang/anagram-scoring/anagrams-sco...
- deleted 10y ago
  [deleted]
- 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 ago
    I 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...