- #1
- 12,354
- 14,331
I hope this isn't going to be a really dumb question, but I'm stuck on a personal project.
I'm writing a multi-tap keyboard (like ye olde phones that actually had keyboards and didn't have predictive text) for a smartphone with a small screen. I'd like the layout to be in some sense optimal. I think I have a working definition of "optimal" in this context, and have cracked some of the maths. Since what I'm writing is a software keyboard, I also have a data source which would allow the keyboard to re-optimise itself on request. I'd appreciate any comments and any help with the maths I haven't figured out.
I think there are three components to optimal - the number of keystrokes required to type a letter, the number of times two consecutive letters are on the same key (which forces you to wait a second), and the actual placement of the keys. What I have chosen to do (and any suggestions for more flexible approaches would be of interest) is to optimise for minimum keystrokes and, since this is non-unique, choose the solution with the minimal repeat use of keys. The third constraint I was intending to implement last, simply placing the most popular keys where my thumb doesn't have to bend too much.
I can do the first optimisation. I record the number of times, [itex]n_i[/itex], that the user types the character [itex]c_i[/itex]. That gives me an estimate of the probability that the user wants to type that character, [itex]p_i=n_i/\sum_jn_j[/itex]. I order the characters by descending [itex]n_i[/itex] and (on a keyboard with [itex]K[/itex] keys) I assign the first [itex]K[/itex] characters as first characters on a key, the next [itex]K[/itex] as second characters, and so on. I'm going to skip proving that this minimises the number of keystrokes. I can do it, but hopefully the idea that common characters should need few keystrokes is uncontroversial.
I have now defined the set of "first rank" characters, the set of "second rank" characters, and so on. The question is which "second rank", "third rank", etc. character to put on a key with which "first rank" character. This is the bit I cannot see how to do. I can record [itex]n_{ij}[/itex], the number of times the character sequence [itex]c_ic_j[/itex] is typed and hence calculate the probability, [itex]p_{ij}[/itex], that the next two characters that the user types will be [itex]c_ic_j[/itex]. That means that, if you type [itex]c_i[/itex], I expect you to have to wait [itex]\sum_{j\in \{k_i\}}p_{ij}/p_i[/itex] (where [itex]\{k_i\}[/itex] means all characters assigned to the key to which [itex]c_i[/itex] is assigned) before typing the second character. Therefore the non-conditional expected waiting time after the first character is [itex]\sum_i\sum_{j\in \{k_i\}}p_{ij}[/itex]. That is to say (I think) that if you write the [itex]p_{ij}[/itex] in a matrix and group the rows and columns by the key to which the characters are assigned, the merit function is the sum of the same-key blocks on the leading diagonal.
I have absolutely no idea how to optimise this in general. In the case that there are only two characters on each key, I can see that you could try any arrangement of the second characters then try swapping any pair of second characters, accept the best swap and iterate. This would lead "downhill", but I have no idea if it necessarily leads to the global optimum. You could extend this to three ranks by starting with this solution, adding the third rank and pairwise swapping the third rank by the same algorithm, but this feels unlikely to lead to a global optimum. Any ideas? I'll go with the above if no-one has a better idea, trying to make an intelligent choice of starting position (say, for the first rank character with the highest [itex]n_i[/itex], pick the second rank character that minimises [itex]p_{ij}[/itex], then move on to the second-highest [itex]n_i[/itex] and pick from the remaining second rank characters).
The final optimisation is actually easy. Once you have the set of characters on each key then the expected number of keystrokes on a key [itex]k_i[/itex] is [itex]\sum_{j\in \{k_i\}}r_jp_j[/itex]. Put the highest-scoring key in the easiest to reach place, etc.
Thank you if you've even read all of the above. Do you have any thoughts? Better approaches to the second optimisation, or a more holistic approach, recommended reading, or just commentary would be welcome.
I'm writing a multi-tap keyboard (like ye olde phones that actually had keyboards and didn't have predictive text) for a smartphone with a small screen. I'd like the layout to be in some sense optimal. I think I have a working definition of "optimal" in this context, and have cracked some of the maths. Since what I'm writing is a software keyboard, I also have a data source which would allow the keyboard to re-optimise itself on request. I'd appreciate any comments and any help with the maths I haven't figured out.
I think there are three components to optimal - the number of keystrokes required to type a letter, the number of times two consecutive letters are on the same key (which forces you to wait a second), and the actual placement of the keys. What I have chosen to do (and any suggestions for more flexible approaches would be of interest) is to optimise for minimum keystrokes and, since this is non-unique, choose the solution with the minimal repeat use of keys. The third constraint I was intending to implement last, simply placing the most popular keys where my thumb doesn't have to bend too much.
I can do the first optimisation. I record the number of times, [itex]n_i[/itex], that the user types the character [itex]c_i[/itex]. That gives me an estimate of the probability that the user wants to type that character, [itex]p_i=n_i/\sum_jn_j[/itex]. I order the characters by descending [itex]n_i[/itex] and (on a keyboard with [itex]K[/itex] keys) I assign the first [itex]K[/itex] characters as first characters on a key, the next [itex]K[/itex] as second characters, and so on. I'm going to skip proving that this minimises the number of keystrokes. I can do it, but hopefully the idea that common characters should need few keystrokes is uncontroversial.
I have now defined the set of "first rank" characters, the set of "second rank" characters, and so on. The question is which "second rank", "third rank", etc. character to put on a key with which "first rank" character. This is the bit I cannot see how to do. I can record [itex]n_{ij}[/itex], the number of times the character sequence [itex]c_ic_j[/itex] is typed and hence calculate the probability, [itex]p_{ij}[/itex], that the next two characters that the user types will be [itex]c_ic_j[/itex]. That means that, if you type [itex]c_i[/itex], I expect you to have to wait [itex]\sum_{j\in \{k_i\}}p_{ij}/p_i[/itex] (where [itex]\{k_i\}[/itex] means all characters assigned to the key to which [itex]c_i[/itex] is assigned) before typing the second character. Therefore the non-conditional expected waiting time after the first character is [itex]\sum_i\sum_{j\in \{k_i\}}p_{ij}[/itex]. That is to say (I think) that if you write the [itex]p_{ij}[/itex] in a matrix and group the rows and columns by the key to which the characters are assigned, the merit function is the sum of the same-key blocks on the leading diagonal.
I have absolutely no idea how to optimise this in general. In the case that there are only two characters on each key, I can see that you could try any arrangement of the second characters then try swapping any pair of second characters, accept the best swap and iterate. This would lead "downhill", but I have no idea if it necessarily leads to the global optimum. You could extend this to three ranks by starting with this solution, adding the third rank and pairwise swapping the third rank by the same algorithm, but this feels unlikely to lead to a global optimum. Any ideas? I'll go with the above if no-one has a better idea, trying to make an intelligent choice of starting position (say, for the first rank character with the highest [itex]n_i[/itex], pick the second rank character that minimises [itex]p_{ij}[/itex], then move on to the second-highest [itex]n_i[/itex] and pick from the remaining second rank characters).
The final optimisation is actually easy. Once you have the set of characters on each key then the expected number of keystrokes on a key [itex]k_i[/itex] is [itex]\sum_{j\in \{k_i\}}r_jp_j[/itex]. Put the highest-scoring key in the easiest to reach place, etc.
Thank you if you've even read all of the above. Do you have any thoughts? Better approaches to the second optimisation, or a more holistic approach, recommended reading, or just commentary would be welcome.