最近筆者在職的公司在不斷的做App的包瘦身工作, 身邊的同事們也研究出了各種各樣實(shí)用的工具來(lái)輔助加快包瘦身的進(jìn)程。在這么一個(gè)大環(huán)境下, 筆者突然又冒出一個(gè)很無(wú)聊的工具想法

通過(guò)文本匹配來(lái)尋找相似的方法函數(shù)

筆者給這個(gè)小工具取了一個(gè)非常傳神且牛逼的名字 - SameCodeFinder

和上一個(gè)查找Block的無(wú)聊的小工具RiskBlockScanner類(lèi)似, 這個(gè)工具筆者覺(jué)得也是一個(gè)應(yīng)用面相對(duì)比較小的一個(gè)工具, 所以筆者自嘲無(wú)聊的小工具哈~

筆者自認(rèn)為這個(gè)是一個(gè)無(wú)聊的小工具, 但是還是堅(jiān)持把它開(kāi)發(fā)出來(lái)了, 因?yàn)楣P者堅(jiān)信:

任何一個(gè)無(wú)聊小眾的作品, 在合適的時(shí)機(jī)總是能夠幫助到合適的人的!

筆者開(kāi)發(fā)這個(gè)小工具除了因?yàn)楣P者相信這個(gè)工具肯定能夠幫助到部分人群以外, 還有另外一個(gè)目的是督促自己不要停止學(xué)習(xí)的步伐哈~

起源-輔助研發(fā)自查

查找相似代碼想法的起源是因?yàn)楣P者在在職的公司項(xiàng)目處于包瘦身的大環(huán)境下。在這個(gè)大環(huán)境下, 筆者身邊的一名同事發(fā)明了基于otool和linkmap分析查找無(wú)用方法的工具, 該工具在Github上有個(gè)類(lèi)似的開(kāi)源腳本項(xiàng)目objc_cover。與此同時(shí), 筆者的另外一名同事發(fā)表了一種基于Clang來(lái)查找無(wú)用方法的博文。

受這兩位同事的影響, 筆者就在想自己能搞什么和他們不一樣點(diǎn)的工具么。因?yàn)楣P者之前用文本掃描的方式搞了一個(gè)簡(jiǎn)易的快速Block檢查腳本, 筆者就在想能不能通過(guò)類(lèi)似的手段寫(xiě)一個(gè)類(lèi)似的程序。筆者想借鑒《基于Clang來(lái)查找無(wú)用方法》的思路進(jìn)行擴(kuò)展, 因?yàn)樵撐恼吕锾岢隽艘环N將文本內(nèi)容Hash后進(jìn)行內(nèi)容比較, 判斷方法是否完全重合的思路。

筆者基于該思路進(jìn)行擴(kuò)展, 設(shè)想能不能不止比較“完全相同”的方法, 還能比較相似的方法。順著這個(gè)思路發(fā)現(xiàn)了Google的全文搜索相似度比較的一種算法simhash[7, 8]。

Simhash

關(guān)于simhash的介紹引用博文《simhash算法原理及實(shí)現(xiàn)》 里的介紹

simhash是google用來(lái)處理海量文本去重的算法。 google出品，你懂的。 simhash最牛逼的一點(diǎn)就是將一個(gè)文檔，最后轉(zhuǎn)換成一個(gè)64位的字節(jié)，暫且稱(chēng)之為特征字，然后判斷重復(fù)只需要判斷他們的特征字的距離是不是<n（根據(jù)經(jīng)驗(yàn)這個(gè)n一般取值為3），就可以判斷兩個(gè)文檔是否相似。

上述引用其實(shí)有點(diǎn)不完全正確, simhash貌似并不是Google出品的, 第一作者的郵箱后綴明明是普林斯頓大學(xué)好不好~ 不過(guò)Google將其應(yīng)用到了網(wǎng)絡(luò)爬蟲(chóng)并發(fā)表了一篇文章哈~

PS: 想了解詳情? 閱讀Paper去... =。=

《simhash算法原理及實(shí)現(xiàn)》 針對(duì)simhash梳理了簡(jiǎn)易的原理介紹以及使用判斷距離的漢明距離, 可以便于讀者快速了解, 但是如果大家想要了解更深層次的實(shí)現(xiàn), 可以去閱讀原版paper《Detecting Near-Duplicates For Web Crawling》和《Similarity estimation techniques from
rounding algorithms》。

原理簡(jiǎn)析

simhash的生產(chǎn)步驟可以分為如下:

1. 提取目標(biāo)文本的關(guān)鍵字feature和權(quán)重weight, 并成對(duì)存儲(chǔ)
   • 如果不知道怎么提取的同學(xué), 可能需要稍微了解全文搜索相關(guān)的知識(shí)
2. 將提取出來(lái)的關(guān)鍵字進(jìn)行傳統(tǒng)Hash, 輸出二進(jìn)制的值
3. 將每一個(gè)關(guān)鍵字提取的Hash按位進(jìn)行運(yùn)算, 如果當(dāng)前位是1, 則增加對(duì)應(yīng)的權(quán)重; 如果當(dāng)前位是0, 增減少當(dāng)前對(duì)應(yīng)的權(quán)重;
4. 將最后得出來(lái)的hash值, 如果大于等于1, 則當(dāng)做1處理; 負(fù)數(shù)和0當(dāng)做0處理, 得出最終的二進(jìn)制值

上述步驟可以簡(jiǎn)化為下圖, 此圖引用了我的數(shù)學(xué)之美系列二 —— simhash與重復(fù)信息識(shí)別中的圖

simhash原理示意

漢明距離

simhash是一種局部敏感Hash。因此可以利用漢明距離去衡量simhash的相似度。

引入Wikipedia的漢明距離介紹:

In information theory, the Hamming distance between two strings of equal length is the number of positions at which the corresponding symbols are different.

字面上意思好像就是兩個(gè)字符串在不一樣字符個(gè)數(shù)的數(shù)量, 在我們現(xiàn)在的應(yīng)用場(chǎng)景就是統(tǒng)計(jì)1或者0的個(gè)數(shù), 然后他們的個(gè)數(shù)差就是距離了。。。一般搜索引擎的歷史經(jīng)驗(yàn)?zāi)J(rèn)是3

PS: 別問(wèn)我怎么知道的3的, 我也是從博客里看來(lái)的, 沒(méi)有數(shù)據(jù)依據(jù)

尋找相似的代碼

尋找完全相似的文件

針對(duì)上述理論, 只要是一個(gè)文檔都可以計(jì)算出兩者的漢明距離, 利用漢明距離來(lái)就可以衡量?jī)蓚€(gè)文檔的相似度了。筆者在這里目前沒(méi)有做太多的工作, 只不過(guò)過(guò)濾了文檔的后綴, 讓相當(dāng)類(lèi)型的文檔進(jìn)行相互的比較。

尋找相似的文件和尋找相似的代碼文件, 其實(shí)本質(zhì)上差距不大。代碼文件有一些特性, 例如前面的聲明和引用都有一列類(lèi)似的地方, 如果在進(jìn)行simhash計(jì)算處理前能夠提前對(duì)代碼文件進(jìn)行預(yù)處理的話, 能夠大幅度的提高整個(gè)代碼文件相似度計(jì)算的精度。

PS: 鑒于思路的完善性和時(shí)間成本, 筆者還沒(méi)有針對(duì)代碼進(jìn)行預(yù)處理

尋找雷同方法函數(shù)

既然利用simhash以及漢明距離可以計(jì)算兩個(gè)文檔的相似度, 然自然可以縮小范圍計(jì)算兩個(gè)函數(shù)方法的相似度。那么問(wèn)題的關(guān)鍵就在于怎么樣才能提取到合適正確的方法函數(shù)內(nèi)容

筆者目前使用的是文本掃描匹配的方式, 但是筆者的同事有提出一種是基于clang插件來(lái)提取編譯器預(yù)處理之后的內(nèi)容進(jìn)行hash比較的可行思路。無(wú)奈鑒于實(shí)現(xiàn)成本和插件無(wú)法獨(dú)立運(yùn)行的方面考慮, 暫時(shí)采用的直接掃描匹配文本的方式進(jìn)行比較。

目前筆者采取的提取方法體方法是:

1. 用正則匹配獲取方法起始行
2. 從起始行開(kāi)始記錄左右括號(hào)的格式, 并且將起始行開(kāi)始的所有字符串記錄
3. 當(dāng)左右括號(hào)的個(gè)數(shù)相互抵消的時(shí)候默認(rèn)當(dāng)做匹配整個(gè)方法, 保存整個(gè)字符串

鑒于方法匹配需要根據(jù)語(yǔ)法實(shí)現(xiàn), 所以目前只能根據(jù)每個(gè)語(yǔ)言的語(yǔ)法特性進(jìn)行截獲, 目前SameCodeFinder僅支持Object-C和Java。

語(yǔ)法特性局限了腳本的可擴(kuò)展性, 步驟一的正則需要和后綴匹配, 步驟二的左右括號(hào)在某些語(yǔ)言下不適用, 只能利用發(fā)現(xiàn)下一個(gè)方法起始行作為步驟三的結(jié)束步驟。

Java目前采用正則:

ur"(public|private)(.*)\)\s?{"

Object-C目前采用正則:

ur"(\-|\+)\s?\(.*\).*(\:\s?\(.*\).*)?{?"

排序

無(wú)論是尋找雷同的文件還是尋找雷同的方法, 最后計(jì)算出的Hash結(jié)果都是N * N個(gè)的, 那么怎么展示計(jì)算的結(jié)果呢? 如果把所有的結(jié)果都展示出來(lái), 那明顯可閱讀性太低。

目前采用的邏輯是:

1. N * N 中第一個(gè)N只找出距離最小的第一個(gè)返回, 這樣過(guò)濾結(jié)果只保留N個(gè)
2. 將第一步過(guò)濾返回的N個(gè)結(jié)果按照從小到大的方式進(jìn)行排序

此外，在執(zhí)行排序的步驟1和步驟2之間, 都可以添加一個(gè)最大距離過(guò)濾, 默認(rèn)不超過(guò)20, 可以大幅度減少步驟1和步驟2的計(jì)算排序過(guò)濾時(shí)間。

開(kāi)源實(shí)現(xiàn)

筆者基于上述思路以及現(xiàn)成的工具, 利用python腳本花了2天時(shí)間去高速實(shí)現(xiàn)了一個(gè)簡(jiǎn)易的python腳本, 并開(kāi)源到了Github上。

訪問(wèn)地址: SameCodeFinder

目前開(kāi)源的版本可能因?yàn)楣P者使用不當(dāng)或者開(kāi)源python版本的simhash的計(jì)算太過(guò)耗時(shí), 因此在性能上存在一定的性能問(wèn)題, 計(jì)算整個(gè)較大的工程需要花費(fèi)不少的時(shí)間(計(jì)算一個(gè)大型工程是分鐘級(jí)別的)。

筆者會(huì)在之后尋找突破方法來(lái)提高這方面的計(jì)算性能~

總結(jié)

SameCodeFinder可以幫助大家尋找相似或者完全重疊的方法以及類(lèi), 極大程度上可以輔助大家尋找可以復(fù)用的代碼。SameCodeFinder的實(shí)現(xiàn)思路都是借用Google的全文相似度比較的現(xiàn)成實(shí)現(xiàn), 并沒(méi)有什么創(chuàng)新, 但是腳本化和針對(duì)語(yǔ)種設(shè)計(jì)的方法識(shí)別, 能夠幫助大家節(jié)省不少直接利用simhash去實(shí)現(xiàn)的成本。

PS: 個(gè)人水平有限, 有錯(cuò)誤之處請(qǐng)大家及時(shí)指出, 隨時(shí)交流哈~

參考文獻(xiàn)

1. CLANG技術(shù)分享系列四:IOS APP無(wú)用代碼/重復(fù)代碼分析
2. A Python Implementation of Simhash Algorithm
3. otool
4. Mac的反編譯工具一：otool (objdump工具的OSX對(duì)應(yīng)工具)
5. iOS APP可執(zhí)行文件的組成
6. simhash算法原理及實(shí)現(xiàn)
7. GS Manku, A Jain, A Das Sarma. Detecting Near-Duplicates For Web Crawling. International Conference on World Wide Web. International Conference on World Wide Web. 141-149. 2007.
8. M. Charikar. Similarity estimation techniques from
   rounding algorithms. In Proc. 34th Annual Symposium
   on Theory of Computing (STOC 2002), pages
   380–388, 2002.
9. 我的數(shù)學(xué)之美系列二 —— simhash與重復(fù)信息識(shí)別
10. Locality-sensitive hashing
11. Hamming_distance
12. Mach-O Executables