器之心整理

參與：思源、一鳴

在項目開發中，優秀的代碼自動補全工具可以提升工作效率。然而，近來的 IDE 基本都使用搜索方法進行補全，在一些場景下效果不佳。近日，有開源項目用深度學習模型進行代碼補全，顯示出非常有潛力的效果。

近日，Reddit 上的一篇帖子引起了網友的熱議。帖子作者「mlvpj」稱：

「我們使用深度學習完成了一個簡單的項目，可以自動進行 Python 代碼補全。」

根據介紹，該項目基于 LSTM 模型，訓練后，負責對代碼的缺失部分進行補全。評價模型的方法是判斷節省了多少的按鍵信息——即模型給出長度為 L 的代碼建議，如果和真實的代碼匹配，則節省 L - 1 個鍵入操作。實驗結果說明，大約有 30%-50% 的鍵入成本可以節省下來。

作者在帖子中表示，他們接下來會嘗試不同的架構，并提高推斷的表現。而現在的模型推斷很慢，不能實際使用。作者已在 GitHub 開源了項目代碼：

鏈接地址: https://github.com/vpj/python_autocomplete

和 IDE 的自動補全有什么區別

該項目對 Python 代碼的自動補全與傳統 IDE（如 PyCharm）等不同。IDE 補全基于檢索方法，需要從已有代碼中進行搜索。

以 PyCharm 中的基本補全（Basic Completion）方法為例。基本補全可幫助補全可見區域的類、方法、關鍵詞代碼。使用時，PyCharm 會分析補全使用情況，并提供當前位置可能的選擇。如果是對空間、參數或變量聲明進行補全，則 PyCharm 會基于類別提供一系列可能的命名。

當出現已定義的類、函數、模塊和變量時，基本補全就會啟動。

此外，PyCharm 也提供智能補全等其他補全功能，但基本上都需要對已有文本進行搜索，根據位置和類型判斷補全的方法。這些方法都沒有配置機器學習模型。

Pycharm 的自動補全介紹：https://www.jetbrains.com/help/pycharm/auto-completing-code.html

深度學習怎樣腦補缺失 TF 代碼

最常用的 PyCharm 自動補全也能省很多功夫，但它需要 IDE 能檢索到你的代碼文件或庫，而且補全會提供多個可能的選項。但是在本項目實驗的工具中，LSTM 會根據上下文語義確定最可能調用的函數，因此它能節省更多的成本。作者表示如果使用束搜索，那么一次能預測 10 多個字符，不過這樣對于實際使用還是有點低效。

在訓練深度補全模型前，我們需要先建立訓練集。開發者會在清洗評論、標注和空行后，構建比較干凈的 Python 代碼。然后，模型會在這些數據上進行訓練與預測。在數據預處理上，開發者發現通過 tokenizing Python 代碼，模型效果比通過 BPE 編碼的字符級預測效果還要好。作者提供了一個簡單的預訓練模型，它是在整個 TensorFlow 項目的 models 代碼中訓練的。

下圖就是作者在驗證集中測試的驗證樣本。綠色的字符表示自動補全的起始位置，用戶需要按下 Tab 鍵選擇開始補全。綠色及后面高亮的灰色字符是自動補全的結果。

如上所示為驗證樣本中的自動補全效果。與代碼生成類似，粗略看起來，似乎效果非常不錯，但實際上會有很多不合理的地方。不過有意思的是，自動補全中所有字符串都只有一個占位操作，這也是非常合理的處理方法。

樣本中自動補全的起始和結束位置都是隨機的，也就是說代碼可能補全到「tensorfl」就結束了，并不會補全完整的標識符「tensorflow」。這在實際場景中用處非常有限，因此作者將生成結束位置限制為終止 token 而修復問題。目前自動補全能完成多種 operator，且當我們增加束搜索的長度時，它完成的代碼長度會更多。

整個模型的主體都是 LSTM，它在 TensorFlow 模型代碼庫訓練后能捕捉非常豐富的 TensorFlow API。如下所示為自動補全模型的主體代碼，基本上簡單的一個 LSTM 就能搞定：

網友評價

項目開源后，有些網友對作者提出了質疑：

「我們已經有很多很好用的自動補全工具了，比如 kite（一個可以在 IDE 上使用的插件），為什么還要費心搞個機器學習模型？」

在討論中，有人提出，一些無良的自動補全工具會悄悄上傳代碼到他們的服務器中，（而自行訓練的深度學習模型不存在這個問題）。

也有人提出，其實不一定要用 LSTM 模型，隱馬爾科夫模型在處理序列數據上效果也很好。

此外，也有網友建議使用 CuDNN 加速 LSTM 的推斷過程。這樣能大大提升推斷速度，集成到 IDE 中也就有了可能。

對于使用深度學習自動補全代碼，機器之心的讀者們有什么想法呢？歡迎留言討論。

擊上方“java進階架構師”，選擇右上角“置頂公眾號”

20大進階架構專題每日送達

進階架構精品專題

• Mysql優化專題（★★★★）
• 網絡協議專題（★★★★）
• 其余18大專題，請在主頁菜單欄查看
• 后臺回復【加群】，獲取BAT真實面經

忘了redis從哪個版本開啟，能夠根據輸入的部分命令前綴給出提示，即自動補全。接下來筆者介紹基于redis實現這個很酷的功能。

about sorted set

假設結果中有mara，marabel，marcela。現在我們輸入mar，就能得到這三個名字，并且輸出結果按照字典排序。在實現這個需求之間，我們先簡單介紹sorted set。

大家都知道sorted set是按照score排序的：

127.0.0.1:6380> zadd test 85 sida
127.0.0.1:6380> zadd test 80 xiaolang
127.0.0.1:6380> zadd test 60 afei
127.0.0.1:6380> zadd test 90 chenssy
127.0.0.1:6380> zadd test 98 yunaiv
127.0.0.1:6380> zrange test 0 -1
1) "afei"
2) "xiaolang"
3) "sida"
4) "chenssy"
5) "yunaiv"

但是如果score都一樣，sorted set是按照什么排序的呢？是按照字典排序的：

127.0.0.1:6380> zadd exam 0 sida
127.0.0.1:6380> zadd exam 0 xiaolang
127.0.0.1:6380> zadd exam 0 chenssy
127.0.0.1:6380> zadd exam 0 yunaiv
127.0.0.1:6380> zadd exam 0 afei
127.0.0.1:6380> zrange exam 0 -1
1) "afei"
2) "chenssy"
3) "sida"
4) "xiaolang"
5) "yunaiv"

這是sorted set一個非常重要的特性，也是我們自動補全需求的一個要點。但是這還不夠，離我們的最終需求還有一段路要走。幸運的是sorted set還有另一個很酷的命令：ZRANK。這個命令能知道你要查詢的key在sorted set中的位置：

127.0.0.1:6380> zrank exam sida
(integer) 2
127.0.0.1:6380> zrank exam yunaiv
(integer) 4
127.0.0.1:6380> zrange exam 2 4
1) "sida"
2) "xiaolang"
3) "yunaiv"

到這里感覺離我們實現自動補全的第一個版本非常接近了，我們能得到sorted set中按照字典排序后任意一個member及其后面N個member。

簡單實現

為了實現最終的自動補全，我們需要付出一些代價：空間。

意思是，對于某個準備添加到sorted set中的member，例如afei，我們不僅要把完整的詞（afei）添加到sorted set中，而且還要添加所有可能的前綴（a, af, afe, afei）。這里為了解決某個詞是真正的member還是某個member的前綴（例如bar既是一個完整的詞，也是某個member例如bark的可能前綴），我們加了一個小把戲，即在真正member的后面增加一個特殊字符，例如"$"，那么afei這個member就會添加下列這些詞：

a, af, afe, afei, afei$

現在假設我們需要添加三個詞：foo, bar, foobar 來進行一些測試， 那么sorted set中就會有如下這些詞：

127.0.0.1:6380> zrange autoc 0 -1
 1) "b"
 2) "ba"
 3) "bar"
 4) "bar$"
 5) "f"
 6) "fo"
 7) "foo"
 8) "foo$"
 9) "foob"
10) "fooba"
11) "foobar"
12) "foobar$"

離我們最終的目標又要近了很多。現在假設用戶輸入"fo"，那么為了實現自動補全，我們需要執行如下命令，仔細查看結果，foo$和foobar$就是我們需要的結果，只需要將特殊后綴$去掉即可（其他沒有以$結尾的詞全部忽略）：

127.0.0.1:6380> zrank autoc fo
(integer) 5
127.0.0.1:6380> zrange autoc 5 -1
1) "fo"
2) "foo"
3) "foo$"
4) "foob"
5) "fooba"
6) "foobar"
7) "foobar$"

更多詞的測試

網址http://antirez.com/misc/female-names.txt 提供了近5000個名字。按照前面說的規則，將所有名字的所有可能前綴全部添加到sorted set中。假定用戶輸入member，那么只需要通過如下兩個命令，得到字典排序后用戶輸入的member后面的50個詞，然后只取$結尾的詞：

127.0.0.1:6380> zrank autoc member
(integer) 8
127.0.0.1:6380> zrange autoc 8 50

時間&空間復雜度

根據官方文檔可知，zrank和zrange的事件復雜度都是O(log(N))。因此，即使數據量比較大，這種方案也是可行的。

ZRANK key member
起始版本：2.0.0
時間復雜度：O(log(N))
ZRANGE key start stop [WITHSCORES]
起始版本：1.2.0
時間復雜度：O(log(N)+M) with N being the number of elements in the sorted set and M the number of elements returned.

那么需要多少內存呢？

假設在最糟糕的情況下，一個長度為M的詞需要添加M+1個詞到sorted set中。那么如果有N個詞，總計需要添加N*(Ma+1)個詞到sorted set中，Ma是這N個詞的平均長度。

幸運的是，實際情況遠比這個要好得多，以近5000個名字為例，只需要添加大約15000個詞到sorted set中，因為這些名詞存在大量重復的前綴。以3個名字為例：marci，marcia，marcile。如果按照最糟糕的情況，需要添加3*(6+1)=21個詞到sorted set中，然而實際情況呢，只需要添加11個詞到sorted set中即可：

m, ma , mar, marc, marci, marci$, marcia, marcia$, marcil, marcile, marcile$。

而且，隨著樣本越來越大，重復的前綴會越大越多。

所以，需要的內存也還OK。是不是覺得美滋滋？哈

查詢預測

我們這次的自動補全是按照字典排序，很多時候，這是我們需要的。但是也有一些情況，我們希望按照相似度來排序。例如google搜索那樣，搜索結果按照頻率和熱度等維度進行排序。例如，當用戶輸入ne，用戶應該希望看到Netflix，news，new york times等這些熱門關鍵詞。

這樣做起來就不那么容易了，如果要能達到根據頻率排序，我們需要一個特別的sorted set能以非阻塞的方式實時更新每個前綴的頻率：

當用戶輸入一個例如"foo"這種查詢，由于它的所有前綴為："f", "fo", "foo"。那么對每個前綴都執行命令：ZINCRBY <prefix> 1 foo ；如果用戶輸入"foobar"，那么對每個前綴都執行：ZINCRBY <prefix> 1 foobar；

這種方法還有一個問題，許多自動補全系統只需要展示TOP N個關鍵詞，假設N為10。但是我們這種方法，如果要計算TOP 10，我們需要取得關鍵詞遠不止10個，理論上我們要這個前綴作為key的sorted set中所有member都取出來。

幸運的是，從統計學上來講，每個對于sorted set中有300個member的前綴，就能得到TOP 5關鍵詞。如果查詢越頻繁，它的得分越高，它最終被選中的概率也就越高。因此，我們要做的就是對搜索字符串的每個前綴：

• 如果前綴作為key的sorted set中member數量還沒有達到300，那么只需要簡單的對其zincrby即可；
• 如果前綴作為key的sorted set中member數量已經達到了300，我們將那些得分比較低的member刪除，增加新的member進來，從而達到關鍵詞頻率不斷迭代的效果。

這個方法一下子可能理解不過來，沒關系，舉個栗子。假設現在用戶輸入了next，其前綴n為key的sorted set中已經有netflix(100), news(120), new york(80), near(23), nequ(1)。由于這個前綴對應的sorted set中的member數量還沒有300，所以，執行：zincrby n 1 next。其中n是前綴，next是用戶輸入的關鍵詞。假設現在用戶輸入了next，其前綴n為key的sorted set中已經有netflix(100), news(120), new york(80), near(23), 省略295個score大于1的關鍵詞, nequ(1)。由于這個前綴對應的sorted set中的member數量達到了300，所以，先刪除得分比較低的nequ，再執行：zincrby n 1 next。

這個方法跟用戶輸入關鍵詞分布有很大的關聯性，如果用戶輸入的所有關鍵詞頻率比較接近，那么這個方法得到的數據并不是很可靠。但是我們知道這不是問題，因為搜索就是絕大部分人在搜索那一小部分關鍵詞集合。

清理階段

由于上面提到的搜索長尾效應，我們可以講那些得分為1的member清理掉，因為用戶對這些關鍵詞幾乎沒有任何關注度。清理操作還能夠減少使用內存，從而讓redis保存更多更有用的數據。

知識總結

• sorted set數據結構中，如果member的score一樣，那么按照字典排序。
• zrank命令能得到指定member在結果中的位置，并可以取排在它后面N個member。
• zincrby能給指定的sorted set中的member加分。

參考：http://oldblog.antirez.com/post/autocomplete-with-redis.html

來源：轉載自阿飛的博客