查找一个string是否匹配一个模式
在我的应用程序的一个点上，我需要匹配一些模式的string。 假设一些示例string如下所示：
- 你好，约翰。
- 今天真是美好的一天！
- 今天可爱的日落，约翰，不是吗？
- 约翰，你今天会见琳达吗？
大多数（不是全部）这些string都来自预定义的模式，如下所示：
- “你好，％s。”
- 今天真是美好的一天！“
- “今天可爱的日落，％s，不是吗？
- “你今天会开会吗，％s？
这个模式库不断扩大（目前在1,500左右），但手动维护。 inputstring虽然（第一组）很大程度上是不可预知的。 虽然他们中的大多数将匹配其中的一种模式，但其中一些不会。
所以，这是我的问题：给定一个string（从第一组）作为input，我需要知道哪些模式（已知第二组）它匹配。 如果没有任何匹配，它需要告诉我。
我猜测解决scheme涉及到从模式中构build一个正则expression式，并迭代地检查哪一个匹配。 不过，我不确定构build这些正则expression式的代码是什么样的。
注：我在这里给出的string是为了说明的目的。 实际上，这些string不是人类生成的，而是由我不能控制的系统在上面显示的计算机生成的人性化string。 由于它们不是手动input的，我们不需要担心types错误和其他人为错误。 只需要find匹配的模式。
注2：我可以修改模式库为其他格式，如果这样可以更容易地构造正则expression式。 当前的结构，printf样式％s，并不是一成不变的。
我首先想到的是让正则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式地狱