我有一组字符串及其坐标和矩形边界，位于两个相似的页面中。这些字符串在三种可能的方面有所不同。 (i) 字符串可以移动到页面上的新位置。 (ii) 字符串位于相同位置但已被修改。说( abc --> abd 或 ABC) (iii) (i) 和 (ii) 的组合。 (iv) 可能缺少字符串。
我尝试使用局部敏感哈希，但找不到合适的哈希函数。任何人都可以建议我一个好的哈希函数或其他算法来解决这个问题。提前致谢
最佳答案
因此，我们有一个源字符串列表 S 和一个大小最多为 |S| 的目标字符串 T 列表。我们希望找到一种方法将 T 中的每个字符串分配给 S 中的不同字符串，从而最大限度地减少不匹配字符的总数
(请注意，由于我们正在寻找一种将 T 与 S 匹配的方法，因此 S 中缺少字符串的情况隐式处理)
如果这是对你的问题的准确解释@programer8，我相信这是一个 assignment problem可以通过 Hungarian algorithm 来解决以立方时间为单位:wiki 文章中提到的“workers”是您的目标字符串，“tasks”是源字符串，源字符串和目标字符串之间不匹配的字符数是工作人员执行任务的成本.
唯一的问题是您的工作人员/目标字符串少于任务/源字符串，但您可以通过添加虚拟工作人员来解决这个问题。
关于algorithm - 匹配两个文档之间的差异，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/20464277/