Is that how things like Swiftkey or Google Now can predict words so well? If so, how do they do it so quickly?
Yes. It's most definitely an important part of their algorithm.
But why would it be slow? The average person has a vocabulary of max. 50-100k words. Maybe it was even less, I forget. You'd probably do more than fine with just the top 10k anyway.
With a clever data structure, that's peanuts for today's mobile hardware.
In particular (and I dunno if that's how they do it) just the lookup needs to be fast, the storing of new words can be done offline in some lost half-second when the user isn't interacting with the device. With that in mind they can even use really cool data-structures such as tries that can do super-efficient partial prefix matching.
Except they also seem to do fuzzy matching, so there needs to be some Levenshtein distance type of thing in there. That can be costly, but it's also been around for some decades and that part doesn't need to be super-exact, so I bet there's some really clever tricks for that as well. If anyone knows, I'd love to hear about it too :)
Comments
Yes. It's most definitely an important part of their algorithm.
But why would it be slow? The average person has a vocabulary of max. 50-100k words. Maybe it was even less, I forget. You'd probably do more than fine with just the top 10k anyway.
With a clever data structure, that's peanuts for today's mobile hardware.
In particular (and I dunno if that's how they do it) just the lookup needs to be fast, the storing of new words can be done offline in some lost half-second when the user isn't interacting with the device. With that in mind they can even use really cool data-structures such as tries that can do super-efficient partial prefix matching.
Except they also seem to do fuzzy matching, so there needs to be some Levenshtein distance type of thing in there. That can be costly, but it's also been around for some decades and that part doesn't need to be super-exact, so I bet there's some really clever tricks for that as well. If anyone knows, I'd love to hear about it too :)