器之心整理

参与：思源、一鸣

在项目开发中，优秀的代码自动补全工具可以提升工作效率。然而，近来的 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

来源：转载自阿飞的博客