标签: string-matching

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

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

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

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

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

其中一些复杂性是：

1. 有些数据匹配比其他数据匹配更好，我想为这些数据分配权重。例如，如果 SSN 完全匹配，但由于有人使用中间名而导致姓名被关闭，那么我想为该匹配分配比名称完全匹配但 SSN 关闭时更高的置信度值。
2. 名称匹配有一些困难。John Doe Jr. 与 John Doe II 相同，但与 John Doe Sr. 不同，如果我得到 John Doe 而没有其他信息，我需要确保系统不会选择一个，因为无法确定选择谁。
3. 名字匹配真的很难。你有鲍勃/罗伯特、约翰/乔恩/乔纳森、汤姆/托马斯等。
4. 仅仅因为我有一个包含 FullName+DOB 的提要，并不意味着每条记录都会填充 DOB 字段。我不想仅仅因为不匹配的 DOB 破坏了匹配的分数而错过链接。如果缺少某个字段，我想将其从可用于匹配的元素中排除。
5. 如果有人手动匹配，我希望他们的匹配影响所有未来的匹配。因此，如果我们再次获得相同的精确数据，下次没有理由不自动匹配它。

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

如何使用 RegEx 来测试以下模式：

1. 字符串长度必须为 4-10 个字符
2. 字符串不得有任何重复字符（两个字符不能相同且相邻）

我对此进行了研究，我认为我很接近：

^(?!(.)\1).{4,10}$

ab12这将正确找到和的匹配项12ab。它还正确地拒绝1111和aaaa。然而它错误地接受了12aa和ab11。

它似乎只查找字符串开头的重复字符。我尝试移动或删除^和$，但我需要它们来进行最大字符检查。我还尝试了几种变体(.)\1来查找重复字符，但没有成功。

任何帮助或提示将不胜感激。

PS - 如果有人知道答案，我实际上希望最多允许一对重复字符，但我认为这太难了，并决定禁止任何重复字符。

我正在尝试创建某种字典来附加我的结果并使用 jaro 距离函数获得最佳匹配。

这是我尝试匹配两个列表并在两个列表中获得最佳匹配名称的一部分。

例子：

import jellyfish
jellyfish.jaro_distance(u'jellyfish', u'sellyfish')

output: 
0.9259259259259259

我想做的是：

listA = ['grellofish','mellofush','jellyfihs','sellyfish','salmonfish']
listB = ['jellyfish','salmonfish']

#convert to unicode
listA = [unicode(i) for i in listA]
listB = [unicode(i) for i in listB]

for nickB in listB:
    for nickA in listA:
        results = jellyfish.jaro_distance(nickA, nickB)
        print nickB,nickA,results

output:
jellyfish grellofish 0.825925925926
jellyfish mellofush 0.777777777778
jellyfish jellyfihs 0.962962962963
jellyfish sellyfish 0.925925925926
jellyfish salmonfish 0.685185185185
salmonfish grellofish 0.733333333333
salmonfish mellofush 0.7
salmonfish jellyfihs 0.618518518519
salmonfish sellyfish 0.755555555556
salmonfish salmonfish 1.0 …

我有一组短信。让我们打电话给他们吧m1, m2, ....。消息的最大数量如下1,000,000。每条消息1024的长度都低于字符，并且全部为小写。我们还可以选择一个 n-gram s1。

我需要从所有这些消息中找到所有可能的子字符串的频率。例如，假设我们只有两条消息：

m1 = a cat in a cage
m2 = a bird in a cage

这两条消息中某些 n 元语法的频率：

'a' = 4
'in a cage' = 2
'a bird' = 1
'a cat' = 1
...

请注意，由于in = 2、 、in a = 2和a cage = 2是 和 的子集in a cage = 2，并且具有相同的频率，因此不应列出它们。只取最长的、频率最高的；遵循以下条件：最长的 sn-gram 最多由 8 个单词组成，总字符数低于 30。如果 n-gram 超过此限制，则可以将其分解为两个或多个 n-gram 并单独列出。 …

当将一个字符串与 data.table 中的两个以上其他字符串进行比较时，我试图创建一个作为逻辑值的变量，我需要忽略 NA。

D2 的样本数据：

structure(list(ID = c("a001", "a002", "a003"), var1 = c("char1", 
"char1", "char2"), var2 = c("char1", NA, "char2"), var3 = c("char1", 
"char1", "char1")), row.names = c(NA, -3L), class = c("data.table", 
"data.frame"), .internal.selfref = <pointer: 0x0000015eb1261ef0>)

尝试了以下建议的解决方案：

D2[, Match := apply(sapply(.SD, `==`, D2[, "var1"]), 1, any), .SDcols = 
c("var2", "var3")]

a003 的结果是 TRUE 而它应该是 FALSE 因为 var1 和 var3 不匹配：

structure(list(ID = c("a001", "a002", "a003"), var1 = c("char1", 
"char1", "char2"), var2 = c("char1", NA, "char2"), var3 = c("char1", …

我想做的事

我有许多唯一的 ID，例如id1, id2, etc.。它们出现在多个组中，每个组都是 1 到 100 个 id 之间的随机样本，例如

[1] "id872- id103- id746-"                             
[2] "id830- id582-"                                   
[3] "id663- id403- id675- id584- id866- id399- id28- id550-"

我想找到一个id所属的所有组，例如id1

groups.with.id[1] = grep("id1-", groups)

我的问题

数据量很大（80k id，1M 个组），在我的笔记本电脑上大约需要12 个小时。我认为这是我正在执行 80k 次（每个 id 一次）以及每次访问一个巨大对象（1M 组）的事实的组合。

有什么办法可以提高效率吗？

（我经常遇到 REg 中较大对象的问题，重复索引具有 >10k 行的数据帧会变得非常慢。也赞赏大型对象的有效索引的一般答案！）

示例代码

# make toy dataset
n.ids = 80000 # number of unique ids
n.groups = 100 # number of groupings

# make data
ids = …

我有一个 CPU 型号列表。现在，我认为最合适的方法是从列表中形成一个特里，如下所示：

Intel -- Core -- i -- 3
      |       |    |- 5
      |       |    |- 7
      |       |    -- 9
      |       |
      |       -- 2 Duo
      |
      |- Xeon -- ...
      |
      |...

现在，我想将输入字符串与此树进行匹配。这对于精确匹配很容易，但是如果我需要一个模糊的匹配，字符串序列可以有遗漏怎么办？对于“Intel i3”，“Core i3”和“i3”都匹配到树中的“Intel -> Core -> i -> 3”。

对于这个问题，尝试是正确的任务吗？我想过使用带通配符的特里搜索，但这里的通配符可以在序列中的任何位置。

我可以使用什么数据结构以最适用于这个问题的方式来表示列表？我使用什么算法进行搜索？

我需要搜索传入的非常长的文本片段以查找给定字符串的出现次数.字符串对于整个会话是不变的并且不是很多(~10).另外的简化是没有任何字符串包含在任何其他字符串中.

我目前正在使用boost正则表达式匹配str1 | str2 | ....这项任务的执行很重要,所以我想知道我是否可以改进它.并不是说我可以比推特人更好地编程,但也许专用实现比普通实现更有效.

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

例如,如果字符串是abcx,bcy而且cz,到目前为止abc,我已经阅读过,那么我应该处于合并状态you're either 3 chars into string 1, 2 chars into string 2 or 1 char into string 1.然后阅读x下一个会将我移动到string 1 matched状态等,除了xyz将移动到初始状态之外的任何其他字符,我将不需要缩回b.

任何想法或参考表示赞赏.

我正在尝试在Mongo中进行不区分大小写的搜索.基本上我想要不区分大小写的字符串匹配我正在使用正则表达式.这是我的代码

Query query = new Query( Criteria.where(propName).regex(value.toString(), "i"));

但是上面的剂量匹配我的整个字符串(有时用空格的字符串).它返回值,即使它是一个子字符串.

例如:假设我的集合有2个值"Bill"和"Bill status",即使我的搜索是"账单状态",它也会返回"账单".即使我正在搜索字符串的子字符串,它也会返回结果对于

我试过了 Query query = new Query( Criteria.where(propName).is(value.toString()));

但以上是区分大小写的.有人可以帮忙解决这个问题.

我正在尝试python的difflib模块,我遇到了SequenceMatcher.所以,我尝试了以下示例,但无法理解发生了什么.

>>> SequenceMatcher(None,"abc","a").ratio()
0.5

>>> SequenceMatcher(None,"aabc","a").ratio()
0.4

>>> SequenceMatcher(None,"aabc","aa").ratio()
0.6666666666666666

现在,根据比例:

将序列相似性的度量返回为[0,1]范围内的浮点数.T两个序列中元素的总数 在哪里M,匹配的数量是多少2.0*M / T.

所以,对于我的情况:

1. T=4和M=1因此比2*1/4 = 0.5
2. T=5和M=2因此比2*2/5 = 0.8
3. T=6和M=1因此比2*1/6.0 = 0.33

根据我的理解T = len(aabc) + len(a),M=2因为a两次进来aabc.

那么,我错在哪里,我错过了什么.

这是源代码SequenceMatcher.ratio()