【51CTO.com快譯】本篇文章意在對github倉庫里不同編程語言中的高頻詞進行可視化展現。

數據源自2016年年中至年末期間，約300萬套開源GitHub庫。其結果以文本詞云的形式展示如下：

 

相關趣聞 

• 這里保存了來自各套代碼庫中不同編程語言的對應常用詞。GitHub的語言識別功能將這套庫的大部分內容視為C++。這樣的結果不無道理，畢竟其中相當一部分語言的誕生是受到C/C++的啟發：

• 許可文本一般位于每種編程語言的注釋當中。在全部語言內，Java代碼以顯著優勢勝出，其在全部966個來自許可文本的詞中占據127個：

Java的優勢太過明顯，因此對許可文本進行過濾。

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

 

下面，將這些數據是如何產生的。

 

如何歸納? 

利用BigQuery從github_repos數據集中提取單個詞匯。每個詞匯在提取時，都會伴隨其出現時所在的前十行代碼。

在保存各個詞之前，使用以下幾項限制條件：

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

 

數據是如何進行收集的？

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

來自GitHub公共數據集內的數據由BigQuery負責索引:github_repos

BigQuery以明文形式在一套表中存儲各索引文件的具體內容，相當于key-value 的形式：

 

要建立這樣一套詞匯云，需要使用權重以進行詞匯擴展。而要獲取權重值，可以將各文本拆分為獨立詞匯（分詞）

 

遺憾的是，這種簡單的方法得出的結果并不理想——因為人們無法理解各個詞出現的具體上下文。

目標是希望能夠避免這種問題，并保證人們能夠查看各個詞及其出現的實際語境：

 

為了實現這一目標，創建了一套臨時表，而非直接計算各行中詞匯的出現次數：

這不僅讓我得以將每個詞匯與其“上下文”配合起來，同時也將整體數據量由數TB縮減至約12 GB。

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

通過這種中間表示方式，我們可以使用SQL窗口函數對各詞匯進行分組，并獲得各個詞的前十行（更多細節信息，請參閱：為每個分類選定前十條記錄，英文原文）。

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

備注一:作者的SQL水平不高，所以如果大家其中的錯誤或者更理想的數據獲取方式，請在評論中指出。另外，雖然目前的腳本能夠正常起效，但其中某些結果可能略有偏差。

備注二:BigQuery的表現非常出色。其強大、靈活且速度極快。在這里，要向能夠玩轉它的朋友表達十二分的敬意。

 

如何進行詞匯云渲染？

詞匯云的核心部分，使用的其實是一條非常簡單的算法：

 

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

為了避免發生內部***循環，可以嘗試限定次數數量并/或去掉那些字體大小不符合要求的詞匯。

從抽象的角度來講，可以用矩形來表達這個問題：對于每個矩形，嘗試將其放在畫布上，直到其任何像素皆不與其它圖形相交。

很明顯，當畫布被大量占用時，為新的矩形找到放置點將變得非常困難甚至完全不可能。

我們可以通過多種方法對已占用空間進行索引，從而加速此項算法：

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

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

作者希望嘗試一些不同的實現方式。建立一套索引，利用其快速選擇一個足夠大的矩形來匹配我新加入的矩形。這意味著為空余空間構建索引，而非對占用空間構建索引。

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

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

原文標題：Common Words

原文作者：anvaka

文章審核人：老曹  譯者：核子可樂

 

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

【51CTO譯稿，合作站點轉載請注明原文譯者和出處為51CTO.com】