是否存在支持自定义homoglyphs列表的类Levenshtein字符串比较函数
回答
目前没有完全匹配你这个定制场景的开箱即用功能,现有公开的homoglyph比对工具基本都是针对印刷体场景预置的固定形似字符集(比如数字0和大写O、小写l和大写I这类),既不支持自定义传入多字符形似组,也没有“非形似字符差异直接判定为不匹配”的规则,不过你只需要对加权Levenshtein算法做少量改动就能实现需求,逻辑非常简单:
- 首先预处理传入的homoglyphs列表,给每一组形似字符/字符组分配唯一的等价类ID,生成映射表:同组内任意token互相替换的成本记为1,不在同一等价类的字符/字符组之间的替换、以及无对应匹配的插入删除操作,直接设置一个远大于合理最大编辑距离的惩罚值,比如你示例里提到的99即可。
- 改造标准Levenshtein的动态规划步进逻辑:不要固定按单字符逐位比对,要同时检查当前指针位置开始、长度1到你设定的最大形似组长度的子串,判断是否存在和对齐位置子串同属一个等价类的情况,如果有就按对应替换成本计分,指针按匹配到的子串长度向后跳转。
- 计算完总得分后做阈值判断:如果总得分超过你预设的可接受差异阈值(比如阈值设为3,只要出现一次非形似字符的替换,得分就会直接超过99),就返回-1/99/false代表不匹配,否则返回统计到的有效编辑距离。
按这个逻辑跑你给出的测试用例,结果完全符合预期:
compare("Mory", "Mary", homoglyphs):o和a属于同一形似组,总有效距离1,返回1compare("Mory", "Tory", homoglyphs):首字符M和T无共同形似组,直接加99惩罚分,总得分超阈值,返回-1compare("Morio", "Mario", homoglyphs):仅存在o和a的一次形似替换,总距离1,返回1compare("Morio", "Maria", homoglyphs):存在o和a、o和a两次形似替换,总距离2,返回2
如果你不想从零写动态规划部分,也可以直接用支持自定义编辑成本的Levenshtein工具库,单字符的形似匹配直接填好对应成本矩阵就能用,只需要额外补一段多字符形似组(比如rn和m、nn这类长度不一致的匹配)的判断逻辑即可,整体代码量非常小。
内容的提问来源于stack exchange,提问作者James McGrath
相关产品推荐
相关产品推荐

