858158 - [keyboard] document prediction algorithm

Status: RESOLVED FIXED

(Firefox OS Graveyard :: Gaia::Keyboard, defect)

Description

[David Flanagan [:djf]]

The word prediction code in apps/keyboard/imes/latin/predictions.js is hard to understand.  For maintainability, I'd like to see an explanation, in English, of how the algorithm works.

Also, I think this is an algorithm that we're going to want to tune, especially as we introduce auto-correction.  We might want to tweak the multipliers for transpositions, insertions, deletions, for example. Similarly, there are presumably constants we need for weighting results that involve nearby keys and the length of the result words relative to the input text. It would be nice to have these constants all in one spot in the file.

Comment 1

[Christoph Kerschbaumer [:ckerschb]]

Attachment: pull request

Comment 2

[Christoph Kerschbaumer [:ckerschb]]

Sorry, I guess it's easier if I just paste the link to the pull request here:

https://github.com/mozilla-b2g/gaia/pull/9071

Comment 3

[David Flanagan [:djf]]

Comment on attachment 735391 [details] [review]
pull request

Christoph,

Thank you, the comment is very helpful. I still have questions though (see github) and I hope you'll write more.

Please just ask for review again when you've got more documentation.

Comment 4

[David Flanagan [:djf]]

Here's another question that you might address in the documentation:

Looking at the predictSuffixes() code, it looks as if the frequency field of any node is being used to save the highest frequency of any word stored under that node, and if I'm understanding the code correctly, it looks like the tree is structured so that that highest-frequency word is found by traversing the center pointer.

That seems like a very important feature of the data structure that needs to be documented, especially since it implies that the tree is balanced in a non-traditional way.

Comment 5

[Christoph Kerschbaumer [:ckerschb]]

David, can you have a look at the documentation again - hopefully this description highlights the important parts of the algorithm and makes things clearer.

https://github.com/mozilla-b2g/gaia/pull/9071

Comment 6

[David Flanagan [:djf]]

Christoph,

Thanks. I understand the nptr now.  I've added more comments on github, but as far as I'm concerned you can land this whenever you're ready.  Unless you plan to work on the tuneability part of it under this bug.

Comment 7

[Christoph Kerschbaumer [:ckerschb]]

Attachment: link to pull request

David,

I guess I addressed all your comments on the bug, please find a new pull request here:

https://github.com/mozilla-b2g/gaia/pull/9106

Comment 8

[David Flanagan [:djf]]

Comment on attachment 736128 [details] [review]
link to pull request

Christoph,

This looks fine to me.  I'm not sure if you have commit rights, and since this is just a comment, we don't need gregor's r+ also, so I'll just go ahead and land it.

We can add tuneable weightings in another bug.

Comment 9

[David Flanagan [:djf]]

Comment on attachment 736128 [details] [review]
link to pull request

Sorry, actually, I can't merge because the comment makes the Travis build fail with lint errors (spaces and the end of lines, I think). So you need to run fixjsstyle over the commit before we can land it.

If you've got commit rights, though, feel free to land it yourself when you're fixed the lint.

Comment 10

[Gregor Wagner [:gwagner]]

https://github.com/mozilla-b2g/gaia/commit/d83b55803088a2b0a447a3282ead603f625ea9ff

Comment 11

[Tony Chung [:tchung]]

Please add a testcase for this bug to moztrap for 1.1 testsuite.  If yes, mark this in-moztrap+ when completed.  If not, mark this in-moztrap-.

Comment 12

[David Flanagan [:djf]]

Uplifted to v1-train in bug 873934

Comment 13

[Tony Chung [:tchung]]

This fix should be covered by auto correct work