4 ms·

"A way to make the plain string search faster would be to use binary search." Isn't that premature optimization, though? As I noted in my post - lookups, even

by jeresig 16y ago

"A way to make the plain string search faster would be to use binary search." Isn't that premature optimization, though? As I noted in my post - lookups, even in the worst case, take less than a millisecond. Presumably someone could do that if they wanted even faster lookup performance, although I don't need it in this case. I definitely agree that a binary representation would probably get us pretty close to an ideal form - although I'm (as you are) skeptical that it could be done in a performant way in JavaScript.

ot 16y ago
> Isn't that premature optimization, though? Yes of course it is, I should have started the sentence with "if performance becomes a concern". Since in the post you say "if you were building a game that required multitudes of dictionary lookups you might want to go with a faster hash or Trie technique" I just wanted to point out that binary search would probably work fine as well, without the huge memory increase.
- jeresig 16y ago
  Ah yes - you're very right! I'm tempted to try fiddling around with a simple binary search across the string just to see what sort of performance characteristics it generates. I imagine that the result would be comparable to doing a Trie lookup (if a bit slower). Although, as mentioned before, we'll still have the file size overhead of the uncompressed string.
dunham 16y ago
Are you just testing if words are members of a dictionary? If so, have you considered using a bloom filter? There is a slight chance of false positives, depending on how you choose your parameters, but it's a very compact way to store a set of strings. To make the initial parsing fast, but retain easy lookup I would store the bit vector in an ascii string, 6 bits per character, adding 32 to the raw value to get the character. The wikipedia article can guide you on the parameters needed to get an acceptable error rate and size.
- jeresig 16y ago
  I looked into bloom filters after someone commented as such on my last post. I guess the possibility of false positives makes me a bit jumpy. I realize that it can be reduced with larger data structures but that prospect doesn't make me terribly excited (and having an as-close-to-zero-as-possible error rate would seem to create a significantly large data structure in the end - at least one that doesn't seem to provide much benefit over gzip compression). Although, please feel free to correct me if I'm wrong - if this does provide a tangible benefit with virtually no errors then I'd be very open to using this technique.
  - ori_b 16y ago
    The way you'd want to use bloom filters when you want zero chance of false positives is to filter out impossible options before falling back to slower methods that don't give false positives. If the slower method takes 10 ms, and the bloom filter takes 1 ms, and you have a 1% false positive rate, you're sitting at about 1.1 ms in the average case, instead of 10 ms.
    - mikepurvis 16y ago
      Rather than the fallback method being the list of all good words, how feasible would it be to use a bloom filter and then have the fallback method be an indexof list of all known false positives? Would there be some more enlightened way of computing such a list than just crunching through every combination of letters up to length n? That is to say, could one devise a bloom filter with hash functions such that given the configured filter, a list of all possible matching elements could be produced?
      - ori_b 16y ago
        As far as I can see, finding all false positives for a bloom filter is effectively impossible, since a false positive is simply a hash collision, effectively.
        16y ago
chime 16y ago
> Presumably someone could do that if they wanted even faster lookup performance, although I don't need it in this case. I actually wanted to do that. I've been following your dictionary posts because I'm doing something similar for an iPad PhoneGap app. I created a dictionary with 600k words & n-grams ( http://ktype.net/wiki/research:articles:progress_20110209 http://ktype.net/wiki/research:articles:progress_20110209 ) and want to make really smart predictions (not just basic spell-check/auto-correct). My raw dictionary is 6MB (too large for localStorage) and I load it from a string into a 1D JS array but it randomly crashes the iPad because of memory issues. I was going to change my code to use a space-saving trie next week and lo and behold you posted your two posts and saved me a lot of ground work (so thanks for that!). But unlike you, I need to loop through large parts of the dictionary in order to make good predictions. E.g. 'mxm' should suggest 'maximum' and 'gd mrong' should suggest 'good morning'. While one could come up with really complex ways on minimizing the number of word lookups, it is far easier to just cycle through all dictionary words that begin with 'm' and filter for specific letters. I'm still uncertain what I'll do. Maybe iOS Sqlite DB or iOS CoreData or JS optimized-trie. But once again, thanks for these posts. They've directly helped me.

by jeresig 16y ago

ot 16y ago

> Isn't that premature optimization, though? Yes of course it is, I should have started the sentence with "if performance becomes a concern". Since in the post you say "if you were building a game that required multitudes of dictionary lookups you might want to go with a faster hash or Trie technique" I just wanted to point out that binary search would probably work fine as well, without the huge memory increase.

jeresig 16y ago
Ah yes - you're very right! I'm tempted to try fiddling around with a simple binary search across the string just to see what sort of performance characteristics it generates. I imagine that the result would be comparable to doing a Trie lookup (if a bit slower). Although, as mentioned before, we'll still have the file size overhead of the uncompressed string.

dunham 16y ago

Are you just testing if words are members of a dictionary? If so, have you considered using a bloom filter? There is a slight chance of false positives, depending on how you choose your parameters, but it's a very compact way to store a set of strings. To make the initial parsing fast, but retain easy lookup I would store the bit vector in an ascii string, 6 bits per character, adding 32 to the raw value to get the character. The wikipedia article can guide you on the parameters needed to get an acceptable error rate and size.

jeresig 16y ago
I looked into bloom filters after someone commented as such on my last post. I guess the possibility of false positives makes me a bit jumpy. I realize that it can be reduced with larger data structures but that prospect doesn't make me terribly excited (and having an as-close-to-zero-as-possible error rate would seem to create a significantly large data structure in the end - at least one that doesn't seem to provide much benefit over gzip compression). Although, please feel free to correct me if I'm wrong - if this does provide a tangible benefit with virtually no errors then I'd be very open to using this technique.
- ori_b 16y ago
  The way you'd want to use bloom filters when you want zero chance of false positives is to filter out impossible options before falling back to slower methods that don't give false positives. If the slower method takes 10 ms, and the bloom filter takes 1 ms, and you have a 1% false positive rate, you're sitting at about 1.1 ms in the average case, instead of 10 ms.
  - mikepurvis 16y ago
    Rather than the fallback method being the list of all good words, how feasible would it be to use a bloom filter and then have the fallback method be an indexof list of all known false positives? Would there be some more enlightened way of computing such a list than just crunching through every combination of letters up to length n? That is to say, could one devise a bloom filter with hash functions such that given the configured filter, a list of all possible matching elements could be produced?
    - ori_b 16y ago
      As far as I can see, finding all false positives for a bloom filter is effectively impossible, since a false positive is simply a hash collision, effectively.
      - 16y ago

chime 16y ago

> Presumably someone could do that if they wanted even faster lookup performance, although I don't need it in this case. I actually wanted to do that. I've been following your dictionary posts because I'm doing something similar for an iPad PhoneGap app. I created a dictionary with 600k words & n-grams ( http://ktype.net/wiki/research:articles:progress_20110209 http://ktype.net/wiki/research:articles:progress_20110209 ) and want to make really smart predictions (not just basic spell-check/auto-correct). My raw dictionary is 6MB (too large for localStorage) and I load it from a string into a 1D JS array but it randomly crashes the iPad because of memory issues. I was going to change my code to use a space-saving trie next week and lo and behold you posted your two posts and saved me a lot of ground work (so thanks for that!). But unlike you, I need to loop through large parts of the dictionary in order to make good predictions. E.g. 'mxm' should suggest 'maximum' and 'gd mrong' should suggest 'good morning'. While one could come up with really complex ways on minimizing the number of word lookups, it is far easier to just cycle through all dictionary words that begin with 'm' and filter for specific letters. I'm still uncertain what I'll do. Maybe iOS Sqlite DB or iOS CoreData or JS optimized-trie. But once again, thanks for these posts. They've directly helped me.