我正在尝试使用近似字符串匹配来确定我的数据存储中的哪些条目几乎是重复的。
在python中是否有以下方法的实现,或者我需要尝试自己动手?
谢谢 :)
...
蛮力方法是计算 T 的所有子串到 P 的编辑距离,然后选择具有最小距离的子串。但是,该算法的运行时间为 O(n3 m)
一个更好的解决方案[3][4],利用动态规划,使用问题的另一种表述:对于文本 T 中的每个位置 j 和模式 P 中的每个位置 i,计算第 i 个字符之间的最小编辑距离模式 Pi 和 T 的任何子串 Tj',j 在位置 j 处结束。
将其应用于许多字符串的最有效方法是什么?