把 javascirpt 敲进这个页面的搜索框排在第一的仍然是 JavaScript相似度 80.0%、编辑距离 2。切成 Damerau-Levenshtein 再算一遍同一条结果的编辑距离变成 1相似度 90.0%。同一份词库、同一个错词两套算法给出两个答案这个差别就是搜索框能不能容错的全部内容。在线案例与源码https://atomgit.com/deli007/demo_park/tree/main/codearts-fuzzy-search-lab一、为什么值得看打错字凭什么还能搜到搜索框容错这件事多数人只见过结果没见过过程。我把它做成一个单页网页内置 116 个开发者常用词输入任意查询词实时看到每个词的编辑距离、相似度和排名。页面还把 Levenshtein 的动态规划矩阵画成热力图每一步数值从哪来鼠标放上去就能看出来。二、先给结论8 组错词的实测距离下表是我在页面上逐条跑出来的左边是敲进去的错词右边是它命中的词。查询词命中词Levenshtein 距离Damerau 距离相似度javascirptJavaScript2180.0%kubernetseKubernetes2180.0%rediseRedis1183.3%dockrDocker1183.3%pyhtonPython2166.7%动态归划动态规划1175.0%二分查早二分查找1175.0%哈希表哈希表00100.0%8 组里有 3 组的两个距离对不上差别全在「相邻两个字符打反了」这一种错法上。Levenshtein 把换位算成两次替换Damerau-Levenshtein 算成一次。拼音首字母匹配是第三条路线它把汉字压成声母串再比距离。三、准备环境进入码道 Web浏览器打开码道 Web 版https://devcloud.cn-north-4.huaweicloud.com/chat?sourcedmzntgwsfsourceaddmzntgwwbwz登录后直接在对话窗口输入需求不用装软件。码道有三种使用方式WebUI 浏览器对话、TUI 终端命令行和桌面 IDE 插件。本文用 WebUI 版演示。四、需求原文把要验的东西先写死给码道的需求里关键的几条是这些。输入任意查询词实时对词库做模糊匹配按相似度从高到低排序每条给出分数和编辑距离。三种算法可切换也可同屏对比Levenshtein、Damerau-Levenshtein、拼音首字母匹配。把 Levenshtein 的动态规划矩阵画出来热力色显示每个格子的值悬停时高亮三个来源方向。每种算法显示本次查询耗时同一个查询连跑 3 次取平均。内置 8 组固定测试用例点一下跑断言逐条显示通过或不通过。空输入、纯空格、超过 32 个字符都要给中文提示并且不崩。第 5 条是有意写死的页面上有能点开的断言文章里的测试数字才有出处。五、页面上有哪几块顶部是查询框和词库容量下面一排四个页签。结果区一行一个词右边是百分数和编辑距离左边一条进度条表示相似度。再往下是动态规划矩阵热力图、三种算法的耗时条最后是自检面板。六、代码亮点一次换位两种答案Damerau-Levenshtein 比 Levenshtein 只多一行判断。当下一个字符和当前字符刚好互换位置时距离可以直接从两格之前的值加 1 得到。拼音首字母匹配走另一条路页面内置一张声母对照表先把汉字压成字母串再算距离。查询 dthg 时动态规划的声母串是 dtgh差一次换位拿到的相似度是 50.0%。相似度公式是 1 减去距离除以两个词的最大长度所以距离 2、长度 10 就是 80.0%。七、验证与踩坑第一步是页面自检 8/8 通过页面上 8 条断言逐条列了出来。第二步我拿 Python 把 8 组错词重算了一遍。用独立实现的 Levenshtein 和 Damerau 算距离再按同一个公式算相似度。8 组的距离和相似度与页面逐条一致没有一处对不上。第三步是三处真实边界我留着没改。第一处是矩阵和列表对不上。矩阵面板固定按 Levenshtein 画切到 Damerau 页签后列表说距离 1矩阵说明还写着距离 2。第二处是排序加成会压过正确答案。查 dthg 时Deno 的首字符同为 d白拿 0.3 分加成把只差一次换位的动态规划挤到了后面。第三处是结果列表永远给 Top 12。查三个问号这种全标点输入页面照样返回 Kubernetes标着 0.0%、距离 10既不报错也不说没找到。超长输入时矩阵区和耗时区都会清空自检面板却还留着上一次的结果这是第五张图里能看到的不彻底的一处。八、本地复现与亲手点三下页面是单文件把 index.html 下载下来双击就能打开没有依赖也没有后端。想用本地服务的方式打开在文件所在目录跑一行命令。python-mhttp.server8080# 浏览器打开 http://127.0.0.1:8080/index.html亲手点三下顺序建议这样。看关键数值输入 javascirpt第一条应该是 JavaScript、80.0%、距离 2。换算法点 Damerau-Levenshtein 页签同一条变成 90.0%、距离 1。看失败路径粘 33 个字符进去应该看到红色提示矩阵与耗时一起清空。九、用码道的体会这一轮里需求写清楚比写得漂亮重要。「内置 8 组固定测试用例点一下跑断言」这一句换来了交付时可以直接点开的 8 条断言。「三种算法可切换也可同屏对比」这一句让我第一轮就撞见了矩阵和列表数字不一致的问题。另一条体会是边界要自己主动喂进去。全标点输入、超长输入、声母换位这三处都是交付之后我自己试出来的。不主动喂极端输入页面看上去是完美的。十、直接下载试玩Demo Park 仓库https://atomgit.com/deli007/demo_park本案例目录https://atomgit.com/deli007/demo_park/tree/main/codearts-fuzzy-search-lab十一、下一步一个明显的改进是让矩阵跟着当前算法走Damerau 页签下把换位那一格也画出来。再往后可以给结果列表加一条相似度下限低于阈值就直接说没找到而不是硬给 Top 12。
把 javascirpt 敲进这个页面的搜索框排在第一的仍然是 JavaScript相似度 80.0%、编辑距离 2。切成 Damerau-Levenshtein 再算一遍同一条结果的编辑距离变成 1相似度 90.0%。同一份词库、同一个错词两套算法给出两个答案这个差别就是搜索框能不能容错的全部内容。在线案例与源码https://atomgit.com/deli007/demo_park/tree/main/codearts-fuzzy-search-lab一、为什么值得看打错字凭什么还能搜到搜索框容错这件事多数人只见过结果没见过过程。我把它做成一个单页网页内置 116 个开发者常用词输入任意查询词实时看到每个词的编辑距离、相似度和排名。页面还把 Levenshtein 的动态规划矩阵画成热力图每一步数值从哪来鼠标放上去就能看出来。二、先给结论8 组错词的实测距离下表是我在页面上逐条跑出来的左边是敲进去的错词右边是它命中的词。查询词命中词Levenshtein 距离Damerau 距离相似度javascirptJavaScript2180.0%kubernetseKubernetes2180.0%rediseRedis1183.3%dockrDocker1183.3%pyhtonPython2166.7%动态归划动态规划1175.0%二分查早二分查找1175.0%哈希表哈希表00100.0%8 组里有 3 组的两个距离对不上差别全在「相邻两个字符打反了」这一种错法上。Levenshtein 把换位算成两次替换Damerau-Levenshtein 算成一次。拼音首字母匹配是第三条路线它把汉字压成声母串再比距离。三、准备环境进入码道 Web浏览器打开码道 Web 版https://devcloud.cn-north-4.huaweicloud.com/chat?sourcedmzntgwsfsourceaddmzntgwwbwz登录后直接在对话窗口输入需求不用装软件。码道有三种使用方式WebUI 浏览器对话、TUI 终端命令行和桌面 IDE 插件。本文用 WebUI 版演示。四、需求原文把要验的东西先写死给码道的需求里关键的几条是这些。输入任意查询词实时对词库做模糊匹配按相似度从高到低排序每条给出分数和编辑距离。三种算法可切换也可同屏对比Levenshtein、Damerau-Levenshtein、拼音首字母匹配。把 Levenshtein 的动态规划矩阵画出来热力色显示每个格子的值悬停时高亮三个来源方向。每种算法显示本次查询耗时同一个查询连跑 3 次取平均。内置 8 组固定测试用例点一下跑断言逐条显示通过或不通过。空输入、纯空格、超过 32 个字符都要给中文提示并且不崩。第 5 条是有意写死的页面上有能点开的断言文章里的测试数字才有出处。五、页面上有哪几块顶部是查询框和词库容量下面一排四个页签。结果区一行一个词右边是百分数和编辑距离左边一条进度条表示相似度。再往下是动态规划矩阵热力图、三种算法的耗时条最后是自检面板。六、代码亮点一次换位两种答案Damerau-Levenshtein 比 Levenshtein 只多一行判断。当下一个字符和当前字符刚好互换位置时距离可以直接从两格之前的值加 1 得到。拼音首字母匹配走另一条路页面内置一张声母对照表先把汉字压成字母串再算距离。查询 dthg 时动态规划的声母串是 dtgh差一次换位拿到的相似度是 50.0%。相似度公式是 1 减去距离除以两个词的最大长度所以距离 2、长度 10 就是 80.0%。七、验证与踩坑第一步是页面自检 8/8 通过页面上 8 条断言逐条列了出来。第二步我拿 Python 把 8 组错词重算了一遍。用独立实现的 Levenshtein 和 Damerau 算距离再按同一个公式算相似度。8 组的距离和相似度与页面逐条一致没有一处对不上。第三步是三处真实边界我留着没改。第一处是矩阵和列表对不上。矩阵面板固定按 Levenshtein 画切到 Damerau 页签后列表说距离 1矩阵说明还写着距离 2。第二处是排序加成会压过正确答案。查 dthg 时Deno 的首字符同为 d白拿 0.3 分加成把只差一次换位的动态规划挤到了后面。第三处是结果列表永远给 Top 12。查三个问号这种全标点输入页面照样返回 Kubernetes标着 0.0%、距离 10既不报错也不说没找到。超长输入时矩阵区和耗时区都会清空自检面板却还留着上一次的结果这是第五张图里能看到的不彻底的一处。八、本地复现与亲手点三下页面是单文件把 index.html 下载下来双击就能打开没有依赖也没有后端。想用本地服务的方式打开在文件所在目录跑一行命令。python-mhttp.server8080# 浏览器打开 http://127.0.0.1:8080/index.html亲手点三下顺序建议这样。看关键数值输入 javascirpt第一条应该是 JavaScript、80.0%、距离 2。换算法点 Damerau-Levenshtein 页签同一条变成 90.0%、距离 1。看失败路径粘 33 个字符进去应该看到红色提示矩阵与耗时一起清空。九、用码道的体会这一轮里需求写清楚比写得漂亮重要。「内置 8 组固定测试用例点一下跑断言」这一句换来了交付时可以直接点开的 8 条断言。「三种算法可切换也可同屏对比」这一句让我第一轮就撞见了矩阵和列表数字不一致的问题。另一条体会是边界要自己主动喂进去。全标点输入、超长输入、声母换位这三处都是交付之后我自己试出来的。不主动喂极端输入页面看上去是完美的。十、直接下载试玩Demo Park 仓库https://atomgit.com/deli007/demo_park本案例目录https://atomgit.com/deli007/demo_park/tree/main/codearts-fuzzy-search-lab十一、下一步一个明显的改进是让矩阵跟着当前算法走Damerau 页签下把换位那一格也画出来。再往后可以给结果列表加一条相似度下限低于阈值就直接说没找到而不是硬给 Top 12。
