文档章节

动态规划算法解LCS问题的JS实践

zcmyworld
 zcmyworld
发布于 2015/08/24 20:48
字数 1101
阅读 73
收藏 0

LCS (最长公共子序列)

定义:一个数列 S,如果分别是两个或多个已知数列的子序列,且是所有符合此条件序列中最长的,则 S 称为已知序列的最长公共子序列。

如有两个字符串:1235和136,则:

1, 12, 123, 1235, 2, 23, ..., 1235是字符串1235的子序列

1, 3, 13, 36, ..., 136是136的子序列

13是1235和136的最长公共子序列

LCS问题即求两集合最长公共子序列的问题

理论基础

设有:

Xi=﹤x1,⋯,xi﹥即X序列的前i个字符 (1≤i≤m)(前缀)

Yj=﹤y1,⋯,yj﹥即Y序列的前j个字符 (1≤j≤n)(前缀)

注:X和Y是从1开始算起

假定Z=﹤z1,⋯,zk﹥∈LCS(X , Y)。

即Z为Xi和Yj的最长公共子序列

  • 若zm=zn(最后一个字符相同),则:该字符必是x与y的任一最长公共子序列Z(设长度为k)的最后一个字符

  • 若zm≠zn,则Zk要么属于ym-1,要么属于yn-1

设Xi和Yj最长公共子序列的长度为C[i,j],则有(公式1):

  • c[i, j] = 0 //when i = 0 or j = 0

  • C[i, j] = c[i - 1, j - 1] + 1; //when zm = zn

  • c[i, j] = max(c[i, j - 1], c[i - 1, j]) //when zm ≠ zn

那么,接下来的目标就是,想办法判断子序列的最后一个字符是只属于X序列还是只属于Y序列,还是属于X序列和Y序列。

而当c[i,j-1] > c[i-1,j]的时候,最长子序列的最后一个字符存在于xi中,反之,存在于yj中

以序列 X:1235 和 Y:136 为例,根据公式1,可以得出以下表格(图1):

举例来说,当x为5,y为6时,序列1235和136的最长公共子序列长度为2;

当x为2,y为3时,序列12和13的最长公共子序列长度为1。

因为存在 c[i, j] = c[i - 1, j - 1] + 1 这样的运算,如果数组以0为开头,会出现下标为-1的情况,所以将表格改变为如下形式,x行和x列没有实际意义:

JavaScript代码以数组的形式生成以上表格的代码如下:

    var arr = [];    //array init
    for (var i = 0; i < str1.length + 1; i++) {
        arr[i] = [];        for (var j = 0; j < str2.length + 1; j++) {
            arr[i][j] = 0;            
        }
    }    
    for (var i = 1; i < str1.length + 1; i++) {        
            for (var j = 1; j < str2.length + 1; j++) {            
            if (str1[i - 1] == str2[j - 1]) {
                arr[i][j] =  arr[i - 1][j - 1] + 1;
            } else if (arr[i - 1][j] >= arr[i][j - 1]) {
                arr[i][j] = arr[i - 1][j];
            } else {
                arr[i][j] = arr[i][j - 1];
            }
        }
    }
接下来,根据这个表格去计算出最长公共子序列

首先以序列X的最后一个字符5和Y的最后一个字符6进行比较,

i为4,j为3,长度为c[4,3]=2,5≠6,又因为c[4,2]=c[3,3],再以c[4,2]开始进行比较

i为3,j为3,长度为c[4,2]=2,5≠3,又因为c[4,2]<c[3,2],再以c[3,2]开始进行比较

...

蓝色部分为比较时经过的路径,最后得出1,3最长公共子序列

JavaScript实现代码为:

    function _lcs(str1, str2, i, j, arr, result) {        
        if (i == 0 || j == 0) {            
           return;
        }         
        if (str1[i - 1] == str2[j - 1]) {
            _lcs(str1, str2, i - 1, j - 1, arr, result);
            result.push(str1[i - 1]);
        } else if (arr[i][j - 1] >= arr[i - 1][j]) {
            _lcs(str1, str2, i, j - 1, arr, result);
        } else {
            _lcs(str1, str2, i - 1, j, arr, result);
        }
    }

最后,完整的实验代码是:

    function lcs(str1, str2) {    
        var arr = [];    //array init
        for (var i = 0; i < str1.length + 1; i++) {
            arr[i] = [];        
            for (var j = 0; j < str2.length + 1; j++) {
                arr[i][j] = 0;            
            }
        }    
        for (var i = 1; i < str1.length + 1; i++) {        
            for (var j = 1; j < str2.length + 1; j++) {            
                if (str1[i - 1] == str2[j - 1]) {
                    arr[i][j] =  arr[i - 1][j - 1] + 1;
                } else if (arr[i - 1][j] >= arr[i][j - 1]) {
                    arr[i][j] = arr[i - 1][j];
                } else {
                    arr[i][j] = arr[i][j - 1];
                }
            }
        }    
        var result = [];
        _lcs(str1, str2, str1.length, str2.length, arr, result);    
        console.log(result)
    }
    
    function _lcs(str1, str2, i, j, arr, result) {    
        if (i == 0 || j == 0) {        
            return;
        }    
        if (str1[i - 1] == str2[j - 1]) {
            _lcs(str1, str2, i - 1, j - 1, arr, result);
            result.push(str1[i - 1]);
        } else if (arr[i][j - 1] >= arr[i - 1][j]) {
            _lcs(str1, str2, i, j - 1, arr, result);
        } else {
            _lcs(str1, str2, i - 1, j, arr, result);
        }
    }

        测试:

    var str1 = "asdfg29hj40kl";    var str2 = "qw29e4r0tyuiop";
    lcs(str1, str2);

输出:

    [ '2', '9', '4', '0' ]

以上。



个人博客原文链接:http://www.zcmyworld.com/singleArticle?articleId=334

© 著作权归作者所有

共有 人打赏支持
zcmyworld
粉丝 0
博文 1
码字总数 1101
作品 0
广州
使用动态规划 实现字符级Diff & Patch

文章开头先上demo,只需键入任意内容的两个字符串,页面上就能自动计算并呈现字符串之间的差分。 demo地址:string-diff-demo.herokuapp.com 源码地址:github.com/lqt0223/str… 动态规划 ...

lqt0223
02/13
0
0
手机腾讯网mt框架之mtwebapp示例解析。

手机腾讯网mt2.0框架发布有一段时间,但是经常有朋友问怎么用,其实项目里面是有一个基于jqmobi和ratchet的webapp示例的,这里我们就来分析一下。代码目录在:https://github.com/mtjs/mt/tr...

卢勇福
2014/11/12
0
10
用js来实现那些数据结构及算法—目录

  首先,有一点要声明,下面所有文章的所有内容的代码,都不是我一个人独立完成的,它们来自于一本叫做《学习JavaScript数据结构和算法》(第二版),人民邮电出版社出版的这本书。github代...

zaking
05/10
0
0
[JS进阶] 编写可维护性代码

1 可维护性代码的特点 可理解性:其他人可以接手代码并理解它的意图,无需原开发人员花太多时间解释! 直观性:代码中的东西一看就能明白,尽管其操作过程复杂。 可适应性:代码以一种数据上...

赵小宾
2015/04/01
0
0
常用算法和复杂度总结

一、常用算法和复杂度 算法 名称 复杂度 备注 快速排序 QuickSort(A,p,r) 最坏:O(n2) 平均:O(nlog n) 均衡划分:O(nlog n) 合并排序 MergeSort(A,p,r) O(nlog n) 选最大 FindMax O(n) 选最...

啊莱
2010/01/03
0
0

没有更多内容

加载失败,请刷新页面

加载更多

原型模式

1、原型模式-定义 用原型实例指定创建对象的种类,并且通过拷贝这些原型创建新的对象 克隆(浅度克隆->拷贝值类型或者引用,深度克隆->创建新的对象,开辟新的内存) 例如客户端知道抽象Pro...

阿元
今天
30
0
awk命令扩展使用操作

awk 中使用外部shell变量 示例1 [root@centos01 t1022]# A=888[root@centos01 t1022]# echo "" | awk -v GET_A=$A '{print GET_A}'888[root@centos01 t1022]# echo "aaaaaaaaaaaaa" | aw......

野雪球
今天
27
0
深入解析MySQL视图VIEW

Q:什么是视图?视图是干什么用的? A:视图(view)是一种虚拟存在的表,是一个逻辑表,本身并不包含数据。作为一个select语句保存在数据字典中的。   通过视图,可以展现基表的部分数据;...

IT--小哥
今天
34
0
虚拟机学习之二:垃圾收集器和内存分配策略

1.对象是否可回收 1.1引用计数算法 引用计数算法:给对象中添加一个引用计数器,每当有一个地方引用它时,计数器值就加1;当引用失效时,计数器值就减1;任何时候计数器值为0的对象就是不可能...

贾峰uk
今天
21
0
smart-doc功能使用介绍

smart-doc从8月份底开始开源发布到目前为止已经迭代了几个版本。在这里非常感谢那些敢于用smart-doc去做尝试并积极提出建议的社区用户。因此决定在本博客中重要说明下smart-doc的功能,包括使...

上官胡闹
昨天
33
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部