问题标签 [agrep]

编辑：在 R 的 32 位版本中发现此错误已在 R 版本 2.9.2 中修复。

这是@leoniedu 今天在推特上发给我的，我没有给他答案，所以我想我会把它贴在这里。

我已经阅读了 agrep() （模糊字符串匹配）的文档，看来我并不完全理解 max.distance 参数。这是一个例子：

这和我预期的完全一样。字符串之间有 18 个不同的字符，所以我希望这是匹配的阈值。这让我感到困惑：

为什么是 30 和 33 匹配，而不是 31 和 32？为了省点数，

我正在尝试建模一个语音识别器，该识别器必须从每个单词之间没有间隙的长音素流中分离出单词实例（音素串）。电话流的识别可能很差，有字母替换/插入/删除，所以我将不得不进行近似的字符串匹配。

但是，我希望匹配以语音为动机，例如“m”和“n”在语音上相似，因此与“m”和“k”相比，“m”对“n”的替换成本应该很小”。因此，如果我正在搜索 [mein] “main”，它将匹配字母序列 [meim] “maim” 与成本 0.1，而它将与字母序列 [meik] “make” 匹配，例如，成本 0.7。同样，插入或删除每个字母的成本也不同。我可以提供一个混淆矩阵，对于每个字母对 (x,y)，给出用 y 代替 x 的成本，其中 x 和 y 是任何字母或空字符串。

我知道有一些工具可以进行近似匹配，例如agrep，但据我所知，它们不会将混淆矩阵作为输入。也就是说，任何插入/替换/删除的成本 = 1。我的问题是，是否有任何可用的开源工具可以与混淆矩阵进行近似匹配，如果没有，我可以实现什么好的算法要做到这一点？

编辑：为了清楚起见，我试图从较长的字符串（例如 [aiammeinlimeiking...]）中分离出诸如 [mein] 之类的单词的近似实例。理想情况下，算法/工具应该报告成本为 0.0（精确匹配）的 [mein]、成本为 0.7（接近匹配）的 [meik] 等所有成本低于给定阈值的近似字符串匹配的实例。

我在 R 中使用 'agrep' 函数，它返回一个匹配向量。我想要一个类似于 agrep 的函数，它只返回最佳匹配，或者如果有平局则返回最佳匹配。目前，我在结果向量的每个元素上使用包“cba”中的“sdist()”函数来执行此操作，但这似乎非常多余。

/edit：这是我目前正在使用的功能。我想加快速度，因为两次计算距离似乎是多余的。

我在我的 PHP 项目中有这个问题要解决，其中一些关键字（从几百到几千，长度可能会有所不同）需要在大约 100-300 个字符长的字符串中进行搜索，有时长度较短，为 30-50 个字符。我可以预处理关键字以重用于搜索字符串的新实例。我是 PHP 的新手，在 PHP 库中没有找到这样做的方法。经过一番搜索，我在 Aho Corasick 算法中找到了一些不错的候选者，然后是 Sun Wu 和 Udi Manber 的改进，它似乎也被称为 agrep（或者是 agrep 的一部分）：http://webglimpse。网/pubs/TR94-17.pdf

还有 Rabin Karp、Suffix Trees 等，但它们看起来不太适合，因为第一个是固定长度的关键字，而后者看起来很通用，需要做很多工作。

谁能让我知道我自己在 php 中实现 Agrep/Sun Wu-Manber 是解决这个问题的好方法吗？还有别的反馈吗？

编辑：正如我在下面的评论中提到的，有数百个或更多不同的搜索关键字，所以正则表达式无济于事。所以这种反应是没有帮助的。

我正在尝试使用 agrep 并且可以进行近似匹配，但我需要知道匹配从哪里开始以及在哪里结束。是否有任何标志可以让我这样做？

伙计们，我正在使用 xargs 传递 agrep 的输入。我正在使用如下所示的 xargs

我的目标是将这个请求 ID 放在另一个文件“文件 B”中。由于这个文件是压缩的，我需要在执行 agrep 之前使用 zcat ......但是如果我这样做，我会得到不正确的结果.. 我在 agrep 中使用的最终“字符串”不正确.. 任何关于此的建议都将是高度有帮助。

尽管我将 max.distance 限制为零，但为什么 agrep 会找到匹配项？adist 确实正确地告诉我我需要两次插入...

使用 R，我正在尝试匹配按年份和城市构建的数据集中的人名。由于一些拼写错误，完全匹配是不可能的，所以我尝试使用 agrep() 来模糊匹配名称。

数据集的一个样本块的结构如下：

整洁的版本：

我想分别在每个城市查一下，几年后是否有候选人出现。例如在示例中，

保罗·塞扎尔·费雷拉·德·阿劳霍

保罗·塞萨尔·费雷拉·德·阿劳霍

出现两次（有拼写错误）。应为整个数据集中的每个候选人分配一个唯一的数字候选人 ID。数据集相当大（5500 个城市，大约 100K 条目），因此稍微有效的编码会有所帮助。关于如何实现这一点的任何建议？

编辑：这是我的尝试（在迄今为止的评论的帮助下）完成手头的任务非常缓慢（效率低下）。对此有何改进建议？

编辑2：现在以良好的速度运行。问题是在每一步都与许多因素进行比较（感谢蓝魔导师指出这一点）。将比较减少到仅一组（即一个城市）中的候选人在 5 秒内运行 80,000 行命令 - 这是我可以忍受的速度。

我有一个字符串：

和一个图案

我想知道有多少次pattern与string模糊匹配 (agrep) 匹配。

gregexpr将为正常匹配执行此操作 - 我只想知道garegexprR 中是否有对应的或模拟它的方法而不会太重。

（aregexec将只返回第一个匹配的索引，“eggs”，并跳过“ham”）。

经过大量的试验/错误和搜索功能后，我仍然对我认为简单的事情（一如既往，hrmpf）一无所知：

我在数据框中有一列，在该列中，每隔一段时间x$question就有一个表达式，我只是希望将其更改为.'A/V''A / B'

我在这里和那里尝试了一点，并认为这应该可行：

但我得到了错误：

或者我可以这样做

但在这里我得到了错误：

由于我完全没有想法，如果您有建议，或者可能是用另一个字符串替换字符串的更简单方法，我将非常感激。