N最短路径分词Python 实现

N最短路径分词Python 实现

[TOC]

内容简介

本文介绍《基于N-最短路径方法的中文词语粗分模型》的实现。 论文中介绍文分词主要分为三个过程：

1.预处理粗分，这步长用的有最大匹配，最短路径，概率统计方法。 2.排歧 未登录词识别（包括人名，实体识别） 3.词性标准

Paper 描述的是一种粗分方法，其实会产生多个粗分结果，并没有介绍分完之后的处理方案。所以我的重点只是对文章内容的实现。

思路描述

根据词典，找出字串中所有可能的词，构造词切分有向无还图，每个词对应图中的一条边。并赋予边一定的权重（这里有机关）。然后求出该图从起点到终点排名前N的最短路径。

Paper 是上面那样描述的, 对我来说看了还不如不看。最清晰和简单的描述方法我认为有三种，1.数学公司，2.代码，3,图，举个例子。 下面有个例子，是对 “他说的确实在理” 这句话的图模型

图的定点是0,1,2....7，这些顶点其实没有什么实际含义，不是词，也不是字。只是一个编号。有n个词的句子就会产生n+1个定点。 图中的每条边都是一个词，边都可以是有权重的（我默认为1）,这个权重可以是概率，词频之类的。

所以整个过程其实只有两部

1.构造一个词图 2.计算前n最短路径

图和最短路径

有像无环图的单源最短路径算法，用得比较多的是Dijstkra算法，这个算的基本想法就是从起点宽度优先遍历图，在每一个顶点都选择离当前节点最近的放入最终的结果集合中，并更新其他没有遍历到的定到起点的距距离。 具体过程如下图（ 图来源博客园 ）

我做了个Python 版本的，主要是图和最短路径两部分 ``` import warnings import sys

class Vertex(object): """

vertex
param:
vertex_id : id
"""

def __init__(self, vertex_id):
    self.id = vertex_id
    self.connections = {}
    self.distance = sys.maxsize
    self.pre = None
    self.visited = False

def __str__(self):
    return 'vertex_' + str(self.id)

def get_weight(self, vertex):
    return self.connections.get(vertex, sys.maxsize)

def add_connection(self, to_vertex, distance):
    self.connections[to_vertex] = distance

def get_distance(self):
    return self.distance

def __lt__(self, other):
    return self.distance < other.distance

def __hash__(self):
    return self.id

class Graph(object): def init (self): self.vertexs = [] self.edges = []

def add_vertex(self, vertex):
    if vertex in self.vertexs:
        warnings.warn('%s is in graph' % (vertex))
        return
    self.vertexs.append(vertex)

def get_vertex(self, vertex):
    if vertex in self.vertexs:
        return vertex
    return None

def add_edge(self, from_vertex, to_vertex, distance):

    if from_vertex not in self.vertexs:
        self.add_vertex(from_vertex)

    if to_vertex not in self.vertexs:
        self.add_vertex(to_vertex)
    from_vertex.add_connection(to_vertex, distance)

def __iter__(self):
    return iter(self.vertexs)

```

最短路径 ```

import copy

def dijkstra(graph, start): path = [] vertex list = copy.deepcopy(graph) for v in vertex list: if v.id == start.id: v.distance = 0

vertex_list = sorted(vertex_list)

while vertex_list:
    current_node = vertex_list.pop(0)
    path.append(current_node)
    for v, distance in current_node.connections.items():
        new_distance = current_node.get_distance() + distance
        if new_distance < v.distance:
            v.distance = new_distance
            v.pre = current_node
    vertex_list = sorted(vertex_list)

for v in path:
    print (str(v), v.distance, str(v.pre))

if name == ' main ': import graph

g = graph.Graph()
v_1 = graph.Vertex(1)
v_2 = graph.Vertex(2)
v_3 = graph.Vertex(3)

g.add_edge(v_1, v_2, 1)
g.add_edge(v_1, v_3, 3)
g.add_edge(v_2, v_3, 2)
dijkstra(g, v_1)

```

n 最短路

计算前N 最短路径其实和上面的Dijkstra 我感觉差距还是比较大的。 每个顶点要记录多个前驱，和对应的权重（起点到前驱的边权重的和），在Dijkstra 里面只是记录一个。

代码实现的时候，充分利用了定点的顺序是递增这一特征，记录前驱就只是记录前驱节点的id,暂时为了简单，默认权重为1，所以也可以忽略不用存储。 Vertex ```

class Vertex(object): def init (self, id):

self.id = id
    self.pre_nodes = []
    self.current_index = 0

def __le__(self, other):
    return self.id <= other.id

def __eq__(self, other):
    return self.id == other.id

def __hash__(self):
    return self.id

def __str__(self):
    return str(self.id)

def add_pre(self, from_pre):
    self.pre_nodes.append(from_pre)
    self.pre_nodes = sorted(self.pre_nodes)

def get_current_node(self):
    return self.pre_nodes[self.current_index]

def pop_pre(self):
    if self.current_index>= len(self.pre_nodes)-1:
        return
    else :
        self.current_index+=1
        return self.pre_nodes[self.current_index]

def has_pre(self):
    if self.current_index >= len(self.pre_nodes)-1:
        return False
    return True

```

Graph ```

class WordNet(object):

def __init__(self, sentence):
    self.vertexs = {}
    self.size = len(sentence)
    self.sentence = sentence
    self.edges = []
    self.init_net()


def init_net(self):
    for index in range(self.size+1):
        self.vertexs[index] = Vertex(index)

    for index in range(0, self.size):
        self.add_connect(index, index+1)


    for w in Dictionary():
        if w not in self.sentence:
            continue

        if len(w) == 1:
            continue
        start_index = self.sentence.index(w)
        end_index = start_index+len(w)
        self.add_connect(start_index, end_index)

def add_connect(self, from_vertex, to_vertex):
    self.edges.append((from_vertex, to_vertex))
    self.vertexs[to_vertex].add_pre(from_vertex)

def get_last(self):
    return self.size

def get_vertex(self, vertex_id):
    return self.vertexs[vertex_id]

`
nshotpath

`

class NShotPath(object):

def __init__(self):
    pass

def seg(self, sentence, n):

    if not sentence:
        return sentence

    stack = []
    path = []
    word_net = WordNet(sentence)

    last_node = word_net.get_last()
    stack.append(last_node)
    current_node = last_node

    while stack:
        while current_node!=0:
            first_node = word_net.get_vertex(current_node).get_current_node()

            stack.append(first_node)
            current_node = first_node

        path.append(copy.deepcopy(stack))


        current_node = stack.pop()

        while True:
            print stack
            current_vertex = word_net.get_vertex(current_node)

            if not stack:
                break

            if not current_vertex.has_pre() and stack:
                current_node = stack.pop()
                continue

            else:
                stack.append(current_node)
                current_node = current_vertex.pop_pre()
                stack.append(current_node)
                break
    return path

``` 所有代码在 GitHub 开源(项目还有文档之类），后面核心功能打算用C实现，所以，很多会改。

精而悟道