问题标签 [string-matching]

假设我有一个数据库，其中包含以下数据元素：

• PersonID（无意义的代理自动编号）
• 名
• 中间初始
• 姓
• 名称后缀
• 出生日期
• AlternateID（如 SSN、军事 ID 等）

我从各种格式中获得了大量的数据馈送，其中包含您能想到的这些信息的每一种合理变化。一些例子是：

• 全名，出生日期
• 全名，最后 4 个 SSN
• 第一，最后，出生日期

当这些数据进来时，我需要写一些东西来匹配它。我不需要或期望获得超过 80% 的匹配率。自动匹配后，我会将不确定的匹配显示在网页上，供某人手动匹配。

一些复杂性是：

1. 一些数据匹配比其他的更好，我想为这些匹配分配权重。例如，如果 SSN 完全匹配但名称因某人使用中间名而关闭，那么与名称完全匹配但 SSN 关闭的情况相比，我想为该匹配分配更高的置信度值。
2. 名称匹配有一些困难。John Doe Jr 与 John Doe II 相同，但与 John Doe Sr. 不同，如果我得到 John Doe 而没有其他信息，我需要确保系统不会选择一个，因为无法确定选谁。
3. 名字匹配真的很难。你有 Bob/Robert、John/Jon/Jonathon、Tom/Thomas 等。
4. 仅仅因为我有一个带有 FullName+DOB 的提要，并不意味着每条记录都填写了 DOB 字段。我不想因为不匹配的 DOB 杀死匹配的分数而错过一个链接。如果缺少某个字段，我想将其从可用于匹配的元素中排除。
5. 如果有人手动匹配，我希望他们的匹配影响所有未来的匹配。因此，如果我们再次获得相同的准确数据，下次没有理由不自动匹配它。

我已经看到 SSIS 具有模糊匹配，但我们目前不使用 SSIS，而且我发现它非常笨拙，几乎不可能进行版本控制，所以它不是我的首选工具。但如果这是最好的，请告诉我。否则，是否有任何（最好是免费的，最好是基于 .NET 或T-SQL的）工具/库/实用程序/技术用于解决此类问题？

我正在与大量数据进行字符串匹配。

编辑：我正在将一个大列表中包含的单词与一些本体文本文件进行匹配。我从本体中获取每个文件，并在每个文件行的第三个字符串与列表中的任何单词之间搜索匹配项。

我在监督我需要做的不是纯匹配（结果很差）这一事实时犯了一个错误，但我需要一些更松散的匹配函数，当字符串包含在另一个字符串中时它也会返回结果。

我用Radix Trie做到了这一点；它非常快并且效果很好，但现在我想我的工作没用，因为 trie 只返回完全匹配。：/

• 执行此操作的算法类型是字符串搜索算法吗？
• 有人可以推荐一些他有经验的Java实现吗？

该算法应该很快，但不是最优先考虑的，会兼顾速度和复杂性。

我非常感谢所有建议/示例/解释/链接！

谢谢！

我的表中有一个具有文本数据类型的字段。

以下两个sql查询的性能是否存在差异：

如果我们要实现这些查询的执行，我认为我们需要这样做：

我们必须匹配两个正则表达式（xyz* 和 *zyx）。

我们必须从头开始检查字符串字符。

对于第一个查询，我们必须读取前三个字符以查看是否匹配，但对于第二个查询，我们必须读取直到我们得到字符串的结尾以确定是否发生匹配。但是，如果我们将字符串的长度存储在某个地方，我们可以直接读取最后三个字符，从而获得与第一种情况类似的性能。

我的问题是 mysql 和 oracle 等商业数据库在执行查询的性能上是否有任何差异。

我需要在传入的不是很长的文本中搜索给定字符串的出现。字符串在整个会话中都是不变的，并且并不多（~10）。额外的简化是没有任何字符串包含在任何其他字符串中。

我目前正在使用与str1 | str2 | .... 这个任务的性能很重要，所以我想知道我是否可以改进它。并不是说我的编程比 boost 家伙更好，但也许专用实现比一般实现更有效。

由于字符串长时间保持不变，我可以预先构建一个数据结构，如状态转换表。

例如，如果字符串是abcx,bcy和cz, 并且到目前为止我已经阅读过abc，我应该处于组合状态，这意味着you're either 3 chars into string 1, 2 chars into string 2 or 1 char into string 1. 然后阅读xnext 将使我进入string 1 matched状态等，并且除了xyz将移动到初始状态之外的任何字符，我都不需要缩回b.

任何想法或参考都表示赞赏。

嘿，我遇到了一个问题，我的程序由于某种原因停止遍历 57802 记录中的文件，我无法弄清楚。我放了一个心跳部分，这样我就可以看到它在哪条线上并且它有所帮助，但现在我不知道为什么它会停在这里。我认为这是内存问题，但我只是在我的 6GB 内存计算机上运行它，它仍然停止。

有没有更好的方法来做我在下面做的任何事情？我的目标是读取文件（如果您需要我将其发送给您，我可以 15MB 文本日志）根据正则表达式查找匹配项并打印匹配行。还会有更多，但这就是我所得到的。我正在使用 python 2.6

任何想法都会有所帮助，也可以编写代码注释！我是一个 python 菜鸟，还在学习。

这是失败的第 57802 行：

这是一条匹配线：

仅前 5 行的示例数据：

上周我进行了一次实习面试，我收到了一个关于在大型数据库中搜索特定字符串的问题。面试的时候我完全不知道，虽然我只是回复了“多级哈希”，因为这是我知道的唯一一个时间效率最高的hin，经过一番谷歌搜索后，我认为他期望的答案是后缀树。现在，在我的搜索过程中，我找到了构建后缀树的算法，甚至还有关于如何构建后缀树的研究论文！！那么真的有可能实现字符串匹配算法的后缀树，尤其是在面试期间吗？

如果有人可以照亮它，那就太好了。

提前致谢

我正在开发一个购物比较网站，该项目处于非常先进的阶段。我们每天使用来自各种联盟网络的商家源为 5000 万种产品编制索引。我遇到的大部分问题都已经解决了，包括大部分性能瓶颈。

我的问题是什么：首先，我们将 apache solr 与 drupal 一起使用，但是，这个问题并不特定于 drupal 或 solr，如果您不了解它们，也没关系。

我们收到来自 2000 多个不同商家的产品信息，这些信息一团糟。他们没有特定的模式，每个商家都以他们想要的方式发送提要。我们已经解决了许多与此相关的问题，但仍然存在一个问题。规范化分面浏览功能的分类术语。

假设我的网站上有“Narrow by Brands”浏览方面。现在假设有 100 个商家提供 Microsoft 的产品。现在问题来了。一些商家在数据馈送的“品牌”列中放入“Microsoft”，另一些为“Microsoft, Inc.”，另一些为“Microsoft Corporation”，另一些为“Products from Microsoft”，等等……商家和最坏的情况之间没有特定的模式，有些个体商家太马虎了，在同一个数据源中对同一个品牌有不同的字符串。

我们不希望所有这些不同的品牌出现在导航中。对于手动将导入的品牌映射到“好”品牌表（“Microsoft Corporation”->“Microsoft”、“Products from Microsoft”->“Microsoft”等）的问题，我们有一个手动解决方案。我们在数据库中有大约 10,000 个品牌，这是可行的。问题是当它带有更大的东西时，比如“作者”。当我们将书籍导入系统时，有超过 800,000 位作者，我们遇到了同样的问题，而这不能通过手工映射来解决。问题是一样的：“Tom Mike Apostol”、“Tom M. Apostol”、“Apostol, Tom M.”等等……

有人知道以可接受的准确度（85%-95% 准确度）自动解决这个问题的好方法吗？

谢谢你的帮助！

这是到目前为止的完整代码：

在设置漫游和本地对象的部分中，它告诉我它永远不会与“game1”以外的任何东西匹配。

我做了'printf'来检查与本地和漫游对象匹配之前和之后......游戏打印在两个printf命令中都正确显示，但与game1以外的任何东西都不匹配......我不确定我犯错的地方。

如何使用python检查字典中是否存在EMP

为此目的有一个内置标签。

用户在文本框中输入一个字符，以输入的字符开头的字符串应该以列表的形式显示。从列表中选择的项目应填充在文本框中。

PS：示例和演示可用显示包含输入字符的字符串。但我只想显示以输入字符开头的那些字符串。