5 ms·

The only thing missing was converting the dictionary data into a trie. ;-) That's what I was thinking. I wonder what the memory and download footprint for that

The only thing missing was converting the dictionary data into a trie. ;-) That's what I was thinking. I wonder what the memory and download footprint for that would be in practice. Considering characters are represented by string objects in JavaScript, it could get expensive, unless the runtime interns short strings. If not, you could represent single letters with integers, which are almost certainly interned or even use a non-pointer representation. All those objects at each tree level might be a bit much though.

rudiger 16y ago
Less than a naive dictionary; it's a very compact and natural representation of ordered lists of unique words.
- pmjordan 16y ago
  I realise that, I'm interested in the per-object overhead. This approaches zero for the single giant string.
  - rudiger 16y ago
    Take a look at Saurabh Odhyan's JavaScript prefix trie implementation; https://github.com/odhyan/trie https://github.com/odhyan/trie
jerf 16y ago
In this situation, I'd seriously consider throwing down a binary blob as a string that directly represents this data as whatever fancy structure you want and writing the small handful of functions it would take to traverse that "string" to do the lookup. Then you can do whatever optimal thing you want and memory usage is very predictable. Technically this is what his final solution converged on, it's just the least fancy "fancy structure" there is. It's a last resort, certainly, but in certain cases it's the simplest answer. Be aware of encoding issues, though; UTF-8 technically can't carry arbitrary binaries and you may have to work around some things a bit.
- jacobolus 16y ago
  I'd recommend sending base64'd data down. Use this to encode/decode from javascript strings of 1-byte-per-character data: https://github.com/mcarter/js.io/blob/master/packages/std/base64.js https://github.com/mcarter/js.io/blob/master/packages/std/ba...
  - gojomo 16y ago
    FYI, many browsers offer (native) 'atob()' and 'btoa()' functions for Base64 encode/decode that will outperform that JS code.
    - deleted 16y ago
      [deleted]
    - tjarratt 16y ago
      For what it's worth, the linked code on github appears to be specific to node.js. Last I checked, there was no native function to convert strings to and from base64, only buffers. If you're writing this for client side, it would indeed be preferable to use the native functions.

rudiger 16y ago

Less than a naive dictionary; it's a very compact and natural representation of ordered lists of unique words.

pmjordan 16y ago
I realise that, I'm interested in the per-object overhead. This approaches zero for the single giant string.
- rudiger 16y ago
  Take a look at Saurabh Odhyan's JavaScript prefix trie implementation; https://github.com/odhyan/trie https://github.com/odhyan/trie

jerf 16y ago

In this situation, I'd seriously consider throwing down a binary blob as a string that directly represents this data as whatever fancy structure you want and writing the small handful of functions it would take to traverse that "string" to do the lookup. Then you can do whatever optimal thing you want and memory usage is very predictable. Technically this is what his final solution converged on, it's just the least fancy "fancy structure" there is. It's a last resort, certainly, but in certain cases it's the simplest answer. Be aware of encoding issues, though; UTF-8 technically can't carry arbitrary binaries and you may have to work around some things a bit.

jacobolus 16y ago
I'd recommend sending base64'd data down. Use this to encode/decode from javascript strings of 1-byte-per-character data: https://github.com/mcarter/js.io/blob/master/packages/std/base64.js https://github.com/mcarter/js.io/blob/master/packages/std/ba...
- gojomo 16y ago
  FYI, many browsers offer (native) 'atob()' and 'btoa()' functions for Base64 encode/decode that will outperform that JS code.
  - deleted 16y ago
    [deleted]
  - tjarratt 16y ago
    For what it's worth, the linked code on github appears to be specific to node.js. Last I checked, there was no native function to convert strings to and from base64, only buffers. If you're writing this for client side, it would indeed be preferable to use the native functions.