Regular Syntax to NFA
Data
示例数据位于：\data.txt 中,如下所示格式：
S->aA|$
A->aB|bA
B->aS|bA|$
S->bB
实现位于/model.py中，基于Python 3。
节点类：
每个节点的属性就是名字，作为键值在Graph对象中可以直接查询以访问。节点中还保存了后继节点的信息。
class node:
def __init__(self,name):
self.name = name
self.nxt = dict({})
pass
def add_edge(self,e,v_node):
self.nxt[e] = v_node
图类：
$self.node_dict$:保存节点，按名字查询
$self.create_graph()$ ：构造图，对于传入的节点名字的列表遍历建立新节点并查询后继节点建立连接。
class graph:
def __init__(self,S,T):
self.S = S
self.T = T
self.node_dict = {}
self.end_nodes = []
self.num_of_end = 0
self.num_of_eps_end = 0
def generate_end_state(self,name = epsilon):
self.num_of_end += 1
if name == epsilon:
self.num_of_eps_end += 1
end_node = node(name)
self.end_nodes.append(end_node)
self.node_dict[name] = end_node
return end_node
def create_graph(self):
for name in self.S:
if name not in self.node_dict:
new_node = node(name=name)
self.node_dict[name] = new_node
for edge in self.T[name]:
if len(edge) == 1:
e = edge
v = edge
if edge == epsilon:
if edge not in self.node_dict:
self.generate_end_state(name=epsilon)
else:
if edge not in self.node_dict:
self.generate_end_state(name=edge)
pass
pass
else:
e = edge[0]
v = edge[1]
if v not in self.node_dict:
self.node_dict[v] = node(name=v)
pass
pass
pass
输出
输出信息：
- 非终止状态的节点名字以及其后继节点和对应转移的终结符
- 终结状态名
NODE S :
edge(from to) transfer_char
( S A ) a
( S $ ) $
( S B ) b
NODE A :
edge(from to) transfer_char
( A B ) a
( A A ) b
NODE B :
edge(from to) transfer_char
( B S ) a
( B A ) b
( B $ ) $
END STATE(s) of this NFA:
$
Minimum Editing Distance
问题描述
假设有两个字符串$S_1$与$S_2$，记：$S_m(k)$为第$m$个字符串的前$k$个字符所构成的子串。那么又记$L(i,j)$为这$S_1.substr(i)$与$S_2.substr(j)$两个子串的最小编辑距离。
算法
考虑到：$L(i,j)$可以有三个相关的子状态$L(i-1,j)$，$L(i,j-1)$,$L(i-1,j-1)$。对于前两种子状态，如果两个字符串前$i$与$j$个字符的最小编辑距离确定了，那么任意一个子串多附加一个字符的话，如果附加的字符与另一个串的末尾字符不相等，显然是需要删去的，也就是编辑距离会+1；如果相等，那么显然用附加字符匹配另一子串的末尾字符后，必然会有之前的一个字符要被删去，所以编辑距离也会+1。最后对于第三种状态，由于之前的状态已经产生了一个最小编辑距离，此时两个同时附加的又是同一个字符，那么显然不需要增加距离，反之一定需要更改操作，将其中一个换成另一个附加的字符才是最小损失操作。故我们可以得出MED的状态转移公式：
初始化状态：
Python实现
def min_dis(str1, str2):
len_str1 = len(str1) + 1
len_str2 = len(str2) + 1
# create matrix
matrix = [0 for n in range(len_str1 * len_str2)]
# init x axis
for i in range(len_str1):
matrix[i] = i
# init y axis
for j in range(0, len(matrix), len_str1):
if j % len_str1 == 0:
matrix[j] = j // len_str1
for i in range(1, len_str1):
for j in range(1, len_str2):
if str1[i - 1] == str2[j - 1]:
cost = 0
else:
cost = 1
matrix[j * len_str1 + i] = min(matrix[(j - 1) * len_str1 + i] + 1,
matrix[j * len_str1 + (i - 1)] + 1,
matrix[(j - 1) * len_str1 + (i - 1)] + cost)
return matrix[-1]
