News for hackers. Stuff that matters.
Re:Compressing Scrabble Dictionaries by binarymax on Wednesday June 04, 2014 @07:49AM (#7845019)
I'm not really a data structures guy, but I love anagrams. When i wrote the anagramica API, the simplest way that I could come up with a fast search was this:

    - Take a word and sort its characters.
    - Add it to a dictionary where the key is the sorted characters and the value is the word.
    - If the sorted characters already exist in the dictionary then add it to the list of words for the same key.
This gives O(log n) when you give it a list of letters and you need to find all the possible words.

What benefits do GADDAG offer over the above?

Re:Compressing Scrabble Dictionaries by lifthrasiir on Wednesday June 04, 2014 @08:20AM (#7845116)
Since finding a set of possible moves given the current Scrabble board is not quite equal to finding anagrams. To make a move in Scrabble you need to find words that, for example, have both E and L characters which are separated by two other letters (i.e. /^.{0,}E..L.{0,}$/) when the board contains a row or column with the same pattern (E, followed by two spaces and then L). A simple anagram list cannot efficiently search for such patterns.
Re:Compressing Scrabble Dictionaries by binarymax on Wednesday June 04, 2014 @08:29AM (#7845156)
Thanks, this makes perfect sense. It probably also accounts for the blank tile in scrabble. Still seems like a hybrid approach could be done to avoid that huge data structure. I'll do some more reading :)
Re:Compressing Scrabble Dictionaries by nathell on Wednesday June 04, 2014 @08:40AM (#7845194)
The thing is that it's not huge. A packed in-memory representation should still be easily traversable and take up less than the space of a plain list of words. See also http://sun.aei.polsl.pl/~mciura/publikacje/lexicon.pdf for more ideas about in-memory lexicon representation.
Re:Compressing Scrabble Dictionaries by nathell on Wednesday June 04, 2014 @08:26AM (#7845143)
When you are building a Scrabble engine and need to construct the list of potential moves, GADDAGs come in handy as you are able to "cast" your search from subgraphs "anchored" at letters already on board.

A sample implementation (in not very idiomatic Clojure, not touched in years, and using DAWGs instead of GADDAGs): https://github.com/nathell/spleen/blob/master/src/pl/danielj...

Re:Compressing Scrabble Dictionaries by emillon on Wednesday June 04, 2014 @08:24AM (#7845129)
I believe that there is no benefit in using a GADDAG. Finding an anagram is an easier problem as you know that you will use all the letters, so sorting them is the optimal solution. But this method does not work with scrabble since you would have (at least) to find all anagrams of all subsets, which adds an exponential step.
Re:Compressing Scrabble Dictionaries by dbaupp on Wednesday June 04, 2014 @08:22AM (#7845123)
In O(log n), what is n? The number of characters? I would've thought that was O(n log n) (due to the sort).
Re:Compressing Scrabble Dictionaries by binarymax on Wednesday June 04, 2014 @08:27AM (#7845150)
Yes good point, allow me to clarify. n is the number of keys in the dictionary (log n for the binary search). I suppose yes it is probably the more complex O(n log n) to sort the letters before the search.
Re:Compressing Scrabble Dictionaries by bradleyjg on Wednesday June 04, 2014 @11:53AM (#7846292)
If n is the number of keys in the dictionary, then the whole procedure would not be O(n log n), it'd be O(m log n) where m is the number of letters. Given that n >> m, I would think your original statement is correct.
Re:Compressing Scrabble Dictionaries by dbaupp on Wednesday June 04, 2014 @07:22PM (#7849123)
Oh, so I guess it is strictly O(m log m + log n) if m is the number of letters. You can theoretically get it to be O(m log m) using a hashmap (makes lookups O(1)) or trie (lookups are O(m)).
Re:Compressing Scrabble Dictionaries by emillon on Wednesday June 04, 2014 @08:26AM (#7845140)
n is the number of words in the dictionary.