{"thread":{"id":"23434","subject":"Rename similarity scoring for file pair","startedAt":"2010-04-12T18:12:59Z","lastAt":"2010-04-17T11:03:56Z","messageCount":3,"participants":["Debayan Banerjee","Jeff King"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"139364","messageId":"t2ua2cc2dbc1004121112h64f5b61ela57f5fa83abf51f@mail.gmail.com","threadId":"23434","inReplyTo":null,"subject":"Rename similarity scoring for file pair","fromName":"Debayan Banerjee","fromEmail":"debayanin@gmail.com","sentAt":"2010-04-12T18:12:59Z","receivedAt":"2010-04-12T18:12:59Z","isPatch":false,"sender":{"key":"debayanin@gmail.com","avatar":"https://gravatar.com/avatar/950309d0a76e4e3eba6b22d59c42c982b6fa077a6c7d2070a12ce64d72f7cfb4?d=mp&s=160"},"body":"I was going through this thread\n<http://markmail.org/message/mge2spy7uqle5ghy#query:diffcore-rename.c%20algorithm+page:1+mid:ji7jkzypzqpml2xn+state:results>\ntrying to understand how the similarity scoring for modified files\nworks. I see that the algorithm uses two hashes, one for each file,\nand proceeds to compare the 2 hashes to determine percentage\nsimilarity.\nI think I have an algorithm which uses only one hash and has a worst\ncase space complexity of O(N) where N is the number of lines\ninserted/deleted/moved.\nThe algorithm is as follows:\n\ndef similarity(leftFileContent, rightFileContent)\n{\n\tint lineCounter = 0;\n\tstruct HashElement  {\n\tHashElement(): leftFileCount(0), rightFileCount(0) // One of these\ncounters will remain 0 for its lifetime. The other will be >=0\n\t\tint leftFileCount; // Increment if line is from leftFile\n\t\tint rightFileCount; // Increment if line is from right file.\n\t};\n\tHash<lineContent, HashElement> hash; //One hash for both files\n\tint similartyCounter = 0;\n\twhile(true)  {\n\t\tleftLline = leftFileContent[lineCounter];\n\t\trightLine = rightFileContent[lineCounter];\n\t\tif (hash.contains(leftLine))  {\n\t\t\tHashElement h = hash.value(leftLine);\n\t\t\tif (h.leftFileCount > 0)   {//The previous occurence has come from\nthe left file\n\t\t\t\th.leftFileCount++;  //This line is another occurence of the same\nline in the same file. So we increment the counter.\n\t\t\t}\n\t\t\telse  {\n\t\t\t\th.leftFileCount--;\n\t\t\t\tsimilarityCounter++;  //Hey, this line matched an earlier\noccurence from the other file!\n\t\t\t}\n\t\t\tif (h.leftFileCount == 0 && h.rightFileCount == 0)\n\t\t\t\thash.remove(leftLine);\t\t\t\n\t\t}\n\t\telse  { // this line is being encountered for the first time, so add\nit to the hash\n\t\t\tHashElement h;\n\t\t\th.leftFileCount++;\n\t\t\thash.add(leftLine, h);\n\t\t}\n\t\t\n\t\tif (hash.contains(rightLine))  {\n\t\t\tHashElement h = hash.value(rightLine);\n\t\t\tif (h.rightFileCount > 0)   {//The previous occurence has come from\nthe right file\n\t\t\t\th.rightFileCount++;  //This line is another occurence of the same\nline in the same file. So we increment the counter.\n\t\t\t}\n\t\t\telse  {\n\t\t\t\th.rightFileCount--;\n\t\t\t\tsimilarityCounter++;  //Hey, this line matched an earlier\noccurence from the other file!\n\t\t\t}\n\t\t\tif (h.leftFileCount == 0 && h.rightFileCount == 0)\n\t\t\t\thash.remove(line2);\t\t\t\n\t\t}\n\t\telse  { // this line is being encountered for the first time, so add\nit to the hash\n\t\t\tHashElement h;\n\t\t\th.rightFileCount++;\n\t\t\thash.add(line2, h);\t\t\t\n\t\t}\n\t\tlineCounter++;\n\t\tif (lineCounter == leftFileContent.size() || lineCounter ==\nrightFileContent.size())\n\t\t\tbreak;\n\t}\n\t/* Upto this point we have processed an equal number of lines in both\nthe files simultaneously. Now we may have a file which is\n\tlarger in size than the other. We need to process the remanant of this file*/\n\tbool leftFileIsLonger;\n\tFileContent fileContent;\n\tint size;\n\tif (leftFileContent.size() == rightFileContent.size())\t\t\n\t\treturn ((similarityCounter*100) / rightFileContent.size());\n\tif (leftFileContent.size() >rightFileContent.size())  {\n\t\tleftFileIsLonger = true;\n\t        fileContent = leftFileContent; //fileContent should really be\n a pointer to leftFileContent\n\t\tsize = leftFileContent.size();\n        }\n\telse  {\n\t\tleftFileIsLonger = false;\n\t\tfileContent = rightFileContent; //fileContent should really be  a\npointer to rightFileContent\n\t\tsize = rightFileContent.size();\n\t}\n\tfor (i = lineCounter + 1;  i < size; i++ )  {\n\t\tline = fileContent[i];\n\t\tif (hash.contains(line))  {\n\t\t\tHash h = hash.value(line);\n\t\t\tif (h.leftLineCount > 0)  { //Line in hash came from left file\n\t\t\t\tif (leftFileIsLonger)\n\t\t\t\t\th.leftFileCount++; //Even this line came from the same file, so\nits just a repeated line.\n\t\t\t\telse  {\n\t\t\t\t\th.leftFileCount--;\n\t\t\t\t\tsimilarityCounter++;  //This line came from the right file, so\nincrease similarityCounter and decrease the leftCounter.\n\t\t\t\t}\n\t\t\t}\n\t\t\telse  { //Line in hash came from right file\n\t\t\t\tif (leftFileIsLonger)  {\n\t\t\t\t\th.rightFileCount--;\n\t\t\t\t\tsimilarityCounter++;\n\t\t\t\t}\n\t\t\t\telse\n\t\t\t\t\th.rightFileCount++;\n\t\t\t}\n\t\t\tif (h.leftFileCount == 0 && h.rightFileCount == 0)\n\t\t\t\t\thash.remove(line);\n\t\t}\n\t}\n    return ((similarityCounter*100) / size); //Formula for calculating\nsimilarity is same as git uses\n}\n\n--\nDebayan Banerjee\nSoftware Engineer\n"},{"id":"139365","messageId":"m2sa2cc2dbc1004121114j5ac8e00amc4eb426e99e2a9cc@mail.gmail.com","threadId":"23434","inReplyTo":"t2ua2cc2dbc1004121112h64f5b61ela57f5fa83abf51f@mail.gmail.com","subject":"Re: Rename similarity scoring for file pair","fromName":"Debayan Banerjee","fromEmail":"debayanin@gmail.com","sentAt":"2010-04-12T18:14:57Z","receivedAt":"2010-04-12T18:14:57Z","isPatch":false,"sender":{"key":"debayanin@gmail.com","avatar":"https://gravatar.com/avatar/950309d0a76e4e3eba6b22d59c42c982b6fa077a6c7d2070a12ce64d72f7cfb4?d=mp&s=160"},"body":"On 12 April 2010 23:42, Debayan Banerjee <debayanin@gmail.com> wrote:\n> I was going through this thread\n\nSorry about that. Sent it prematurely, and by mistake. Find the\nattached file for the algorithm.\n\n-- \nDebayan Banerjee\nSoftware Engineer\n\n\ndef similarity(leftFileContent, rightFileContent)\n{\n\tint lineCounter = 0;\n\tstruct HashElement  {\n\t\tHashElement(): leftFileCount(0), rightFileCount(0) // One of these counters will remain 0 for its lifetime. The other will be >=0\n\t\tint leftFileCount; // Increment if line is from leftFile\n\t\tint rightFileCount; // Increment if line is from right file.\n\t};\n\tHash<lineContent, HashElement> hash; //One hash for both files  \n\tint similartyCounter = 0;\n\twhile(true)  {\n\t\tleftLline = leftFileContent[lineCounter];\n\t\trightLine = rightFileContent[lineCounter];\n\t\tif (hash.contains(leftLine))  {\n\t\t\tHashElement h = hash.value(leftLine);\n\t\t\tif (h.leftFileCount > 0)   {//The previous occurence has come from the left file\n\t\t\t\th.leftFileCount++;  //This line is another occurence of the same line in the same file. So we increment the counter.\n\t\t\t}\n\t\t\telse  {\n\t\t\t\th.leftFileCount--;\n\t\t\t\tsimilarityCounter++;  //Hey, this line matched an earlier occurence from the other file! \n\t\t\t}\n\t\t\tif (h.leftFileCount == 0 && h.rightFileCount == 0)\n\t\t\t\thash.remove(leftLine);\t\t\t\n\t\t}\n\t\telse  { // this line is being encountered for the first time, so add it to the hash\n\t\t\tHashElement h;\n\t\t\th.leftFileCount++;\n\t\t\thash.add(leftLine, h);\n\t\t}\n\t\t\n\t\tif (hash.contains(rightLine))  {\n\t\t\tHashElement h = hash.value(rightLine);\n\t\t\tif (h.rightFileCount > 0)   {//The previous occurence has come from the right file\n\t\t\t\th.rightFileCount++;  //This line is another occurence of the same line in the same file. So we increment the counter.\n\t\t\t}\n\t\t\telse  {\n\t\t\t\th.rightFileCount--;\n\t\t\t\tsimilarityCounter++;  //Hey, this line matched an earlier occurence from the other file! \n\t\t\t}\n\t\t\tif (h.leftFileCount == 0 && h.rightFileCount == 0)\n\t\t\t\thash.remove(line2);\t\t\t\n\t\t}\n\t\telse  { // this line is being encountered for the first time, so add it to the hash\n\t\t\tHashElement h;\n\t\t\th.rightFileCount++;\n\t\t\thash.add(line2, h);\t\t\t\n\t\t}\n\t\tlineCounter++;\n\t\tif (lineCounter == leftFileContent.size() || lineCounter == rightFileContent.size())\n\t\t\tbreak;\n\t}\n\t/* Upto this point we have processed an equal number of lines in both the files simultaneously. Now we may have a file which is\n\tlarger in size than the other. We need to process the remanant of this file*/\n\tbool leftFileIsLonger;\n\tFileContent fileContent;\n\tint size;\n\tif (leftFileContent.size() == rightFileContent.size())\t\t\n\t\treturn ((similarityCounter*100) / rightFileContent.size());\n\tif (leftFileContent.size() >rightFileContent.size())  {\n\t\tleftFileIsLonger = true;\n\t        fileContent = leftFileContent; //fileContent should really be  a pointer to leftFileContent\n\t\tsize = leftFileContent.size();\n        }\n\telse  {\n\t\tleftFileIsLonger = false;\n\t\tfileContent = rightFileContent; //fileContent should really be  a pointer to rightFileContent\n\t\tsize = rightFileContent.size();\n\t}\n\tfor (i = lineCounter + 1;  i < size; i++ )  {\n\t\tline = fileContent[i];\n\t\tif (hash.contains(line))  {\n\t\t\tHash h = hash.value(line);\n\t\t\tif (h.leftLineCount > 0)  { //Line in hash came from left file\n\t\t\t\tif (leftFileIsLonger)\n\t\t\t\t\th.leftFileCount++; //Even this line came from the same file, so its just a repeated line.\n\t\t\t\telse  {\n\t\t\t\t\th.leftFileCount--;\n\t\t\t\t\tsimilarityCounter++;  //This line came from the right file, so increase similarityCounter and decrease the leftCounter.\n\t\t\t\t}\n\t\t\t}\n\t\t\telse  { //Line in hash came from right file\n\t\t\t\tif (leftFileIsLonger)  {\n\t\t\t\t\th.rightFileCount--;\n\t\t\t\t\tsimilarityCounter++;\n\t\t\t\t}\n\t\t\t\telse  \n\t\t\t\t\th.rightFileCount++;\n\t\t\t}\n\t\t\tif (h.leftFileCount == 0 && h.rightFileCount == 0)\n\t\t\t\t\thash.remove(line);\n\t\t}\n\t}\n    return ((similarityCounter*100) / size); //Formula for calculating similarity is same as git uses\n}\n"},{"id":"139735","messageId":"20100417110356.GA28623@coredump.intra.peff.net","threadId":"23434","inReplyTo":"t2ua2cc2dbc1004121112h64f5b61ela57f5fa83abf51f@mail.gmail.com","subject":"Re: Rename similarity scoring for file pair","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2010-04-17T11:03:56Z","receivedAt":"2010-04-17T11:03:56Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Mon, Apr 12, 2010 at 11:42:59PM +0530, Debayan Banerjee wrote:\n\n> I was going through this thread\n> <http://markmail.org/message/mge2spy7uqle5ghy#query:diffcore-rename.c%20algorithm+page:1+mid:ji7jkzypzqpml2xn+state:results>\n> trying to understand how the similarity scoring for modified files\n> works. I see that the algorithm uses two hashes, one for each file,\n> and proceeds to compare the 2 hashes to determine percentage\n> similarity.\n> I think I have an algorithm which uses only one hash and has a worst\n> case space complexity of O(N) where N is the number of lines\n> inserted/deleted/moved.\n\nThat looks pretty similar to the algorithm that Andy Chup proposed. I\ndid some work towards integrating it, but never completed it. See these\nthreads for details:\n\n  http://thread.gmane.org/gmane.comp.version-control.git/61975\n\n  http://thread.gmane.org/gmane.comp.version-control.git/62655\n\nSo yes, it's an interesting way to go. But it needs somebody to:\n\n  1. Implement it in C and integrate it into diffcore-rename (I did\n     that, but there were some problems, see below).\n\n  2. Confirm that the quality of results is similar to the current\n     algorithm. In my case, the results were different, and I suggested\n     some tweaks to improve them (see the second thread above). I don't\n     remember if I ever followed up.\n\n  3. Confirm that we really do get a speed improvement on the slow\n     cases, and don't slow down or significantly bloat memory usage for\n     the fast cases.\n\nIf you're interested in working on it, I'd be happy to help with\ndiscussion and code review.\n\n-Peff\n"}]}