Kamil Dworakowski wrote:
The timing per expression however
showed something useful, 70% of the time was being spent around
determining membership in the known words dictionary (Data.Map). There
are about 30 000 items in the dictionary.
Right... Python uses hashtables while here I have a tree with log n
access time. I did not want to use the Data.HashTable, it would
pervade
my program with IO. The alternative is an ideal hashmap that never
gets
changed. This program creates a dictionary at start which then is only
being used to read from: an ideal application for the Data.PerfectHash
by Mark Wotton available on Hackage [3].
The PerfectHash is a dictionary keyed by ByteStrings, so I had to
migrate the program to use these instead of Strings. Sadly it
increased
the running time to 59s. Adding PerfectHash brought the running time
down to 39s. I have done some code restructuring with the view to
publishing it, which brought the running time up to 45s. The code is
available on patch-tag [4] for anyone to scrutinize and hopefully
point
out mistakes (it uses big.txt and misspellings file which are linked
to
from Norvig's page [1]).
You should also consider using Data.Trie from the bytestring-trie
package. It also uses ByteStrings as the keys, but it uses a big-endian
patricia tree instead of a hash. This removes Data.Map's duplication of
effort for comparing common prefixes of strings. Constructing a
Data.Trie can be somewhat slower than constructing a Data.Map
ByteString, but the lookup is much faster.
If your misspellings file changes infrequently and you're not afraid of
utilities, you can pre-compile the Data.Trie and read it in with
Data.Binary. If it changes really infrequently and you're not afraid of
recompilation, you can use Template Haskell to store the pre-compiled
form directly in the executable.
Frankly, I am not impressed with the PerfectHash performance; It looks
as if it is only two times faster than Data.Map. Is this because of
the number of elements?
Perfection does have its cost.
I haven't played with Data.PerfectHash, but if the hashing function is
slow then it will kill your performance. In general hashing will do too
much work because it looks at the whole ByteString which is usually
unnecessary (though this extra work can be less than the costs of
putting the work off, depending on the dataset).
...
Though honestly, most spellcheckers are more interested in optimizing
for space rather than optimizing for time. For this, you'll want to look
into something like Golomb codes (that is, Huffman codes for
exponentially-distributed infinite-alphabets) as was used in the Unix
"spell" utility back in the day.
Once you've defined a prefix-free code for all possible words, you can
encode each word and pack the result into a ByteString (treated as an
array of bits) and hand it off to Data.Trie which will do the right
thing. Depending on the size of your data, you may want to squash the
Data.Trie down into an array and use an algorithm rather than the
datastructure to do your search (just as binary search algorithms on
arrays actualize data structures like Data.Map (or datastructures like
data.Map reify binary search algorithms, if you prefer)).
--
Live well,
~wren
_______________________________________________
Haskell-Cafe mailing list
[email protected]
http://www.haskell.org/mailman/listinfo/haskell-cafe
