字符串相似度工具接收两条文本字符串, String A 和 String B, 默认是 kitten 和 sitting, 在浏览器内算出两者之间的 Levenshtein 编辑距离. 每敲一个键, 结果实时重算: 三张统计卡片打印距离, 相似度百分比和操作数, 默认值是 3, 57.1% 和 7, 下方是一条进度条和一份编号的, 按类型上色的编辑脚本, 从第一个字符列到最后一个. 一切都是浏览器内对两条字符串的动态规划遍历: 不发送任何东西, 全程没有上传.
工具接收什么, 给出什么
输入是并排的两个单行文本框, 标签是 String A 和 String B, 等宽字体, 不需要其他任何东西. 默认是 A 里 kitten, B 里 sitting, 两个框的占位符也是同样两个词. 输出是一排三张卡片: 距离是纯整数, 相似度是带一位小数的百分比, 操作数是纯整数. 卡片下方, 进度条填到同样的百分比, 一个可滚动的列表打印完整编辑脚本, 每行从 1 开始编号, 每行按类型着色: 替换是黄色, 插入是蓝色, 删除是红色, 匹配是弱化的文字色. 没有按钮: 边敲边重算, 因为整个计算是对两个框值的一次带记忆读取.
距离是怎么算的
距离是经典 Levenshtein 距离, 用一张 (A 长度加 1) 乘 (B 长度加 1) 格的动态规划表搭出来. 每格取三个邻居加代价的最小值: 上方格加 1, 是删除; 左方格加 1, 是插入; 对角格加代价, 两字符相等时代价 0, 不等时 1, 是匹配或替换. 比较逐字符且区分大小写, 所以 K 和 k 是不同字符. 对默认的 kitten 对 sitting, 表是 7 乘 8, 56 格, 右下角读出 3: 把 k 替换成 s, 把 e 替换成 i, 再插入 g. book 对 back 是 2, 两个 o 的位置; flaw 对 lawn 是 2, 删掉 f, 末尾插入 n.
操作列表显示什么
列表是沿完成的表回溯一遍, 从右下角走回左上角. 每一步, 回溯优先取匹配 (当前两字符相等时), 然后替换, 然后插入, 然后删除, 收集到的步骤再反转打印, 从先到后. 这样走出来的是某个最小编辑脚本, 不是唯一的: 平局处不同的等代价选择会给出同长度的不同列表. 匹配也算在内, 所以操作数是脚本的长度, 不是距离. kitten 对 sitting 打印 7 个操作, 距离是 3, 四个匹配是 i, t, t 和 n; kitten 对自身打印 6 个操作, 全是匹配, 距离 0; flaw 对 lawn 打印 5, 两个编辑加三个匹配.
相似度百分比怎么读出来
百分比是较长长度减距离, 除以较长长度, 乘 100, 打印一位小数. 对默认的 7 减 3 除以 7, 读作 57.1%, 落在黄色带: 数字和条在 70 及以上变绿, 40 及以上是黄, 40 以下是红. 相同字符串读 100.0%, 距离 0. 单个大小写翻转, Kitten 对 kitten, 是 6 的长度上的距离 1, 读作 83.3%. 重音算一个字符差异: café 对 cafe 是距离 1, 读作 75.0%. 代理对算两个单元, 所以 a😀b 对 ab 里的笑脸是距离 2, 读作 50.0%.
什么时候没有结果
任一方去掉首尾空白后是空, 结果就是 null, 两个输入框下方什么都不渲染: 没有卡片, 没有条, 没有列表. 比较并不去掉内部或边缘的空白, 空白只用来判空, 所以尾随空格是一个编辑: key 带尾随空格对 key 是距离 1, 在长度 4 上读作 75.0%. 对空串, 距离就是另一方的整个长度, 所以 abc 对空一方算出 3 和 0.0%, 尽管框保持空时页面不显示它.
字符串能有多长
代码里没有长度上限. 代价是表的大小, (A 长度加 1) 乘 (B 长度加 1) 格, 所以工作量随两个长度的乘积增长: kitten 对 sitting 是 56 格, 两条 1,000 字符的字符串约 100 万格, 两条 10,000 字符的约 1 亿格, 页面会算但慢. 输入是单行框, 所以很长的字符串是敲或粘贴在一行里的.
它不是什么
工具是比较, 不转换文本: 比较前去掉多余空白和空行, 用空白字符清理; 把字符串首尾颠倒, 是文本反转工具的活; 只数字符不需要第二条字符串, 是字符计数器与分析器的活. 反转工具的详解, 看文本反转指南.