当前位置：首页 > news >正文

做聚类热图的网站/企业网站官网

news 2025/7/1 0:30:34

做聚类热图的网站,企业网站官网,弹幕网站是什么技术做的,彩票网站有人做吗问题：给定一个长度为m和n的两个字符串，设有以下几种操作：替换（R），插入（I）和删除（D）且都是相同的操作。寻找到转换一个字符串插入到另一个需要修改的最小&…

问题：给定一个长度为m和n的两个字符串，设有以下几种操作：替换（R），插入（I）和删除（D）且都是相同的操作。寻找到转换一个字符串插入到另一个需要修改的最小（操作）数量。
关于编辑距离
编辑距离（Edit Distance），又称Levenshtein距离，是指两个字串之间，由一个转成另一个所需的最少编辑操作次数。许可的编辑操作包括将一个字符替换成另一个字符，插入一个字符，删除一个字符。例如：字符串abc和字符串adbe之间的最小编辑距离是2 因为adbe删除d然后将e替换为c经过这两部
找递归函数：
这个案例的子问题是什么呢？考虑寻找的他们的前缀子串的编辑距离，让表示他们为[1 ... i]和[1 ....j] , 1<i<m 和1 <j <n。显然，这是解决最终问题的子问题，记为E（i，j）。我们的目标是找到E（m，n）和最小的编辑距离。我们可以用三种方式: (i, -), (-, j) 和(i, j)右对齐两个前缀字符串。连字符符号（ – ）表示没有字符。看一个例子或许会更清楚：
假设给定的字符串是 SUNDAY 和 SATURDAY。如果 i= 2 , j = 4，即前缀字符串分别是SU和SATU（假定字符串索引从1开始）。这两个字串最右边的字符可以用三种不同的方式对齐：
1 (i, j): 对齐字符U和U。他们是相等的，没有修改的必要。我们仍然留下其中i = 1和j = 3，即问题E（1,3）
2 (i, -) : 对第一个字符串右对齐，第二字符串最右为空字符。我们需要一个删除（D）操作。我们还留下其中i = 1和j = 4的子问题 E（i-1，j）。
3 (-, j) : 对第二个字符串右对齐，第一个字符串最右为空字符。在这里，我们需要一个插入（I）操作。我们还留下了子问题 i= 2 和 j = 3，E（i，j-1）。
对于这三种操作，我们可以得到最少的操作为：
E(i, j) = min( [E(i-1, j) + D], [E(i, j-1) + I], [E(i-1, j-1) + R (如果 i,j 字符不一样)] )
到这里还没有做完。什么将是基本情况？
当两个字符串的大小为0，其操作距离为0。当其中一个字符串的长度是零，需要的操作距离就是另一个字符串的长度. 即：
E（0，0）= 0，E（i，0）= i，E（0，j）= j
为基本情况。这样就可以完成递归程序了。

动态规划解法：

我们先计算出上面递归表达式的时间复杂度：T(m, n) = T(m-1, n-1) + T(m, n-1) + T(m-1, n) + CT（M，N）的复杂性，可以通过连续替代方法或结二元齐次方程计算。结果是指数级的复杂度。这是显而易见的，从递归树可以看出这将是一次又一次地解决子问题。我们对重复子问题的结果打表存储，并在有需要时（自下而上）查找。动态规划的解法时间复杂度为 O(mn) 正是我们打表的时间.通常情况下，D，I和R操作的成本是不一样的。在这种情况下，该问题可以表示为一个有向无环图（DAG）与各边的权重，并且找到最短路径给出编辑距离。
a[m]表示第一个字符串，m表示该字符串字符的下标为0~m
b[n]表示第二个字符串，n表示该字符串字符的下标为0~n

d[i][j]表示子串a[i]和子串a[j]的最小编辑距离

那么边界条件：

d[i][0]=i, 0=<i<=m

d[0][j]=j, 0=<j<=n

状态转移方程：d[i][j]=min{d[i-1][j]+1,d[i][j-1]+1,d[i-1][j-1]+lastCharCommon}

lastCharCommon=1,如果a[i-1]等于b[j-1]

lastCharCommon=0,如果a[i-1]不等于b[j-1]

具体实例及实现代码如下所示：

/**
 * @Title: MinEditDistance.java
 * @Package dynamicprogramming
 * @Description: TODO
 * @author peidong
 * @date 2017-6-6 上午9:19:02 
 * @version V1.0
 */
package dynamicprogramming;

/**
 * @ClassName: MinEditDistance
 * @Description: 最小编辑距离
 * @date 2017-6-6 上午9:19:02 
 *
 */

public class MinEditDistance {/**
     *
     * @Title: minEditDistanceRecrusion
     * @Description: 递归求解最小编辑距离
     * @param x
     * @param y
     * @param m
     * @param n
     * @return
     * @return int
     * @throws
     */
    public static int minEditDistanceRecrusion(String x, String y, int m, int n){//边界条件
        if(m == 0 && n == 0)return 0;
        if(m == 0)return n;
        if(n == 0)return m;

        //递归
        int left = minEditDistanceRecrusion(x, y, m - 1, n) + 1;
        int right = minEditDistanceRecrusion(x, y, m, n - 1) + 1;
        int conner = minEditDistanceRecrusion(x, y, m - 1, n - 1) + (x.charAt(m-1)==y.charAt(n-1)?0:1);

        return min(left, right, conner);
    }/**
     *
     * @Title: min
     * @Description: 返回最小值
     * @param a
     * @param b
     * @param c
     * @return
     * @return int
     * @throws
     */
    public static int min(int a, int b, int c){return Math.min(Math.min(a,b),c);
    }/**
     *
     * @Title: getDistance
     * @Description: 求解亮哥字符串的编辑距离
     * @param str1
     * @param str2
     * @return
     * @return int
     * @throws
     */
    public static int getMinEditDistance(String str1, String str2){int distance = -1;
        //边界条件判断
        if(str1 == null || str2 == null ||str1.isEmpty() || str2.isEmpty()){return distance;
        }//若两个字符串相等，编辑距离为0
        if(str1.equals(str2)){return 0;
        }System.out.println("第一个字符串：" + str1);
        System.out.println("第二个字符串：" + str2);

        int len1 = str1.length();
        int len2 = str2.length();
        int len = Math.max(len1, len2);

        //初始化二维数组，存放转移矩阵
        int[][] arr = new int[len + 1][ len + 1];
        //边界条件初始化
        for(int i = 0; i <= len; i++){arr[i][0] = i;
        }for(int j = 0; j <= len; j++){arr[0][j] = j;
        }//状态转移方程
        for(int i = 1; i <= len1; i++){for(int j = 1; j <=len2; j++){arr[i][j] = min(arr[i-1][j] + 1, arr[i][j-1] + 1, arr[i-1][j-1] + (str1.charAt(i-1)==str2.charAt(j-1)?0:1));
            }}//打印状态转移矩阵
        System.out.println("状态转移矩阵为：");
        for(int i = 0; i <= len1; i++){for(int j = 0; j <= len2; j++){System.out.print(arr[i][j] + " ");
            }System.out.println();
        }return arr[len1][len2];
    }/**
     * @Title: main
     * @Description: TODO
     * @param args
     * @return void
     * @throws
     */
    public static void main(String[] args) {// TODO Auto-generated method stub

        String a=null;
        String b="abd";
        System.out.println("case 1：编辑距离为："+getMinEditDistance(a,b));


        a="Program";
        b="P-r-o-g-r-a-m";
        System.out.println("case 2：编辑距离为"+getMinEditDistance(a,b));
        System.out.println("case 2：编辑距离为："+minEditDistanceRecrusion(a,b,a.length(), b.length()));
        System.out.println();
        System.out.println();

        a="adbe";
        b="abc";
        System.out.println("case 3：编辑距离为"+getMinEditDistance(a,b));
        System.out.println("case 3：编辑距离为："+minEditDistanceRecrusion(a,b,a.length(), b.length()));
        System.out.println();
    }}