yhongm


  • Home

  • Archives

编辑距离算法

Posted on 2019-05-06

使用的莱文斯坦算法(编辑距离算法)

wike介绍

前期了解

莱文斯坦距离,又称Levenshtein距离,是编辑距离的一种。指两个字串之间,由一个转成另一个所需的最少编辑操作次数。允许的编辑操作包括将一个字符替换成另一个字符,插入一个字符,删除一个字符。
莱文斯坦距离以俄国科学家Vladimir levenshtein命名,于1965年发明了这个算法,莱文斯坦距离又称为编辑距离。
在信息论中,两个等长字符串之间的汉明距离(英语:Hamming distance)是两个字符串对应位置的不同字符的个数。换句话说,它就是将一个字符串变换成另外一个字符串所需要替换的字符个数。
汉明重量是字符串相对于同样长度的零字符串的汉明距离,也就是说,它是字符串中非零的元素个数:对于二进制字符串来说,就是1的个数,所以11101的汉明重量是4。

这里, 和 分别表示字符串a和b的长度, 是当 时值为1,否则值为0的示性函数。这样, 是 的前 个字符和 的前 个字符之间的距离。

概念

字符串的编辑距离,又称为Levenshtein距离,由俄罗斯的数学家Vladimir Levenshtein在1965年提出。是指利用字符操作,把字符串A转换成字符串B所需要的最少操作数。其中,字符操作包括:

  • 删除一个字符
  • 插入一个字符
  • 修改一个字符

上下界

莱文斯坦距离包括几个简单的上下界,包括:

  • 至少是两个字符串之间的差值
  • 最多是较长字符串的长度
  • 如果两个字符串相同为0
  • 如果两个字符串长度相同,汉明距离即为莱文斯坦距离上届
  • 两个字符串之间的莱文斯坦距离不大于它们与第三个字符串之间的莱文斯坦距离之和(三角形不等式)

例子

比如,字符串“kitten”和“sitting”的莱文斯坦距离为3

  • kitten → sitten (k替换为s)
  • sitten → sittin (e替换为i)
  • sittin → sitting (在结尾添加g).

下面是一个由C语言实现的简单但效率低下的莱文斯坦距离函数,函数给定两个字符串以及他们对应的长度s和t作为参数,并将编辑距离返回.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// len_s and len_t are the number of characters in string s and t respectively
int LevenshteinDistance(const char *s, int len_s, const char *t, int len_t)
{
int cost;

/* base case: empty strings */
if (len_s == 0) return len_t;
if (len_t == 0) return len_s;

/* test if last characters of the strings match */
if (s[len_s-1] == t[len_t-1])
cost = 0;
else
cost = 1;

/* return minimum of delete char from s, delete char from t, and delete char from both */
return minimum(LevenshteinDistance(s, len_s - 1, t, len_t ) + 1,
LevenshteinDistance(s, len_s , t, len_t - 1) + 1,
LevenshteinDistance(s, len_s - 1, t, len_t - 1) + cost);
}

这种执行效率太低,因为它会多次从新计算相同字符串的编辑距离
一个更有效的方法是永远不会计算相同字符串的编辑距离,所有可能前缀的莱文斯坦距离都可以存储在一个数组d[][]中,
其中d[i][j]是字符串s的前i字符和字符串t的前j个字符的距离,这个表非常容易构造一张每次从0开始的行,当整张表建成后,距离为d[len_s][len_t]
计算编辑距离的依据是观察到,如果保存一个矩阵来持有第一个字符串前缀和第二个字符串前缀之间的编辑距离,然后我们可以用动态编程的方式来计算矩阵中的值,因次可以计算出两个完整字符串最后的值
该算法的解决是基于动态规划的思想,具体如下:
设 s 的长度为 n,t 的长度为 m。如果 n = 0,则返回 m 并退出;如果 m=0,则返回 n 并退出。否则构建一个数组 d[0..m, 0..n]。
将第0行初始化为 0..n,第0列初始化为0..m。
依次检查 s 的每个字母(i=1..n)。
依次检查 t 的每个字母(j=1..m)。
如果 s[i]=t[j],则 cost=0;如果 s[i]!=t[j],则 cost=1。将 d[i,j] 设置为以下三个值中的最小值:
紧邻当前格上方的格的值加一,即 d[i-1,j]+1
紧邻当前格左方的格的值加一,即 d[i,j-1]+1
当前格左上方的格的值加cost,即 d[i-1,j-1]+cost
重复3-6步直到循环结束。d[n,m]即为莱茵斯坦距离。

用全矩阵迭代

下面是一个简单的伪代码实现的LevenshteinDistance函数,函数给定了两个字符串,s字符串的长度为m,t字符串的长度为n,并且返回两个字符串的编辑距离

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
function LevenshteinDistance(char s[1..m], char t[1..n]):
// for all i and j, d[i,j] will hold the Levenshtein distance between
// the first i characters of s and the first j characters of t
// note that d has (m+1)*(n+1) values
declare int d[0..m, 0..n]

set each element in d to zero

// source prefixes can be transformed into empty string by
// dropping all characters
for i from 1 to m:
d[i, 0] := i

// target prefixes can be reached from empty source prefix
// by inserting every character
for j from 1 to n:
d[0, j] := j

for j from 1 to n:
for i from 1 to m:
if s[i-1] = t[j-1]:
substitutionCost := 0
else:
substitutionCost := 1
d[i, j] := minimum(d[i-1, j] + 1, // deletion
d[i, j-1] + 1, // insertion
d[i-1, j-1] + substitutionCost) // substitution

return d[m, n]

结果矩阵的两个示例

















































































k
i
t
t
e
n
0123456
s
1123456
i
2212345
t
3321234
t
4432123
i
5543223
n
6654332
g
7765443


























































































S
a
t
u
r
d
a
y

012345678
S
101234567
u
211223456
n
322233456
d
433334345
a
543444434
y
654455543

在整个算法中不变的是,我们可以转换初始片段s[1..i]到t[1..j]通过使用一个最小数d[i][j]的操作,在最后,数组右下角的元素包含答案

用两个矩阵进行迭代

结果表明,如果不想重新构造已编辑的输入字符串,则构造只需要表的两行(上一行和只计算的当前行)
可以使用以下迭代法计算编辑距离

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
function LevenshteinDistance(char s[1..m], char t[1..n]):
// create two work vectors of integer distances
declare int v0[n + 1]
declare int v1[n + 1]

// initialize v0 (the previous row of distances)
// this row is A[0][i]: edit distance for an empty s
// the distance is just the number of characters to delete from t
for i from 0 to n:
v0[i] = i

for i from 0 to m-1:
// calculate v1 (current row distances) from the previous row v0

// first element of v1 is A[i+1][0]
// edit distance is delete (i+1) chars from s to match empty t
v1[0] = i + 1

// use formula to fill in the rest of the row
for j from 0 to n-1:
// calculating costs for A[i+1][j+1]
deletionCost := v0[j + 1] + 1
insertionCost := v1[j] + 1
if s[i] = t[j]:
substitutionCost := v0[j]
else:
substitutionCost := v0[j] + 1

v1[j + 1] := minimum(deletionCost, insertionCost, substitutionCost)

// copy v1 (current row) to v0 (previous row) for next iteration
swap v0 with v1
// after the last swap, the results of v1 are now in v0
return v0[n]

这两行变种是次优的,所需的内存量减少到一行和一个字的开销
Hirschberg的算法可以将这两种方法分而治之,他可以在相同的时间和空间边界计算出最佳序列而不仅仅是编辑距离

通常编辑距离时间复杂度是O(M*N),但通常我们只要一些简单的移动就能满足需要,降低点精确性,将时间复杂度降低到O(max(M, N)即可

虚拟dom diff算法

Posted on 2019-05-05

虚拟DOM

为什么使用虚拟DOM

因为直接操作虚拟DOM效率低,并且执行慢

浏览器工作流

下图使用webkit,除了一些细微差别,所有浏览器工作流相同

创建DOM树:

  • 一旦浏览器接收一个HTML文件,渲染引擎解析它并创建一个节点DOM树,HTML节点有一个一对一的关系
    创建渲染树
  • 与此同时解析外部CSS文件,内联样式文件.样式信息随着DOM树中节点,被用作创建其他的树,被称为渲染树
    创建渲染树的背后
  • 在webkit中,解析节点,样式的过程被称为“attachment”,DOM树中的所有节点都有一个attach方法,它接收计算出的样式信息并且返回一个渲染对象(renderer)
  • Attachment 是同步的,节点插入DOM树会调用新节点的attach方法
  • 构建渲染树过程中,由这些渲染对象组成的,需要计算每个渲染对象的视觉属性.这是通过元素的计算样式属性来完成的。
    布局(重排)
  • 在构建渲染树之后,他经过一个布局过程,在屏幕上都会给渲染树中的每个节点一个确定的坐标,显示在屏幕的确切位置
    绘制
  • 下一步就是绘制渲染对象-渲染树通过调用每一个节点的paint方法进行绘制(使用浏览器的后端API agnostic UI),最终展示内容在屏幕上

进入虚拟DOM

每当修改一个DOM行为时候,浏览器工作流中所有步骤都会触发,从创建渲染树开始(从新计算所有节点的的所有样式信息),布局,绘制,所有步骤都会从做
在一个复杂的过程中,通常涉及大量的DOM的操作,这需要多个计算步骤,这是效率非常低的
当你的视图变化时候,在真实DOM上进行所有假定的更改,首先生成虚拟DOM,然后发送到真实的DOM,从而减少计算的数量
实际上虚拟DOM是将双缓冲应用于虚拟DOM

DOM DIFF算法

什么是 DOM Diff 算法

Web 界面由 DOM 树来构成,当其中某一部分发生变化时,其实就是对应的某个 DOM 节点发生了变化.在虚拟dom中,状态决定界面,前后两种状态对应两种界面,比较两个界面的区别就需要比较两个界面
即给定任意两棵树,找到最少的转换步骤。但是标准的的 编辑距离算法复杂度需要 O(n^3),这显然无法满足性能要求。要达到每次界面都可以整体刷新界面的目的,势必需要对算法进行优化。FACEBOOK工程师做了以下两点如下假设,使算法复杂度降低到O(n):

  • 两个相同组件产生类似的 DOM 结构,不同的组件产生不同的 DOM 结构;
  • 对于同一层次的一组子节点,它们可以通过唯一的 id 进行区分。

不同节点类型的比较

为了在树之间进行比较,我们首先要能够比较两个节点,比较两个虚拟 DOM 节点,当两个节点不同时,应该如何处理。
这分为两种情况:

  • (1)节点类型不同
  • (2)节点类型相同,但是属性不同。
    当在树中的同一位置前后输出了不同类型的节点,直接删除前面的节点,然后创建并插入新的节点。假设我们在树的同一位置前后两次输出不同类型的节点。
    1
    2
    3
    renderA: <div/>
    renderB: <span/>
    => [removeNode <div/>], [insertNode <span/>]

当一个节点从 div 变成 span 时,简单的直接删除 div 节点,并插入一个新的 span 节点。这符合我们对真实 DOM 操作的理解。
需要注意的是,删除节点意味着彻底销毁该节点,而不是再后续的比较中再去看是否有另外一个节点等同于该删除的节点。如果该删除的节点之下有子节点,那么这些子节点也会被完全删除,它们也不会用于后面的比较。这也是算法复杂能够降低到 O(n)的原因。
不同的组件一般会产生不一样的 DOM 结构,与其浪费时间去比较它们基本上不会等价的 DOM 结构,还不如完全创建一个新的组件加上去。
DOM Diff 算法实际上只会对树进行逐层比较,如下所述。

逐层进行节点比较

树的算法其实非常简单,那就是两棵树只会对同一层次的节点进行比较。如下图所示:

只会对相同颜色方框内的 DOM 节点进行比较,即同一个父节点下的所有子节点。当发现节点已经不存在,则该节点及其子节点会被完全删除掉,不会用于进一步的比较。这样只需要对树进行一次遍历,便能完成整个 DOM 树的比较。

例,比如下面的DOM结构

A 节点被整个移动到 D 节点下,直观的考虑 DOM Diff 操作应该是

1
2
A.parent.remove(A); 
D.append(A);

只会简单的考虑同层节点的位置变换,对于不同层的节点,只有简单的创建和删除。当根节点发现子节点中 A 不见了,就会直接销毁 A;而当 D 发现自己多了一个子节点 A,则会创建一个新的 A 作为子节点。因此对于这种结构的转变的实际操作是

1
2
3
4
5
A.destroy();
A = new A();
A.append(new B());
A.append(new C());
D.append(A);

可以看到,以 A 为根节点的树被整个重新创建.虽然看上去这样的算法有些“简陋”,但是其基于的是第一个假设:两个不同组件一般产生不一样的 DOM 结构。

1
2
3
4
5
6
7
C will unmount.
C is created.
B is updated.
A is updated.
C did mount.
D is updated.
R is updated.

可以看到C节点是完全重建后再添加到 D 节点之下,而不是将其“移动”过去

相同类型节点的比较

相同类型的节点,对属性进行重设从而实现节点的转换。例如:

1
2
3
renderA: <div id="before" />
renderB: <div id="after" />
=> [replaceAttribute id "after"]

虚拟 DOM 的 style 属性稍有不同,其值并不是一个简单字符串而必须为一个对象,因此转换过程如下:

1
2
3
renderA: <div style={{color: 'red'}} />
renderB: <div style={{fontWeight: 'bold'}} />
=> [removeStyle color], [addStyle font-weight 'bold']

列表节点的比较

对于不在同一层的节点的比较,即使它们完全一样,也会销毁并重新创建。那么当它们在同一层时
列表节点的操作通常包括添加、删除和排序。例如下图,我们需要往 B 和 C 直接插入节点 F

这时如果每个节点都没有唯一的标识,React 无法识别每一个节点,那么更新过程会很低效,即,将 C 更新成 F,D 更新成 C,E 更新成 D,最后再插入一个 E 节点。效果如下图所示:

会逐个对节点进行更新,转换到目标节点。而最后插入新的节点 E,涉及到的 DOM 操作非常多。而如果给每个节点唯一的标识(key),那么 React 能够找到正确的位置去插入新的节点,入下图所示:

对于列表节点顺序的调整其实也类似于插入或删除,

即将同一层的节点位置进行调整。如果未提供 key,那么认为 B 和 C 之后的对应位置组件类型不同,因此完全删除后重建,控制台输出如下:

1
2
3
4
5
6
7
8
B will unmount.
C will unmount.
C is created.
B is created.
C did mount.
B did mount.
A is updated.
R is updated.

而如果提供了 key,如下面的代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
shape5: function() {
return (
<Root>
<A>
<B key="B" />
<C key="C" />
</A>
</Root>
);
},

shape6: function() {
return (
<Root>
<A>
<C key="C" />
<B key="B" />
</A>
</Root>
);
},

控制台输出如下:

1
2
3
4
C is updated.
B is updated.
A is updated.
R is updated.

引用
引用
引用

yhongm

2 posts
© 2019 yhongm
Powered by Hexo
|
Theme — NexT.Muse v5.1.4