{"thread":{"id":"35158","subject":"[PATCH] diffcore-rename.c: Estimate filename similarity for rename detection","startedAt":"2013-10-17T09:20:13Z","lastAt":"2013-10-17T12:52:54Z","messageCount":2,"participants":["Yoshioka Tsuneo"],"isPatch":true,"patchVersion":1,"patchTotal":null},"messages":[{"id":"229115","messageId":"7658EED3-641E-4AE7-A691-0399ED14D298@gmail.com","threadId":"35158","inReplyTo":null,"subject":"[PATCH] diffcore-rename.c: Estimate filename similarity for rename detection","fromName":"Yoshioka Tsuneo","fromEmail":"yoshiokatsuneo@gmail.com","sentAt":"2013-10-17T09:20:13Z","receivedAt":"2013-10-17T09:20:13Z","isPatch":true,"sender":{"key":"yoshiokatsuneo@gmail.com","avatar":"https://gravatar.com/avatar/1a1dddcd048d4e847e125557e79d2cad1cbe84a9775bb0298a24a6bf687aa040?d=mp&s=160"},"body":"\nOn rename detection like command \"git diff -M ...\", rename is detected\nbased on file similarities. This file similarities are calculated based\non the contents of file. And, if the similarities of contents are the\nsame, filename is taken into account.\nBut, the similarity of filename is calculated just whether the basename\nis the same or not, and always returns just one or zero.\nSo, for example, if there are multiple same files in the diff-ing commits,\nthe result of rename detection is almost random, without taking into account\nthe similarity of filename.\n\nCalculate filename similarities, and use the result to compare file similarity\nin case contents similarities are the same.\nUse Sorensen-Dice coefficient of bigrams in strings to calculate filename\nsimilarities because it take into account all part of the filenames, and time\ncomplexity is O(N), assuming N is the length of filenames.\n---\n diffcore-rename.c | 81 +++++++++++++++++++++++++++++++++++++++++++------------\n 1 file changed, 64 insertions(+), 17 deletions(-)\n\ndiff --git a/diffcore-rename.c b/diffcore-rename.c\nindex 6c7a72f..355ea6d 100644\n--- a/diffcore-rename.c\n+++ b/diffcore-rename.c\n@@ -96,26 +96,51 @@ static struct diff_rename_src *register_rename_src(struct diff_filepair *p)\n \treturn &(rename_src[first]);\n }\n \n-static int basename_same(struct diff_filespec *src, struct diff_filespec *dst)\n+static int estimate_filename_similarity(struct diff_filespec *src, struct diff_filespec *dst)\n {\n-\tint src_len = strlen(src->path), dst_len = strlen(dst->path);\n-\twhile (src_len && dst_len) {\n-\t\tchar c1 = src->path[--src_len];\n-\t\tchar c2 = dst->path[--dst_len];\n-\t\tif (c1 != c2)\n-\t\t\treturn 0;\n-\t\tif (c1 == '/')\n-\t\t\treturn 1;\n+\t/*\n+\t * Calculate similarity between src path and dst path using\n+\t * Sorensen-Dice coefficient of bigrams in strings\n+\t */\n+\tconst char *src_path = src->path;\n+\tconst char *dst_path = dst->path;\n+\tsize_t src_len = strlen(src_path);\n+\tsize_t dst_len = strlen(dst_path);\n+\tstatic uint16_t src_bigram[256][256];\n+\tint i;\n+\tint bigrams_number = 0;\n+\tint similarity;\n+\n+\tfor (i=0; i<src_len; i++) {\n+\t\tint c1 = ((unsigned char*)src_path)[i];\n+\t\tint c2 = ((unsigned char*)src_path)[i + 1];\n+\t\tsrc_bigram[c1][c2] ++;\n+\t}\n+\tfor (i=0; i<dst_len; i++) {\n+\t\tint c1 = ((unsigned char*)dst_path)[i];\n+\t\tint c2 = ((unsigned char*)dst_path)[i + 1];\n+\t\tif (src_bigram[c1][c2] > 0) {\n+\t\t\tsrc_bigram[c1][c2] --;\n+\t\t\tbigrams_number ++;\n+\t\t}\n+\t}\n+\tsimilarity = MAX_SCORE * 2 * bigrams_number / (src_len + dst_len);\n+\n+    /* Clean up src_bigram */\n+\tfor (i=0; i<src_len; i++) {\n+\t\tint c1 = ((unsigned char*)src_path)[i];\n+\t\tint c2 = ((unsigned char*)src_path)[i + 1];\n+\t\tsrc_bigram[c1][c2] = 0;\n \t}\n-\treturn (!src_len || src->path[src_len - 1] == '/') &&\n-\t\t(!dst_len || dst->path[dst_len - 1] == '/');\n+\n+\treturn similarity;\n }\n \n struct diff_score {\n \tint src; /* index in rename_src */\n \tint dst; /* index in rename_dst */\n \tunsigned short score;\n-\tshort name_score;\n+\tunsigned short name_score;\n };\n \n static int estimate_similarity(struct diff_filespec *src,\n@@ -228,7 +253,7 @@ static void record_rename_pair(int dst_index, int src_index, int score)\n  */\n static int score_compare(const void *a_, const void *b_)\n {\n-\tconst struct diff_score *a = a_, *b = b_;\n+\tstruct diff_score *a = (struct diff_score *)a_, *b = (struct diff_score *)b_;\n \n \t/* sink the unused ones to the bottom */\n \tif (a->dst < 0)\n@@ -236,8 +261,23 @@ static int score_compare(const void *a_, const void *b_)\n \telse if (b->dst < 0)\n \t\treturn -1;\n \n-\tif (a->score == b->score)\n+\tif (a->score == b->score){\n+\t\tif(a->score == 0)\n+\t\t\treturn 0;\n+\t\t/* Calculate name_score only when both score is the same */\n+\t\tif(a->name_score == USHRT_MAX){\n+\t\t\tstruct diff_filespec *two = rename_dst[a->dst].two;\n+\t\t\tstruct diff_filespec *one = rename_src[a->src].p->one;\n+\t\t\ta->name_score =  estimate_filename_similarity(one, two);\n+\t\t}\n+\t\tif(b->name_score == USHRT_MAX){\n+\t\t\tstruct diff_filespec *two = rename_dst[b->dst].two;\n+\t\t\tstruct diff_filespec *one = rename_src[b->src].p->one;\n+\t\t\tb->name_score = estimate_filename_similarity(one, two);\n+\t\t}\n+\n \t\treturn b->name_score - a->name_score;\n+\t}\n \n \treturn b->score - a->score;\n }\n@@ -282,7 +322,7 @@ static int find_identical_files(struct file_similarity *src,\n \t\t\tscore = !source->rename_used;\n \t\t\tif (source->rename_used && options->detect_rename != DIFF_DETECT_COPY)\n \t\t\t\tcontinue;\n-\t\t\tscore += basename_same(source, target);\n+\t\t\tscore += estimate_filename_similarity(source, target);\n \t\t\tif (score > best_score) {\n \t\t\t\tbest = p;\n \t\t\t\tbest_score = score;\n@@ -605,10 +645,17 @@ void diffcore_rename(struct diff_options *options)\n \n \t\t\tthis_src.score = estimate_similarity(one, two,\n \t\t\t\t\t\t\t     minimum_score);\n-\t\t\tthis_src.name_score = basename_same(one, two);\n+\t\t\t/*\n+\t\t\t * name_score is needed only when \"score\"s are the same.\n+\t\t\t * So, name_score will be calculated on score_compare\n+\t\t\t * only when needed.\n+\t\t\t */\n+\t\t\tthis_src.name_score = USHRT_MAX;\n \t\t\tthis_src.dst = i;\n \t\t\tthis_src.src = j;\n-\t\t\trecord_if_better(m, &this_src);\n+\t\t\tif(this_src.score >= minimum_score){\n+\t\t\t\trecord_if_better(m, &this_src);\n+\t\t\t}\n \t\t\t/*\n \t\t\t * Once we run estimate_similarity,\n \t\t\t * We do not need the text anymore.\n-- \n1.8.4.475.g867697c\n"},{"id":"229120","messageId":"51F48C86-8C52-4F89-9F0B-204A4C84AB13@gmail.com","threadId":"35158","inReplyTo":"7658EED3-641E-4AE7-A691-0399ED14D298@gmail.com","subject":"[PATCH v2] diffcore-rename.c: Estimate filename similarity for rename detection","fromName":"Yoshioka Tsuneo","fromEmail":"yoshiokatsuneo@gmail.com","sentAt":"2013-10-17T12:52:54Z","receivedAt":"2013-10-17T12:52:54Z","isPatch":true,"sender":{"key":"yoshiokatsuneo@gmail.com","avatar":"https://gravatar.com/avatar/1a1dddcd048d4e847e125557e79d2cad1cbe84a9775bb0298a24a6bf687aa040?d=mp&s=160"},"body":"\nOn rename detection like command \"git diff -M ...\", rename is detected\nbased on file similarities. This file similarities are calculated based\non the contents of file. And, if the similarities of contents are the\nsame, filename is taken into account.\nBut, the similarity of filename is calculated just whether the basename\nis the same or not, and always returns just one or zero.\nSo, for example, if there are multiple same files in the diff-ing commits,\nthe result of rename detection is almost random, without taking into account\nthe similarity of filename.\n\nCalculate filename similarities, and use the result to compare file similarity\nin case contents similarities are the same.\nUse Sorensen-Dice coefficient of bigrams in strings to calculate filename\nsimilarities because it take into account all part of the filenames, and time\ncomplexity is O(N), assuming N is the length of filenames.\n\nSigned-off-by: Tsuneo Yoshioka <yoshiokatsuneo@gmail.com>\n---\n diffcore-rename.c | 81 +++++++++++++++++++++++++++++++++++++++++++------------\n 1 file changed, 64 insertions(+), 17 deletions(-)\n\ndiff --git a/diffcore-rename.c b/diffcore-rename.c\nindex 6c7a72f..355ea6d 100644\n--- a/diffcore-rename.c\n+++ b/diffcore-rename.c\n@@ -96,26 +96,51 @@ static struct diff_rename_src *register_rename_src(struct diff_filepair *p)\n \treturn &(rename_src[first]);\n }\n \n-static int basename_same(struct diff_filespec *src, struct diff_filespec *dst)\n+static int estimate_filename_similarity(struct diff_filespec *src, struct diff_filespec *dst)\n {\n-\tint src_len = strlen(src->path), dst_len = strlen(dst->path);\n-\twhile (src_len && dst_len) {\n-\t\tchar c1 = src->path[--src_len];\n-\t\tchar c2 = dst->path[--dst_len];\n-\t\tif (c1 != c2)\n-\t\t\treturn 0;\n-\t\tif (c1 == '/')\n-\t\t\treturn 1;\n+\t/*\n+\t * Calculate similarity between src path and dst path using\n+\t * Sorensen-Dice coefficient of bigrams in strings\n+\t */\n+\tconst char *src_path = src->path;\n+\tconst char *dst_path = dst->path;\n+\tsize_t src_len = strlen(src_path);\n+\tsize_t dst_len = strlen(dst_path);\n+\tstatic uint16_t src_bigram[256][256];\n+\tint i;\n+\tint bigrams_number = 0;\n+\tint similarity;\n+\n+\tfor (i=0; i<src_len; i++) {\n+\t\tint c1 = ((unsigned char*)src_path)[i];\n+\t\tint c2 = ((unsigned char*)src_path)[i + 1];\n+\t\tsrc_bigram[c1][c2] ++;\n+\t}\n+\tfor (i=0; i<dst_len; i++) {\n+\t\tint c1 = ((unsigned char*)dst_path)[i];\n+\t\tint c2 = ((unsigned char*)dst_path)[i + 1];\n+\t\tif (src_bigram[c1][c2] > 0) {\n+\t\t\tsrc_bigram[c1][c2] --;\n+\t\t\tbigrams_number ++;\n+\t\t}\n+\t}\n+\tsimilarity = MAX_SCORE * 2 * bigrams_number / (src_len + dst_len);\n+\n+    /* Clean up src_bigram */\n+\tfor (i=0; i<src_len; i++) {\n+\t\tint c1 = ((unsigned char*)src_path)[i];\n+\t\tint c2 = ((unsigned char*)src_path)[i + 1];\n+\t\tsrc_bigram[c1][c2] = 0;\n \t}\n-\treturn (!src_len || src->path[src_len - 1] == '/') &&\n-\t\t(!dst_len || dst->path[dst_len - 1] == '/');\n+\n+\treturn similarity;\n }\n \n struct diff_score {\n \tint src; /* index in rename_src */\n \tint dst; /* index in rename_dst */\n \tunsigned short score;\n-\tshort name_score;\n+\tunsigned short name_score;\n };\n \n static int estimate_similarity(struct diff_filespec *src,\n@@ -228,7 +253,7 @@ static void record_rename_pair(int dst_index, int src_index, int score)\n  */\n static int score_compare(const void *a_, const void *b_)\n {\n-\tconst struct diff_score *a = a_, *b = b_;\n+\tstruct diff_score *a = (struct diff_score *)a_, *b = (struct diff_score *)b_;\n \n \t/* sink the unused ones to the bottom */\n \tif (a->dst < 0)\n@@ -236,8 +261,23 @@ static int score_compare(const void *a_, const void *b_)\n \telse if (b->dst < 0)\n \t\treturn -1;\n \n-\tif (a->score == b->score)\n+\tif (a->score == b->score){\n+\t\tif(a->score == 0)\n+\t\t\treturn 0;\n+\t\t/* Calculate name_score only when both score is the same */\n+\t\tif(a->name_score == USHRT_MAX){\n+\t\t\tstruct diff_filespec *two = rename_dst[a->dst].two;\n+\t\t\tstruct diff_filespec *one = rename_src[a->src].p->one;\n+\t\t\ta->name_score =  estimate_filename_similarity(one, two);\n+\t\t}\n+\t\tif(b->name_score == USHRT_MAX){\n+\t\t\tstruct diff_filespec *two = rename_dst[b->dst].two;\n+\t\t\tstruct diff_filespec *one = rename_src[b->src].p->one;\n+\t\t\tb->name_score = estimate_filename_similarity(one, two);\n+\t\t}\n+\n \t\treturn b->name_score - a->name_score;\n+\t}\n \n \treturn b->score - a->score;\n }\n@@ -282,7 +322,7 @@ static int find_identical_files(struct file_similarity *src,\n \t\t\tscore = !source->rename_used;\n \t\t\tif (source->rename_used && options->detect_rename != DIFF_DETECT_COPY)\n \t\t\t\tcontinue;\n-\t\t\tscore += basename_same(source, target);\n+\t\t\tscore += estimate_filename_similarity(source, target);\n \t\t\tif (score > best_score) {\n \t\t\t\tbest = p;\n \t\t\t\tbest_score = score;\n@@ -605,10 +645,17 @@ void diffcore_rename(struct diff_options *options)\n \n \t\t\tthis_src.score = estimate_similarity(one, two,\n \t\t\t\t\t\t\t     minimum_score);\n-\t\t\tthis_src.name_score = basename_same(one, two);\n+\t\t\t/*\n+\t\t\t * name_score is needed only when \"score\"s are the same.\n+\t\t\t * So, name_score will be calculated on score_compare\n+\t\t\t * only when needed.\n+\t\t\t */\n+\t\t\tthis_src.name_score = USHRT_MAX;\n \t\t\tthis_src.dst = i;\n \t\t\tthis_src.src = j;\n-\t\t\trecord_if_better(m, &this_src);\n+\t\t\tif(this_src.score >= minimum_score){\n+\t\t\t\trecord_if_better(m, &this_src);\n+\t\t\t}\n \t\t\t/*\n \t\t\t * Once we run estimate_similarity,\n \t\t\t * We do not need the text anymore.\n-- \n1.8.4.475.g867697c\n"}]}