莱文斯坦编辑距离算法(Levenshtein distance)

在做在线考试系统时 遇到了填空与简述题的系统评分问题，使用传统的包含(constant)已经无法满足需求，可以借助Levenshtein distance算法实现简单的匹配

下面是关于Levenshtein distance的简单理解

莱文斯坦编辑距离算法
举个生活中的例子 🌟
想象你正在手抄一份文件，但是抄的时候会犯一些小错误。编辑距离就是衡量你需要修改多少次才能让抄错的文本变回原版。

比如原句是："今天天气真好"
你抄成了："今天天气真好啊"

怎么修改？

在"好"后面添加一个"啊"（或者反过来，删除"啊"）

编辑距离 = 1（只需要1次操作）

三种基本操作 ✏️
莱文斯坦距离只允许三种最简单的修改：

插入一个字（多写了一个字）

原句：猫 → 修改后：猫咪（插入了"咪"）

删除一个字（少写了一个字）

原句：苹果 → 修改后：苹（删除了"果"）

替换一个字（写错了字）

原句：太阳 → 修改后：大阳（"太"替换成了"大"）

算法怎么"思考"的？ 🧠
算法像一个聪明的校对员，它会把两个文本一个字一个字地对比：

对比 "小猫" 和 "小狗"

text
步骤1：比较第一个字
"小" vs "小" → 相同！不需要操作 ✅

步骤2：比较第二个字  
"猫" vs "狗" → 不同！需要替换 ✏️
（把"猫"替换成"狗"）

总共操作：1次替换
编辑距离 = 1
复杂一点的例子 📝
原句： "我喜欢编程"
抄错的： "我喜爱写代码"

算法会这样计算：

"我" vs "我" → 相同 ✅

"喜" vs "喜" → 相同 ✅

"欢" vs "爱" → 不同！替换（欢→爱）✏️

"编" vs "写" → 不同！替换（编→写）✏️

"程" vs "代" → 不同！替换（程→代）✏️

（原句结束）vs "码" → 不同！删除"码"（或者说是原句需要插入"码"）✏️

编辑距离 = 4（3次替换 + 1次删除/插入）

算法如何选择最佳方案？ 🎯
有时候有多种修改方法，算法会选择操作次数最少的那一种。

比如：

原句："abcdef"

错句："azcdef"

两种改法：

替换法：把第二个字'b'替换成'z'（1次操作）

删除+插入法：删除'b'，再插入'z'（2次操作）

算法选择第1种，因为只需要1次操作！

在你们系统中的应用 🎯
用户答案： "Spark需要搭建集群"
正确答案： "Spark 需要搭建集群"（数据库里有空格）

算法处理：

先去掉所有空格（你们代码里的 removeAllFormatting）

用户答案 → "spark需要搭建集群"

正确答案 → "spark需要搭建集群"

现在两个字串完全一样！

编辑距离 = 0

相似度 = 100%

即使有拼写错误：

用户写："spakr集群"（拼错了）

正确答案："spark集群"

编辑距离 = 2（需要：插入'r'、替换'k'为'c'）
相似度 = 1 - 2/10 = 80% → 刚好达到阈值，判为正确！

为什么用80%作为阈值？ 📊
考虑实际情况：

70%太松："苹果手机" vs "华为手机"（50%相似）可能会误判

90%太严："Spark集群" vs "Spark 集群"（多一个空格）可能判错

80%刚刚好：允许一些小错误（打错1-2个字），但核心内容要对

就像老师批改简答题：

要点都答到了（相似度>80%）→ ✓ 正确

只答对一半（相似度50%）→ ✗ 错误

完全跑题（相似度<30%）→ ✗ 错误

简单总结 🎁
莱文斯坦距离 = 把A改成B的最少修改次数

你的系统是这样工作的：

去掉格式（空格、换行都删掉）→ 避免"形式错误"

计算编辑距离 → 看看差了多少字

算相似度 → (1 - 距离/总长度)

判断 → 大于80%就判对

就像一个体贴的助教：

不扣格式分（忽略空格换行）

允许小笔误（错1-2个字没关系）

但核心内容要对（80%以上正确）

这样既严格（保证学习效果）又人性化（不给学生太大压力）！