Plynomial Autocompletion

[sallam-ahmed]

Any previous entered polynomial and loaded in the history will be auto-completed instead of typing it again.

[khaledkee]

• The auto-completion feature will be a bit tricky. Trie data-structure is sometimes called Prefix-Tree. As the name suggests, it can give only suggestions that match a specific prefix. For example, suppose the Trie originally contains 3X³+2X²+X+5 and 2X²+X+5. If the user entered 3X³, 2X+5, or X, there will be no completion menu (remember we store terms in a sorted list by degree). If the user entered 5, X+5, or 2X²+X+5 ONLY, both polynomials will appear in the completion menu.
• I don't want to mess around, but we can use BenderRMQ (customization of segment tree for auto-completion) for slightly faster auto-completion for large data set. We can also use a SuggestTree for a much faster and less complicated auto-completion. Another option for significantly faster completion and very low memory consuming is RadixTree (AKA Patricia).
• About searching for an arbitrarily (not necessary consecutive) sub-sequence is an open problem in Computer Science as I can recall. But we can take the advantage of the fact that the polynomial are stored in a SortedList to increase the speed of auto-completion (still slow). For an arbitrarily CONSECUTIVE sub-sequence, We can use SuffixArray, however, we should build the SuffixArray every time we want to search for a polynomial in it, very slow but simple solution. For a faster solution, we can use z-algorithm. Actually forcing the sub-sequence to be CONSECUTIVE makes it worse only.
• To sum up:
  • Let N be number of polynomials in history, M be the length of the longest polynomial in history, and K be the length of the current input of the user. Assuming K < M. All complexities are given per query.
  • Searching for non-consecutive sub-sequence requires O(N * K * lgM).
  • Searching for consecutive sub-sequence requires O((N * M + K) * lg²(N * M)) using SuffixArrays, O(N * M + K) using SuffixTree, or O(N * (M+K)) using z-algo.
  • Searching for prefix requires O(K + N) using Trie, O(K * lgN) using BenderRMQ, O(K + lgN) using SuggestTree, or O(K) using RadixTree.

[khaledkee]

Remember the order of the input doesn't matter. In the trie example above, if the input is 5+2X²+X it's the same as X+5+2X². But if X or 5 were not presented, the Trie can't find any suggestion. I mean the only restriction is that the input should form a prefix of a polynomial in the history.

[sallam-ahmed]

@khaledkee Looks like it's going to be tricky as a byte not just a bit.. hence we don't want the user to type the whole polynomial.. I think of reassigning it to phase 5 instead, until we do the proper research about the preferred method .

[sallam-ahmed]

The auto-completion algorithm should be performance favored at first hence it will be called with each new character added to the RTBox

Like O((N * M +K) * lg² (N *M)) isn't a good performance complexity for text change.