标签: string-matching

我一直在使用C++中的Rabin-Karp字符串匹配函数,但我没有得到任何结果.我有一种感觉,我没有正确计算一些值,但我不知道哪一个.

原型

void rabinKarp(string sequence, string pattern, int d, int q);

功能实现

void rabinKarp(string sequence, string pattern, int d, int q)
{
    //d is the |?|
    //q is the prime number to use to lessen spurious hits
    int n = sequence.length(); //Length of the sequence
    int m = pattern.length(); //Length of the pattern
    double temp = static_cast<double> (m - 1.0);
    double temp2 = pow(static_cast<double> (d), temp); //Exponentiate d
    int h = (static_cast<int>(temp2)) % q; //High Order Position of an m-digit …

我有一个有点高级别的问题,所以我会尝试尽可能具体.

我正在进行大量研究,涉及将不同的数据集与引用同一实体(通常是公司或财务安全性)的标题信息相结合.此记录链接通常涉及标题信息,其中名称是唯一的公共主要标识符,但通常可用某些辅助信息(例如城市和州,操作日期,相对大小等).这些匹配通常是一对多,但可能是一对一甚至多对多.我通常手工完成这种匹配或者对清理过的子串进行非常基本的文本比较.我偶尔使用一种简单的匹配算法,比如Levenshtein距离测量,但我从来没有太多的东西,部分是因为我没有一个很好的正式应用方法.

我的猜测是,这是一个相当普遍的问题,并且必须有一些正式的流程可以用来做这类事情.我已经阅读了一些关于这个主题的学术论文,这些论文涉及给定方法的理论适用性,但我没有找到任何有用的资料来完成一个配方或至少一个实际的框架.

我的问题如下:

• 有没有人知道实现多维模糊记录匹配的良好来源,如书籍或网站,发表的文章或工作文件？

• 我更喜欢有实际例子和明确方法的东西.

• 该方法可以是迭代的,人工检查中间阶段的改进.

• (编辑)链接数据用于统计分析.因此,一点点的噪音是可以的,但是对于较少的"错误的不匹配"而言,更少的"不正确的匹配"是强烈的偏好.

• 如果他们在Python中是很棒的,但不是必需的.

最重要的是,如果重要的是,我不太关心计算效率.我没有动态实现它,我通常处理几千条记录.

在这行代码中,我希望它匹配"Review Notes\50optional\51"中的字符串,直到文本文件的末尾.我怎样才能做到这一点？

reviewNotes = contents.match(/Review Notes \50optional\51\n==================(.*?)/m)[1].strip

如何在Quora中实现前缀匹配的实时自动完成？

由于Solr和Sphinx不支持实时更新,因此进行了哪些更改以支持实时更新？

我正在寻找一种匹配2个列表的有效方法,一个包含完整信息,另一个包含通配符.我已经能够使用固定长度的通配符来做到这一点,但我现在正尝试使用可变长度的通配符.

从而:

match( ['A', 'B', '*', 'D'], ['A', 'B', 'C', 'C', 'C', 'D'] )

只要所有元素在两个列表中的顺序相同,它就会返回True.

我正在使用对象列表,但为了简单起见,使用了上面的字符串.

假设我有几十亿行文本和几百万个"关键字".任务是通过这些行,看看哪一行包含哪些关键字.换句话说,考虑到地图上 (K1 -> V1),并(K2 -> V2)创建地图(K2 -> K1),其中K1=lineID,V1=text,K2=keywordID和V2=keyword.还要注意:

• 所有文字/关键字均为英文
• 文本(V1)可能包含拼写错误.
• 大多数关键字(V2)是单个单词,但有些关键字可能包含多个英文单词(例如"干净毛巾")

到目前为止,我最初的想法是解决这个问题如下:

1) Chop up all my keywords into single words and 
   create a large set of single words (K3)
2) Construct a BK-Tree out of these chopped up keywords,
   using Levenshtein distance
3) For each line of data (V1), 
    3.1) Chop up the text (V1) into words
    3.2) For each said word,
        3.2.1) Retrieve words (K3) …

查询索引时,如何获取匹配标记列表,而不是整个字符串.说,我们必须查询包含值列表的字段,如 -

'Sunsilk shampoo conditioner'
'Dove Soap'
'Bread Bun Biscuit'
'Sunscreen cream'

当我查询时s,它应该只返回 -

'Sunsilk'
'shampoo'
'Soap'
'Sunscreen'

我在这里解决了这个程序.以前我认为复杂性是O(n!),其中n是单词中的字符.

但今天我觉得这是错的.它应该是(6)^(单词中的字符),其中6是立方体中的边.

使其更通用,假设cube有6个以上的边,复杂度应为O(cubefaces ^(输入字中的字符))

在这种情况下,有人可以解释一下时间复杂度吗？

我需要验证文本标签,但它包含动态部分,所以我尝试使用正则表达式,但它不起作用.

expect(aboutPage.userInterfaceText.getText()).toMatch('/- User Interface: v \d+\.\d+\.\d+/');

我总是得到下一个错误:

- Expected '- User Interface: v 4.4.63' to match '/- User Interface: v d+.d+.d+/'.

我想检查句子中是否存在特定字符串.我为此目的使用简单的代码

subStr = 'joker'
Sent = 'Hello World I am Joker'

if subStr.lower() in Sent.lower():
    print('found')

这是一种简单直接的方法,但当句子出现时它会失败

你好世界我是Jo ker

你好世界我是J oker

当我从PDF文件中解析句子时,会有一些不必要的空间来到这里.

解决此问题的一种简单方法是从句子中删除所有空格并查找子字符串匹配.我想知道其他人对此的想法,我应该坚持这种方法还是寻找其他一些选择.