4 ms·

Wouldn't using something like trie be useful here?

by nafey 6y ago

ignoramous 6y ago
You may be interested in any or all of these: Minimal Acyclic Finite State Automata: http://stevehanov.ca/blog/?id=115 http://stevehanov.ca/blog/?id=115 (related: https://web.archive.org/web/20120302104036/http://siganakis.com/challenge-design-a-data-structure-thats-small https://web.archive.org/web/20120302104036/http://siganakis....) Succinct Tries: http://stevehanov.ca/blog/?id=120 http://stevehanov.ca/blog/?id=120 (related: https://alexbowe.com/succinct-debruijn-graphs/ https://alexbowe.com/succinct-debruijn-graphs/) Compression and completion using GPT-2: https://bellard.org/textsynth/index.html https://bellard.org/textsynth/index.html (related: https://ed-von-schleck.github.io/shoco/ https://ed-von-schleck.github.io/shoco/) Search and compression with Finite State Transducers: http://blog.burntsushi.net/transducers/ http://blog.burntsushi.net/transducers/ (related: https://swtch.com/~rsc/regexp/ https://swtch.com/~rsc/regexp/) Collection of succinct string representations: https://github.com/simongog/sdsl-lite https://github.com/simongog/sdsl-lite (related: http://pizzachili.dcc.uchile.cl/ http://pizzachili.dcc.uchile.cl/) Search with compressed Radix Trie: https://cr.yp.to/critbit.html https://cr.yp.to/critbit.html related: http://reports-archive.adm.cs.cmu.edu/anon/2020/CMU-CS-20-101.pdf http://reports-archive.adm.cs.cmu.edu/anon/2020/CMU-CS-20-10...
RegW 6y ago
In the case of the ZX Spectrum +3 there wasn't enough disk or memory to hold the uncompressed word list, nevermind some form of tree structure. The search method involved uncompressing each word (one at a time) until either the word was found or one that should follow it. However, I did intend to use a binary search of the word list on the floppy. I arranged it so any zeroes in the list indicated the start of a word from which decompression could start. Under maximum compression there would be only 26 zero bytes in the list, but by selecting short words at regular intervals I could spinkle zeros throughout the list (approx 1 per block). A binary search could scan for the zeros, decompress the associated word and find the section that should contain the target word. Tasman didn't go for this. They sorted all the words to be checked in memory, then opened the file and did a complete scan.

Wouldn't using something like trie be useful here?

by nafey 6y ago

Wouldn't using something like trie be useful here?

You may be interested in any or all of these: Minimal Acyclic Finite State Automata: http://stevehanov.ca/blog/?id=115 http://stevehanov.ca/blog/?id=115 (related: https://web.archive.org/web/20120302104036/http://siganakis.com/challenge-design-a-data-structure-thats-small https://web.archive.org/web/20120302104036/http://siganakis....) Succinct Tries: http://stevehanov.ca/blog/?id=120 http://stevehanov.ca/blog/?id=120 (related: https://alexbowe.com/succinct-debruijn-graphs/ https://alexbowe.com/succinct-debruijn-graphs/) Compression and completion using GPT-2: https://bellard.org/textsynth/index.html https://bellard.org/textsynth/index.html (related: https://ed-von-schleck.github.io/shoco/ https://ed-von-schleck.github.io/shoco/) Search and compression with Finite State Transducers: http://blog.burntsushi.net/transducers/ http://blog.burntsushi.net/transducers/ (related: https://swtch.com/~rsc/regexp/ https://swtch.com/~rsc/regexp/) Collection of succinct string representations: https://github.com/simongog/sdsl-lite https://github.com/simongog/sdsl-lite (related: http://pizzachili.dcc.uchile.cl/ http://pizzachili.dcc.uchile.cl/) Search with compressed Radix Trie: https://cr.yp.to/critbit.html https://cr.yp.to/critbit.html related: http://reports-archive.adm.cs.cmu.edu/anon/2020/CMU-CS-20-101.pdf http://reports-archive.adm.cs.cmu.edu/anon/2020/CMU-CS-20-10...

RegW 6y ago

In the case of the ZX Spectrum +3 there wasn't enough disk or memory to hold the uncompressed word list, nevermind some form of tree structure. The search method involved uncompressing each word (one at a time) until either the word was found or one that should follow it. However, I did intend to use a binary search of the word list on the floppy. I arranged it so any zeroes in the list indicated the start of a word from which decompression could start. Under maximum compression there would be only 26 zero bytes in the list, but by selecting short words at regular intervals I could spinkle zeros throughout the list (approx 1 per block). A binary search could scan for the zeros, decompress the associated word and find the section that should contain the target word. Tasman didn't go for this. They sorted all the words to be checked in memory, then opened the file and did a complete scan.