github熱度最高的語言是什么，用wordcloud制作流程解析（上）
譯文【51CTO.com快譯】本篇文章意在對github倉庫里不同編程語言中的高頻詞進(jìn)行可視化展現(xiàn)。
數(shù)據(jù)源自2016年年中至年末期間，約300萬套開源GitHub庫。其結(jié)果以文本詞云的形式展示如下：
相關(guān)趣聞
- 這里保存了來自各套代碼庫中不同編程語言的對應(yīng)常用詞。GitHub的語言識(shí)別功能將這套庫的大部分內(nèi)容視為C++。這樣的結(jié)果不無道理，畢竟其中相當(dāng)一部分語言的誕生是受到C/C++的啟發(fā)：
- 許可文本一般位于每種編程語言的注釋當(dāng)中。在全部語言內(nèi)，Java代碼以顯著優(yōu)勢勝出，其在全部966個(gè)來自許可文本的詞中占據(jù)127個(gè)：
Java的優(yōu)勢太過明顯，因此對許可文本進(jìn)行過濾。
- Lua是惟一一款在前1000條常用詞中包含一個(gè)臟話的編程語言——感興趣的朋友可以來找找看。
- 在Go語言中，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)不超過120個(gè)字符。這能幫助我們過濾掉那些并非人為編寫的代碼，例如經(jīng)過精簡的JavaScript代碼。
- 忽略掉了標(biāo)點(diǎn)符號(hào)(, ; : .)、運(yùn)算符(+ - * ...)與數(shù)字。因此如果該代內(nèi)容為a+b+42，那么過濾后的內(nèi)容僅為：a與b。
- 忽略掉了那些包含“許可標(biāo)記”的行——即那些出現(xiàn)在許可文本內(nèi)的詞匯（例如license、noninfringement等）。許可文本在代碼中非常常見，雖然初看起來確實(shí)非常有趣，但通過歸納結(jié)果可以發(fā)現(xiàn)其內(nèi)容數(shù)量太多，因此決定將其過濾掉。
- 對各詞的大小寫狀態(tài)進(jìn)行了區(qū)分：This與this被視為兩個(gè)獨(dú)立的詞。
數(shù)據(jù)是如何進(jìn)行收集的？
在這部分內(nèi)容中，我們將深入了解詞匯提取方式。如果大家不感興趣，也可直接跳轉(zhuǎn)至詞云算法部分。
來自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é)果并不理想——因?yàn)槿藗儫o法理解各個(gè)詞出現(xiàn)的具體上下文。
目標(biāo)是希望能夠避免這種問題，并保證人們能夠查看各個(gè)詞及其出現(xiàn)的實(shí)際語境：
為了實(shí)現(xiàn)這一目標(biāo)，創(chuàng)建了一套臨時(shí)表，而非直接計(jì)算各行中詞匯的出現(xiàn)次數(shù)：
這不僅讓我得以將每個(gè)詞匯與其“上下文”配合起來，同時(shí)也將整體數(shù)據(jù)量由數(shù)TB縮減至約12 GB。
為了從這份表中獲得出現(xiàn)頻率***的詞匯，我們可以采用之前提到的方法，即將內(nèi)容拆分成具體詞匯，而后利用表對每個(gè)詞進(jìn)行分組。如果我們將原始行保留在中間表內(nèi)，亦可獲取各詞匯的對應(yīng)上下文：
通過這種中間表示方式，我們可以使用SQL窗口函數(shù)對各詞匯進(jìn)行分組，并獲得各個(gè)詞的前十行（更多細(xì)節(jié)信息，請參閱：為每個(gè)分類選定前十條記錄，英文原文）。
現(xiàn)在大家可以在此查看提取到的代碼：extract_words.sql。
備注一:作者的SQL水平不高，所以如果大家其中的錯(cuò)誤或者更理想的數(shù)據(jù)獲取方式，請?jiān)谠u論中指出。另外，雖然目前的腳本能夠正常起效，但其中某些結(jié)果可能略有偏差。
備注二:BigQuery的表現(xiàn)非常出色。其強(qiáng)大、靈活且速度極快。在這里，要向能夠玩轉(zhuǎn)它的朋友表達(dá)十二分的敬意。
如何進(jìn)行詞匯云渲染？
詞匯云的核心部分，使用的其實(shí)是一條非常簡單的算法：
- 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ù)量并/或去掉那些字體大小不符合要求的詞匯。
從抽象的角度來講，可以用矩形來表達(dá)這個(gè)問題：對于每個(gè)矩形，嘗試將其放在畫布上，直到其任何像素皆不與其它圖形相交。
很明顯，當(dāng)畫布被大量占用時(shí)，為新的矩形找到放置點(diǎn)將變得非常困難甚至完全不可能。
我們可以通過多種方法對已占用空間進(jìn)行索引，從而加速此項(xiàng)算法：
- 使用區(qū)域求和表以快速通過O(1)次計(jì)算判斷新矩形是否與其下矩形相交。這種方法的弊端在于，每一次畫布進(jìn)行更新時(shí)，整套表也需要進(jìn)行一次更新，這會(huì)導(dǎo)致O（N2）性能;
- 使用R-Tree來維護(hù)排序可以快速判斷某一新的候選矩形是否與其下任何矩形相交。利用這種方法，像素相交查找速度要比區(qū)域求和表的效果更慢，但索引的維護(hù)速度則更快。
作者認(rèn)為這兩種方法都存在一種重要弊端，即很可能在找到適合新矩形的空間之前浪費(fèi)大量嘗試次數(shù)，這對于性能保障非常不利。
作者希望嘗試一些不同的實(shí)現(xiàn)方式。建立一套索引，利用其快速選擇一個(gè)足夠大的矩形來匹配我新加入的矩形。這意味著為空余空間構(gòu)建索引，而非對占用空間構(gòu)建索引。
這里，選擇了四叉樹作為索引方案。其中每一個(gè)非旁枝節(jié)點(diǎn)都包含有可用于其下子枝的空余像素信息。從基礎(chǔ)層面來講，這就能夠快速回答我們的問題：“是否還有足夠的空間來容納M個(gè)像素？”如果四叉樹中的可用像素空間低于M，則不再需要進(jìn)一步查詢其子分枝。
至此，完成了具體算法的選擇。在本系列文章的下一部分內(nèi)容中，將一同來看其實(shí)際效果以及最終得到的不同編程語言中高頻詞匯的分析結(jié)論。
原文標(biāo)題：Common Words
原文作者：anvaka
文章審核人：老曹 譯者：核子可樂
老曹專欄文章鏈接：http://zhuanlan.51cto.com/columnlist/laocao/
【51CTO譯稿，合作站點(diǎn)轉(zhuǎn)載請注明原文譯者和出處為51CTO.com】
