工作总结

CSS分类（需要构建一棵树）（全局的特征）

要求：输入两篇论文的名字（或其他标识符）就可以获得这两篇论文的分类所在节点到公共父节点的最短距离。

首先我们研究树中求得两个节点X,Y到最近公共父节点的距离。

方法一：暴力求解

思路：利用BFS或者DFS，从一个节点出发，沿着树的结构一层层查找，知道到达另一个节点，此时的距离为最短距离。 分析：时间复杂度$O(n)$

方法二：简单LCA

思路：

$d=d(x,root)+d(y,root)-2\ast d(z,root)$ 其中，x，y为两个待求节点，z为最近公共祖先。 我们需要提前预处理的是求得所有的$d(\ast ,root)$ ，这样，根据公式，我们只需要知道那个节点是z就可以根据公式求出d。

LCA假设永远满足$d(x,root)<d(y,root)$ ，若不满足，则将x，y互换即可。

步骤一：预处理深度数组。 维护数组 $dep[\ast ]$ ，使得 $dep[\ast ]=d(\ast ,root)$ ，做查表用。

步骤二：跳到相同高度。 当 $d(x,root)<d(y,root)$ 时，$y=fa[y]$（ $fa[y]$ 数组存储的是y的直接父亲节点），即当x，y不“同级”时， 将$fa[y]$赋值给y，y“向上跳了一级”。

步骤三：xy同时跳。 当 $d(x,root)=d(y,root)$ 后，我们使x和y同时“向上跳”。即，当 $x!=y$ 时：$x=fa[x]$，$y=fa[y]$。 找到z之后，就可以套公式求出距离。当然，我们也可以直接在每次跳的时候都$d=d+1$（假设边权重为1）。 分析：步骤一时间复杂度为$O(n)$，执行一次步骤二三的时间复杂度为 $logn$ ，因此，对于需求为“树结构基本不变，需要多次查询”的任务来说，时间复杂度为$O(q\ast logn+n)$（q为查询次数）

时间复杂度的分析是很有必要的，因为我们最终是以网页的形式呈现的，我们需要点击后的快速响应，而对于较为庞大的数据量来说，时间复杂度非常重要。

简单LCA对于结构较为“平衡”的树来说比较友好，但是对于比较“偏”的树来说步骤二三的时间复杂度可能上升为$O(n)$，因此，我们需要进一步加快“跳”的过程。我们利用“倍增”的思想来实现算法的改进。

方法三：改进LCA

思路：在简单LCA的基础上改进“跳”的过程。

步骤一：预处理深度数组。 同上

步骤二：跳到相同高度。 已知任何一个十进制的自然数都能拆分成若干个2的幂的和。比如：$17=2^4+2^0$，那么我们是不是可以利用这种性质进行优化？ 已知$fa[i]$表示的是节点i的直接父亲节点，我们假设$fa[i][j]$表示节点i向root方向走$2^j$个边到达的父节点。我们需要做的预处理还有维护数组$fa[i][j]$。代码如下：

void GET(){ for(int j=1;j<=23;j++){ for(int i=1;i<=n;i++){ fa[i][j]=fa[fa[i][j-1]][j-1]; } } }

我们利用以上函数求得数组$fa[i][j]$的所有值。 解析：已知$fa[i][j]$的含义是节点i向root方向走$2^j$个边到达的父节点，那么$fa[i][j-1]$的含义是节点i向root方向走$2^{j-1}$个边到达的父节点。已知$2^j$=$2^{j-1}+2^{j-1}$，因此我们想要得到$fa[i][j]$，我们可以先得到$fa[i][j-1]$，然后再得到它的$fa[i][j-1]$，也就是关键代码$fa[i][j]=fa[fa[i][j-1]][j-1]$

由于我们已知 $dep[x]$和 $dep[y]$，因此我们可以得到 $dep[y]-dep[x]$，设为$P$（已保证$d(x,root)<d(y,root)$）。 为了优化“跳”的过程，我们可以把$P$分解，例如，假设$P=17$，而$17=2^4+2^0$，因此，我们$y$向上“跳”$P(17)$的过程可以分解为“跳”$2^4$和$2^0$的过程。那么关键的问题就变成如何寻找$P$的分解。

for(int i=0;i<23;i++){ if(P & (1<<i)){ y=fa[y][i]; } }

已知$1<<i$表示$1$左移$i$位，例如，当$i=5$时，$1<<i=(100000{)}_2$，而KaTeX parse error: Expected 'EOF', got '&' at position 3: P &̲ (1<<i)其实就是检测了$P$的哪一位为$1$。观察二进制表示与分解的关系可知，当$P=17$时，$P$的二进制表示为$(10001{)}_2$而$17=2^4+2^0$，因此可以看出，分解出来的各个指数的幂次就是原来数的二进制表示的$1$的位置。因此，我们通过 $Pand(1<<i)$找到$P$二进制表示为$1$的位置，我们就找到了分解。

步骤三：xy同时跳。

假设树结构如下图： 则执行完步骤二时，$x,y$已经同深度了。此时我们需要做的是“同时跳”。

for(int i=23;i>=0;i--){ if(fa[x][i]!=fa[y][i]){ x=fa[x][i]; y=fa[y][i]; } }

一旦$fa[x][i]=fa[y][i]$，那么我们有两种情况：

恰好是LCA跳过了，是LCA的父节点

如果是第一种情况，那么非常好，这是我们想要的，但是我们没法判断是否出现了第二种情况，因此我们我们先 “尝试跳”，即我们使$i$递减。这样我们找到的第一个大概率是跳过了，因此当$fa[x][i]=fa[y][i]$时，我们不做改变，反而当$fa[x][i]!=fa[y][i]$时，我们选择往上跳。

$i$递减

为什么使得$i$递减？

若$i$递增，则我们$i=0,1,2,3...$的时候就很容易就跳，但是我们以后若还需要跳比较小的深度的时候，$i$却无法取到比较小的值了，因此我们使$i$递减。

该循环运行完后的结果是图中红圈圈出的： 显而易见，我们要求的LCA是图中红色节点的直接父亲，因此$fa[x][0]$或者$fa[y][0]$就是LCA。

找到对应的节点后，我们就可以套公式求出$d$。

完整代码：

#include<cstdio> #include<iostream> #define maxn 1010 using namespace std; int n,m,num,head[maxn],c[maxn],fa[maxn][25],dis[maxn]; struct node{ int t,v,pre; }e[maxn*2]; void Add(int from,int to,int dis){ num++;e[num].v=to; e[num].t=dis; e[num].pre=head[from]; head[from]=num; } void Dfs(int now,int from,int dep,int S){ c[now]=dep;fa[now][0]=from;dis[now]=S; for(int i=head[now];i!=0;i=e[i].pre){ int v=e[i].v; if(v==from)continue; Dfs(v,now,dep+1,S+e[i].t); } } void Get(){ for(int j=1;j<=23;j++) for(int i=1;i<=n;i++) fa[i][j]=fa[fa[i][j-1]][j-1]; } int LCA(int a,int b){ if(c[a]<c[b])swap(a,b); int t=c[a]-c[b]; for(int i=0;i<=23;i++) if(t&(1<<i))a=fa[a][i]; if(a==b)return a; for(int i=23;i>=0;i--) if(fa[a][i]!=fa[b][i]){ a=fa[a][i];b=fa[b][i]; } return fa[a][0]; } int main() { cin>>n>>m;//n个点m次询问 //建树 int u,v,t;//起点，终点，权值 for(int i=1;i<n;i++){//n-1条边 cin>>u>>v>>t; Add(u,v,t);Add(v,u,t);//建双向边 } Dfs(1,0,0,0);Get(); while(m--){ cin>>u>>v; int anc=LCA(u,v); int re=dis[u]+dis[v]-2*dis[anc]; printf("%d\n",re); } return 0; }

修改后的python版本

class Tree: def __init__(self, n): self.n = n self.Graph = [[] for i in range(n + 1)] def insert(self, x, y): self.Graph[x].append(y) self.Graph[y].append(x) # # class Node: # def __init__(self, id): # self.id = id def dfs(now, father, deep): fa[now][0] = father dep[now] = deep for v in tree.Graph[now]: if v != father: dfs(v, now, deep + 1) def get_fa(): for j in range(1, S + 1): for i in range(1, n + 1): fa[i][j] = fa[fa[i][j - 1]][j - 1] def get_same(a, t): for i in range(S + 1): if t & (1 << i): a = fa[a][i] return a def LCA(a, b): if dep[a] < dep[b]: a, b = (b, a) a = get_same(a, dep[a] - dep[b]) if a == b: return a for i in range(S, -1, -1): if fa[a][i] != fa[b][i]: a = fa[a][i] b = fa[b][i] return fa[a][0] n, m, s = input().split() n = int(n) m = int(m) s = int(s) S = 25 tree = Tree(n) fa = [[0 for _ in range(S + 1)] for __ in range(n + 1)] dep = [0 for _ in range(n + 1)] for _ in range(n - 1): x, y = input().split() x = int(x) y = int(y) tree.insert(x, y) dfs(s, s, 0) get_fa() for _ in range(m): x, y = input().split() x = int(x) y = int(y) print(LCA(x, y))

依据CCS分类建树（简单方案）

CCS分类

ACM Computing Classification System（CCS） 2012 ACM计算分类系统已开发为一种多层次的本体，可以在语义Web应用程序中使用。它替代了1998年的ACM计算分类系统（CCS）的传统版本，该版本已成为计算领域的事实上的标准分类系统。 它已集成到ACM数字图书馆的搜索功能和可视主题显示中。它依赖于语义词汇作为类别和概念的唯一来源，它反映了计算机科学的最新水平，并且随着未来的发展而接受结构性变化。 ACM在可视显示格式内提供了一种工具，以促进将2012 CCS类别应用到即将发表的论文中，并提供确保CCS与时俱进的过程。新的分类系统将在ACM数字图书馆的人员搜索界面的开发中起到关键作用，以补充其当前的传统书目搜索。 完整的CCS分类树可以HTML格式免费用于教育和研究目的。在ACM数字图书馆中，CCS以可视化显示格式显示，有助于导航和反馈。完整的CCS分类树也可以在数字图书馆中以平面文件形式查看。 来源：https://dl.acm.org/ccs

即，CCS分类是一种树结构的分类标准。接下来看一下给出的CCS分类文件： 由这个文件可以很显然的看出每篇论文的所属的类别。 例如：

h. information systems h.3 information storage and retrieval h.3.3 information search and retrieval subjects: search processH.信息系统 h.3信息存储和检索 h.3.3信息搜索和检索主题：搜索过程 由此可见，该文件属于h.3.3类。

文件的每一行对应一个类，空行是空数据，作特殊处理。 在查询的过程中也发现了中国标准文献分类法(CCS)，在这里也可以记录一下。

建树求距离

方案一：借助文件求

观察文件IndexTerms.txt，我们可以知道一篇论文可能会有三种情况：

论文属于a（假设）论文属于a.1论文属于a.1.1 （以后都以a，a.1，a.1.1为例）

因此，树结构最多有三层。那么，我们可以通过分类讨论列举所有情况并进行处理的方式来解决这个问题。

数据预处理

对于文件IndexTerms.txt来说，我们需要的是能够表达论文所属类型的关键词（a，a.1，a.1.1等），而不需要冗长的介绍，因此我们需要对文件进行预处理。 对于这种，我们选择提取k.3.1 但是并不是每个论文都能精确的分类到第三级，因此会有： 这种情况出现，对于这样的我们选择提取j.5。 而有的论文只能划分到大类，例如 对于这种情况，我们选择提取a。

对于这种提取我们有一个很好用的工具：正则表达式。能想到这个问题就很简单了，代码如下

s="" for i in range(len(lis)): if(len(lis[i])==0): #print(i) s+=str(i) s+=',' s+='\n' else: s+=str(i) s+=',' ret = re.findall(r'\w.\d.\d',lis[i]) if(len(ret)==0): print(i) ret = re.findall(r'\w.\d',lis[i]) if(len(ret)==0): ret = re.findall(r'\w',lis[i]) s+=ret[0] else: s+=ret[0] else: for j in range(len(ret)): s+=ret[j] if(j<len(ret)-1): s+="," s+='\n' print(s)

需要注意的是，还有一种特殊情况需要单独考虑： 图中展示的论文分类表示，该论文可以被分到多个类中，这种情况我们需要把它所属的类都统计下来，因此在匹配的时候选择的函数是$re.findall()$

为了方便之后的计算，我们把处理后的数据存到一个文件中。存储的形式为“论文id，分类”，因此在构造字符串的时候也进行了相应的处理。写入文件：

fh = open('E:\\创新实训\\资料整理\\code+data\\treenode.txt', 'w', encoding='utf-8') fh.write(s) fh.close()

文件如下：

计算距离

因为树的结构是规则的，因此距离也是有规律可循的，接下来我们对每种情况进行分类讨论。 假设论文为X和Y，并且，我们把 “* . * . *” 部分记为该论文的分类属性。

其中有论文没有所属类： 相似度为0 两篇论文不属于同一个大类： 相似度为0（该相似度仍有待商榷） 两篇论文的分类属性字符串完全相同 相似度为1 两篇论文的分类属性字符串不同 两篇论文分类属性长度$l$相同（字符串长度） $l==3$：同为二级节点，没有多种情况，边数为2，设边权为2（*），相似度记为距离的倒数，因此相似度为1/4。$l==5$： 两篇论文属于同一个二级结点：边数为2，距离为4，相似度为1/4。两篇论文不同属于一个二级结点，那么它们的最近公共父节点就是根节点，因此边数为4，距离为8，相似度为1/8. 注：$l！=1$，因为当属性分类字符串长度为1时，说明是“a”这种情况，这种情况已经由上一步的“分类属性字符串完全相同”处理了，因此这里没有。 两篇论文分类属性长度$l$不同（字符串长度） 声明： 我们保证$l_x<l_y$，如正好相反，则交换$x,y$。$l_x==1$ and $l_y==3$：边长为1，距离为2，相似度为1/2。$l_x==1$ and $l_y==5$：边长为2，距离为4，相似度为1/4。$l_x==3$ and $l_y==5$： 两篇论文是父子关系： 边长为1，距离为2，相似度为1/2。两篇论文不是父子关系：边长为3，距离为6，相似度为1/6。

至此，所以的情况我们已经都讨论完了，只要按照这个编写代码即可完成。

def fun(): X,Y=input().split() X=int(X) Y=int(Y)##ID i tx=listid[X].split(",") ty=listid[Y].split(",") if(tx[1]==ty[1]): return 1 XT=tx[1][0] YT=ty[1][0] #print(XT,YT) if(XT!=YT): return 0##直接返回相似度，不是距离，距离算无穷大 else : lx=len(tx[1]) ly=len(ty[1]) if(lx>ly):##保证lx<ly tt=lx lx=ly ly=tt tt=tx tx=ty ty=tt##数值和字符串都换回来 if(lx==ly): if(lx==1): return 1/1 elif(lx==3): return 1/4 else: #print(lx) xx=tx[1] yy=ty[1] mx=xx.split(".")[1] my=yy.split(".")[1]##找出第二位 if(mx==my): return 1/4 else: return 1/8 else:##lx<ly if(lx==1)&(ly==3): return 1/2 elif(lx==1)&(ly==5): return 1/4 else: xx=tx[1] yy=ty[1] mx=xx.split(".")[1] my=yy.split(".")[1]##找出第二位 if(mx==my): return 1/4 else: return 1/6

调用该函数，输入需要计算的论文id，即可得到结果。

全部代码如下：

# -*- coding: utf-8 -*- """ Created on Tue Jun 23 10:33:22 2020 @author: nyy """ #import re def Load(): listid = [] for line in open("treenode.txt","r"): #设置文件对象并读取每一行文件 listid.append(line.replace("\n","")) #print(listid) return listid def fun(listid): print("请输入论文id：") X,Y=input().split() X=int(X) Y=int(Y)##ID i tx=listid[X].split(",") ty=listid[Y].split(",") if(len(tx[1])==0) or (len(ty[1])==0): return 0 if(tx[1]==ty[1]): return 1 XT=tx[1][0] YT=ty[1][0] #print(XT,YT) if(XT!=YT): return 0##直接返回相似度，不是距离，距离算无穷大 else : lx=len(tx[1]) ly=len(ty[1]) if(lx>ly):##保证lx<ly tt=lx lx=ly ly=tt tt=tx tx=ty ty=tt##数值和字符串都换回来 if(lx==ly): if(lx==1): return 1/1 elif(lx==3): return 1/4 else: #print(lx) xx=tx[1] yy=ty[1] mx=xx.split(".")[1] my=yy.split(".")[1]##找出第二位 if(mx==my): return 1/4 else: return 1/8 else:##lx<ly if(lx==1)&(ly==3): return 1/2 elif(lx==1)&(ly==5): return 1/4 else: xx=tx[1] yy=ty[1] mx=xx.split(".")[1] my=yy.split(".")[1]##找出第二位 if(mx==my): return 1/4 else: return 1/6 def main(): lis=Load() #print(lis) rere=fun(lis) print(rere) main()