- Triagers deal with bug reports in software triage systems like Bugzilla to prioritizing, finding duplicates, and assigning those to developers, which these processes should be automated, especially for substantial open source projects. These bug reports must be mined by text mining, information retrieval, and natural language processing techniques for automation processes. There are many typos in user bug reports which cause low accuracy for artificial intelligence techniques. These typos can be detected based on standard dictionaries, but correction of these typos needs human knowledge based on the context of bug reports. It is essential which neither Google Translator nor Microsoft Office Word can detect interconnected terms -a common type of typos in bug reports- having more than two meaningful terms. This research provides a novel language-independent approach for fast correction of interconnected typos based on natural language processing and human neural network structure to detect and correct interconnected typos - a new tree-based method proposed for term matching. Also, two algorithms proposed for a fast finding the longest meaningful term in an interconnected typo. A dataset is used including 180-kilo typos based on four famous bug report dataset of Android, Eclipse, Mozilla Firefox, and Open Office projects. Then proposed method evaluated on typos versus state of the art. The results show the runtime performance of the proposed method is as same as the related works, but the average length of words is improved and at least more than 57% of typos in the dataset can be classified as interconnected typos.
Keywords— Information Retrieval, Natural Language Processing, Duplicate Detection, Bug Reports, Typo Correction, Lexical Interconnected Typo, Trie
I.
INTRODUCTION
Many massive projects, especially open source projects have
a large range of analyzers, designers, developers, testers and end
users, which after each new release, all of them may find some
issues or bugs and/or have some suggestions to improve the
software. Software triage systems such as Bugzilla are software
which usually gets these reports online and then the Triagers will
deal with these bug reports to evaluate the importance and
priority of each report, finding duplicate reports based on their
© 2019 for this paper by its authors. Use permitted under Creative
contents, assign bug reports to developers for checking bugs and
planning to modify the project in future [1]. Because of the large
amount and volume of bug reports, many researchers have tried
to automate these processes since 2004 by artificial intelligence
techniques and algorithms[1]. Duplicate bug reports detection is
an essential problem in this research area [2, 3]. The algorithms
and techniques of duplicate bug report detection such as Term
Frequency and Inverse Document Frequency in information
retrieval technique need to check the similarity of two bug
reports to each other word by word, so the lexical correctness of
words and terms is essential for these techniques [
There are many types of typos in texts such as additional, removal, or substitute characters. Interconnected terms are a regular typo in the software context because there are many method or class names in this context which contains interconnected terms like ‘getItemById’ or ‘printAllMembers’. Sometimes these words are camel case, and sometimes users typed them and have not any specific case sensitivity. Also, sometimes typists forgot to press space between words so there will be many interconnected terms in the software bug reports or even other contexts too. Also, it is possible to find some interconnected typos in optical character recognition (OCR) output too. These interconnected terms must be separated otherwise humans and/or computers algorithms, and methods like term frequency of information retrieval techniques cannot recognize the text or detect similarities for duplicate bug report detection problem. The primary purpose of this research is to figure out how does correct these typos rapidly.
The organization of the paper is as follows: section 2 explains the literature view and related works. Section 3 describes the methodology of interconnected typo correction, section 4 will discuss evaluation results in experiments, and section 5 will conclude the research.
II. LITERATURE REVIEW
Typo detection and correction is a regular and an ancient issue in text mining and natural language processing [6, 7]. There are many efforts on typo detection and correction in a scientific context like clinical records, which uses Shannon’s noisy channel model to predict next words based on the previous word sequence [8]. In some case, there is less previous word sequence like web query, so the log of web query can be used as a baseline, and maximum entropy model can help for rare queries to conquer the sparseness problem of prior data [9].
Some researchers focus on correction of misspelled typos by different kind of machine learning and natural language processing models, e.g., creating a confusion matrix for a different type of misspellings like additional or removal or transposal or replaced characters to searching these patterns in terms and predict the correction [10]. Also, phonetic, language, and keyboard models can be useful for correction prediction by decision tree as a machine learning based technique [11, 12]. Another approach can be creating a model based on machine learning techniques to detect typos and predict the correction according to context and domain knowledge [13, 14]. String transduction tries to map one string to another and can be used for misspelled typo corrections too [15]. Also, machine learning is used in character scale to typo detection and corrections, but the recall rate is low (about 30%) [16].
Some other researchers focus on using tree structure for typo correction. It is possible to make a tree based on a probabilistic model of the relationship between characters of words which what characters can become after a particular character and in advance mode, after a sequence of characters. So, these models use Bayes theory to make a prediction model on a tree called Trie and use it for typo correction as the user is typing [17, 18]. The tree structure can be used for grammatical checking and translating too by merging several grammatical trees in a Trie [19]. The simple Trie (without probability) is used for spell checking too [20]. The acyclic deterministic finite automata is a graph with a similar structure which can be used for spell checking and typo correction [21]. There are some methods for query in Trie by wild characters, too [22]. Trie-based index structure can be used for real-time interaction like search recommendation and query completion [23].
The interconnected terms problem was not significant a lot in other contexts, and there is no specific method for correction of interconnected terms. As it was tested, the google translate, and Microsoft office word can detect two parts interconnected terms and suggest a correction for them, but if there are more than two meaningful terms, they cannot detect and suggest any correction. It shows that even huge companies have not been investigated algorithm
with this problem. So, a divide and conquer based on the
most extended common sequence algorithm have been made, as shown in Fig. 1 to find meaningful terms in an interconnected term. It is a simple brute force algorithm which will consider all combinations of start and end index of a substring in interconnected term to find a meaningful term. Meaningfully checking needs a dictionary. Luckily an excellent trustful dictionary for computer context have been made in past research [24] and can be used for this purpose too.
Checking a word in the dictionary usually is a daily operation, especially in meaningful word detection; so the time complexity of this process is significant. Usually, dictionaries sort their terms to use the binary search with log2 (N) time complexity for term checking which N is the number of terms in the dictionary. Also, every word needs to be compared with a suspicious meaningful word which complexity of this operation is based on the length of terms even though almost string comparer method uses short circuit idea for time reduction, in other words when they find first different character between two words, and they will cut the comparison operation. So, the meaningful word detection takes the logarithm (N) operation in the worst case to find out the result, and it is in the worst case usually in this procedure because many substrings are meaningless and they are not in dictionaries.
Algorithm: Meaningful Word Finding Input: a connected term with index of 1 to L Output: a list of meaningful words with start and end index in connected term For I in range of 1 to L
For J in range of I+1 to L
If substring of term from I to J is in dictionary
Put the (I, J, substring) in the output 2) operations equal to n×(n-1)/2 time complexity. Each iteration needs a dictionary term checking, so the total complexity of this algorithm is in the equation (1) which N is the number of terms in dictionaries, L is the average length of each term and n is the length of the interconnected term. Also, this algorithm can be parallel easily by dispatching combinations between some threads or processes, and two threads or processes can be made at least to parallelize this algorithm, which everyone uses half combinations. ( , , ) 1 = 2 × × ×( −1) 2
Meaningful substring can be everywhere in interconnected term and have overlap, e.g. ‘hishe’ can be ‘hi’ and ‘she’ or ‘his’ and ‘he’, so the next step is to find the meaningfulness combination between substrings which have no overlap (e.g. ‘his’ and ‘she’ which is not possible according to ‘s’ overlap in primary interconnected term). This algorithm uses a recursive depth-first search approach to find all non-overlap combination shown in Fig. 2. It takes four inputs containing the output list of the previous algorithm, a start index based on the list of meaningful words, a list of the selected index in meaningfulness combination, and the length of the interconnected term. These parameters are the meaningful words, start search index for next combinations, considered in the current path of depth search, and can be considered as a constant in this algorithm respectively. Also, the output of this algorithm is a list of combination too. This final list should be evaluated based on the context of interconnected terms, and the best combination is picked semantically. This algorithm will consider all combinations of meaningful words and choose those combinations with no overlap. So, if there are N words in the meaningful words list, the time complexity of this algorithm equals 2N, which is exponential, and it is a non-polynomial problem. It takes a long time, and it is not suitable for a real-time situation like correction suggestion as the user is typing in text editors which is very important; because if the user looks the suggestion and correct this typo, it is not necessary to evaluate the result combination semantically by artificial intelligence techniques. It is enough to sort the output list based on a metric and show the top-10 suggestion to the user; then the user will pick the best one. The average length of words can be a useful metric because every much the average length of words be high, the combination contains the largest meaningful component in interconnected terms, and the possibility of meaningfulness is more.
Algorithm: Finding meaningfulness combination between substrings Input: MW as a list of meaningful words from 1 to n indexes, SI as start index of searching in meaningful words with 0 initial value, SC as selected combination with empty initial value, LCT as length of connected term Output: a list of meaningfulness combination of words If start index is 0
Consider end point equal to 0 Else
Consider end point equal to end index in SI-th of MW If end point equals to LCT
Return SC For each index J which start index of J-th of MW equals to end point
Consider SCn as new list containing SC plus J as appended value
Call this algorithm with MW, J, SCn , LCT …
and put the result in output list if it is not empty
In the middle procedure of the process of meaningful word finding, it has been considered that neural networks of the human brain look at a word and predict the next letters based on priors and it seems the human brain uses a tree-like algorithm to find the correctness of a word. So, a binary like a tree proposed to be made for meaningful word checking. This process needs two steps: creating the tree, parsing the tree for checking the existence of a term in the dictionary. Also after making this tree, it was found that this tree can be used to find meaningful words more efficient than brute force algorithm, so in step 3 this tree should be used for finding the meaningful terms. Then these meaningful terms should be checked where which one is much possible in primary interconnected term to be meaningful. Thus, there are four main steps to separate interconnected terms which shown in Fig. 3 which every step will be explained in the next sections with an example.
Creating NMT
Detecting Correct Terms
Making All
Possible Combination
Evaluating and Finding Best Combinations
Suppose that there is a dictionary with these words: ‘hello’, ‘book’, ‘help’, ‘his’, ‘hiss’, ‘she’. Also, ‘hellohelphissbookhishel’ is considered as multiple interconnected terms with a typo in the last term. Now the process of neural-like tree making will be explained for matching the input terms which this tree has called a neural matching tree (NMT). 1.1
This tree is like the binary tree, but it has more than two children, so it is an n-ary like a tree. It has a root, and every word in the dictionary will have appeared as a path below of the root. Every letter in words will be put in a node in the tree. Also, every node will contain a flag for showing the end of the word, and if a node contains a letter which is the end of a word, the flag will be true; otherwise it will be false. Every node can be implemented by a map or dictionary data structure in programming languages. So, for the supposed example, this tree will be like the Fig. 4. In this tree, the flag of end letter of every word is T (true) and has different color.
Root / F b / F h / F
s / F o / F e / F i / F
h / F o / F l / F s / T e / T k / T l / F p / T
s / T o / T
It is interesting that a path can have multiple final nodes, for example, both words ‘his’ and ‘hiss’ have the same prefix and in this tree, have the same path. It should be mentioned that this neural matching tree, can compress the dictionary too. The human mind is like this tree as to when we look at a word, some path in our brain will be activated and we can predict next letters. The procedure of creating NMT is explained in Fig. 5. This algorithm takes a list of words of a dictionary and returns the root node for NMT. This procedure is very simple and for every word, parse the tree once time from the root node and check the child nodes to have the letters of a word, otherwise create a child node for each letter as shown in Fig. 3. Also, for the last node, which contains the last letter of a word, the flag must be true to show the end of a word.
Algorithm: Creating Neural Match Tree Input: a list of words in a dictionary Output: a root node to a neural match tree Create a Root node containing no letter with false flag as end character For each word in words list of dictionary
Consider n as a node pointed to Root node For each letter in word
If letter is not in child node of n
Create a child node for n with letter and false flag
Consider child node containing the letter as new n Put true flag for node n (the last one) Fig. 5. Algorithm of creating neural match tree
Time and memory complexity of NMT are essential too. As explained before, the NMT memory is less than a simple dictionary, and it can be used for compression too. Also, the creation procedure of NMT need a parse on the whole dictionary just one time, so it depends on the number of words in the dictionary and the length of each word. If every word has an average length of L and there are N words in the dictionary (as denoted before), the time complexity will be N×L. 1.2
The next step is to use the NMT for checking a new term is valid or not; in other words, is it in the dictionary or not. This procedure is like the NMT creation process, which had described in Fig. 6. It will check every letter of the suspicious term is in NMT or not. If the first letter is in child nodes of the root node, then the next letter will check with the child node of that selected child node. Unlike the checking process in regular dictionaries, which has Log2(N)×L time complexity, this process has L time complexity. 1.3
Finding Meaningful Words in an Interconnected Term by Neural Matching Term
Now, it is time to do the main procedure instead of the brute force algorithm in Fig. 1. The first loop step of brute force algorithm cannot be connivance because there may be some lexical mistake in interconnected term and some substring is useless, so every substring maybe meaningful.
Algorithm: Checking the existence of word in NMT as a dictionary Input: a Root node for NMT and a term for checking Output: a Boolean value indicating the existence of the … word in the NMT Consider n as a node pointed to Root node For each letter in word
If letter is not in child node of n
Return False
Consider child node containing the letter as new n Return True
The second loop in the brute force algorithm can be more intelligence based on NMT by cutting the searching existence of substring as soon as finding a letter is that substring is not in the next node of NMT. The algorithm of finding meaningful words in interconnected term by NMT is shown in Fig. 7. The time complexity of searching in NMT is less than regular dictionaries. So, the time complexity of this algorithm will be L×L.
Algorithm: Finding Meaningful Words of a Connected Term by NMT Input: Root of NMT and a Connected Term with index of 1 to L Output: the list of meaningful substring of connected term An empty list for connected terms as output For I in range of 1 to L
J = I Consider n as a node pointed to Root node While J <= L
If n has a final flag (is the last letter of a word)
Put substring of connected term from I to J …
index into output list If letter is not in child node of n
Break out from while loop
Consider child node containing the letter as new n
As mentioned before, the recursive algorithm of finding meaningfulness combinations has high time complexity, so, a new iteration based algorithm has created for this purpose, as shown in Fig. 8. There is a new input in this algorithm to limit the search based on average word length metric as mentioned and select just top combination with most ranks. This algorithm needs a priority queue which can be implemented by heap algorithm as heap queue to contain every combination with its rank. Every time this algorithm chooses the highest rank combination. If this combination is completed and considered all non-overlap words, the combination will be added to the output list. Otherwise, it will be progressed to choose the next word and add to its combination, and calculate the rank again based on the new combination. This algorithm sort the non-overlap combination by the length of them descending and then choose combination as noted in the algorithm by underline. It causes the longest combination of chose. The time complexity of this algorithm depends on several words in a combination and parameter N which in the worst case if every letter of the interconnected term has considered as a meaningful word, the time complexity of this algorithm will be LCT×N and it is polynomial.
Algorithm: Finding meaningfulness combination between substrings by NMT Input: MW as a list of meaningful words from 1 to n indexes, LCT as length of connected term, N as number of top most meaningfulness combination Output: a list of meaningfulness combination of words Consider LS as a list of search states … with a combination containing 0 as index of selected … words with 0 rank While LS is not empty and has not N output
Pop highest rank combination in LS as HRC Choose last index of combination in HRC as end point For each index J which start index of J-th of MW … equals to end point Sorted by J descending
Consider HRCn as new combination containing … HRC combination plus J as appended value … and calculate rank based on HRCn
If the end point of J-th of MW equals to LCT
Put the combination of HRCn in output list Else
Put HRCn in LS
The new scientific semi dictionary as word list and unique
typo dataset of bug reports have picked for evaluating proposed
algorithms [
AVERAGE WORD LENGTH
Alg. 1
Alg. 2 Fig. 9. Average Word Length of Detected Terms versus Alg.1 [24] The detail of Fig.9 is tabulated in Table 1. As it is evident in this table, the number of detected terms with lower length is less than the higher length, and it is because the new proposed algorithm chooses the longest combination which is more relevant based on our observations.
This research focuses on the correction of interconnected terms typos by natural language processing based on a reliable word list like a formal dictionary to build an n-ary tree inspired from human neural network to recall the memory. This tree was called Neural Matching Tree (NMT), which is created based on the word list. Then the interconnected term will be parsed based on NMT, and the meaningful substrings in interconnected term will be extracted. Then non-overlap combinations of meaningful substrings had picked as correction output words. The proposed algorithms are elementary, and their time complexity is negligible. Another achievement of this research is showing that there are many interconnected terms in the software context, especially bug reports. So the correction of interconnected typos can be useful for other goals like duplicate bug report detection which use information retrieval techniques like term frequency that use the lexical form of words and depends on having nontypo in bug reports.
In the next step, any improvements can be used for meaningfulness combination extraction process to achieve the best one between other combinations and also based on the main context. Also, other metrics can be introduced for this purpose instead of the average length of words, which this research had introduced and had used.