CN108182181A - A Method for Duplicative Detection of Public Contribution Merge Requests Based on Hybrid Similarity - Google Patents

Abstract

The invention belongs to the field of software collaborative development, and discloses a method for detecting repetition of public contribution merge requests based on mixed similarity. The method includes: for a newly submitted public contribution merge request, firstly calculate the textual similarity between it and the historical public contribution merge request; then calculate the change similarity between it and the historical public contribution; further collect a group on the popular collaborative development platform Historical repeated contribution data set, under the training of this data set, use the weight calculation method based on the greedy search strategy to combine the two similarities to calculate the mixed similarity between the public contributions; finally, according to the mixed similarity value, a Group with a given crowd-contributed merge request is most likely a duplicate of the list of historical crowd-contributed merge requests. The invention can timely detect the repetition of public contributions, avoid repeated manual code review work, and improve the efficiency of public contribution review.

Description

A Method for Duplicative Detection of Public Contribution Merge Requests Based on Hybrid Similarity

technical field

The invention belongs to the field of software collaborative development, and relates to a method for detecting repetition of public contribution merging requests based on mixed similarity.

Background technique

In open source communities (such as GitHub), the software development model based on large-scale group collaboration has greatly improved the efficiency of software innovation and inspired more and more developers to devote themselves to the creation process of open source software. However, this development model is a parallel and uncoordinated process. When multiple developers spontaneously contribute code to the same open source software project, if they want to achieve the same purpose, they may submit duplicate Contributed merge requests (Pull-requests), especially those popular projects that attract a large number of peripheral developers and receive a steady stream of community contributions, are more prone to this problem. As shown in Figure 2, two developers, Bob and Alice, both clone (fork) the same master version library, and then the two developers independently make modifications on their respective local clone libraries. When they both want to implement the same function or fix the same code defect, since neither of them knows what the other is doing, both of them may make corresponding changes and then submit a merge request to the main version repository. Requests will go through contribution review and update actions separately, until a developer becomes aware of the existence of two duplicate crowd-contributed merge requests.

Repeated public contribution merge requests cause a waste of platform resources and increase the maintenance cost of the platform. It also results in a duplicate contribution review process for duplicate crowd-contributed merge requests, which costs reviewers additional time and effort. During the lifetime of a crowd-contributed merge request (the period from when it is submitted to the platform until it is accepted or rejected), duplicate crowd-contributed merge requests may be identified at any point in time, and the later it is identified, it The resulting waste of resources and energy is more serious. Also, during the review process of a crowd-contributed merge request, contributors will often update it based on the reviewer's feedback, so if a duplicate crowd-contributed merge request is not identified early on, two contributors may also do Redundant work is repeated, which casts doubt on the competence of the project management team. Especially if their contributing pull request is considered a duplicate of a late contributing pull request and closed by a reviewer, which can negatively impact contributors even more.

At present, the GitHub platform (GitHub is a hosting platform for open source and private software projects, because it only supports git as the only repository format for hosting, hence the name GitHub) is to rely on reviewers to manually find out the mechanism for identifying duplicate contribution merge requests. . However, for those popular projects, there is a steady stream of code contributions made by popular developers to the main repository, and a large number of contributed merge requests require code reviews. It is unrealistic for a reviewer to memorize information about all historically contributed pull requests, compare them to newly submitted contributed pull requests, and then judge duplication. Under the current mechanism, only when a developer happens to be aware of the existence of two duplicate contribution merge requests, their duplication is discovered, which causes most of the duplicate contribution merge requests to not be identified in time . In the above situation, a tool that can automatically detect duplicates during the contribution merge request submission stage is necessary. First, automated detection tools can assist reviewers in their work, allowing them to avoid redundant duplication of work. Secondly, automatically detecting duplicate contribution merge requests at the first time can allow contributors from both parties to establish contact and collaborate together as early as possible, preventing them from continuing to do repetitive work.

Contents of the invention

In order to solve the above technical problems, the present invention proposes a hybrid similarity detection method for repetitive contributions that may exist in the open source software project hosting platform, and the specific technical solution is as follows.

A method for detecting duplication of public contribution merge requests based on mixed similarity, comprising the following steps:

S1. Calculate the text similarity between the newly submitted public contribution merge request and the historical public contribution merge request, the text similarity includes title text similarity and description text similarity;

S2. Calculate the change similarity between the newly submitted public contribution merge request and the historical public contribution merge request, the change similarity refers to the path similarity between files modified by the public contribution merge request;

S3. Collect a set of historical duplicate contribution merge request data sets on the collaborative development platform, and use a weight search algorithm based on a greedy strategy to train the historical duplicate contribution merge request data sets to obtain weight values of text similarity and change similarity , and further calculate the mixed similarity between public contribution merge requests according to the weight value;

S4. According to the above steps S1 to S3, each historical public contribution merge request corresponds to a mixed similarity, sorted according to the size of the mixed similarity value, and obtains a group of historical public that is duplicated with the newly submitted public contribution merge request Contribute to the list of merge requests.

Further, the specific process of the step S1 is:

S11. Extract title text and description text from the newly submitted public contribution merge request and the historical public contribution merge request respectively, to obtain two title texts and two description texts;

S12. Preprocessing the title text and description text;

S13. Convert the preprocessed title text and description text into multi-dimensional vectors respectively, to obtain two title text vectors and two description text vectors;

S14. Use the Cosine formula to calculate the similarity between the two title text vectors, that is, the title text similarity between the newly submitted public contribution merge request and the historical public contribution merge request; use the Cosine formula to calculate the two description text vectors The similarity between the newly submitted public contribution merge request and the description text similarity of the historical public contribution merge request.

Further, the specific process of the step S2 is:

S21. Extracting the files specifically modified by the newly submitted public contribution merge request and the historical public contribution merge request to obtain two file sets;

S22. Calculate the path similarity between two files in the two file sets, that is, the change similarity between the newly submitted public contribution merge request and the historical public contribution merge request.

Further, the collaborative development platform is GitHub platform.

Further, the preprocessing of the title text and the description text in the step S12 specifically includes word segmentation, conversion of word roots and removal of stop words.

Compared with the prior art, the present invention has the following beneficial effects: 1. The present invention proposes a detection method based on mixed similarity for possible repetitive contributions in the open source software project hosting platform. This method is a key part of improving the efficiency of code review. It can avoid repeated review work by reviewers, help core developers organize the code review process more efficiently, and improve the efficiency of public contribution aggregation. 2. The present invention proposes to comprehensively utilize the text similarity including the title and text of the public contribution merge request, and the change similarity caused by the modified file to calculate the similarity between the public contribution merge requests, which can better reveal the public contribution Duplication across merge requests. 3. The present invention collects a set of historical duplicate public contribution merge request data sets from the GitHub platform through automatic identification and manual inspection. This data can be used to optimize the automatic detection model of duplicate public contribution merge requests and improve its detection effect . 4. The present invention proposes to use a strategy based on greedy search to effectively combine the two similarities, so as to calculate a mixed similarity value that can better reflect the similarity of public contribution merge requests.

Description of drawings

Fig. 1 is a schematic flow sheet of the method of the present invention;

FIG. 2 is a flow chart of parallel contributions made by multiple developers in the background technology;

Fig. 3 is a program code diagram of the public contribution merge request change similarity calculation algorithm of the present invention;

Fig. 4 is the program code diagram of the path similarity calculation algorithm of two files;

Fig. 5 is the program code diagram of the weight calculation algorithm based on the greedy search strategy among the present invention;

Detailed ways

The following will clearly and completely describe the technical solutions in the embodiments of the present invention with reference to the accompanying drawings in the embodiments of the present invention. Obviously, the described embodiments are only some, not all, embodiments of the present invention. Based on the embodiments of the present invention, all other embodiments obtained by persons of ordinary skill in the art without making creative efforts belong to the protection scope of the present invention.

As shown in Figure 1, it is a schematic flow sheet of the method of the present invention; the concrete steps are as follows:

S1. Calculate the text similarity between the newly submitted public contribution merge request and the historical public contribution merge request, the text similarity includes title text similarity and description text similarity.

For text extracted from crowd-contributed merge request titles and descriptions, standard preprocessing procedures are first performed, including tokenization, stemming, and removal of stop words. There are various strategies in the prior art for splitting a sentence into phrases, depending on the type of data to be processed and the domain of application. There is some text that would normally be split into multiple words, but should be treated as a single word in the context of a public contribution pull request, e.g. text representing code paths and hyperlinks are often long, but they refer to a whole concept, so they should not be cut apart. Therefore, we used a regular expression tokenizer to parse the original text, below are some regular expressions and the text matched by them.

code path:

–\w+(?:\:\:\w+)*

– "ActionDispatch::Http::URL"

Publicly contributed merge requests are numbered on the GitHub platform:

–\#\d+

– "#10319"

After the text is tokenized, each word is converted to its root form (for example, "was" is converted to "be", "errors" is converted to "error"), and this conversion is done by the Porter root conversion algorithm. Finally, some stop words (such as "the", "a") that occur frequently but do not contribute much to the recognition of a sentence are removed.

The preprocessed text will be further converted into a multidimensional vector that can be calculated in the Vector Space Model (Vector Space Model, VSM) according to the TF-IDF model (Term Frequency–Inverse Document Frequency, abbreviated as TF-IDF), and the vectorized text i Can be expressed as: TextVec _i =(wi _{, 1} , _{wi, 2} ,...,wi _{, v} ), each dimension of the vector corresponds to a word of the text, and what v represents is the word in the entire text corpus total. The value of w _{i, k} is the weight of the kth element in the vector corresponding to the text i, which is calculated by the TF-IDF model:

w _i,k =tf _i,k ×idf _i,k

In the above formula, tf _i,k represents word frequency, which is the frequency of the kth word in text i, and idf _i,k represents inverse document frequency, which is used to measure the degree of distinction of a word to an article.

After the text is vectorized, we use the Cosine formula to calculate the similarity SimText(i, j) of the two text vectors TextVec _i and TextVec _j . The specific calculation formula is:

Based on the Cosine calculation formula, the title text similarity SimText _title (i, j) and the description text similarity SimText _desc (i, j) between two popular contribution merge requests are respectively obtained; i, j represent text, |·| Finds the modulus of a vector.

S2. Calculate the change similarity between the newly submitted public contribution merge request and the historical public contribution merge request, the change similarity refers to the path similarity between files modified by the public contribution merge request;

Collaboration on the GitHub platform relies on Git. With the support of Git tools, when a contributor submits a contribution merge request on the GitHub platform, the changes involved in the contribution can be displayed in a diff form. To calculate the similarity between two public contribution merge requests based on the diff information, first parse the original diff data into structured data to extract which modules and which files have been specifically modified by a public contribution merge request. The specific code algorithm is shown in Figure 3, which calculates the change similarity between two public contribution merge requests. The input of the algorithm is the file sets files _i and files _j respectively modified by two popular contribution merge requests (indicated by PR in the algorithm). The first line of the algorithm code in Figure 3 initializes a list for storing the temporary results generated in the algorithm, and the codes from the second line to the fifth line are used to calculate the file path similarity of any two files in the two file sets. And store the two files and their similarity in a list, and the file path similarity of the two files is calculated by the algorithm shown in FIG. 4 . The 6th line of code sorts the elements in the list according to the similarity value, and the 7th line of code determines the similarity of how many file pairs to keep in the end. The eighth line of code initializes a new list to store the last file pairs to be kept and their similarity values. The codes from lines 9 to 13 find the file pairs with the highest similarity in turn from the temporary list and put their similarity into the final list. Since the same file only appears once in the final list, that is, the same file only It will have the maximum similarity value with another file, so the 12th line of code will delete all the file pairs formed by the maximum similarity file pair and other files in the intermediate result list. Finally, the sum of the similarity values in the final list is divided by the maximum size of the two changed file collections to obtain the change similarity of the two public contribution merge requests. The algorithm shown in Figure 4 is used to calculate the path similarity of two files. First, this function splits the paths of the two files according to the path separator, and obtains two sets of directory names respectively. Then calculate the depth of the longest common subdirectory of the two file paths through the codes in the 3rd to 7th lines, and finally divide the depth by the maximum value of the depth of the two file paths to get the path similarity of the two files.

S3. Collect a set of historical duplicate contribution merge request data sets on the collaborative development platform, and use a weight search algorithm based on a greedy strategy to train the historical duplicate contribution merge request data sets to obtain weight values of text similarity and change similarity , and further calculate the mixed similarity between public contribution merge requests according to the weight value;

In this embodiment, the specific process of collecting historical duplicate public contribution merge request data sets from the GitHub platform is as follows:

(1) Random sampling: 26 popular projects on the GitHub platform are selected; for a project, a part is randomly selected from all its public contribution merge requests.

(2) manual screening: for each selected public contribution merge request, each of its comments containing other public contribution merge request references is manually checked, and further selected are about the repeated comments of the public contribution merge request, the present invention puts This kind of comment about the repetitiveness of a merge request contributed by the general public is called an indicative comment.

(3) Rule extraction: Based on the set of indicative comments collected in the previous step, it is found that some words or phrases are frequently used when reviewers point out that one public contribution merge request is duplicated with another public contribution merge request. For example, "dup of", "closed by" and "addressed in" in the following groups of comments are all phrases that are often used by reviewers to point out duplication.

– "dup of #xxxx"

– "Closed by https://github.com/rails/rails/pull/13867"

– “This has been addressed in #27768.”

Therefore, regular expressions are extracted based on these indicative comments, and these regular expressions are used as rules to automatically match indicative comments. Some examples of rules are listed below:

clos(e|ed|ing)(\w+){,5}(by|of)(\w+:?){,5}#\d+

(4) Automatic identification: according to the above-mentioned regular expression identification rules, the indicative comments can be automatically identified, so as to find two overlapping public contribution merge requests. If a comment is identified as an indicative comment, the referenced public contribution merge request number will be extracted from the comment, and a duplicate public contribution merge request will be formed with the public contribution merge request to which the indicative comment belongs.

(5) Manual inspection: automatic identification according to the rules will introduce erroneous data, that is, there are some public contribution merge request pairs that are not duplicates of each other. Therefore, manual inspection of the automatically identified data is required. Manual checks are based on the following criteria:

1) The author of a duplicate crowd-contributed merge request is unaware of the existence of the source crowd-contributed merge request. This requires looking at the comment data of the two crowd-contributed merge requests to see if the authors were aware.

2) The reviewers agreed on the duplication of crowd-contributed merge requests. That is, after a reviewer proposes that a public contribution merge request is a duplicate of another public contribution merge request, no other reviewer disagrees, but expresses approval and closes one of the public contribution merge requests.

On the other hand, after computing various types of similarities between a given crowd-contributed pull request and historical crowd-contributed pull-requests, these similarities are used to find the crowd-contributed pull-request most similar to the given crowd-contributed pull-request list. In order to make full use of these types of similarities, the present invention adopts a mixed similarity method to calculate the final similarity between two public contribution merge requests, and the calculation formula of the final similarity Sim(i, j) is as follows:

Sim(i,j)=a×SimText _title (i,j)+

b×SimText _desc (i, j)+

c×SimDiff _file (i, j)

In the above formula, Sim(i, j) is a mixed similarity after a weighted combination of multiple similarities, the title text similarity SimText _title (i, j), and the description text similarity SimText _desc (i, j ), change the similarity SimDiff _file (i, j), and their corresponding weights are a, b, c respectively. In order to select better weights, as shown in Figure 5, based on the collected data sets of GitHub platform repeated public contribution merge requests, the greedy search algorithm is used to automatically determine their values. Inputs to the algorithm include a set of repeated crowd-contributed merge requests, the maximum number of algorithm iterations, and the step size the algorithm tries for each search. Finally, the algorithm returns a locally optimal set of weights. In the algorithm code shown in Figure 5, the first 3 lines (lines 1-3) initialize the three weights, and combine the weight values into a vector for operation, and then use the initialized weight vector to obtain the initial evaluation function value . The evaluation function is used to evaluate whether a set of weight vectors can better reflect the contribution of various types of similarity to the actual public contribution merge request similarity, that is, whether a set of weight vectors can produce a similarity ratio that is more in line with the actual situation . For a public contribution merge request, in the returned list, the higher the rank of the public contribution merge request that is duplicated with it, the better, so the evaluation function fitness is defined as:

In the above formula, DupPR represents the historical repeated public contribution merge request data set, wts represents the current weight vector, <pre,prl> represents a pair of repeated public contribution merge requests, SimPRs(Prl) returns the most similar to prl A list of crowd-contributed merge requests, Rank( _pre ,SimPRs(Prl)) returns the rank of _pre in the list.

Lines 4-21 of Figure 5 iteratively search for weight parameters with better effects until the number of iterations reaches the maximum number of iterations specified in the algorithm input. On line 5, we first create a list to hold the search history for each iteration. In each iteration, we try to change the weight vector in two directions: forward search (lines 7-10) and backward search (lines 11-14). At the beginning of each search, the current optimal weight vector is first recorded and saved (lines 7 and 12), and in the forward search, the weight to be observed will be increased by a step unit (line 8 ), while in the reverse search, the weight to be observed will be reduced by one step unit (line 12). The updated weight vector is used to calculate the new evaluation function value (lines 9 and 13), and at the same time, the new weight vector is also stored and recorded in the history record search_history (lines 10 and 14 code). When all the weights have been observed, that is, the three weights of a, b, and c are observed once, the highest function evaluation value (line 15) will be taken from the search history. If this value is higher than the current optimal weight vector If the value of the evaluation function is even higher, then the current optimal weight vector and the value of the optimal evaluation function will be updated accordingly (line 16-line 19), otherwise no update will be performed, and then the next round of iteration will start. Finally, the algorithm shown in Figure 5 outputs the best performing weight vector (line 23).

S4. According to the above steps S1 to S3, each historical public contribution merge request corresponds to a mixed similarity, sorted according to the size of the mixed similarity value, and obtains a group of historical public that is duplicated with the newly submitted public contribution merge request Contribute to the list of merge requests. In the embodiment, a top-k value can be preset, and the top-k historical public contribution merge requests in the list are selected, which are the most similar public contribution merge requests to the newly submitted public contribution merge requests.

To sum up, the public contribution merge request duplication detection method based on mixed similarity proposed by the present invention can detect the duplication of public contributions in time, avoid repetitive manual code review work, and improve the efficiency of public contribution review.

Although the embodiments of the present invention have been shown and described, those skilled in the art can understand that various changes, modifications and substitutions can be made to these embodiments without departing from the principle and spirit of the present invention. and modifications, the scope of the invention is defined by the appended claims and their equivalents.

Claims (5)

1. A public contribution merge request duplication detection method based on mixed similarity, is characterized in that, comprises the following steps: S1. Calculate the text similarity between the newly submitted public contribution merge request and the historical public contribution merge request, the text similarity includes title text similarity and description text similarity; S2. Calculate the change similarity between the newly submitted public contribution merge request and the historical public contribution merge request, the change similarity refers to the path similarity between files modified by the public contribution merge request; S3. Collect a set of historical duplicate contribution merge request data sets on the collaborative development platform, and use a weight search algorithm based on a greedy strategy to train the historical duplicate contribution merge request data sets to obtain weight values of text similarity and change similarity , and further calculate the mixed similarity between public contribution merge requests according to the weight value; S4. According to the above steps S1 to S3, each historical public contribution merge request corresponds to a mixed similarity, sorted according to the size of the mixed similarity value, and obtains a group of historical public that is duplicated with the newly submitted public contribution merge request Contribute to the list of merge requests. 2. a kind of public contribution merge request duplication detection method based on mixed similarity as claimed in claim 1, is characterized in that, the specific process of described step S1 is: S11. Extract title text and description text from the newly submitted public contribution merge request and the historical public contribution merge request respectively, to obtain two title texts and two description texts; S12. Preprocessing the title text and description text; S13. Convert the preprocessed title text and description text into multi-dimensional vectors respectively, to obtain two title text vectors and two description text vectors; S14. Use the Cosine formula to calculate the similarity between the two title text vectors, that is, the title text similarity between the newly submitted public contribution merge request and the historical public contribution merge request; use the Cosine formula to calculate the two description text vectors The similarity between the newly submitted public contribution merge request and the description text similarity of the historical public contribution merge request. 3. a kind of public contribution merge request repetition detection method based on mixed similarity as claimed in claim 1, is characterized in that, the specific process of described step S2 is: S21. Extracting the files specifically modified by the newly submitted public contribution merge request and the historical public contribution merge request to obtain two file sets; S22. Calculate the path similarity between two files in the two file sets, that is, the change similarity between the newly submitted public contribution merge request and the historical public contribution merge request. 4. A method for detecting duplication of public contribution merge requests based on mixed similarity as claimed in claim 1, characterized in that: said collaborative development platform is a GitHub platform. 5. A kind of public contribution merging request duplication detection method based on mixed similarity as claimed in claim 2, it is characterized in that, in said step S12, preprocessing title text and description text specifically includes word segmentation, conversion word root and Remove stop words.