前言
第一次参加泰迪杯，前期跟队友配合的不算太好，不过后期经过老师的教育指导，再通过大家的努力，终于把泰迪杯给解决了，这期间困难重重，收获也颇丰，其中收获最大的大概是把楼层结构识别算法做出来了，刚刚开始的时候还认为自己没办法写出这个算法，不过最后在队友的帮助之下，还是将它实现了，下面就来详细介绍一下这个算法。
发现
经过对BBS论坛源代码的研究，我们发现主题帖跟回帖都在同一个标签之下（div），并且他们都是此div的子节点，同时，我们还知道，帖与帖之间部分标签数量相差不大。由此，我们可以把主题帖和回帖看成一个个楼层，把帖子的标签作为楼层的特征，进而识别出楼层，并将其绝对路径找出来。
原理
将网页源代码转换为DOM树，使用层序遍历DOM树，通过余弦相似度识别相似楼层，根据统计出来的楼层数，与识别出来的楼层数进行比较进而得出正确楼层，输出楼层位置。
前期准备
- 软件和开发环境：sublime text3、python-Anaconda、Win10系统
- python包：lxml（你没看错，就一个包）
算法流程
构建DOM树
层序遍历DOM树
楼层矩阵筛选
楼层矩阵相似度比较
获得楼层矩阵绝对路径
1.构建DOM树
1.1 传入两个值（网页源代码，楼层数标准值）
网页源代码（bs0bj）：用于操作DOM树
楼层数标准值（standard_value）：用于比较楼层矩阵数，我们是通过“发表于”、“只看该作者”和时间把这个值确定下来
# 算法
def TreeAlgotithm(bs0bj, standard_value):
tree = etree.HTML(bs0bj) # 用HTML方法解析文件
t = tree.getroottree() # 获得一个节点对应的树
root = t.getroot() # 用于存储当前根节点，即爸爸节点
save_children_tag = Queue() # 队列，用于存储子节点
# 将body节点放到队列中
if(root[0].getnext()):
save_children_tag.enqueue(root[1])
else:
return None
网页正文都在body节点之下，所以直接定位body节点就可以减少遍历时间。
1.2 初始化存储容器
similar_tag = 0 # 用于计算有多少个相似的儿子对象
matrix_pack = [] # 矩阵容器，用于存放未进行相似度计算的矩阵
tag_pack = [] # 标签容器，用于存放未进行相似度计算的标签
one_path = [] # 用于临时存放某节点的绝对路径
new_matrix_pack = [] # 矩阵容器，用于存放已经进行相似度计算的矩阵
new_tag_pack = [] # 标签容器，用于存放相似度高的标签
test = [] # 观察数据进度
2.层序遍历DOM树
DOM树是一种普通的树结构，层序遍历是寻找楼层结构最快的方法，我们要寻找的网页正文和楼层结构基本都在body节点之下，用层序遍历，是最快找到楼层标签的方法。
2.1 构造队列
数据结构知识，使用队列保存每层节点的信息，先进先出层序遍历树的每一个节点。
# 构造队列，用于树的层序遍历
class Queue(object):
def __init__(self):
self.items = []
def isEmpty(self):
return self.items == []
def enqueue(self, item):
self.items.insert(0, item)
def dequeue(self):
return self.items.pop()
def size(self):
return len(self.items)
2.2 遍历DOM树
while(similar_tag > standard_value + 2 or similar_tag < standard_value - 2):
similar_tag = 0 # 相似节点数初始化
if (save_children_tag.isEmpty()):
print("栈为空")
return None
else:
root = save_children_tag.dequeue() # 队列弹栈
# 父节点遍历
for child in root:
save_children_tag.enqueue(child)
3.楼层矩阵筛选
3.1 初始化矩阵容器
matrix_pack = [] # 矩阵容器，用于存放未进行相似度计算的矩阵
tag_pack = [] # 标签容器，用于存放未进行相似度计算的标签
new_matrix_pack = [] # 矩阵容器，用于存放已经进行相似度计算的矩阵
new_tag_pack = [] # 标签容器，用于存放相似度高的标签
3.2 构建楼层矩阵
经过对楼层源代码的研究，发现这些标签出现频数较多，但是在过程中少考虑了一个问题，就某些标签会受到回帖内容的影响，比如img，回帖多一张照片就会多一个img标签。
def TagMatrix(tree, path):
# 统计标签频数
def List_Count_Tag(children):
List_tag = []
if 'a' in children:
List_tag.append(children.count('a'))
else:
List_tag.append(0)
if 'div' in children:
List_tag.append(children.count('div'))
else:
List_tag.append(0)
if 'p' in children:
List_tag.append(children.count('p'))
else:
List_tag.append(0)
if 'span' in children:
List_tag.append(children.count('span'))
else:
List_tag.append(0)
if 'img' in children:
List_tag.append(children.count('img'))
else:
List_tag.append(0)
if 'td' in children:
List_tag.append(children.count('td'))
else:
List_tag.append(0)
if 'dd' in children:
List_tag.append(children.count('dd'))
else:
List_tag.append(0)
return List_tag
tag_save = []
child_Node = tree.xpath(path + '//*')
for child in child_Node:
tag_save.append(child.tag)
return List_Count_Tag(tag_save)
3.3 矩阵初筛选
这一步至关重要，因为在初期没加这一步的时候，很多空矩阵被视为楼层，后来我们发现，加入了这个矩阵的初步筛选之后，不仅准确率提高了，连效率也大大提高了。
one_matrix = TagMatrix(tree, one_path) # 获得儿子节点的矩阵
if(one_matrix[0] < 2 or one_matrix[1] < 2): # 筛选没可能是楼层的元素
continue
# 存储没有进行相似度计算的矩阵和标签
matrix_pack.append(one_matrix)
tag_pack.append(child)
3.4 选择标准矩阵
由于下一步要进行矩阵相似度的比较，我们需要找出一个最有可能是楼层的矩阵（标准矩阵），与其他的矩阵进行相似度比较。经过研究我们发现，各个楼层的a标签基本一致，因此统计a标签频数，并找到跟a标签频数相等的第一个矩阵作为标准矩阵。
具体步骤
提取所有楼层矩阵的第一个元素，建立新列表
统计列表中，返回出现次数最多的元素
在所有楼层矩阵中找到第一个跟频数一致的矩阵，并返回作为标准矩阵
# 选出标准值
def StandardMatrix(tag_pack, matrix_pack):
# 计算矩阵第一个元素，用于选出标准值
def CountKey(matrix_pack):
temp = 0
temp_list = []
# 提取标签容器的第一个标签，
for one in matrix_pack:
temp_list.append(one[0])
result_list = collections.Counter(temp_list)
dict(result_list)
# 返回a标签的频数，用作选出标准矩阵
return max(result_list.items(), key=lambda x: x[1])[0]
if(len(tag_pack) > 1):
first_key = CountKey(matrix_pack)
for i in matrix_pack:
if(i[0] == first_key):
standar_matrix = i
return standar_matrix
4.楼层矩阵相似度比较
- 相似度>0.9：判断为楼层矩阵
if(standar_matrix != None):
i = 0
for new_one_matrix in matrix_pack:
Cos_key = CosSimilarity(new_one_matrix, standar_matrix)
if(Cos_key > 0.90):
new_tag_pack.append(tag_pack[i])
new_matrix_pack.append(matrix_pack[i])
i = i + 1
4.1 余弦相似度比较
这个其实没什么好看的，有技术含量的内容都在上面，这个在网上都能找到。
# 两个矩阵余弦相似度计算
def CosSimilarity(hinsA, hinsB):
up_count = 0
down_left_count = 0
down_right_count = 0
result_count = 0
i = 0
# 计算两个向量的点积
while i < len(hinsA):
up_count = up_count + hinsA[i] * hinsB[i]
i = i + 1
i = 0
# 计算两个向量的模
while i < len(hinsA):
down_left_count = down_left_count + hinsA[i] ** 2
i = i + 1
i = 0
while i < len(hinsB):
down_right_count = down_right_count + hinsB[i] ** 2
i = i + 1
return up_count / (math.sqrt(down_left_count) * math.sqrt(down_right_count))
4.2 释放矩阵容器内存
这么做主要是为了避免下次计算的时候，把前一次的数据也算进去了，这一步也是很重要的。
if(similar_tag > standard_value + 2 or similar_tag < standard_value - 2):
del(matrix_pack)
del(tag_pack)
del(new_tag_pack)
del(new_matrix_pack)
5.获得楼层矩阵绝对路径
做到这一步也基本差不多了，把楼层矩阵的绝对路径拿到手，就可以定位每一个楼层的位置了。
tag_path = []
for tag in new_tag_pack:
tag_path.append(t.getpath(tag))
return tag_path
总结
- 存在问题：
少于3个楼层识别困难
矩阵构造不严谨，部分标签会受回帖影响
依赖于标准值的准确性
没有树结构深度限制（一直识别到最后一个节点，但其实楼层不可能很深层的节点，一般在4到7层）
源代码
个人博客，最新更新的文章都发在这，欢迎关注：https://yeah-kun.github.io/
