标签: string-matching

我想给字符串和通配符匹配的可能性*.

例

$mystring = 'dir/folder1/file';
$pattern = 'dir/*/file';

stringMatchWithWildcard($mystring,$pattern);  //> Returns true

例2:

$mystring = 'string bl#abla;y';
$pattern = 'string*y'; 

stringMatchWithWildcard($mystring,$pattern);  //> Returns true

我想的是:

function stringMatch($source,$pattern) {
    $pattern = preg_quote($pattern,'/');        
    $pattern = str_replace( '\*' , '.*?', $pattern);   //> This is the important replace
    return (bool)preg_match( '/^' . $pattern . '$/i' , $source );
}

基本上,更换*到.*?(考虑*nix环境*相匹配empty的字符串) ©vbence

任何改进/暗示？

//添加return (bool)因为preg_match返回int

我正在寻找类似于Redis KEYS命令所接受的匹配的glob样式模式.引用:

• h？llo匹配hello,hallo和hxllo
• h*llo匹配hllo和heeeello
• h [ae] llo匹配hello和hallo,但不匹配hillo

但是我没有匹配文本字符串,而是将模式与另一个模式匹配,所有运算符都在两端都有意义.

例如,这些模式应该在同一行中相互匹配:

prefix*       prefix:extended*
*suffix       *:extended:suffix
left*right    left*middle*right
a*b*c         a*b*d*b*c
hello*        *ok
pre[ab]fix*   pre[bc]fix*

这些不应该匹配:

prefix*       wrong:prefix:*
*suffix       *suffix:wrong
left*right    right*middle*left
pre[ab]fix*   pre[xy]fix*
?*b*?         bcb

所以我想知道......

• 如果可以这样做(实施验证算法),如果有的话？
• 如果不可能,正则表达式的哪个子集是可能的？(即禁止*通配符？)
• 如果它确实可能,什么是有效的算法？
• 需要什么时间复杂度？

编辑:在RegEx子集上找到这个其他问题,但这与单词hello*和*ok匹配不是彼此的子集/超集的单词不完全相同,但它们相交.

所以我想从数学角度来看,这可能是用来表达的; 是否有可能确定地检查一个模式匹配的一组单词与另一个模式匹配的一组单词相交,导致非空集？

编辑:朋友@neizod绘制了这个消除表,它可以整齐地显示可能是潜在/部分解决方案:消除规则

编辑:将为那些也可以提供工作代码(使用任何语言)和测试用例证明它的人增加额外的奖励.

编辑:添加？*b*？@DanielGimenez在评论中发现的测试用例.

使用OCR工具我从截图中提取文本(每个约1-5个句子).但是,在手动验证提取的文本时,我注意到有时会出现几个错误.

鉴于文本"你好!我真的喜欢Spark❤️!",我注意到:

1)像"I","!"和"l"这样的字母被"|"代替.

2)Emojis未被正确提取并被其他字符替换或被遗漏.

3)不时删除空格.

结果,我可能会得到一个像这样的字符串:"你好7l |真实|喜欢Spark!"

因为我试图将这些字符串与包含正确文本的数据集相匹配(在这种情况下"Hello there!我真的很喜欢Spark❤️!"),我正在寻找一种有效的方法来匹配Spark中的字符串.

任何人都可以建议一个有效的Spark算法,它允许我比较提取文本(〜100.000)与我的数据集(约1亿)？

有没有办法在pandas文本DataFrame列上执行与SQL的LIKE语法类似的操作,以便返回索引列表或可用于索引数据帧的布尔值列表？例如,我希望能够匹配列以"prefix_"开头的所有行,类似于WHERE <col> LIKE prefix_%SQL.

鉴于两个字符串变量$string和$needlein perl,什么是检查是否$string开始的最有效方法$needle.

• $string =~ /^\Q$needle\E/ 是我能想到的最接近的匹配,它做了所需要的但是效率最低(到目前为止)我尝试过的解决方案.
• index($string, $needle) == 0对某些值有效并且相对有效$string,$needle但不必要地在其他位置搜索针(如果在开始时没有找到).
• substr($string, 0, length($needle)) eq $needle 应该是非常简单和有效的,但在我的几个测试中,大多数测试并不比前一个测试更有效.

是否有规范的方法可以做到这一点perl,我不知道或以任何方式优化任何上述解决方案？

(在我的特定用例中,$string并且$needle在每次运行中将会有所不同,因此预编译正则表达式不是一种选择).

如何衡量给定解决方案性能的示例(此处来自POSIX sh):

string='somewhat not so longish string' needle='somew'
time perl -e '
  ($n,$string,$needle) = @ARGV;
  for ($i=0;$i<$n;$i++) {

    index($string, $needle) == 0

  }' 10000000 "$string" "$needle"

使用这些值,使用perl 5.14.2 index()比substr()+eq使用此系统更好,但是:

string="aaaaabaaaaabaaaaabaaaaabaaaaabaaaaab" needle="aaaaaa"

那是相反的.

我正在使用长度为25的DNA序列(参见下面的例子).我有一个230,000的清单,需要寻找整个基因组中的每个序列(弓形虫寄生虫).我不确定基因组有多大,但比230,000个序列长得多.

我需要查找每个25个字符的序列,例如,(AGCCTCCCATGATTGAACAGATCAT).

基因组被格式化为连续的字符串,即(CATGGGAGGCTTGCGGAGCCTGAGGGCGGAGCCTGAGGTGGGAGGCTTGCGGAGTGCGGAGCCTGAGCCTGAGGGCGGAGCCTGAGGTGGGAGGCTT ....)

我不关心它被发现的地点和次数,只关注它是否存在.
我认为这很简单 -

str.find(AGCCTCCCATGATTGAACAGATCAT)

但我还要找到在任何位置定义为错误(不匹配)的近距离匹配,但只有一个位置,并记录序列中的位置.我不知道怎么做到这一点.我唯一能想到的是使用通配符并在每个位置使用通配符执行搜索.即,搜索25次.

例如,
AGCCTCCCATGATTGAACAGATCAT
AGCCTCCCATGATAGAACAGATCAT

与位置13处的不匹配密切匹配.

速度不是一个大问题,因为我只做了3次,但如果它很快就会很好.

有些程序可以执行此操作 - 查找匹配项和部分匹配项 - 但我正在寻找一种使用这些应用程序无法发现的部分匹配项.

这是perl的类似帖子,虽然它们只是比较序列而不是搜索连续的字符串:

相关文章

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

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

library(cba)
word <- 'test'
words <- c('Teest','teeeest','New York City','yeast','text','Test')
ClosestMatch <- function(string,StringVector) {
  matches <- agrep(string,StringVector,value=TRUE)
  distance <- sdists(string,matches,method = "ow",weight = c(1, 0, 2))
  matches <- data.frame(matches,as.numeric(distance))
  matches <- subset(matches,distance==min(distance))
  as.character(matches$matches)
}

ClosestMatch(word,words)

我正在研究一个非常粗略的初稿算法,以确定2个字符串的相似程度.我也使用Levenshtein Distance来计算字符串之间的编辑距离.

我目前正在做的是基本上采用编辑总数并将其除以较大字符串的大小.如果该值低于某个阈值,当前随机设置为25%,则它们"足够相似".

然而,这完全是任意的,我不认为这是计算相似性的一种非常好的方法.是否有某种数学方程或概率/统计方法来获取Levenshtein距离数据并使用它来说"是的,根据所做的编辑数量和字符串的大小,这些字符串是否足够相似"？

此外,关键是我使用任意阈值,我宁愿不这样做.如何计算此阈值而不是分配它,以便我可以安全地说2个字符串"足够相似"？

UPDATE

我正在比较代表Java堆栈跟踪的字符串.我想这样做的原因是通过相似性对一堆给定的堆栈跟踪进行分组,并将其用作过滤器来对"东西"进行排序:)这种分组对于我无法公开分享的更高级别的原因很重要.

到目前为止,我的算法(伪代码)大致如下:

/*
 * The input lists represent the Strings I want to test for similarity. The
 * Strings are split apart based on new lines / carriage returns because Java
 * stack traces are not a giant one-line String, rather a multi-line String.
 * So each element in the input lists is a "line" from its stack trace.
 */
calculate similarity (List<String> list1, List<String> list2) {

    length1 = 0; …

我一直在研究一种基于不完美字符串连接两个数据集的方法,例如公司名称.在过去,我必须匹配两个非常脏的列表,一个列表有名称和财务信息,另一个列表有名称和地址.没有唯一的ID匹配!假设清洁已经应用,并且可能有类型和插入.

到目前为止,AGREP是我发现的最接近的工具.我可以在AGREP包中使用levenshtein距离,它测量两个字符串之间的删除,插入和替换的数量.AGREP将返回距离最小的字符串(最相似).

但是,我一直无法从单个值转换此命令以将其应用于整个数据帧.我粗略地使用了for循环来重复AGREP函数,但是必须有一个更简单的方法.

请参阅以下代码:

a<-data.frame(name=c('Ace Co','Bayes', 'asd', 'Bcy', 'Baes', 'Bays'),price=c(10,13,2,1,15,1))
b<-data.frame(name=c('Ace Co.','Bayes Inc.','asdf'),qty=c(9,99,10))

for (i in 1:6){
    a$x[i] = agrep(a$name[i], b$name, value = TRUE, max = list(del = 0.2, ins = 0.3, sub = 0.4))
    a$Y[i] = agrep(a$name[i], b$name, value = FALSE, max = list(del = 0.2, ins = 0.3, sub = 0.4))
}

我需要自动将来自不同来源的产品名称(相机,笔记本电脑,电视等)与数据库中的规范名称相匹配.

例如"Canon PowerShot a20IS","来自佳能的NEW powershot A20 IS"和"数码相机佳能PS A20IS" 都应该与"佳能PowerShot A20 IS"相匹配.我已经使用了levenshtein距离和一些额外的启发式方法(删除了明显的常用词,为数字更改分配了更高的成本等),这在某种程度上起作用,但遗憾的是不够好.

主要问题是即使相关关键字中的单字母更改也会产生巨大差异,但要检测哪些是相关关键字并不容易.例如,考虑三个产品名称:
联想T400
联想R400
新联想T-400,酷睿2双核
任何标准前两个是可笑的类似字符串(好吧,soundex可能有助于在这种情况下消除T和R,但名称可能同样是400T和400R),第一个和第三个是相互远离的字符串,但是是相同的产品.

显然,匹配算法不能100%精确,我的目标是自动匹配大约80%的名字,具有很高的信心.

非常感谢任何想法或参考