Our T9 predictive text entry implementation has just been updated with a binary search. By using this kind of search method, with just a 6kB overhead for a 22kB dictionary (about 3,000 entries), the search time decreases considerably from 6.3 to about 0.27 milliseconds. The previous version required over 11 milliseconds to perform the same task (using linear method).
That extra space is used to store word locations within the sorted dictionary (array of uint16_t).
GitHub: https://github.com/M17-Project/M17_T9
Search time for 1,000 operations:
Old, linear: 11.5ms
New, linear: 6.3ms (no additional overhead)
New, binary: 0.27ms
The code is yet to be tested on STM32 (modified Nokia 3310, OpenRTX targets?) and the LinHT.
Enjoy!
Leave a Reply