4 ms·
Effectively, you need to keep a small heap and if possible have "simple" data structure. In my case, I implemented the Python code of a trie based levenshtein d
by Loic 12y ago
Effectively, you need to keep a small heap and if possible have "simple" data structure. In my case, I implemented the Python code of a trie based levenshtein distance algorithm[0]. I used maps because it was basically a direct translation of the Python code. This resulted in millions of maps and oft the index would just stop in the garbage collector for a couple of seconds. I solved it using my own map which is travelled linearly.
type SpellCheckerMap struct {
Runes []rune
Nodes []*SpellCheckerNode
}
with only few runes, I can just go through the list to find the index of the following node. You save the computation of the map hash key. It is pretty fast, here is an example of a spelling suggestion over a 500,000 words corpus[1].
Basically, the garbage collection cost forced me to think about a better data structure for my case. Maybe not that bad all in all.
[0]: http://stevehanov.ca/blog/index.php?id=114 http://stevehanov.ca/blog/index.php?id=114
[1]: https://www.chemeo.com/search?q=asparine https://www.chemeo.com/search?q=asparine
- danieldk 12y agoSemi-offtopic: The are more compact representations, e.g. you can store the dictionary in a deterministic acyclic minimized finite state automaton (which can be stored in a flat array/slice). This gives you O(n) time lookups, where n is the length of the word, and reduces much of the redundancy in a dictionary. Words within an edit distance can be found by computing a Levenshtein automaton for the word (which can be done in linear time) and computing the intersection language of the dictionary automaton and the Levenshtein automaton. This approach is fast and very compact. I have a Java implementation: https://github.com/danieldk/dictomaton https://github.com/danieldk/dictomaton
- eric_bullington 12y agoOh, this is very cool. I wonder how many CAT (Computer-Aided Translation) tools out there (many of which are notoriously slow) could be significantly sped up using this approach. I'd bet most of them, although they're almost all closed-source so we will likely never know.
- Loic 12y agoI am a chemical engineer so reading "deterministic acyclic minimized finite state automaton" is sending me back in my first years at university. As I want to implement instant search with part of string matching, this can be very interesting. This is to match "Octane, 2,4,6-trimethyl-" when typing "trimethyl". For the moment I am looking at the Linkedin approach[0]. Sorry for keeping this semi-offtopic thread alive, but these problems are so interesting that I cannot stop. [0]: https://github.com/jamra/gocleo https://github.com/jamra/gocleo
- logicchains 12y agoOne issue is that the server uses Google Protocol Buffers. The following definition, for instance: message Foo { required string a = 1; required int32 b = 2; optional int64 c = 3; } Generates a struct like: type Foo struct { a *string b *int32 c *int64 } This is not particularly friendly to the garbage collector compared to a POD struct with no pointers.
- whyever 12y agoHow can you have a POD struct without pointers if one of your fields is a string?
- logicchains 12y agoCouldn't it be done with a fixed-size array of runes or bytes? It's definitely possible in C/C++.
- z92 12y agoNot without wasting a lot of space depending on the difference between average size of string vs maximum size of string.
- a8da6b0c91d 12y agoYou can use a string class like the one in Folly that decays from a fixed array to heap allocated space if the string gets too long.
- logicchains 12y agoWe generally know the maximum string sizes for each property, and they're pretty small, so this wouldn't have been a problem.
- masklinn 12y agoI believe it's also possible to use variable-size arrays in C or C++ (and end up with a variable-size struct). Go does allow fixed size arrays in structs, and they're inline in the struct, so `struct { foo [8]uint }` is 32 bytes, whereas `struct { foo []uint }` is 12 bytes and `struct { foo string }` is 8.
- stcredzero 12y agoLots of small maps becoming little arrays. The more things change, the more they stay the same. (There is production Smalltalk code from the late 80's running in large multinationals that's basically what you just described.)