问题标签 [fuzzy-comparison]

我正在寻找一个可以进行简单模糊字符串比较的 Python 模块。具体来说，我想要字符串相似程度的百分比。我知道这可能是主观的，所以我希望找到一个可以进行位置比较以及最长相似字符串匹配等的库。

基本上，我希望找到足够简单的东西来产生一个百分比，同时仍然足够可配置，我可以指定要执行的比较类型。

我正在编写 iPhone 代码，它可以模糊地识别刷过的线是否是直线。我得到两个端点的方位，并将其与 0、90、180 和 270 度进行比较，公差为正负 10 度。现在我用一堆 if 块来做，这看起来超级笨重。

如何编写一个函数，在给定轴承0..360、公差百分比（比如 20% = (-10° 到 +10°)）和90 度等直角的情况下，返回轴承是否在公差范围内？

更新： 也许我太具体了。我认为一个很好的通用函数可以确定一个数字是否在另一个数字的百分比范围内，在许多领域都有用。

例如：数字swipeLength是否在maxSwipe的10%范围内？那会很有用。

你明白我在说什么吗？

我有两张表我想比较重复。这些表只是基本的公司信息字段，如名称、城市、州等。我能看到的唯一可能的常见字段是名称列，但名称并不完全准确。有没有办法可以使用 LIKE 语句在两者之间进行比较？我也愿意接受任何人可能提出的任何其他建议。

谢谢。

I'm wondering if there is some kind of way to do fuzzy string matching in PHP. Looking for a word in a long string, finding a potential match even if its mis-spelled; something that would find it if it was off by one character due to an OCR error.

I was thinking a regex generator might be able to do it. So given an input of "crazy" it would generate this regex:

It would then return all matches for that word or variations of that word.

How to build the generator: I would probably split the search string/word up into an array of characters and build the regex expression doing a foreach the newly created array replacing the key value (the position of the letter in the string) with ".+".

Is this a good way to do fuzzy text search or is there a better way? What about some kind of string comparison that gives me a score based on how close it is? I'm trying to see if some badly converted OCR text contains a word in short.

我有一张包含订单号、取消日期和原因的表格。原因字段是 varchar(255) 字段，它是由许多不同的销售代表编写的，很难按原因类别进行分组，我需要生成一份报告来对取消原因进行分类。用 TSQL 分析原因的最佳方法是什么？

销售代表输入的原因示例

顺便说一句，我有 SQL Server 2005。

我有一个包含 300 万个人记录的表，我想在其上使用 q-grams 执行模糊匹配（例如姓氏）。我已经创建了一个 2 克表链接到这个，但是在这个数据量（大约 5 分钟）上搜索性能不是很好。

我基本上有两个问题：（1）你能建议任何方法来提高性能以避免表扫描（即必须计算搜索字符串和 300 万个姓氏之间的常见 q-gram）（2）使用 q-gram，如果 A与 B 相似，C 与 B 相似，是否意味着 C 与 A 相似？

亲切的问候

彼得

我有一个非常大的 jpeg 图像数据库，大约 200 万张。我想对这些图像中的重复项进行模糊搜索。重复图像是两个图像，它们的许多（大约一半）像素具有相同的值，其余的 R/G/B 值相差约 +/- 3。图像与肉眼相同。这是您从重新压缩 jpeg 获得的那种不同。

我已经有一种万无一失的方法来检测两个图像是否相同：我将所有像素的增量亮度相加并与阈值进行比较。这种方法已被证明 100% 准确，但对 200 万张照片进行 1 张照片的速度非常慢（每张照片需要数小时）。

我想以一种可以比较哈希表中的指纹的方式对图像进行指纹识别。即使我可以可靠地将需要比较的图像数量减少到仅 100 个，我也可以很好地比较 1 到 100 个。什么是一个好的算法呢？

我正在对一个表的视图进行模糊查找，该表可以很好地返回与偶尔异常的相似之处，我似乎无法弄清楚是什么导致了问题。每隔一段时间，比较就会从查找视图中得出空值，即使这些值同时存在于视图和原始表中，并且我为“精确”匹配选择的列在查找视图中具有相同的值和源 SQL。

关于它为什么拉空值的任何想法？

替代文字 http://img689.imageshack.us/img689/4846/fuzzylkp.jpg

在我的工作中，我使用了近似字符串匹配算法（例如 Damerau-Levenshtein 距离）来使我的代码不易受到拼写错误的影响，取得了很好的效果。

现在我需要将字符串与简单的正则表达式进行匹配，例如TV Schedule for \d\d (Jan|Feb|Mar|...). 这意味着字符串TV Schedule for 10 Jan应该返回 0 而T Schedule for 10. Jan应该返回 2。

这可以通过在正则表达式中生成所有字符串（在本例中为 100x12）并找到最佳匹配来完成，但这并不实用。

你有什么想法如何有效地做到这一点？

我正在尝试使用 Python 2.6 和 PIL 计算两个图像的相似度（阅读：Levenshtein distance）。

我计划使用python-levenshtein库进行快速比较。

主要问题：

比较图像的好策略是什么？我的想法是这样的：

• 转换为 RGB（透明 -> 白色）（或者可能转换为单色？）
• 将较小的放大到较大的尺寸
• 将每个通道（= 唯一通道，如果转换为单色）转换为序列（项目值 = 像素的颜色值）
• 计算两个序列之间的 Levenshtein 距离

当然，这不会处理镜像图像、裁剪图像等情况。但是对于基本比较，这应该很有用。

是否有更好的策略记录在某处？

编辑： Aaron H 在速度问题上是对的。对于大于几百乘几百像素的图像，计算 Levelshtein 大约需要永远。但是，在我的示例中，缩小到 100x100 和 200x200 后的结果之间的差异小于 1%，因此将最大图像尺寸设置为 ~100px 左右可能是明智之举......

编辑：谢谢 PreludeAndFugue，这个问题就是我要找的。

顺便说一句，Levenshtein 距离似乎可以优化，但它给了我一些非常糟糕的结果，可能是因为背景中有很多冗余元素。必须看看其他一些算法。

EIDT：均方根偏差和峰值信噪比似乎是另外两个不太难实现的选项，而且看起来 CPU 开销也不是很大。但是，似乎我需要某种上下文分析来识别形状等。

无论如何，感谢所有链接，也感谢您指出 NumPy/SciPy 的方向。