编程之美2016复赛题目思路

编程之美2016复赛题目可参见此处

简单看了一下题目,发现题目描述中定义了很多符号,不是很清晰,于是先看了看实体属性的定义。官方文档里定义了很多属性,这里我们只需要关注题目中出现的属性即可(以下加粗部分)。

符号与解释

  • Id:实体的id号
  • Ti:论文标题
  • Y:论文发表年份
  • D:论文发表日期
  • CC:被引用次数
  • AA.AuN:作者姓名
  • AA.AuId:作者的id号
  • AA.AfN:单位的名称
  • AA.AfId:单位的id号
  • F.FN:研究领域的名称
  • F.FId:研究领域的id号
  • J.JN:期刊名称
  • J.JId:期刊的id号
  • C.CN:会议名称
  • C.CId:会议的id号
  • RId:引用的论文的id号
  • W:关键字
  • E:扩展的元数据
    显然,可以把这里的“实体”理解为论文,所以实体的id就是论文的id。看起来,论文是在哪个会议/哪个期刊发表的,研究领域是什么,作者是谁,引用论文,这些数据都有定义。

详细数据结构

上面的实体属性定义,看起来不是很复杂。结果后来我随便拖了些数据来看,发现有些地方还是有坑的。用struct的方式大致描述一下数据结构(只涉及重要的属性)

struct entity{
int Id;
List RId;
struct Field {
string FN;
int FId;
};
List F;
struct Conference {
string CN;
int CId;
} optional C;
struct Journal {
string JN;
int JId;
} optional J;
struct AuthorOrAffiliation {
string AuN;
int AuId;
string optional AfN;
int optional AfId;
}
List AA;
}

所有标注为optional的字段都是可以没有的。AuId和AfId可能是一对多的关系,即一个作者可能对应多个单位,也可以一个单位也不对应(其实也是很符合实际情况的)。

查询方法

Academic Knowledge API提供了三个查询类型Interpret(翻译),evaluate(计算),calchistogram(统计直方图)。可能需要用到的就只有evaluate。

往下面这个网址发送GET请求,就会返回一个结果,为JSON字符串。

http://oxfordhk.azure-api.net/academic/v1.0/evaluate?{expression}&subscription-key=f7cc29509a8443c5b3a5e56b0e38b5a6

其中,{expression}需要被替换成一个查询表达式,形式大概是这样:

expr=Composite(AA.AfId=82880672)&count=10000&attributes=Id,AA.AuId,AA.AfId

意思是,查询这样的论文:作者列表中包含id为82880672对应的单位(其实对应的就是Beihang University),返回的最大数量为10000个,返回的属性有:论文id,作者id,单位id。

写成SQL语句的形式就是这样:(由于MAG不是关系型数据库,所以写成这种形式不是很恰当)

SELECT TOP 10000 Id, AA.AuId, AA.AfId FROM MAG WHERE AA.AfId=82880672

问题分析

问题是给定MAG中一对实体的标识符,能够找到所有连接它们的1跳,2跳,3跳路径。而且,给定的实体的标识符是[Id, Id], [Id, AA.AuId], [AA.AuId, Id], [AA.AuId, AA.AuId]。

仔细想想,情况也不是很复杂。按输入分类讨论如下:

输入为[Id, Id],可能的路径:
Id——Id
Id——Id——Id
Id——F.FId——Id
Id——C.CId——Id
Id——J.JId——Id
Id——AA.AuId——Id
Id——Id——Id——Id
Id——Id——F.FId——Id
Id——Id——C.CId——Id
Id——Id——J.JId——Id
Id——Id——AA.AuId——Id
Id——F.FId——Id——Id
Id——C.CId——Id——Id
Id——J.JId——Id——Id
Id——AA.AuId——Id——Id

输入为[AA.AuId, AA.AuId],可能的路径:
AA.AuId——Id——AA.AuId
AA.AuId——AA.AfId——AA.AuId
AA.AuId——Id——Id——AA.AuId

输入为[Id, AA.AuId],可能的路径:
Id——AA.AuId
Id——Id——AA.AuId
Id——Id——Id——AA.AuId
Id——F.FId——Id——AA.AuId
Id——C.CId——Id——AA.AuId
Id——J.JId——Id——AA.AuId
Id——AA.AuId——Id——AA.AuId
Id——AA.AuId——AA.AfId——AA.AuId

输入为[AA.AuId, Id],可能的路径:
AA.AuId——Id
AA.AuId——Id——Id
AA.AuId——Id——Id——Id
AA.AuId——Id——F.FId——Id
AA.AuId——Id——C.CId——Id
AA.AuId——Id——J.JId——Id
AA.AuId——Id——AA.AuId——Id
AA.AuId——AA.AfId——AA.AuId——Id

由于数据量巨大,所以两跳和三跳的情况只能从两头往中间查找。