查找一个string是否匹配一个模式

在我的应用程序的一个点上,我需要匹配一些模式的string。 假设一些示例string如下所示:

  1. 你好,约翰。
  2. 今天真是美好的一天!
  3. 今天可爱的日落,约翰,不是吗?
  4. 约翰,你今天会见琳达吗?

大多数(不是全部)这些string都来自预定义的模式,如下所示:

  1. “你好,%s。”
  2. 今天真是美好的一天!“
  3. “今天可爱的日落,%s,不是吗?
  4. “你今天会开会吗,%s?

这个模式库不断扩大(目前在1,500左右),但手动维护。 inputstring虽然(第一组)很大程度上是不可预知的。 虽然他们中的大多数将匹配其中的一种模式,但其中一些不会。

所以,这是我的问题:给定一个string(从第一组)作为input,我需要知道哪些模式(已知第二组)它匹配。 如果没有任何匹配,它需要告诉我。

我猜测解决scheme涉及到从模式中构build一个正则expression式,并迭代地检查哪一个匹配。 不过,我不确定构build这些正则expression式的代码是什么样的。

注:我在这里给出的string是为了说明的目的。 实际上,这些string不是人类生成的,而是由我不能控制的系统在上面显示的计算机生成的人性化string。 由于它们不是手动input的,我们不需要担心types错误和其他人为错误。 只需要find匹配的模式。

注2:我可以修改模式库为其他格式,如果这样可以更容易地构造正则expression式。 当前的结构,printf样式%s,并不是一成不变的。

       

网上收集的解决方案 "查找一个string是否匹配一个模式"

我首先想到的是让正则expression式引擎处理这个问题。 他们通常被优化来处理大量的文本,所以它不应该是一个性能的麻烦。 这是蛮力,但performance似乎没问题。 你可以把input分成几部分,并有多个进程处理它们。 这是我经过适度testing的解决scheme(在Python中)。

 import random import string import re def create_random_sentence(): nwords = random.randint(4, 10) sentence = [] for i in range(nwords): sentence.append("".join(random.choice(string.lowercase) for x in range(random.randint(3,10)))) ret = " ".join(sentence) print ret return ret patterns = [ r"Hi there, [a-zA-Z]+.", r"What a lovely day today!", r"Lovely sunset today, [a-zA-Z]+, isn't it?", r"Will you be meeting [a-zA-Z]+ today, [a-zA-Z]+\?"] for i in range(95): patterns.append(create_random_sentence()) monster_pattern = "|".join("(%s)"%x for x in patterns) print monster_pattern print "--------------" monster_regexp = re.compile(monster_pattern) inputs = ["Hi there, John.", "What a lovely day today!", "Lovely sunset today, John, isn't it?", "Will you be meeting Linda today, John?", "Goobledigoock"]*2000 for i in inputs: ret = monster_regexp.search(i) if ret: print ".", else: print "x", 

我创造了一百个模式。 这是python正则expression式库的最大限制。 其中4个是你的实际例子,其余的是随机的句子,只是为了强调一点。

然后我把它们组合成一个有100个组的单个正则expression式。 (group1)|(group2)|(group3)|... 我猜你必须消除正则expression式中的含义(如?等)的input。 这是monster_regexp

根据这个testing一个string,在一个镜头中对100个模式进行testing。 有一些方法可以找出匹配的确切组。 我testing了10000个string,其中80%应该匹配,10%不会。 如果有成功的话,它会缩短成本,这将会相对较快。 失败将不得不贯穿整个正则expression式,所以它会变慢。 你可以根据input的频率来sorting,以获得更多的性能。

我在我的机器上运行这个,这是我的时机。

python /tmp/scratch.py 0.13s user 0.00s system 97% cpu 0.136 total

这不算太糟糕。

然而,针对如此大的正则expression式运行一个模式,失败将需要更长的时间,所以我改变了input有大量的随机生成的string,将不匹配,然后尝试。 10000个string,其中没有一个匹配monster_regexp,我得到了这个。

python /tmp/scratch.py 3.76s user 0.01s system 99% cpu 3.779 total

我正在看这个parsing问题。 这个想法是parsing器函数接受一个string,并确定它是否有效。

该string是有效的,如果你可以在给定的模式中find它。 这意味着你需要一个所有模式的索引。 索引必须是全文索引。 也必须根据字的位置进行匹配。 例如。 如果在模式的第一个字中没有findinput的第一个字,它应该会短路。 它应该照顾any匹配,即模式中的%s

一种解决scheme是将模式放在内存数据库(例如redis)中,并对其进行全文索引。 (根据单词的位置不匹配),但是应该可以通过将input分割成单词和search来缩小到正确的模式。 search将会非常快,因为你有一个小内存数据库。 另外请注意,你正在寻找最接近的匹配。 一个或多个单词不匹配。 比赛的最高数量是你想要的模式。

更好的解决scheme是以字典格式生成自己的索引。 以下是您作为JavaScript对象提供的四种模式的示例索引。

 { "Hi": { "there": {"%s": null}}, "What: {"a": {"lovely": {"day": {"today": null}}}}, "Lovely": {"sunset": {"today": {"%s": {"isnt": {"it": null}}}}}, "Will": {"you": {"be": {"meeting": {"%s": {"today": {"%s": null}}}}}} } 

这个索引根据词位置recursion递减。 因此,search第一个单词,如果find第一个单词返回的对象内的下一个,依此类推。 在给定的水平上相同的词将只有一个关键。 你也应该匹配any情况。 这应该是在记忆中快速致盲。

与Noufal的解决scheme类似,但返回匹配的模式或None。

 import re patterns = [ "Hi there, %s.", "What a lovely day today!", "Lovely sunset today, %s, isn't it", "Will you be meeting %s today, %s?" ] def make_re_pattern(pattern): # characters like . ? etc. have special meaning in regular expressions. # Escape the string to avoid interpretting them as differently. # The re.escape function escapes even %, so replacing that with XXX to avoid that. p = re.escape(pattern.replace("%s", "XXX")) return p.replace("XXX", "\w+") # Join all the pattens into a single regular expression. # Each pattern is enclosed in () to remember the match. # This will help us to find the matched pattern. rx = re.compile("|".join("(" + make_re_pattern(p) + ")" for p in patterns)) def match(s): """Given an input strings, returns the matched pattern or None.""" m = rx.match(s) if m: # Find the index of the matching group. index = (i for i, group in enumerate(m.groups()) if group is not None).next() return patterns[index] # Testing with couple of patterns print match("Hi there, John.") print match("Will you be meeting Linda today, John?") 

Python解决scheme。 JS应该是相似的。

 >>> re2.compile('^ABC(.*)E$').search('ABCDE') == None False >>> re2.compile('^ABC(.*)E$').search('ABCDDDDDDE') == None False >>> re2.compile('^ABC(.*)E$').search('ABX') == None True >>> 

诀窍是使用^和$来绑定你的模式,并把它作为一个“模板”。 使用(。*)或(。+)或任何你想要“search”。

你的主要瓶颈,恕我直言,将迭代通过这些模式的列表。 正则expression式search在计算上是很昂贵的。

如果你想要“做任何模式匹配”的结果,build立一个大规模的OR基于正则expression式,让你的正则expression式引擎处理你的“OR”。

另外,如果只有前缀模式,请查看TRIE数据结构。

这可能是sscanf的一个工作,在js中有一个实现: http : //phpjs.org/functions/sscanf/ ; 被复制的function是这样的: http : //php.net/manual/en/function.sscanf.php 。

你应该能够使用它,而不用更改准备好的string,但是我对表演有所怀疑。

问题不清楚给我。 你想采取模式,并build立正则expression式吗? 大多数正则expression式引擎都有一个“带引号的string”选项。 (\ Q \ E)。 所以你可以把string做成^ \ QHi在这里,\ E(?:。*)\ Q. \ E $这些是正则expression式,它和你想要的variables之外的string完全匹配。

如果你想使用一个正则expression式匹配一个模式,你可以把它们放在分组模式中找出哪一个匹配,但不会给你每一个匹配,只是第一个匹配。

如果你使用了一个合适的parsing器(我已经使用了PEG.js),它可能会更易于维护。 所以这是另一种select,如果你认为你可能卡在正则expression式地狱