Yargs里的Levenshtein距离算法

“Yargs 是一个 Node.js 库，专为那些想要解析命令行选项字符串的开发者设计。”

yargs介绍

yargs 是一个用于解析命令行参数的流行库，周下载量达到了惊人的93154k，它能帮助开发者轻松地定义 CLI（命令行接口），并提供参数处理、命令组织、help文本自动生成等功能。

它通过简洁的 API 使复杂的命令行应用开发变得更加直观。

官网地址：https://yargs.js.org/

yargs 提供了丰富的功能支持，如：

• 自动生成帮助和版本信息
• 参数类型验证
• 别名处理
• 子命令支持

使用案例

自动生成帮助和版本信息

假设你正在编写一个命令行工具来处理文件，以下是如何使用 yargs 来解析命令行参数的示例：

背景：你需要创建一个工具，接受 --input 和 --output 选项，并支持一个 --verbose 标志。

const yargs = require('yargs');

const argv = yargs
  .option('input', {
    alias: 'i',
    description: 'Input file path',
    type: 'string',
    demandOption: true
  })
  .option('output', {
    alias: 'o',
    description: 'Output file path',
    type: 'string',
    demandOption: true
  })
  .option('verbose', {
    description: 'Run with verbose logging',
    type: 'boolean',
    default: false
  })
  .help()
  .alias('help', 'h')
  .argv;

console.log(argv);

输出如下：

可以看出来，通过这个工具可以很方便地获得一个cmd的帮助提示。

参数类型验证

yargs 允许你为命令行参数设置类型，并进行验证。这可以确保用户输入符合预期的格式，从而提高程序的健壮性。

示例：假设我们需要一个工具来处理文件，--port 选项应为一个数字，--debug 选项应为布尔值。

const yargs = require('yargs');

const argv = yargs
  .option('port', {
    alias: 'p',
    description: 'Port number for the server',
    type: 'number',
    demandOption: true,
    coerce: (arg) => {
      if (isNaN(arg)) throw new Error('Port must be a number');
      return arg;
    }
  })
  .option('debug', {
    description: 'Enable debugging',
    type: 'boolean',
    default: false
  })
  .help()
  .alias('help', 'h')
  .argv;

console.log(argv);

解析：

• type: 'number' 指定 --port 选项必须是一个数字。
• coerce 函数进一步验证输入，确保它是有效的数字。如果用户输入的不是数字，会抛出错误。

别名处理

yargs 支持为参数设置别名，使得命令行选项更具灵活性和可读性。

我们可以为 --input 和 --output 选项设置别名。

const yargs = require('yargs');

const argv = yargs
  .option('input', {
    alias: 'i',
    description: 'Input file path',
    type: 'string',
    demandOption: true
  })
  .option('output', {
    alias: 'o',
    description: 'Output file path',
    type: 'string',
    demandOption: true
  })
  .help()
  .alias('help', 'h')
  .argv;

console.log(argv);

解析：

• alias: 'i' 为 --input 设置了 -i 的别名。
• alias: 'o' 为 --output 设置了 -o 的别名。

这样，用户可以使用 -i 或 -o 代替 --input 和 --output，提高了命令行的便捷性。

子命令支持

yargs 支持定义多个子命令，每个子命令可以有自己独立的选项和参数。这使得创建复杂的命令行工具变得更加简单。

创建一个命令行工具，支持两个子命令 add 和 remove，每个子命令有不同的选项。

const yargs = require('yargs');

yargs
  .command('add [name]', 'Add a new item', (yargs) => {
    yargs
      .positional('name', {
        describe: 'Name of the item to add',
        type: 'string'
      })
      .option('quantity', {
        alias: 'q',
        description: 'Quantity of the item',
        type: 'number',
        demandOption: true
      });
  })
  .command('remove [name]', 'Remove an item', (yargs) => {
    yargs
      .positional('name', {
        describe: 'Name of the item to remove',
        type: 'string'
      });
  })
  .help()
  .alias('help', 'h')
  .argv;

解析：

• add [name] 和 remove [name] 是两个子命令。
• add 命令要求 name 参数，并且支持 --quantity 选项。
• remove 命令要求 name 参数。

这样，用户可以使用以下命令：

• node script.js add item --quantity 10
• node script.js remove item

Yargs里的Levenshtein距离算法

命令修正是指用户输入错误的命令时，会给出有效的提示。例如，用户输入了 lis，但正确的命令是 list。启用 recommendCommands 后，yargs 会提示类似的命令并推荐使用 list。

const yargs = require('yargs');

// 定义命令
yargs
  .command('list', 'List all items', () => {}, (argv) => {
    console.log('Listing items');
  })
  .command('add', 'Add a new item', () => {}, (argv) => {
    console.log('Adding a new item');
  })
  .recommendCommands() // 启用推荐功能
  .help()
  .argv;

这是如何实现的呢？其内部使用了一个叫做Levenshtein的算法，一种计算两个字符串之间编辑距离（也称为 Levenshtein 距离）的动态规划算法。编辑距离表示从一个字符串转换到另一个字符串所需的最小操作次数。

这些操作包括以下三种：

• 插入（Insertion）：在一个字符串中插入一个字符。
• 删除（Deletion）：删除一个字符串中的字符。
• 替换（Substitution）：将一个字符替换为另一个字符。

Levenshtein算法是由苏联科学家 Vladimir Levenshtein 于 1965年 提出的。他是一名数学家和信息学家，他的研究领域包括信息论、纠错编码和组合数学。编辑距离的概念最初源于信息论中的编码纠错，Levenshtein 的目标是找到一种方法来衡量两个字符串之间的差异，以此用于分析不同数据序列的相似性和错误修复策略。

在提出 Levenshtein 算法的年代，计算机科学刚刚起步，信息理论和编码理论等领域的研究对数据传输中的错误检测和纠正有着重要影响。Levenshtein 距离的提出为编码理论提供了新的工具，可以量化两个符号序列（如文本或DNA序列）之间的差异。

该算法当前常用来处理如下场景：

• 拼写检查：在文本编辑器和搜索引擎中，Levenshtein 距离被用来纠正用户的拼写错误。
• 自然语言处理：用于衡量文本之间的相似度，例如判断两个句子或单词的差异程度。
• 生物信息学：Levenshtein距离也被应用于比较DNA序列或蛋白质序列，查看它们在进化或功能上的相似性。

export function levenshtein(a: string, b: string) {
  // 如果 a 是空字符串，则返回 b 的长度，意味着需要对 b 进行 b.length 次的插入操作才能变为 a。
  if (a.length === 0) return b.length;
  // 如果 b 是空字符串，同理，返回 a.length，即删除 a.length 次。
  if (b.length === 0) return a.length;

  // 创建一个矩阵，用来存储两个字符串在不同位置的编辑距离。矩阵的每个单元格 matrix[i][j] 代表 a 的前 j 个字符与 b 的前 i 个字符的编辑距离。
  const matrix = [];

  // 初始化矩阵的第一列，每个值都等于当前行号 i。这是因为将一个空字符串变为另一个字符串的操作次数等于该字符串的长度，即多次插入。
  let i;
  for (i = 0; i <= b.length; i++) {
    matrix[i] = [i];
  }

  // 初始化矩阵的第一行，每个值都等于当前列号 j。将 a 变为空字符串需要 a.length 次删除操作。
  let j;
  for (j = 0; j <= a.length; j++) {
    matrix[0][j] = j;
  }

  // 从第二行和第二列开始，遍历每个矩阵单元，计算两个字符串在该位置的最小编辑距离。
  for (i = 1; i <= b.length; i++) {
    for (j = 1; j <= a.length; j++) {
      // 如果 a 和 b 当前的字符相等，则它们之间没有操作，编辑距离等于上一个单元格 matrix[i - 1][j - 1] 的值。
      if (b.charAt(i - 1) === a.charAt(j - 1)) {
        matrix[i][j] = matrix[i - 1][j - 1];
      } else {
        // 如果当前字符不相等，检查是否可以通过字符调换（transposition）来匹配。调换的前提是当前字符和前一个字符可以相互交换，即 b 的第 i-1 个字符等于 a 的第 j-2 个字符，b 的第 i-2 个字符等于 a 的第 j-1 个字符。如果可以调换，编辑距离加 1。
        if (
          i > 1 &&
          j > 1 &&
          b.charAt(i - 2) === a.charAt(j - 1) &&
          b.charAt(i - 1) === a.charAt(j - 2)
        ) {
          matrix[i][j] = matrix[i - 2][j - 2] + 1; // transposition
        } else {
          // 如果不能调换，计算三个可能的编辑操作中的最小值：
          // 替换（substitution）：将 a 的第 j 个字符替换为 b 的第 i 个字符。
          // 插入（insertion）：在 a 中插入一个字符，使其匹配 b 的当前字符。
          // 删除（deletion）：从 a 中删除一个字符。
          matrix[i][j] = Math.min(
            matrix[i - 1][j - 1] + 1, // substitution
            Math.min(
              matrix[i][j - 1] + 1, // insertion
              matrix[i - 1][j] + 1
            )
          ); // deletion
        }
      }
    }
  }
  // 最终返回矩阵右下角的值，即两个字符串 a 和 b 的 Levenshtein 距离
  return matrix[b.length][a.length];
}

这个算法通过构建一个矩阵并逐步填充其值，找到了最小的编辑操作次数来将一个字符串转换为另一个。它有效地处理了字符串比较问题，广泛用于拼写检查、DNA 序列比对等领域。

• 时间复杂度：Levenshtein 算法的时间复杂度为 O(m * n)，其中 m 和 n 分别是字符串 a 和 b 的长度。因为它需要遍历每个字符，并计算所有可能的操作。
• 空间复杂度：由于使用了一个 m x n 的矩阵，空间复杂度也是 O(m * n)。

在执行recommendCommands的时候，实际的操作如下：

 self.recommendCommands = function recommendCommands(cmd, potentialCommands) {
     // 设置了一个阈值为 3，表示如果某个候选命令与输入命令的编辑距离超过 3，则认为它与输入命令差异太大，不再考虑。
    const threshold = 3;
    // 将所有候选命令按长度从大到小排序，增加命令建议的精确性
    potentialCommands = potentialCommands.sort((a, b) => b.length - a.length);
    // recommended 用于存储找到的最佳推荐命令，bestDistance 用于记录当前找到的最小编辑距离，初始为 Infinity。
    let recommended = null;
    let bestDistance = Infinity;
    // 遍历所有 potentialCommands 并计算编辑距离
    for (
      let i = 0, candidate;
      (candidate = potentialCommands[i]) !== undefined;
      i++
    ) {
      const d = distance(cmd, candidate);
      // 如果编辑距离 d 小于或等于 threshold 且比当前最小距离 bestDistance 小，则更新 bestDistance 和 recommended。
      if (d <= threshold && d < bestDistance) {
        bestDistance = d;
        recommended = candidate;
      }
    }
    if (recommended) usage.fail(__('Did you mean %s?', recommended));
  };

总结

1965年提出的算法，历经数十年仍在现代技术中发挥着重要作用，真是太厉害了。看完你还会觉得算法没用么？算法通常具备简单性与普适性，这才是它的持久价值来源。

不说了，好好阅读，好好思考，才能好好写代码。