不会构建依存语义图?不存在的
各位看官里面请~
今天我们的主题是:图结构在句法分析中的应用
今天的主题来源于最近慕寒解决的一个模型问题:对于一个文本,
如何得到一个分词在依存句法层面距离小于等于3个单位的所有分词?可能各位看官看到这个问题会有点迷糊,没事儿,让我慢慢道来。图结构就不再赘述,各位看官可以看这篇文章:
所以,我们紧随其后,构建依存关系的Graph!!!构建图的函数如下:
传送门:
数据结构慕寒说,公众号:慕寒说当“Python”遇上“数据结构”不过为了解决这个问题,我们需要对基本的图结构相关的函数做一些修改,修改后的函数如下:
那什么是句法分析?什么是依存句法层面距离呢?这就涉及慕寒接触的自然语言处理领域了。对于文本:“台风豪雨所造成的水把市区淹得惨不忍睹。”我们可以分析它的结构信息,比如说:各个词的词性、不同词之间的逻辑关系、不同词之间的语义关系等等。这方面的内容,慕寒不说太多,因为不是本文章的关注点,我们今天关注的是算法层面。如果各位看官想要了解的话,可以后台留言,慕寒可以出文章进行说明~ 我们来分析一下这个问题,既然要获得分词在依存句法层面距离小于等于3个单位的所有分词,那我们首先要获得这个文本的分词结果、依存关系!!!这个很简单,慕寒这里用的哈工大的pyltp实现,后面也用了哈工大的一些模型(如侵必删)。 完成之后,如果我们将不同分词之间依存关系画出来的话,我们可以发现,这不明显就是图结构嘛?看下图:class Vertex:
'''
表示图中的每一个顶点
' ''
def __init__(self, index):
self.id = index
self.connectedTo = {}
self.color = 'white'
self.dist = sys.maxsize # 从起点到当前顶点的最小权重路径的总权重
self.pred = None
self.disc = 0
self.fin = 0
def addNeighbor(self, nbr, weight = 0, relation = None):
self.connectedTo[nbr] = [weight, relation]
def __str__(self):
nbrInfo = []
for nbr in self.connectedTo.keys():
nbrInfo.append([nbr.id, self.connectedTo[nbr][0], self.connectedTo[nbr][1]])
return str(nbrInfo)
def getConnections(self):
return self.connectedTo.keys()
def getId(self):
return self.id
def getWeight(self, nbr):
return self.connectedTo[nbr][0]
def getRelation(self, nbr):
return self.connectedTo[nbr][1]
def setColor(self,color):
self.color = color
def setDistance(self,d):
self.dist = d
def setPred(self,p):
self.pred = p
def setDiscovery(self,dtime):
self.disc = dtime
def setFinish(self,ftime):
self.fin = ftime
def getFinish(self):
return self.fin
def getDiscovery(self):
return self.disc
def getPred(self):
return self.pred
def getDistance(self):
return self.dist
def getColor(self):
return self.color
class Graph:
'''
图
' ''
def __init__(self):
self.vertList = {}
self.numVertices = 0
#self.count = 0
def addVertex(self, index, name):
self.numVertices = self.numVertices + 1
newVertex = Vertex(index)
self.vertList[name] = newVertex
return newVertex
def getVertex(self, n):
if n in self.vertList:
return self.vertList[n]
else:
return None
def __contains__(self, n):
return n in self.vertList
def addEdge(self, f, fIndex, t, tIndex, cost = 0, relation = None):
if f not in self.vertList:
nv = self.addVertex(fIndex, f)
if t not in self.vertList:
nv = self.addVertex(tIndex, t)
self.vertList[f].addNeighbor(self.vertList[t], cost, relation)
def getVertices(self):
return self.vertList.keys()
def __iter__(self):
return iter(self.vertList.values())
所以,我们紧随其后,构建依存关系的Graph!!!构建图的函数如下:
各位客官会发现,这个图节点的名字的格式为:分词+索引。为啥呢?因为这里图结构采用字典的键值对表示的,我们都知道字典中不能存在同样的键,所以慕寒就用这个分词在分词列表中的索引信息来表示键了。 那么问题来了,我怎么获得依存句法层面距离小于等于3个单位的所有分词呢?(为了方便期间,这个距离慕寒就说成:依存距离)这里我们需要引入一个权重的概念,慕寒想的是:既然只考虑单位距离,那就可以让每个相邻的分词之间的距离权重为1。当然了,我们要默认各分词一开始是不相邻的,所以距离设置成很大很大(代码实现为:sys.maxsize)。那么如何找到依存距离小于等于3的所有分词呢?通过对图相关算法的回顾,慕寒发现了Dijkstra算法,没错!就是解决最短路径的Dijkstra算法。各位看官是不是突然明白了这个问题该如何解决呢?有了各节点之间的最短路径,那么我们就只需要把最短路径小于等于3个单位的分词找出来,那不就大功告成了!!!Dijkstra函数如下:def buildGraph(self):
'''
构建图结构
权重距离为1个单位
' ''
for index in range(len(self.segList)):
seg = self.segList[index]
arcIndex = self.arcs[index][0] - 1
arcSeg = self.segList[arcIndex]
arcName = self.arcs[index][1]
self.Graph.addVertex(index, seg + str(index))
for index in range(len(self.segList)):
seg = self.segList[index]
arcIndex = self.arcs[index][0] - 1
arcSeg = self.segList[arcIndex]
arcName = self.arcs[index][1]
self.Graph.addEdge(seg + str(index), index, arcSeg + str(arcIndex), arcIndex, 1, arcName)
self.Graph.addEdge(arcSeg + str(arcIndex), arcIndex, seg + str(index), index, 1, arcName)
当然,为了实现这个算法,我们还需要引入“优先级队列”,这可以在Python的第三方库“pythonds”导入,具体的各位看官可以看慕寒最后附上的所有代码链接~。通过Dijkstra算法,我们就可以对原始的Graph进行修正,并用于后续的引用。 所以具体怎么用呢?别急,慕寒这里给出了使用的函数:def dijkstra(self, aGraph, start):
pq = PriorityQueue()
start.setDistance(0) # 将start节点到start节点的距离设置为0
pq.buildHeap([(v.getDistance(), v) for v in aGraph])
while not pq.isEmpty():
currentVert = pq.delMin()
#print("currentVert:",currentVert)
#print("pq:\n", pq.heapArray)
for nextVert in currentVert.getConnections():
newDist = currentVert.getDistance() + currentVert.getWeight(nextVert)
if newDist < nextVert.getDistance():
nextVert.setDistance(newDist)
nextVert.setPred(currentVert)
pq.decreaseKey(nextVert, newDist)
return pq, aGraph
大致思路就是:对于每个分词seg,我们要通过Dijkstra算法对文本依存句法分析得到的Graph进行修正后的newGraph,该图中各节点之间的距离为节点之间最短路径。然后再根据分词seg得到newGraph中所有与该seg的最短路径小于等于3的节点(我们需要的分词)以及其在分词列表中的索引位置,最终的输出如下:def getNArc(self, arcLen):
'''
获取语义逻辑arcLen内所有分词的索引
'''
segArcLenL = []
for index in range(len(self.segList)):
segArcLenL.append([])
seg = self.segList[index]
aGraph = self.Graph
start = self.Graph.getVertex(seg + str(index))
pq, newAGraph = self.dijkstra(aGraph, start)
vertexConnectArcLenIndexL = []
for vertex in newAGraph:
vertexConnectIndexL = [v.id for v in list(vertex.getConnections())]
shortDistanceL = []
for nextV in vertex.getConnections():
shortDistanceL.append(nextV.getDistance())
for vertexIndex in range(len(vertexConnectIndexL)):
vertexConnectIndex = vertexConnectIndexL[vertexIndex]
shortDistance = shortDistanceL[vertexIndex]
if (vertexConnectIndex >= 0) and (vertexConnectIndex != index) and (shortDistance > 0 and shortDistance <= arcLen):
vertexConnectArcLenIndexL.append(vertexConnectIndex)
vertexConnectArcLenIndexL = list(set(vertexConnectArcLenIndexL))
vertexConnectArcLenIndexL.sort()
segArcLenL[-1] = segArcLenL[-1] + vertexConnectArcLenIndexL
vertexConnectArcLenIndexL = []
self.buildGraph()
return segArcLenL
segList表示分词列表,arcs表示文本依存句法关系,segArcLenL表示与每个分词的依存距离小于等于3的所有分词在segList中的位置。 到此位置,今天的问题就解决了,不知道各位看官是否看明白了呢?慕寒觉得这个问题的解决方案是具有一定普适性的,虽然,慕寒还没想出来可以用在哪里。各位看官自行探索叭,欢迎分享~ 溜~~~
传送门:
链接:
https://pan.baidu.com/s/1mYiiK-3ngYvY_wBbXhlTEg 提取码: 1105评论