C 语言实现 Levenshtein 距离计算算法的程序

在本文中，我们将讨论使用 C 语言实现 Levenshtein 距离计算算法。用于计算两个字符串之间差异的矩阵称为 Levenshtein 距离或编辑距离。它被描述为将一个字符串转换为另一个字符串所需的单个字符修改（替换、插入或删除）的最小数量。需要在 C 语言中实现 Levenshtein 距离算法，并且通常使用动态规划和一个矩阵。

应用 Levenshtein 距离算法的基本思想如下：

1. 动态规划方法
   1. 该技术通常利用动态规划，构建一个矩阵来存储每个子问题的最小编辑距离。
   2. 要比较的两个字符串的长度决定了矩阵的大小。
   3. 矩阵中的每一列的值表示将子串修改到该点所需的最小编辑次数。
2. 初始矩阵配置
   1. 矩阵的第一行和第一列的初始化表示将空字符串转换为相应子字符串所需的修改次数。
   2. 每个单元格的值是根据相邻单元格的值填充的，这些值表示可以执行的多种编辑操作，例如插入、删除或替换。
3. 计算和矩阵遍历
   1. 在遍历矩阵的同时计算每个单元格处的最小编辑距离，同时考虑相邻单元格的值以及相关编辑操作的成本。
   2. 每个单元格表示可以执行的多种编辑操作，例如插入、删除或替换，并且是根据相邻单元格的值填充的。
4. 最终结果
   1. Levenshtein 距离，表示将一个字符串转换为另一个字符串所需的最小修改次数，位于矩阵的 右下角。

示例

让我们通过一个例子来说明 C 语言中的 Levenshtein 距离计算算法。

输出

The Levenshtein distance between 'kitten' and 'sitting' is: 3

说明

1. 函数声明和头文件
   • 代码中包含两个头文件：一个用于 输入/输出 操作，另一个用于 字符串操作。
   • 在代码的开头，声明了 min 函数。其目的是确定三个数字中的最小值。
2. min 函数
   • min 函数接收三个整数 (a, b, c)，并返回其中最小的一个。它稍后应用于 Levenshtein 距离的计算。
3. Levenshtein 距离函数的工作原理
   • Levenshtein 距离函数用于计算两个输入字符串 str_1 和 str_2 之间的 levenshteinDistance。
   • 首先，它使用 strlen 获取输入字符串的长度。
   • 输入字符串的每个子字符串之间的距离存储在名为 distance 的二维数组中。
   • 通过两个嵌套循环迭代子字符串来使用 Levenshtein 距离技术填充 distance 数组。
   • 如果其中一个字符串为空，则将距离设置为另一个字符串的长度，这表示所需的插入或删除次数。
   • 如果两个字符串在相应位置的字符匹配，则距离设置为前一个子字符串的值，并且不需要进行编辑。
   • 如果字母不匹配，则距离为 (1 + 插入、删除或替换操作的距离中的最小值)。
   • Levenshtein 距离（在两个输入字符串之间返回）由 distance 数组中的最后一个条目表示。
4. main 函数
   • 在 main 函数中，为 Levenshtein 距离计算提供了两个字符串作为输入：str_1 ("kitten") 和 str_2 ("sitting")。
   • 然后，调用 levenshteinDistance 函数并用这些字符串进行调用后，使用 Printf() 函数将结果输出到控制台。
5. 输出
   • 它显示了 "kitten" 和 "sitting" 之间的 Levenshtein 距离，即转换一个字符串为另一个字符串所需的最少单字符修改次数。