欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

动态规划-编辑距离

程序员文章站 2022-07-15 16:30:35
...
using System;
using System.Collections.Generic;

namespace 编辑距离
{
    class Program
    {
        public static readonly string str1 = "FAMILY";
        public static readonly string str2 = "FRAME";
        public static int[,] map = new int[str1.Length + 1, str2.Length + 1];

        static void Main(string[] args)
        {
            EditDistence();

            Console.WriteLine("行表示str1,列表示str2:");
            DisplayMap();

            Console.WriteLine();
            DisplayRes();

            Console.ReadKey();
        }

        /// <summary>  
        /// 编辑距离算法  
        /// </summary>  
        static void EditDistence()
        {
            //初始化矩阵  第一行为0-str2的字符串长度 第一列为0-str1的字符串长度
            for (int i = 0; i < str1.Length + 1; i++)
                map[i, 0] = i;
            for (int j = 0; j < str2.Length + 1; j++)
                map[0, j] = j;

            for (int i = 1; i < str1.Length + 1; i++)
            {
                for (int j = 1; j < str2.Length + 1; j++)
                {
                    //若str1的第i个元素和str2的第j个元素相等 则map[i,j]等于 map中当前单元格左边或者上面或左上较小的值
                    //若str1的第i个元素和str2的第j个元素不相等 则map[i,j]等于 map中当前单元格左边或者上面或左上较小的值+1  
                    if (str1[i - 1] == str2[j - 1])
                        map[i, j] = Math.Min(Math.Min(map[i - 1, j], map[i, j - 1]), map[i - 1, j - 1]);
                    else
                        map[i, j] = Math.Min(Math.Min(map[i - 1, j], map[i, j - 1]), map[i - 1, j - 1]) + 1;
                }
            }
        }
        /// <summary>  
        /// 显示编辑距离算法运算后的MAP矩阵  
        /// </summary>  
        static void DisplayMap()
        {
            Console.Write("    ");
            for (int i = 0; i < str2.Length; i++)
            {
                Console.Write("  " + str2[i]);
            }
            Console.Write("\r\n");

            for (int i = 0; i < str1.Length + 1; i++)
            {
                if (i > 0 && i < str1.Length + 1)
                    Console.Write(str1[i - 1] + "  ");
                else
                    Console.Write("   ");
                for (int j = 0; j < str2.Length + 1; j++)
                {
                    Console.Write(map[i, j] + "  ");
                }
                Console.Write("\r\n");
            }
        }

        /// <summary>  
        /// 显示编辑距离长度和编辑过程  
        /// </summary>  
        static void DisplayRes()
        {
            Console.WriteLine("str1和str2的编辑距离是:" + map[str1.Length, str2.Length]);
            Console.WriteLine("str1和str2的编辑距离的过程是:");

            List<string> process = new List<string>(); //用于存放过程

            int i = str1.Length, j = str2.Length;//分别表示MAP矩阵行和列 
            //逆序推测过程
            while (i > 0 && j > 0)
            {
                //若str1的第i个元素和str2的第j个元素不相等 则map[i,j]的元素来源于 上面、左侧、左上的元素+1,若想等则取后者 同时定位到取值元素所在的位置
                //3钟取值情况分别代表 删除、插入、替换
                //若str1的第i个元素和str2的第j个元素相等 则取左上角元素继续执行循环
                if (str1[i - 1] != str2[j - 1])
                {
                    if (map[i, j] == (map[i - 1, j - 1] + 1))
                    {
                        process.Add(str1[i - 1] + " 替换为 " + str2[j - 1]);
                        i--;
                        j--;
                        continue;
                    }
                    if (map[i, j] == (map[i - 1, j] + 1))
                    {
                        process.Add("删除 " + str1[i - 1]);
                        i--;
                        continue;
                    }
                    if (map[i, j] == (map[i, j - 1] + 1))
                    {
                        process.Add("插入 " + str2[j - 1]);
                        j--;
                        continue;
                    }
                }
                else
                {
                    i--;
                    j--;
                }
            }

            for (int index = process.Count - 1; index > -1; index--)
                Console.WriteLine(process[index]);
        }
    }
}
动态规划-编辑距离