引用

Raphael Sirres and Tegawendé F. Bissyandé and Dongsun Kim and David Lo and Jacques Klein and Kisub Kim and Yves Le Traon. Augmenting and structuring user queries to support efficient free-form code search. Empirical Software Engineering, 2018, 23(5): 2622-2654

摘要

源代码术语（例如方法名称和变量类型）通常与搜索查询中提到的概念词不同。这个词汇不匹配的问题会使代码搜索效率低下。在本文中，我们介绍了 COdevoCABUlary（CoCaBu），这是一种解决自由格式代码搜索查询时出现的词汇不匹配问题的方法。我们的方法利用了常见的开发者问题和相关的专家答案，以使用相关但缺省的结构化代码实体来扩展用户查询，以提高在大型代码存储库中匹配相关代码示例的性能。为了实例化这种方法，我们在 GitHub 和 Stack Overflow 问答数据之上构建了代码搜索引擎 GitSearch。我们在多个方面对 GitSearch 进行评估，以证明（1）对于用户可接受的答案，其代码搜索结果是正确的；（2）结果在质量上要优于现有的 Internet 级代码搜索引擎；（3）我们的引擎在帮助用户完成解决编程任务方面与 Google 等网络搜索引擎相比具有竞争力；（4）GitSearch 提供了社区可以接受或感兴趣的代码示例，作为 Stack Overflow 问题的答案。

2 动机

在代码搜索中，与查询词匹配的索引中关键字可能不包含 API 名称，因为可通过几种不同的类和方法来翻译和实现单个编程概念。这种不匹配可能会降低代码搜索结果的质量。

我们的目标是解决词汇不匹配问题，使代码搜索引擎为用户自由格式查询返回高度相关的代码段。如果我们可将搜索查询中使用的单词适当地转换为在源代码中找到的关键字，则搜索结果将更加准确，如图 2。这是我们在下一节中描述的方法的实际搜索结果。从真实世界代码中提取生成的代码片段实际上与“问答”帖子中问题所接受的人工回答答案相同。

由于词汇不匹配问题，当前最新的代码搜索方法无法完全支持自由格式和复杂查询，例如开发者在问答网站上向其他有经验开发者提出的查询。

我们利用问答网站的开发者问题和相关代码段记录概念映射，即人类概念到程序元素的映射。大量此类可用映射将缓解词汇失配问题。任何以自然语言编写的开发者查询都可转换为明确引用特定程序元素的程序查询。然后可将此新查询与任何源代码文件直接匹配。

3 方法

CoCaBu 旨在检索最相关的代码片段以回答用户的自由格式查询。图 3 概述了我们的方法。

搜索过程从用户的自由格式查询开始，即以自然语言写成的句子：

(a)-对于给定查询，CoCaBu 首先在“问答”论坛中搜索相关帖子。搜索代理将开发者自由格式的查询转发到 Web 搜索引擎来收集和排列问答中与查询最相关的文档中的条目。

(b)-然后 CoCaBu 主要根据先前确定的帖子中的代码段生成增强查询。这些代码段已被开发者批准为发布问题中可接受的代码示例，因此 CoCaBu 将其视为人类概念到程序元素的翻译。CoCaBu 的代码查询生成器会创建另一个查询，包含最初的用户查询字词和提取的摘录中的程序元素。CoCaBu 预先为问答帖子建立了摘要索引来加快这一步。

(c)-构造扩展查询后，CoCaBu 会在源代码文件中搜索与查询词匹配的代码位置。它通过爬取大量公共代码库，为源代码中程序元素预先构建代码索引，进而生成给定的增强查询的搜索结果。可以以相关的源代码文件或代码片段等不同粒度向用户呈现该搜索结果。

3.1 结构化代码实体提取

为有效地在存储库中搜索源代码以查找与来自“问答”帖子的信息相匹配的相关代码位置，CoCaBu 会在代码段和源代码文件中创建结构化代码实体的索引。表 1 列出了 CoCaBu 在解析来自“问答”帖子的摘录和来自代码库的源代码文件时收集的结构化代码实体。

包装代码段：CoCaBu 通过使用自定义伪类和方法模板来删除省略号并包装代码段，以使其能够由标准 Java 解析器进行解析。

使名称合格：CoCaBu 使用 AST 遍历期间收集的结构信息将不合格名称转换为部分合格名称。图 4 以方法限定之前和之后的代码片段示例说明了此处理步骤。

文本处理：CoCaBu 将源代码视为文本进行预处理，如标记化，停用词移除和词干提取。

索引：利用收集的信息集，CoCaBu 可用 Lucene 构建文本术语索引及源代码中找到的结构化代码实体。Lucene 将数据存储为索引，索引由一组代表本例中用于搜索的基本代码元素的字段组成。字段中填充了上述过程产生的结构和文本信息及特定于索引的元数据。

3.2 搜索代理

搜索代理以自由格式查询作为输入，并返回从开发者问答网站收集的一组相关帖子作为输出。该组件的目的是收集足够的数据，以便搜索引擎以后可以发现如何将自然语言概念转换为程序元素。问答环节中的代码片段可提供潜在的翻译规则，通过减轻用户查询和源代码元素之间存在的词汇不匹配问题，促进后续代码搜索过程。

依靠 Google Web Search，Bing 和 Yahoo Search 等通用引擎，CoCaBu 可以搜索多个不同论坛，并根据它们与查询的相关性对搜索结果进行排名。我们认为专用语文本搜索的通用引擎比“问答”论坛中其他内置搜索引擎要好。搜索代理会过滤 Web 搜索结果以消除与问答帖子无关的 URL。相关帖子排名根据通用引擎建议的排序顺序保留。如果我们考虑 “用 Java 生成随机词？”问题，Google Web Search 支持的搜索代理返回表 2 中列出的相关帖子。

3.3 代码查询生成器

代码查询生成器创建一个代码搜索查询，该查询搜索查询可增强和构造由搜索代理采取的自由格式查询。该增强查询是程序元素的列表以及可用于匹配文档的自然语言术语。

为生成增强查询，CoCaBu 从搜索代理返回的相关帖子中问题答案嵌入的代码片段中提取结构化代码实体(图 5(b))。代码查询生成器组件仅问答网站社区批准接受的答案。

图 5(c)中基于 Lucene 搜索引擎查询格式说明了由代码查询生成器生成的增强查询。读者可以从所示的示例查询中观察到以下内容，其字段语义先前已在表 1 中进行了描述：

-词干提取之后，用户自由格式查询(图 5(a))中的术语(不含停用词)将保留在增强查询中。

-问答片段(图 5(b))中收集的结构化代码实体在增强型查询中被提及其类型。

CoCaBu 通过建立帖子索引加快代码查询生成速度。通常问答论坛提供使用如 XML 的结构化语言格式化过的帖子存档。如图 6，CoCaBu 下载问答站点中的帖子，提取每个帖子的元数据(帖子 ID，问题标题)和代码段，然后分析每个代码段以检索结构代码实体。

如果已经为目标帖子建立了索引，则预先构建索引可以减少查询生成时间。对于收集的新帖子，该组件按照图 6 所示的过程将其插入索引中。

3.4 代码搜索引擎

代码搜索引擎从代码查询生成器获取扩展查询，并向发出原始查询的用户提供搜索结果列表。搜索结果具有两个粒度级别：,

-如果查询被扩大，则由于结构代码实体在源文件中匹配，并且搜索结果可以集中于仅显示发生匹配的代码行的摘录，因此可以进一步控制粒度。

-如果查询没有得到扩展(即搜索代理未在前十个网络搜索结果集中找到任何问答链接)，则搜索引擎会针对每个结果返回一个完整的文件。

为有效提供增强查询的答案，代码搜索引擎构建了在存储库中找到的源代码文件索引(图 7)。随着增强查询中的结构化实体以及 NLP 术语使用将列出最相关文件的索引直接进行搜索，匹配变得非常简单。

由于代码段索引和代码索引(分别如图 6 和 7 所示)以相同格式存储索引，因此全文搜索可以有效获得搜索结果。源代码文件就是文档，而结构代码实体则代表搜索词。

由于显示源代码文件的全部内容通常使用户无法理解代码示例，代码搜索引擎会在汇总内容并突出显示与给定查询相关的代码行后显示文件。为总结和突出显示搜索结果，CoCaBu 使用一种依赖于查询的方法，根据源文件中出现的查询词来显示一组包含匹配查询关键字的相邻代码行。最后，我们突出显示了摘要文件中出现的查询词以方便识别。

3.5 GitSearch 代码搜索引擎

为构建 GitSearch 代码搜索引擎，我们选择 Stack Overflow 作为问答站点来检索开发者认可的相关代码段。我们直接利用 Google 网络搜索实现搜索代理。用户查询将发送到 Google 搜索以检索所有相关问答环节(即文本相似度匹配)。其他实现可能使用其他 Web 搜索引擎，包括问答网站内置搜索服务。

我们使用 2008 年 7 月至 2015 年 3 月之间的 Stack Overflow 帖子转储，其中包含 1363002 个 Java 和 Android 标记的问题来构建代码段索引。我们使用具有实际帖子(即问题和答案对)以及其他相关元数据(例如标签，创建日期，问题 ID，帖子的查看数量和答案得分)的 posts.xml 文档。此外，我们从已接受且答案为正的答案中摘录片段以确保代码示例的高质量。为说明帖子中的更新，我们利用 StackExchange REST API9 提取元数据和摘要。 CoCaBu 的用户可从其他多个问答论坛收集和使用帖子，以扩展搜索更多代码段的机会。

对于代码索引，我们考虑了至少被 fork 一次的非玩具、活跃的、主要语言是 Java 的 GitHub 项目(我们专注于 Java 和 Android)，然后在构建代码索引时从项目中删除所有非 Java 文件。表 3 显示了这项工作中收集的 GitHub 项目统计信息。

表 4 总结了根据 Stack Overflow 帖子和 GitHub 开源代码存储库构建的结果索引(即图 6 和 7 中所示的代码片段和代码索引)。

4 评估

评估包括：手动验证，在线调查，受控用户研究和实时研究，分别专注于回答以下研究问题：

• RQ1：GitSearch 可以有效地为开发者查询生成相关的代码示例吗？
• RQ2：GitSearch 的性能是否比现有的代码搜索引擎好得多？
• RQ3：GitSearch 在帮助解决编程任务方面是否与一般搜索引擎竞争？
• RQ4：Stack Overflow 用户可以接受 GitSearch 的搜索结果作为答案吗？

4.1 RQ1：针对社区基本事实的验证

首先，我们调查 GitSearch 产生的结果的相关性。

研究设计：我们基于两个要求从 Stack Overflow 帖子中收集著名开发者问题：(i)帖子中问题必须与“ Java”相关，并且(ii)其答案必须包含代码段。我们选择“观看次数”值最高的前 10 个帖子，以确保研究重点放在有代表性的开发者任务上。表 5 列出了研究中使用的查询。

结果：图 8 显示 GitSearch 结果很大程度上与用户查询相关，间接证明该方法的准确性。

4.2 RQ2: 与其他代码搜索引擎的比较

我们进行了一项用户研究，要求开发者检查不同代码搜索引擎的有效性，并从从业者的角度评估 GitSearch 的有用性。

研究设计：我们通过在软件开发者社区(750 个 GitHub，Mozilla 和 Eclipse 开发者及一家韩国公司的开发者)中发布在线调查邀请来招募参与者。所有调查邀请中，我们明确指出仅邀请具有 Java 经验的开发者/学生。为促进研究，我们构建了一个基于 Web 的调查工具，它在三个匿名列中显示来自 OpenHub，Codota 和 GitSearch 的代码搜索结果。为避免人们对使用该工具的偏见，我们仅考虑使用表 5 中的查询完整完成研究的参与者的条目。

结果：研究结束时，我们有 47 位参与者尝试了该工具(至少一项答复)。他们中有些人没有完成研究。其中，有 14 位参与者完成了这项研究。

图 9(a)显示了每个代码搜索引擎的选定搜索结果数。与所有其他查询相比，参与者选择了更多 GitSearch 返回的代码示例。除查询 Q3 外，所选结果数量是其他结果的两倍多。

此外，我们计算了所选搜索结果排名分布。若用户选择一个引擎的多个搜索结果，则我们只会计算排名最高的结果。如图 9(b)，GitSearch 的中值等于 1，而其他引擎为 2。

讨论：尽管我们无法与最新的 CodeHow 工具进行比较，但其作者报告说，它产生的相关结果比 OpenHub 多 20％，而图 9(a)表明，GitSearch 比 OpenHub 多 50％。

4.3 RQ3: 与传统搜索引擎的比较

我们对 GitSearch 和一般网络搜索引擎(谷歌和百度)进行比较研究。由于许多开发者依靠通用搜索引擎查找编程任务解决方案，我们评估了 GitSearch 与此类引擎相比的竞争力。

研究设计：我们从三所大学(法国皮埃尔和玛丽·居里大学，卢森堡大学和中国浙江大学)招募了 20 名研究生。要求每个学生找到解决以下两个编程任务的代码示例：

• 任务 1：发送电子邮件-编写 Java 程序以从文本文件中读取电子邮件地址列表，然后将带有附件文件的电子邮件发送到所有电子邮件地址。
• 任务 2：图像格式转换-编写 Java 程序以读取 JPEG 格式的图像，将其旋转 180°，然后将其转换为 PNG 格式。

结果：研究参与者输入了 77 种不同形式自由格式查询(任务 1 为 37，任务 2 为 40)。

表 7 显示了参与者为不同搜索引擎标记的相关搜索结果的百分比。这表明 GitSearch 与 Web 搜索引擎相比具有竞争力。我们没考虑在 Web 搜索中遵循链接重定向和解析网页以查找不完整的代码段所需的努力。另外 GitSearch 提供了现实中的工作代码示例。

讨论：我们从参与者输入的 77 个查询中发现，网络搜索引擎上输入的查询更加“完整”，且在参与者之间更具冗余性。参与者承认自己遵循了网络搜索引擎的自动完成建议。

我们通过对参与者在网络搜索引擎上输入的 10 个查询进行随机抽样并在 GitSearch 上使用它们来执行交叉验证实验。我们对参与者在 GitSearch 上输入的 10 个查询进行随机抽样，并在 Google 搜索引擎上使用它们。对 GitSearch，任务 1 和 2 的 MRR 值分别为 0.94 和 0.90。对 Web 搜索引擎，任务 1 和 2 的 MRR 值分别降低到 0.72 和 0.65。

这些结果表明了 GitSearch 的未来工作方向，我们必须使用日志记录和反馈机制来记录成功的查询，并建议它们自动完成对未来请求者的查询。

4.4 RQ4: Live study into the wild

我们发布代码搜索结果作为 Stack Overflow 问题的答案来评估代码搜索引擎的有用性。这项研究调查了开发者遇到编程问题时如何解释有效的代码示例。尽管 GitSearch 并非旨在直接回答开发者的问题，但可帮助他们找到编程任务的起点。由于 Stack Overflow 中有许多未回答问题，因此 GitSearch 在 Stack Overflow 方面可以是一个很好的第一回答者。

研究设计：我们使用 Java 标签监视问题，并根据以下标准从其中选择了 25 个：

• 有关 Java 编程的问题。
• “操作方法”问题，例如“列出 Java 项目中资源目录中的所有文件”。
• 没有工具使用问题，例如“如何在 Eclipse 中创建项目？”
• 没有概念性问题，例如“ A 或 B 之间有什么区别”和“为什么这门课这么慢？”。
• 尚未有人回答的问题。

对每个问题，我们提取其标题并将其放入 GitSearch 中，并将最好的搜索结果发布为答案。答案包括 1) GitSearch 选择的最相关代码片段，及 2) GitSearch 从中找到片段的原始源代码超链接。我们对 OpenHub 重复相同过程，以将其有效性与我们的技术进行比较。

结果：如表 8 所示，GitSearch 比 OpenHub 回答了更多问题并获得了更多的赞成和反对意见，而人类回答则接受了更多的赞成票和更少的反对票。表 8 展示了我们在 GitSearch，OpenHub 和人类间进行的实时研究结果。“#Ans”中的“Resp”是每种技术回答的问题数量，而“Acc”是发问者接受的答案数量。“Upvotes”和“Downvotes”票数是 Stack Overflow 用户给出的票数。“Pos. Comm.”和“Neg. Comm.”评论是用户对每个答案的正面和负面评论。“Most voted？”代表获得最多投票的答案数量。|x|表示具有至少一个 Upvotes/Downvotes 投票和正面/负面评论的答案数量。Σ 是出现次数的总和，而括号中的数字是平均值(即 Σ/|x|)。

Stack Overflow 的投票表明那些用户鼓励(或劝阻)答案。尽管它的优缺点几乎与人工结果相关，但显而易见的是，与 OpenHub 相比，GitSearch 对用户的兴趣更大。GitSearch 更频繁地引起用户讨论。GitSearch 并未明显胜过人类回答，但人类用户尚未回答 17 个。对这 17 个问题，GitSearch 回答并获得 1 票赞成和 3 票反对，3 条正面和 2 条负面评论。

讨论：这项研究的结果表明，与 OpenHub 相比，GitSearch 可以是更好的第一回答者。如表 8 所示，Stack Overflow 中的许多问题几天都没有得到回答。我们的技术可以提供问题的起点，即使它们不是完整的答案，因为许多用户会通过投票和添加评论来跟进答案。一旦用户对一个问题感兴趣，讨论该问题的解决方案的可能性就会更大。

另外，Stack Overflow 用户将 GitSearch 的代码搜索结果选择为可接受的答案，意味着结果与问题高度相关且适当。请注意，提问者只能选择一个答案作为接受的答案。这可能表明发问者将利用代码搜索结果来处理问题中显示的问题。此外，这可能意味着如果代码搜索引擎的准确性得到提高，它们将成为 Stack Overflow 中某些问题的自动答案生成器。

4.5 对有效性的威胁

CoCaBu 的设计和 GitSearch 的实施带来了许多我们试图缓解的有效性威胁：

内部有效性：与其他 API 示例搜索引擎的用户研究相比，我们的研究参与者较少，仅为 34 名。但在自由格式代码搜索作品的用户研究中参与者少于我们或没有用户研究。我们试图通过邀请专业开发者和研究生来达到代表性。而在 4.4 节中，我们尝试在问题解决循环中从 Stack Overflow 用户那里获取反馈。这意味着我们的评估涉及更多的参与者。

外部有效性：我们仅使用英语作为查询语言，重点关注与 Java 有关的问题，且在实现中仅探讨了 Stack Overflow 和 GitHub。这种威胁应受到以下事实的限制：(1)英语是编程社区中的一种流行语言，(2)Java 是最受欢迎的编程语言之一，(3)GitHub 和 Stack Overflow 是最大的代码托管站点和问答论坛。

构造有效性：我们只关注没有确切 API 名称的查询。但这种威胁是有限的，因为对于新任务，开发者通常不知道相关 API 的名称。

致谢

感谢国家重点研发计划课题：基于协同编程现场的智能实时质量提升方法与技术（2018YFB1003901）和国家自然科学基金项目：基于可理解信息融合的人机协同移动应用测试研究（61802171）支持！

本文由南京大学软件学院 2019 级硕士生朱晨乾翻译转述。