GSoC project progress: part two

In my previous post, I talked about all the major discussions that have been made with the community, what the suggestion feature would be like, how I plan to realize this feature, and how I have extended the functionality of the scripts/help/__unimplemented__.m function file to integrate the command line suggestion feature with Octave. In this post, I would like to share my progress and talk about how the current implementation of the suggestion feature is working. The link to the public repository that contains the code for this feature can be found here.

The goal for the first evaluations was to code up a small model that would show how this feature integrates itself with Octave. That part, however, was completed by the time I had made my last blog post. I had been working on a full-fledged command line suggestion feature since then and till now, I have been able to complete a working command suggestion feature that supports identifiers from core octave and 40 octave-forge packages. Lets start looking at various parts of the feature.

Whenever the __unimplemented__.m function file, fails to identify, whatever the user entered, as a valid, unimplemented octave command, it calls one of my m-script, called __suggestions__.m and the command suggestion feature gets triggered. This script, __suggestions__.m, does the following things...

• Firstly, based on the setting of the custom preference (set by the user with the command setpref ("Octave", "autosuggestion", true/false) it decides whether to display/not to display any suggestions. If the preference is 'false', it realizes that the user has turned off the feature and so it returns the control without calculating or displaying any suggestions. 
• However, if the preference is true, it checks if whatever the user has entered is at-least a two letter string. If not, it again, returns the control without calculating or displaying any suggestions. This is done because it is less likely that a one letter strings is a misspelled form of some command.
• However, if the string entered by the user is two lettered or more, the script goes on to calculate the commands that closely match the misspelling. The work of calculation is done by a different script and __suggestions__.m, only calls that script to get the closest matching commands. These commands are then displayed to the user as potential corrections.
• If the misspelling of the user is short (length of the misspelling < 5), the script entertains one typo only, However, if the length of the misspelling is more than or equal to 5, two typos are entertained as well. This essentially means that for short misspellings, commands which are at an edit distance of 1 from the misspelling are shown as potential corrections and for relatively longer misspellings, commands which are at an edit distance of 2 from the misspelling are also shown as potential corrections.

Commands that closely match the misspelling are calculated by a different m-script. This m-script is called __generate__.m. It loads a list of possible commands from a database file called  func.db and then calculates the edit distance between the misspelling and each entry of the list using a different script called edit_distance.m. The commands having an edit distance equal to one or two are accepted as close matches and a list of all such commands along with their edit distances is returned to __suggestions__.m which displays some or all of these suggestions depending on the logic described before.

I'd like to mention that the strings package of Octave forge also has a function file that calculates the edit distance. It is called "editdistance.m". Therefore, to avoid compatibility issues or to avoid having two different function files that do the same thing, later on, I will include the edit_distance function that I wrote within the __generate__.m script.

Improving the speed of the generation script 

If we go on and calculate the edit distance between the misspelling and each and every identifier of octave (core+forge), our algorithm would take nearly 20 years to generate an output for each typographic error that the user makes. We, however, would like the time to be 20 milliseconds or so. For that, we use some smart techniques that reduce the sample space on which the algorithm has to operate.

To reduce the time, I've made a small assumption. I have assumed that the user never mistypes the first letter of a command. A rough analysis of the misspelling data that I received from Shane of octave-online before the commencement of the project, suggests that this is a reasonable assumption and would hardly reduce the accuracy of the suggestion feature. How good is this assumption for the speed? Well, I'd just say that, for a misspelling starting with the letter 'n', this small assumption reduces the sample size from 1492 to 36 (and that is not the best case!). The worst case was that of the letter 's' in which 178 out of 1492 commands were left. Even that corresponds to an 88% reduction in the sample size.

It is important to mention that doing this alphabetical separation at run-time would be a redundant task and a stupid idea, that would correspond to the algorithm taking 20 years again.

Another thing that we should consider, to improve the speed, is to show suggestions from octave core + loaded packages only. Obviously it is not a good idea to check among the commands that belong to a package which the user is not currently using (or worst, a package that is not installed on the user's machine).

Keeping these things in mind, I have created the func.db database file in such a way that the commands belonging to different packages are stored in different structures and are alphabetically separated as fields of that structure. So for example, func.db contains a structure called control which holds the identifiers from the control package only, and another structure core which holds the identifiers of core Octave only, and another structure signal which holds the identifiers of the signal package only and so on. The field a of the control structure (accessed by typing control.a) contains all the identifiers of control package starting with 'a', The field b (accessed by typing control.b) contains those identifiers of the control package that start with b, and so on. This has been repeated for all the packages available.

To make our __generate__.m script memory efficient as well, we load the core structure (which is always required) and then check for the loaded packages and load the structures corresponding to the loaded packages only, then, using a switch case, fetch all those commands which have the same first letter as that of the misspelling (in O(1), thanks to the way in which the database is arranged) and then proceed to the next step.

To understand the next step, we need to understand that the if a misspelling is of length p (say), and we are accepting corrections that are at an edit distance of one or two from the misspelling, then the corrections could have the following lengths only...

• p-2: Two deletes in the misspelling,
• p-1: One delete and one substitution, or one delete only.
• p: One delete and one addition, or one or two substitutions.
• p+1: One addition and one substitution, or one substitution only.
• p+2: Two additions to the misspelling.

This fact, allows us to reduce the list further and would cut out some 5-10 more entries for normal length misspellings. This logic, however, is particularly useful for large length misspellings, because commands with large lengths are very less in number. If a user misspells the command "suppress_verbose_help_message" the script would take days to suggest a correction for this command without this logic, this is because edit distance algorithm is O(n1*n2) with dynamic programming, where n1 and n2 are the lengths of the strings being compared. This O(n1*n2) is repeated m times where m is the number of possible commands that could be close matches. With this logic however, the possible list would be cut down to one or two commands only. Thus, the value of m will be reduced and the close matches will be found within one or two iterations.

That summarizes all the measures that I have taken to improve the speed of the suggestion feature. The control flow had been described before this and so that concludes the working of the suggestion feature.

Conclusion

This concludes phase one. What's left is to include more forge packages and to include graphic properties within the scope of this feature. Writing the documentation, writing the tests, and debugging also remains but these shall be the tasks for subsequent coding phases. Till then, goodbye, see you in the next blog post. :)