问题标签 [matching]

我以前从未构建过匹配算法，也不知道从哪里开始。所以这是我的基本设置以及我这样做的原因。如果我没有提出正确的问题，请随时纠正我。

我有一个人名和唯一标识符数据库。几个生成的标识符（内部生成的和一些第三方的）、姓氏、名字和出生日期是我将使用的主要标识符。

一年中我多次收到来自第三方的列表，需要导入并绑定到我数据库中的现有人员，但数据从来没有我的干净。ID 可能会改变，出生日期可能有错别字，名字可能有错别字，姓氏可能会改变，等等。

每次导入可能有 20,000 条记录，因此即使准确率为 99%，我仍需要手动输入 200 条记录并进行匹配。我认为在将传入人员与我的用户匹配时，我正在寻找更像 99.9% 的准确度。

那么，我该如何制定一个可以解决这个问题的算法呢？

PS 即使您没有确切的答案，但知道一些可参考的材料也会有所帮助。

PPS 一些例子类似于 m3rLinEz 写的：

我对 SQL 很陌生，并且对匹配表中两列的名称有疑问：

假设我想使用 soundex() 函数来匹配两个列。如果我使用这个查询：

如果该行中的两个名称匹配，则返回该行。现在我还想在 column1 和 column2 之间获取不在同一行中的名称匹配。有没有办法自动化一个过程，将 column1 中的每个名称与 column2 中的每个名称进行比较？

谢谢 ：）

ps：如果有人能指出一个n-gram/bi-gram匹配算法的方向，这种算法对于菜鸟来说很容易实现到mysql中，那也很好。

几个月前有一个关于“ 1:n 匹配问题”的好问题，似乎没有多时间算法。

我想添加约束以使用多项式算法找到 1:n 匹配问题的最大匹配。我想说：“对于顶点 A1，如果顶点尚未取自另一个 A 顶点，请选择 {B1,B2,B5} 或 {B2,B3}”，即我不会允许所有可能的组合。

如果我们为每个选择引入辅助顶点 H 并用树替换边 => 我们会遇到类似于普通二分匹配的问题，则可以表达这一点。A 或 B 的每个顶点在匹配中只能有一条边。H 中的顶点到或来自顶点的边要么全部在匹配中，要么在匹配中都不存在。想象一下下面的三部图：

现在定义 h_ij="tree rooted that contains H_ij" 来轻松表达匹配：

• 然后在示例中 M={h12,h22} 将是一个“最大”匹配，尽管并非涉及 B 的所有顶点
• 集合 {h12,h23} 不匹配，因为 B3 将被选择两次。

那么这个问题可以在多项式时间内解决吗？如果是，是否有加权 (w(h_ij)) 变体的多时间解决方案？如果不是，您能否为像我这样的“简单人”争论甚至证明它，或者建议其他约束来解决 1:n 匹配问题？

例如，该图是否可以转换为通用图，然后可以通过通用图的加权匹配来解决？或者分支甚至匹配的森林在这里有帮助吗？

PS：不是作业;-)

我最近从 FreeBSD 4.x 服务器迁移到 FreeBSD 8.0 服务器。我现在正在使用 expect-5.43.0_3。不记得旧版本的expect是什么，也无法快速查看，因为旧系统上的硬盘在完成迁移后几分钟内就崩溃了！（哇！）

无论如何，我有一个期望脚本，它创建一个压缩的 tar 文件并每晚通过 FTP 传输它。该脚本已成功运行了 YEARS。突然，自从迁移/升级以来，它就无法正常工作，我盯着它看了好几天，却无法修复它。我想确保每个 FTP 命令都已成功完成，然后再继续执行下一个命令，因为接下来的步骤包括删除远程服务器上选定的旧版本文件，如果传输是，我不想执行删除操作不能正常工作。

所以 - 这部分脚本仍然有效：

...

...这是与上述执行相对应的对话流：

（注意 - 哈希标记允许我使用低超时值并快速检测脚本是否挂起）

到目前为止，一切都很好！在过去的 6 年里，一切仍然正常工作，但下一行失败并显示“ftp unexpected prompt 2”，即使它正在寻找的字符串“\n226”在对话流中很明显

请注意，非常清楚的是，在“ftp>”之前的对话流中有一个“\n226”，但我一直得到“ftp unexpected prompt 2”。我尝试将其更改为“转移”或“完成”，但它仍然具有相同的效果。现在，我在没有检查是否成功完成的情况下运行脚本，但很明显，我对此并不满意，这是一个等待发生的意外，因为以下步骤删除了选定的旧文件，我不想这样做如果这些文件没有成功传输，我目前没有哪个测试。

我认为输入流缓冲/处理发生了一些变化，我需要改变它，以便它在“看到”“ftp>”字符串之前“看到”“\n226”或“传输”或“完成” ， 但为什么？而且，就此而言，如何？:)

作为 Ocaml 的初学者，我有这个当前的工作代码：

现在我想为不存在的输入文件添加错误处理，我写了这个：

并得到一条错误消息：此模式匹配 'a 选项类型的值，但这里用于匹配最后一行的 exn 类型的值。如果我用None代替_，我会收到关于不完整匹配的错误。

我读到exn是异常类型。我确定我不明白这里到底发生了什么，所以请指出正确的方向。谢谢！

我有以下模型和实例：

现在我希望能够搜索对象，但使用 ascii 字符而不是 unicode，如下所示：

在 Django 中有没有办法进行这种近似字符串匹配，使用 ascii 替代数据库中的 unicode 字符？

这是一个相关的问题，但针对 Apple 的核心数据。

这个简单的正则表达式匹配在每个浏览器上返回一个字符串而不是一个对象，但最新的 firefox...

据我所知，匹配函数应该返回一个对象（数组）。有没有人遇到过这个问题？

我不明白为什么这段代码有效：

我知道这是一个零宽度匹配，它没有将匹配的字符串放在 $& 中，但为什么将它放在 $1 中？

谢谢你！

I'm working on a project to recognize simple audio patterns. I have two data sets, each made up of between 4 and 32 note/duration pairs. One set is predefined, the other is from an incoming data stream. The length of the two strongly correlated data sets is often different, but roughly the same "shape". My goal is to come up with some sort of ranking as to how well the two data sets correlate/match.

I have converted the incoming frequencies to pitch and shifted the incoming data stream's pitch so that it's average pitch matches that of the predefined data set. I also stretch/compress the incoming data set's durations to match the overall duration of the predefined set. Here are two graphical examples of data that should be ranked as strongly correlated:

http://s2.postimage.org/FVeG0-ee3c23ecc094a55b15e538c3a0d83dd5.gif

(Sorry, as a new user I couldn't directly post images)

I'm doing this on a 8-bit microcontroller so resources are minimal. Speed is less an issue, a second or two of processing isn't a deal breaker.

It wouldn't surprise me if there is an obvious solution, I've just been staring at the problem too long. Any ideas?

Thanks in advance...

我有一个字符串列表，其中包含大约 700 万个项目，大小为 152MB 的文本文件。我想知道实现接受单个字符串并返回它是否在该字符串列表中的函数的最佳方法是什么。