尋找一個字符串是否匹配模式

Question

在我的應用程序的某一點，我需要匹配一些模式的字符串。假設一些示例字符串如下所示：

1. 嗨，那裏，約翰。
2. 今天真是美好的一天！
3. 今天可愛的日落，約翰，不是嗎？
4. 約翰，你今天會和琳達見面嗎？

大多數（不是全部）的這些字符串是從預先定義的模式如下：

1. 「您好，％S」。
2. 「今天真是美好的一天！」 「今天可愛的日落，％s，不是嗎？」 「你今天會見％s嗎，％s？」

這個模式庫不斷擴大（目前在1,500左右），但是手動維護。儘管（第一組）輸入字符串在很大程度上是不可預知的。雖然他們中的大多數會匹配其中一種模式，但其中一些模式不會。

所以，這裏是我的問題：給定一個字符串（從第一組）作爲輸入，我需要知道哪些模式（稱爲第二組）它匹配。如果沒有匹配，它需要告訴我。

我猜的解決方案包括建立一個正則表達式出來的圖案，並反覆檢查哪一個匹配。但是，我不確定構建這些正則表達式的代碼是什麼樣的。

注：我在這裏給出的字符串僅用於說明目的。實際上，這些字符串不是人類生成的，而是由我無法控制的系統在上面顯示的計算機生成的人性化字符串。由於它們不是手動輸入的，因此我們不需要擔心類型錯誤和其他人爲錯誤。只需要找到它匹配的模式。

注2：我可以修改圖形庫是一些其他的格式，如果這使得它更容易構建正則表達式。當前的結構與printf樣式％s不同。

Answer 1

我首先想到的是具有正則表達式引擎採取的處理這一切的麻煩。它們通常被優化來處理大量的文本，所以它不應該成爲性能問題。這是蠻力，但表現似乎沒問題。你可以將輸入分成幾部分，並有多個進程處理它們。這是我經過適度測試的解決方案（使用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 regexp庫的最大限制。其中4個是你的實際例子，其餘的都是隨機句，只是爲了強調一點。

然後我將它們組合成一個包含100個組的單個正則表達式。 (group1)|(group2)|(group3)|...。我猜你必須對正則表達式中的含義進行消毒處理（如?等）。這是monster_regexp。

根據此測試一個字符串在單次測試中對100個模式進行測試。有一些方法可以找出匹配的確切組。我測試了10000個字符串，其中80％應該匹配，10％不會。它縮短了成本，所以如果取得成功，它會比較快。失敗將不得不貫穿整個正則表達式，所以它會變慢。您可以根據輸入頻率排序，以獲得更多性能。

我在我的機器上運行了這個，這是我的計時。

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

這是不是太糟糕。

但是，要對這麼大的正則表達式的模式和失敗將需要更長的時間，所以我改變了輸入有大量隨機生成的字符串，將不匹配，然後嘗試的。 10000個字符串，其中沒有一個匹配monster_regexp，我得到了這個。

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

Answer 2

Python解決方案。 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 
>>> 

的技巧是使用^和$來約束你的模式，並使其成爲一個「模板」。使用（。*）或（。+）或任何你想要「搜索」的東西。

你，恕我直言，將通過這些模式的列表迭代的主要瓶頸。正則表達式搜索的計算量很大。

如果你想要一個「沒有任何模式匹配」的結果，建立一個巨大的或基於正則表達式，讓你的正則表達式引擎處理「的OR'ing你。

此外，如果您只有前綴模式，請查看TRIE數據結構。

Answer 3

這可能是sscanf的工作，存在的js實現：http://phpjs.org/functions/sscanf/;正在複製的功能是：http://php.net/manual/en/function.sscanf.php。

您應該能夠使用它沒有太多的改變準備的字符串，但我對錶演的疑慮。

Answer 4

這個問題我不清楚。你想採取模式，並建立正則表達式嗎？ 大多數正則表達式引擎都有一個「帶引號的字符串」選項。 （\ Q \ E）。所以，你可以採取的字符串，使其 ^ \ QHi那裏，\ E（：*？）\問。\ E $這將是正是你想要的變量外的字符串相匹配的正則表達式。

如果你想使用一個正則表達式來匹配一個模式，你可以把它們放在分組模式中找出哪一個匹配，但不會給你每一個匹配，只是第一個匹配。

如果您使用合適解析器（我用PEG.js），它可能是更容易維護，但。所以這是另一種選擇，如果你認爲你可能會停留在正則表達式地獄

Answer 5

類似Noufal的解決方案，但返回匹配的模式或無。

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?") 

Answer 6

我將此視爲解析問題。這個想法是解析器函數接受一個字符串並確定它是否有效。

的字符串是有效的，如果你能在給定模式中find它。這意味着你需要一個所有模式的索引。索引必須是全文索引。它也必須根據單詞的位置進行匹配。例如。如果在模式的第一個字中沒有找到輸入的第一個字，它應該會短路。它應該照顧any匹配，即模式中的%s。

一種解決方案是將模式放入內存數據庫（例如redis）中並在其上執行全文索引。 （根據單詞的位置，這不會匹配），但您應該能夠通過將輸入分爲單詞和搜索來縮小到正確的模式。搜索速度會非常快，因爲您的內存數據庫很小。另請注意，您正在尋找最接近的匹配。一個或多個單詞不匹配。最高數量的比賽是你想要的模式。

更好的解決方案是以字典格式生成自己的索引。以下是您作爲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}}}}}} 
} 

該索引根據單詞postion遞歸遞減。因此，搜索第一個單詞，如果找到第一個單詞返回的對象內的下一個內容，依此類推。同一級別的單詞只有一個。你也應該匹配any的情況。這應該在記憶中快速致盲。