作业地址

• 博客地址：http://www.cnblogs.com/vancasola/p/9769732.html
• 队友博客地址：http://www.cnblogs.com/multhree/p/9769738.html
• GitHub地址：https://github.com/Professorchen/pair-project/tree/master/Cplusplus/031602507%26031602543

分工

031602507：陈俞辛

• 新功能设计实现、附加题构思实现

031602543：周政演

• 基于 python 及 java 的爬虫实现、附加题构思、对俞辛写各功能模块进行测试、博客撰写

解题思路与设计实现

爬虫

该爬虫可以从CVPR的论文列表上爬取论文题目、摘要，并输出到一个.txt文件中。在此使用两种了工具实现了爬取功能：Java、python

思路

两种语言的实现思路大致相同：

1. 发送http请求
2. 获取整个页面的html
3. 寻找论文页面的URL
4. 循环进入每篇论文页面
5. 获取每篇论文的信息
6. 输出到result.txt文件

• 其中实现的关键：是找出html的特征部分。也就是能够唯一确定title、abstract位置的html代码段。
• 例如，针对某段html代码；

<dt class="ptitle"><br><a href="content_cvpr_2018/html/Das_Embodied_Question_Answering_CVPR_2018_paper.html">Embodied Question Answering</a></dt>

其中下段代码可以在整个html页面中确定url的位置

<dt class="ptitle">

通过观察各个页面的url形式，a href = 后的双引号部分中间，加上一段url的头部，即是该篇论文的URL。

贴出python方法的部分代码作为示例：

def GetPaper(FullPaper,begin,end)://获取论文url
         left = FullPaper.find('''<dt class="ptitle">''',begin,end)#特征代码首位置
         right = FullPaper.find('''</a></dt>''',begin,end)#特征代码末位置
         paper = FullPaper[left:right]
         str1=paper.split('"') # 分割开该段文本
         return str1[3]# 提取url链接

代码github地址

• 同时，抓取的过程可以显示抓取进度

• 此部分是提取出来的 PaperList 的部分 url 列表

• 此部分为导出的 .txt 文本

代码组织

• 代码主要由两个关键部分组成：Count类和FileIO.h
• Count类： 由

算法关键

关键代码一：统计出现频率最高的X个词组：

//统计出现频率最高的X个词组
vector<map<string, int>::iterator> & Count::countTopXPhrase(int topX)
{
	int phraseMapSize = int(phraseMap.size());
	for (int i = 0; i < phraseMapSize && i < topX; i++)
	{
		auto maxFrxPhrase = phraseMap.begin();
		for (map<string, int>::iterator it = phraseMap.begin(); it != phraseMap.end(); it++)
		{
			if (it->second > maxFrxPhrase->second)
			{
				maxFrxPhrase = it;
			}
		}
		topXPhrase.push_back(maxFrxPhrase);
		maxFrxPhrase->second = -maxFrxPhrase->second;
	}
	return topXPhrase;
}

代码思路

• map中存储的是词组和出现频次的 键-值 对，要统计出现频率最高的X个词组，主要有以下两种思路：

思路一

• 对所有 键-值 对进行排序，从高到低逐个输出词组，得到词组出现频次的排行榜。
• 由于不可直接对map进行排序，所以考虑将map的键值对提取，存入自定义的键值对结构体，然后对结构体进行排序。
• 优点：直接获得排好序的词组排行榜，以后可以根据需要，灵活输出前x个词组的排行。
• 缺点：使用结构体存储，带来空间资源的开销；对结构体数组进行排序，降低了算法性能。

思路二

• 不对 键-值 对进行排序，对map直接进行遍历，找到频次最高的词组。
• 无需对map排序，直接对map遍历，每遍历一次，找到频次最高的词组，然后将该词组置为负数。
• 优点：资源开销小，算法性能高。

二者比较

• 经过测试，思路二的方法性能明显高于思路一，且更不易出错。本次要求无需多次查找不同词组个数的排行榜，思路二更适用于本测试。故使用思路二。
• 思路二遍历 topX 遍的时间复杂度 O(n) ， 而思路一若采用快排时间复杂度为 O(nlogn) 如果单词数 > 100，那么思路一更快。如果单词数 < 100，那么思路二更快，但单词数过少，性能的提升十分有限的。
• 算法关键：将每一次遍历找出的最高频词组频率置为负数，这样在下一次遍历的时候就不会被重复查找，并且在输出的时候只需要找到负数，输出该词即可。

函数流程图：

• 注：( 其中 topX 指命令行输入的自定义词频，如果不指定默认为 10) 。

关键代码二：加入权重的词频统计（部分）

if (wordBuf == "title" && linesBuf[i][j] == ':' && j == 5)
	{
		paperCount++;	//每出现一个 title: 说明是一篇论文
		isTitle = true;
		wordBuf = "";
		continue;
	}
	if (wordBuf == "abstract" && linesBuf[i][j] == ':' && j == 8)
	{
		isTitle = false;
		wordBuf = "";
		continue;
	}

• 根据需求：属于 Title 的单词权重为10，属于 Abstract 单词权重为1 。首先要区分，单词是属于 Title 部分还是 Abstract 部分。
• 通过检测到文本中的 title 区分: (读取文件时已经都转为小写) 设置一个 flag 来标记 title。
• 同时，为了避免文中本身有 title: 这样的串，必须是出现在行首的才设置flag。
• 算法过程：对全文进行遍历操作，当文本为 title串，且出现在行首时，设置一个flag作为标记，以此来确定，之后的单词属于 title 部分。

关键算法功能一：词组统计

关键算法功能二：文件读取

• 此外文件的读取同样重要，因为有部分的字符是不需要读取的，并且有固定的格式，因此需要额外的处理。对于每一篇论文都只读取 title 和 abstract两个字段的内容。每次开始读取前都先将论文编号跳过（也就是判断为数字则继续读取下一个字符直至换行符出现）然后读取两行。然后继续等待数字出现。
  

附加题设计与展示

相关实现文件网盘地址

会议领军人

设计的创意独到之处

“会议领军人”简介：根据在CVPR的论文发表情况，对会议的作者进行一个排行，不同位次的作者占有不同的权重。例如：第一作者权重为5，第二作者权重为4，依次递减，从第五作者后权重均为一。

“会议领军人”作用：

• 根据排行，可以迅速找到本会议、甚至本领域的“领军人物”，通过作者位次的排行，可以有丰富的作用。
• 可以通过位次靠前的作者，找一个或多个较为热门的研究方向。
• 可以通过位次靠前的作者，查他的所作出的相关工作，沿着大牛走过的路前进，少走弯路。
• 可以通过位次靠前的作者，查找他的研究成果，了解世界最前沿，质量较高的科研成果。

实现思路

思路：

• 修改爬虫程序，使其可以爬取作者信息，并以逗号分隔作者名。
• 处理文件时，对以 Authors:开头的行进行遍历。每遇到一个逗号则将作者名保存进数组。
• 通过作者名在数组中的位置即可分辨是第几作者。每一篇论文进行一次加权计算，然后清空数组进行下一篇论文的计算。
• 其中第一作者权重为 5 ，依次递减。第五作者之后权重均为 1.

可视化思路：

• 在原有基础上对生成的文件进行处理
• 利用 python 的 Matplotlib库生成柱状图
• 并且在每个柱上添加了具体的数值方便查看
• 横轴标签作者名过长旋转30°显示。

实现成果展示

通过“会议领军人”，对作者进行了排行，以下是爬取的结果：

然后生成可视化的界面

关键代码解释

对读取到的作者进行加权

int authorCountSize = int(authorCount.size());
			for (int i = 0; i < authorCountSize; i++)
			{
				if (i < 5)
				{
					authorMap[authorCount[i]] += (5 - i);
				}
				else
				{
					authorMap[authorCount[i]]++;
				}
			}

可视化部分的python代码

import matplotlib.pyplot as plt

def autolabel(rects):
 for rect in rects:
  height = rect.get_height()
  plt.text(rect.get_x()+rect.get_width()/2.-0.2, 1.03*height, '%s' % float(height))
  
rf = open('AuthorRank.txt','r',encoding='UTF-8')
content = rf.readlines()
name_list = []
num_list = []
for x in content:
    Author = ""
    Count = ""
    flag1 = 0
    flag2 = 0
    for y in range(len(x)):
        if flag1 == 1:
            Author += x[y]
        if flag2 == 1:a
            Count += x[y]
        if x[y] == ' ' and x[y-1] == ':':
            flag1 = 1
        if x[y] == ',':
            flag1 = 0
            flag2 = 1
    name_list.append(Author)
    num_list.append(int(Count))
plt.ylabel("Impact Factor")
plt.xlabel("Author Name")
plt.title(u"Author Rank")
fig = plt.bar(range(len(num_list)), num_list,width = 0.35,align='center',color = 'c',alpha=1)
plt.xticks(range(len(num_list)),name_list,size='small',rotation=30)
autolabel(fig)
plt.savefig("test.png")
plt.show()

词云

原先生成的字符词频统计排行有以下下缺点：

• 生成的词频排行不够直观
• 缺少可视化
• 应用在网站上不够美观，且难以吸引眼球
• 与整体UI设计难以一致

故根据获得的词频排行，做出一个可视化的词云，词的大小即代表着词频的大小，可以瞬间catch your eyes，且便于根据图片生成词云，与网站ui风格契合。

设计的创意独到之处

• 可视化的词云：词的大小即代表着词频的大小。
• 吸引眼球：越大的单词，代表该词越热，瞬间吸引读者。
• 可定制化：且便于根据图片生成词云，与网站ui风格契合。

实现思路

• 使用 python 自带的jieba库对分本进行分词
• 然后自带的wordcloud库根据之前分词的结果形成词云
• 设置停用词集过滤一些无意义的词，比如which this等

实现成果展示

关键代码解释

from wordcloud import WordCloud,ImageColorGenerator,STOPWORDS
import jieba
import matplotlib.pyplot as plt
from PIL import Image
import numpy as np 
 

text = open('result.txt','r', encoding='UTF-8').read()

cut_text = jieba.cut(text)
result = '/'.join(cut_text)

stopwords = set(STOPWORDS)

image = Image.open('fivestart.png')  
img = np.array(image) 
#词云的生成,字体的路径一定要写上不然会出现乱码 可以下载其他字体创新
wc = WordCloud(font_path = "C:WindowsFontsSTHUPO.ttf",background_color='white',max_font_size=150,mask=img) 
# WordCloud其他参数设置,random_state=42,max_words=2000,min_font_size=20
wc.generate(result)
#绘制文字的颜色以背景图颜色为参考  
image_color = ImageColorGenerator(img)
wc.recolor(color_func=image_color)  
#图片的展示 
plt.imshow(wc)
plt.axis("off")
# 像素点多少
plt.savefig("wordcloud3.png",dpi=300)
# plt.show()

论文分类器

CVPR上缺少对论文的分类，事实上，论文的分类有许多作用：

• 根据方向分类：便于了解当前本领域有哪些研究方向，对该领域有一个横向的了解。
• 便于文献查阅：根据方向，直接查找相关论文，增加查找效率。
• 便于综述撰写：根据论文分类，可以对本领域有更全面的了解，并为综述的撰写打好基础，为进一步分类的细化做好准备。
  故设计论文分类器，根据已有方向，对论文进行分类。

设计的创意独到之处

• CVPR上缺少对论文的分类，而论文分类却益处良多。
• 可以根据论文的方向分类，便于查阅论文。
• 有利于撰写综述，对本领域有更全面的了解，进一步细化分类。

实现思路

• 可根据该领域最主要的几个研究方向，进行关键词爬取。
• 拥有该关键词的论文，归为一类，且可以重复。
• 可以根据该研究方向的关键词相关词，进行分类，增加分类的准确度。

实现成果展示

• 可以参照ccf a类会议 sigcomm 的论文分类形式，对 CVPR 的论文进行分类：
  

性能分析与改进

性能分析

分析一

0
Title: Monday Tuesday Wednesday Thursday
Abstract: Monday Tuesday Wednesday Thursday Friday

• 词组统计功与单词统计功能相互耦合。不论是否开启词组统计功能，都会进行词组统计操作，若是不使用词组统计功能，该统计将成为冗余的功能，影响统计性能。
  

分析二

• 改进词频统计部分：针对词频统计部分，由于不可直接对map进行排序，所以考虑将map的键值对提取，存入自定义的键值对结构体，然后对结构体进行排序。使用结构体存储，带来空间资源的开销；对结构体数组进行排序，降低了算法性能。

• 思路一遍历 topX 遍的时间复杂度 O(n) ， 而思路二若采用快排时间复杂度为 O(nlogn) 。如果单词数 > 100，那么思路一更快。如果单词数 < 100，那么思路二更快，但是单词数这么少的情况下对性能的提升是十分有限的。因此还是采用思路一。

描述你改进的思路

改进一

• 将词频统计和词组统计解耦合，分成了 countWordNum 和 countPhraseNum 两个函数，可以分别调用。在使用单个功能时，避免了对另一功能的额外调用。以此提升性能。
  

改进二

• 不对 键-值 对进行排序，对map直接进行遍历，找到频次最高的词组。
• 无需对map排序，直接对map遍历，每遍历一次，找到频次最高的词组，然后将该词组置为负数。
• 优点：资源开销小，算法性能高。
• 经过测试，性能明显提高。

展示性能分析图和程序中消耗最大的函数

• 改进前

• 改进后

• 如图所示，消耗最大的函数为countWordNum()，改进后，性能有了一定的提升

单元测试

展示出项目部分单元测试代码，并说明测试的函数，构造测试数据的思路

序号	测试用例	测试对象	测试意图	测试结果
1	文件名输入错误	readFile(inputFileName, charBuf, linesBuf)	测试读取文件函数	返回false，通过
2	文件名输出错误	outputToFile(characterCount, wordCount, lineCount, outputFileName, topX)	测试输出文件函数	返回false，通过
3	一篇论文测试	countCharNum(charBuf)	测试字符统计功能	通过
4	一篇论文测试	countWordNum(linesBuf,weightValue)	测试单词统计功能	通过
5	一篇论文测试	countWordNum(linesBuf, weightValue)	测试当加入权重时单词个数统计是否影响	通过
6	多个词组测试	countTopXWord(topX)	测试无权重单词词频统计功能	通过
7	多个词组测试	countWordNum(linesBuf, weightValue)	测试有权重单词词频统计功能	通过
8	多篇论文测试	countPhraseNum(linesBuf, 0, 2)	测试词组统计功能	符合字典序
9	更多词组测试	countLineNum(linesBuf)	测试行数统计功能	通过
10	修改词组形式	countTopXWord(10))	文本为 cvpr2018 官网爬取结果，测试所有功能	迭代器崩溃，更改后通过
11	增加特殊用例测试	count.countTopXPhrase(10)	测试单词之间有多个分隔符的词组	通过
12	单个特殊用例测试	topXPhrase = count.countTopXPhrase(10)	测试单词之间有不合法单词的词组	输出为0，通过

其中，7号测试用例的代码，测试有权重单词词频统计功能：

TEST_METHOD(TestMethod7)	//测试有权重单词词频统计功能
		{
			int weightValue = 1;
			int topX = 10;
			const char* inputFileName = "../WordCountTest/input5.txt";
			string charBuf;
			vector<string> linesBuf;
			Assert::AreEqual(FileIO::readFile(inputFileName, charBuf, linesBuf), true);
			Count count;
			Assert::AreEqual(count.countWordNum(linesBuf, weightValue), 11);
			vector<map<string, int>::iterator> topXWord = count.countTopXWord(topX);
			Assert::AreEqual(topXWord[0]->first, string("abcd"));
			Assert::AreEqual(-topXWord[0]->second, 31);
			Assert::AreEqual(topXWord[1]->first, string("abce"));
			Assert::AreEqual(-topXWord[1]->second, 10);
			Assert::AreEqual(topXWord[2]->first, string("abcf"));
			Assert::AreEqual(-topXWord[2]->second, 10);
			Assert::AreEqual(topXWord[3]->first, string("abcg"));
			Assert::AreEqual(-topXWord[3]->second, 10);
			Assert::AreEqual(topXWord[4]->first, string("asda"));
			Assert::AreEqual(-topXWord[4]->second, 3);
			Assert::AreEqual(topXWord[5]->first, string("abch"));
			Assert::AreEqual(-topXWord[5]->second, 1);
		}

12号测试用例，测试是否存在不合法词组，增强程序鲁棒性：

TEST_METHOD(TestMethod12)	//测试单词之间有不合法单词的词组
		{
			const char* inputFileName = "../WordCountTest/input10.txt";
			string charBuf;
			vector<string> linesBuf;
			Assert::AreEqual(FileIO::readFile(inputFileName, charBuf, linesBuf), true);
			Count count;
			Assert::AreEqual(count.countPhraseNum(linesBuf, 0, 2), 4);
			vector<map<string, int>::iterator> topXPhrase = count.countTopXPhrase(10);
			Assert::AreEqual(topXPhrase[0]->first, string("delicious apple"));
			Assert::AreEqual(-topXPhrase[0]->second, 1);
		}

测试结果以及代码覆盖率附图

• 由于添加了附加功能，而附加功能并未纳入单元测试的范畴，故测试率有一定降低。

贴出Github的代码签入记录

陈俞辛：

周政演：

遇到的代码模块异常或结对困难及解决方法

问题描述

1. 爬虫部分，出现爬取导的内容乱码的问题。

2. 在做单元测试时，不了解需要测试部分的函数功能、接受参数、返回值、调用方式等等；

3. 本次作业算是对个人作业的扩展，俞辛的代码得分相对较高，于是打算以俞辛的代码为基础。政演在阅读俞辛的代码来了解模块的接口时，出现了一些困难，又正值国庆，两个人没有办法面对面的沟通。

做过哪些尝试

1. 上网查找正确编码的方式，使用 UTF-8 编码。
2. 由俞辛写出详细的接口说明，介绍有关功能、参数等，政演对函数进行单元测试。
3. 和队友详细介绍单元测试测出的问题，帮助队友改进源代码
4. 在国庆期间，每天晚上固定一段时间的电话交流，反馈问题以及制定接下来的任务。（家里人一度认为有了对象）

是否解决

1. 解决
2. 解决
3. 解决

有何收获

1. 了解了爬虫相关的编码问题的解决策略
2. 在和队友沟通中发现，分工并不是那么简单，若是没有合理到位的沟通，没有把接口等信息描述清的话，一加一或许未必大于二，甚至会小于二。幸亏及时预见了接口说明的重要性，在接口说明方面下了大的功夫，对各个接口详细报告，实现了单元测试的代码，达到了一加一大于二的效果。
3. 当局者迷，旁观者请。有时候自己也未能发现代码中的bug，代码看似完美，实则需要经过多方的检验。而在编码功能不繁重的情况下，若是二人编码，编码功能存在耦合，则编码交互带来的效率损耗很可能大于独自编码。所以，一人主要负责编码，一人主要负责单元测试，适当地兼顾了结对编程的优点，又规避了其缺点，做到相互裨补缺漏、相得益彰。
4. 一个人很难 push 整个作业，两个人相互扶持，相互沟通，才能很好的完成任务。重中之重就是沟通，只有沟通才能解决问题。

评价队友

值得学习的地方

• 十分注重细节
• 灵感十足
• 对于新技能上手十分快，可以很快的掌握
• 思路清晰，明确要完成的任务，有很好的规划

需要改进的地方

• 执行力不够强

学习进度条

第N周	新增代码(行)	累计代码(行)	本周学习耗时(小时)	累计学习耗时(小时)	重要成长
1	72	72	5	5	map 容器的性能瓶颈分析
2	508	580	7	13	完成基本功能的实现及附加功能的构思
3	149	729	6	19	学习 python 中与附加功能相关的库，例如 wordcloud

PSP表格记录

PSP2.1	header 2	预估耗时（分钟）	实际耗时（分钟）
Planning	计划	35	30
· Estimate	·估计这个任务需要多少时间	15	5
Development	开发	645	1220
· Analysis	需求分析（包括学习新技术）	40	80
· Design Spec	· 生成设计文档	40	120
· Design Review	· 设计复审	10	30
· Coding Standard	· 代码规范 (为目前的开发制定合适的规范)	20	30
· Design	· 具体设计	120	180
· Coding	· 具体编码	600	1200
· Code Review	· 代码复审	30	180
· Test	·测试（自我测试，修改代码，提交修改）	240	420
Reporting	报告	245	145
· Test Repor	· 测试报告	240	120
· Size Measurement	· 计算工作量	5	5
· Postmortem & Process Improvement Plan	· 事后总结, 并提出过程改进计划	20	20

|合计||2265|3785