【51CTO.com快譯】本篇文章意在對(duì)github倉(cāng)庫(kù)里不同編程語(yǔ)言中的高頻詞進(jìn)行可視化展現(xiàn)。

數(shù)據(jù)源自2016年年中至年末期間，約300萬(wàn)套開源GitHub庫(kù)。其結(jié)果以文本詞云的形式展示如下：

相關(guān)趣聞 

• 這里保存了來(lái)自各套代碼庫(kù)中不同編程語(yǔ)言的對(duì)應(yīng)常用詞。GitHub的語(yǔ)言識(shí)別功能將這套庫(kù)的大部分內(nèi)容視為C++。這樣的結(jié)果不無(wú)道理，畢竟其中相當(dāng)一部分語(yǔ)言的誕生是受到C/C++的啟發(fā)：

• 許可文本一般位于每種編程語(yǔ)言的注釋當(dāng)中。在全部語(yǔ)言內(nèi)，Java代碼以顯著優(yōu)勢(shì)勝出，其在全部966個(gè)來(lái)自許可文本的詞中占據(jù)127個(gè)：

Java的優(yōu)勢(shì)太過(guò)明顯，因此對(duì)許可文本進(jìn)行過(guò)濾。

• Lua是惟一一款在前1000條常用詞中包含一個(gè)臟話的編程語(yǔ)言——感興趣的朋友可以來(lái)找找看。
• 在Go語(yǔ)言中，err的使用頻率與return一樣。

下面，將這些數(shù)據(jù)是如何產(chǎn)生的。

如何歸納? 

利用BigQuery從github_repos數(shù)據(jù)集中提取單個(gè)詞匯。每個(gè)詞匯在提取時(shí)，都會(huì)伴隨其出現(xiàn)時(shí)所在的前十行代碼。

在保存各個(gè)詞之前，使用以下幾項(xiàng)限制條件：

• 此詞匯出現(xiàn)的行應(yīng)不超過(guò)120個(gè)字符。這能幫助我們過(guò)濾掉那些并非人為編寫的代碼，例如經(jīng)過(guò)精簡(jiǎn)的JavaScript代碼。
• 忽略掉了標(biāo)點(diǎn)符號(hào)(, ; : .)、運(yùn)算符(+ - * ...)與數(shù)字。因此如果該代內(nèi)容為a+b+42，那么過(guò)濾后的內(nèi)容僅為：a與b。
• 忽略掉了那些包含“許可標(biāo)記”的行——即那些出現(xiàn)在許可文本內(nèi)的詞匯（例如license、noninfringement等）。許可文本在代碼中非常常見，雖然初看起來(lái)確實(shí)非常有趣，但通過(guò)歸納結(jié)果可以發(fā)現(xiàn)其內(nèi)容數(shù)量太多，因此決定將其過(guò)濾掉。
• 對(duì)各詞的大小寫狀態(tài)進(jìn)行了區(qū)分：This與this被視為兩個(gè)獨(dú)立的詞。

數(shù)據(jù)是如何進(jìn)行收集的？

在這部分內(nèi)容中，我們將深入了解詞匯提取方式。如果大家不感興趣，也可直接跳轉(zhuǎn)至詞云算法部分。

來(lái)自GitHub公共數(shù)據(jù)集內(nèi)的數(shù)據(jù)由BigQuery負(fù)責(zé)索引:github_repos

BigQuery以明文形式在一套表中存儲(chǔ)各索引文件的具體內(nèi)容，相當(dāng)于key-value 的形式：

要建立這樣一套詞匯云，需要使用權(quán)重以進(jìn)行詞匯擴(kuò)展。而要獲取權(quán)重值，可以將各文本拆分為獨(dú)立詞匯（分詞）

遺憾的是，這種簡(jiǎn)單的方法得出的結(jié)果并不理想——因?yàn)槿藗儫o(wú)法理解各個(gè)詞出現(xiàn)的具體上下文。

目標(biāo)是希望能夠避免這種問(wèn)題，并保證人們能夠查看各個(gè)詞及其出現(xiàn)的實(shí)際語(yǔ)境：

為了實(shí)現(xiàn)這一目標(biāo)，創(chuàng)建了一套臨時(shí)表，而非直接計(jì)算各行中詞匯的出現(xiàn)次數(shù)：

這不僅讓我得以將每個(gè)詞匯與其“上下文”配合起來(lái)，同時(shí)也將整體數(shù)據(jù)量由數(shù)TB縮減至約12 GB。

為了從這份表中獲得出現(xiàn)頻率***的詞匯，我們可以采用之前提到的方法，即將內(nèi)容拆分成具體詞匯，而后利用表對(duì)每個(gè)詞進(jìn)行分組。如果我們將原始行保留在中間表內(nèi)，亦可獲取各詞匯的對(duì)應(yīng)上下文：

通過(guò)這種中間表示方式，我們可以使用SQL窗口函數(shù)對(duì)各詞匯進(jìn)行分組，并獲得各個(gè)詞的前十行（更多細(xì)節(jié)信息，請(qǐng)參閱：為每個(gè)分類選定前十條記錄，英文原文）。

現(xiàn)在大家可以在此查看提取到的代碼：extract_words.sql。

備注一:作者的SQL水平不高，所以如果大家其中的錯(cuò)誤或者更理想的數(shù)據(jù)獲取方式，請(qǐng)?jiān)谠u(píng)論中指出。另外，雖然目前的腳本能夠正常起效，但其中某些結(jié)果可能略有偏差。

備注二:BigQuery的表現(xiàn)非常出色。其強(qiáng)大、靈活且速度極快。在這里，要向能夠玩轉(zhuǎn)它的朋友表達(dá)十二分的敬意。

如何進(jìn)行詞匯云渲染？

詞匯云的核心部分，使用的其實(shí)是一條非常簡(jiǎn)單的算法：

for each word `w`: 
  repeat: 
    place word `w` at random point (x, y) 
  until `w` does not intersect any other word 

為了避免發(fā)生內(nèi)部***循環(huán)，可以嘗試限定次數(shù)數(shù)量并/或去掉那些字體大小不符合要求的詞匯。

從抽象的角度來(lái)講，可以用矩形來(lái)表達(dá)這個(gè)問(wèn)題：對(duì)于每個(gè)矩形，嘗試將其放在畫布上，直到其任何像素皆不與其它圖形相交。

很明顯，當(dāng)畫布被大量占用時(shí)，為新的矩形找到放置點(diǎn)將變得非常困難甚至完全不可能。

我們可以通過(guò)多種方法對(duì)已占用空間進(jìn)行索引，從而加速此項(xiàng)算法：

• 使用區(qū)域求和表以快速通過(guò)O(1)次計(jì)算判斷新矩形是否與其下矩形相交。這種方法的弊端在于，每一次畫布進(jìn)行更新時(shí)，整套表也需要進(jìn)行一次更新，這會(huì)導(dǎo)致O（N2）性能;
• 使用R-Tree來(lái)維護(hù)排序可以快速判斷某一新的候選矩形是否與其下任何矩形相交。利用這種方法，像素相交查找速度要比區(qū)域求和表的效果更慢，但索引的維護(hù)速度則更快。

作者認(rèn)為這兩種方法都存在一種重要弊端，即很可能在找到適合新矩形的空間之前浪費(fèi)大量嘗試次數(shù)，這對(duì)于性能保障非常不利。

作者希望嘗試一些不同的實(shí)現(xiàn)方式。建立一套索引，利用其快速選擇一個(gè)足夠大的矩形來(lái)匹配我新加入的矩形。這意味著為空余空間構(gòu)建索引，而非對(duì)占用空間構(gòu)建索引。

這里，選擇了四叉樹作為索引方案。其中每一個(gè)非旁枝節(jié)點(diǎn)都包含有可用于其下子枝的空余像素信息。從基礎(chǔ)層面來(lái)講，這就能夠快速回答我們的問(wèn)題：“是否還有足夠的空間來(lái)容納M個(gè)像素？”如果四叉樹中的可用像素空間低于M，則不再需要進(jìn)一步查詢其子分枝。

至此，完成了具體算法的選擇。在本系列文章的下一部分內(nèi)容中，將一同來(lái)看其實(shí)際效果以及最終得到的不同編程語(yǔ)言中高頻詞匯的分析結(jié)論。

原文標(biāo)題：Common Words

原文作者：anvaka

文章審核人：老曹  譯者：核子可樂(lè)

老曹專欄文章鏈接：http://zhuanlan.51cto.com/columnlist/laocao/

【51CTO譯稿，合作站點(diǎn)轉(zhuǎn)載請(qǐng)注明原文譯者和出處為51CTO.com】