Алгоритм для сопоставления 2 списков с подстановочными знаками

Question

Я ищу эффективный способ сопоставления 2 списков, один из которых содержит полную информацию, и ту, которая содержит подстановочные знаки. Я смог сделать это с помощью подстановочных знаков фиксированной длины, но теперь я пытаюсь сделать это с помощью подстановочных знаков переменной длины.

Таким образом:

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

вернется Правда, пока все элементы находятся в том же порядке, в обоих списках.

Я работаю со списками объектов, но использовал строки выше для простоты.

Answer 1

[редактировать для оправдания нет RE после ОП комментария на сравнивающих объектов]

Похоже, вы не используете строки, а сравнивать объекты.Поэтому я даю явный алгоритм - регулярные выражения обеспечивают хорошее решение, адаптированное для строк, не поймите меня неправильно, но из того, что вы говорите как комментарий к своим вопросам, кажется, что простой, простой алгоритм может упростить вам работу ,

Оказывается, что это может быть решено с гораздо более простым алгоритмом, чем this previous answer:

def matcher (l1, l2): 
    if (l1 == []): 
     return (l2 == [] or l2 == ['*']) 
    if (l2 == [] or l2[0] == '*'): 
     return matcher(l2, l1) 
    if (l1[0] == '*'): 
     return (matcher(l1, l2[1:]) or matcher(l1[1:], l2)) 
    if (l1[0] == l2[0]): 
     return matcher(l1[1:], l2[1:]) 
    else: 
     return False 

Ключевая идея заключается в том, что, когда вы сталкиваетесь с подстановочным, вы можете изучить два варианта:

• либо продвигается в списке, который содержит подстановочный знак (и считайте, что подстановочный знак соответствует тому, что было до сих пор)
• или продвигается в списке, который не содержит подстановочный знак (и считайте, что все, что находится в руководитель списка должен соответствовать шаблону).

Answer 2

Согласен с комментарием относительно этого можно сделать с помощью регулярных выражений. Например:

import re 

lst = ['A', 'B', 'C', 'C', 'C', 'D'] 
pattern = ['A', 'B', 'C+', 'D'] 

print re.match(''.join(pattern), ''.join(lst)) # Will successfully match 

Edit: Как было отмечено в комментарии, это может быть заранее известно только, что какой-то символ должен быть согласован, но не один, который. В этом случае, регулярные выражения полезны еще:

import re 

lst = ['A', 'B', 'C', 'C', 'C', 'D'] 
pattern = r'AB(\w)\1*D' 

print re.match(pattern, ''.join(lst)).groups() 

Answer 3

Как о следующем:

import re 

def match(pat, lst): 
    regex = ''.join(term if term != '*' else '.*' for term in pat) + '$' 
    s = ''.join(lst) 
    return re.match(regex, s) is not None 

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

Он использует регулярные выражения. Подстановочные знаки (*) изменены на .*, и все остальные условия поиска хранятся как есть.

Одно из предостережений заключается в том, что если ваши поисковые термины могут содержать вещи, которые имеют особое значение в языке регулярных выражений, они должны быть надлежащим образом экранированы. Довольно легко справиться с этим в функции match, я просто не был уверен, что это то, что вам нужно.

Answer 4

Я бы рекомендовал преобразовать ['A', 'B', '*', 'D'] в '^AB.*D$', ['A', 'B', 'C', 'C', 'C', 'D'] к 'ABCCCD', а затем с помощью модуля re (регулярные выражения), чтобы сделать матч.

Это будет действительным, если элементы ваших списков имеют только один символ, и если они являются строками.

что-то вроде:

import(re) 
def myMatch(patternList, stringList): 
    # convert pattern to flat string with wildcards 
    # convert AB*D to valid regex ^AB.*D$ 
    pattern = ''.join(patternList) 
    regexPattern = '^' + pattern.replace('*','.*') + '$' 
    # perform matching 
    against = ''.join(stringList) # convert ['A','B','C','C','D'] to ABCCCD 
    # return whether there is a match 
    return (re.match(regexPattern,against) is not None) 

Если списки содержат цифры или слова, выберите символ, который вы не ожидали бы быть в любом, например #. Затем ['Aa','Bs','Ce','Cc','CC','Dd'] может быть преобразован в Aa#Bs#Ce#Cc#CC#Dd, шаблон подстановки может быть преобразован в ^Aa#Bs#.*#Dd$, а совпадение выполнено.

Практически это означает, что все ''.join(...) становится '#'.join(...) в myMatch.

Answer 5

Я согласен, регулярные выражения, как правило, подходят для такого рода вещей. Этот алгоритм работает, но он просто выглядит запутанным для меня. Было интересно писать.

def match(listx, listy): 
    listx, listy = map(iter, (listx, listy)) 
    while 1: 
     try: 
      x = next(listx) 
     except StopIteration: 
      # This means there are values left in listx that are not in listy. 
      try: 
       y = next(listy) 
      except StopIteration: 
       # This means there are no more values to be compared in either 
       # listx or listy; since no exception was raied elsewhere, the 
       # lists match. 
       return True 
      else: 
       # This means that there are values in listy that are not in 
       # listx. 
       return False 
     else: 
      try: 
       y = next(listy) 
      except StopIteration: 
       # Similarly, there are values in listy that aren't in listx. 
       return False 
     if x == y: 
      pass 
     elif x == '*': 
      try: 
       # Get the value in listx after '*'. 
       x = next(listx) 
      except StopIteration: 
       # This means that listx terminates with '*'. If there are any 
       # remaining values of listy, they will, by definition, match. 
       return True 
      while 1: 
       if x == y: 
        # I didn't shift to the next value in listy because I 
        # assume that a '*' matches the empty string and well as 
        # any other. 
        break 
       else: 
        try: 
         y = next(listy) 
        except StopIteration: 
         # This means there is at least one remaining value in 
         # listx that is not in listy, because listy has no 
         # more values. 
         return False 
        else: 
         pass 
     # Same algorithm as above, given there is a '*' in listy. 
     elif y == '*': 
      try: 
       y = next(listy) 
      except StopIteration: 
       return True 
      while 1: 
       if x == y: 
        break 
       else: 
        try: 
         x = next(listx) 
        except StopIteration: 
         return False 
        else: 
         pass 

Answer 6

У меня был этот кусок кода C++, который, кажется, делает то, что вы пытаетесь сделать (входы представляют собой строки вместо массивов символов, но вам все равно придется адаптировать материал).

bool Utils::stringMatchWithWildcards (const std::string str, const std::string strWithWildcards) 
    PRINT("Starting in stringMatchWithWildcards('" << str << "','" << strWithWildcards << "')"); 
    const std::string wildcard="*"; 

    const bool startWithWildcard=(strWithWildcards.find(wildcard)==0); 
    int pos=strWithWildcards.rfind(wildcard); 
    const bool endWithWildcard = (pos!=std::string::npos) && (pos+wildcard.size()==strWithWildcards.size()); 

    // Basically, the point is to split the string with wildcards in strings with no wildcard. 
    // Then search in the first string for the different chunks of the second in the correct order 
    std::vector<std::string> vectStr; 
    boost::split(vectStr, strWithWildcards, boost::is_any_of(wildcard)); 
    // I expected all the chunks in vectStr to be non-empty. It doesn't seem the be the case so let's remove them. 
    vectStr.erase(std::remove_if(vectStr.begin(), vectStr.end(), std::mem_fun_ref(&std::string::empty)), vectStr.end()); 

    // Check if at least one element (to have first and last element) 
    if (vectStr.empty()) 
    { 
     const bool matchEmptyCase = (startWithWildcard || endWithWildcard || str.empty()); 
     PRINT("Match " << (matchEmptyCase?"":"un") << "successful (empty case) : '" << str << "' and '" << strWithWildcards << "'"); 
     return matchEmptyCase; 
    } 

    // First Element 
    std::vector<std::string>::const_iterator vectStrIt = vectStr.begin(); 
    std::string aStr=*vectStrIt; 
    if (!startWithWildcard && str.find(aStr, 0)!=0) { 
     PRINT("Match unsuccessful (beginning) : '" << str << "' and '" << strWithWildcards << "'"); 
     return false; 
    } 

    // "Normal" Elements 
    bool found(true); 
    pos=0; 
    std::vector<std::string>::const_iterator vectStrEnd = vectStr.end(); 
    for (; vectStrIt!=vectStrEnd ; vectStrIt++) 
    { 
     aStr=*vectStrIt; 
     PRINT("Searching '" << aStr << "' in '" << str << "' from " << pos); 
     pos=str.find(aStr, pos); 
     if (pos==std::string::npos) 
     { 
      PRINT("Match unsuccessful ('" << aStr << "' not found) : '" << str << "' and '" << strWithWildcards << "'"); 
      return false; 
     } else 
     { 
      PRINT("Found at position " << pos); 
      pos+=aStr.size(); 
     } 
    } 

    // Last Element 
    const bool matchEnd = (endWithWildcard || str.rfind(aStr)+aStr.size()==str.size()); 
    PRINT("Match " << (matchEnd?"":"un") << "successful (usual case) : '" << str << "' and '" << strWithWildcards); 
    return matchEnd; 
} 

    /* Tested on these values : 
    assert(stringMatchWithWildcards("ABC","ABC")); 
    assert(stringMatchWithWildcards("ABC","*")); 
    assert(stringMatchWithWildcards("ABC","*****")); 
    assert(stringMatchWithWildcards("ABC","*BC")); 
    assert(stringMatchWithWildcards("ABC","AB*")); 
    assert(stringMatchWithWildcards("ABC","A*C")); 
    assert(stringMatchWithWildcards("ABC","*C")); 
    assert(stringMatchWithWildcards("ABC","A*")); 

    assert(!stringMatchWithWildcards("ABC","BC")); 
    assert(!stringMatchWithWildcards("ABC","AB")); 
    assert(!stringMatchWithWildcards("ABC","AB*D")); 
    assert(!stringMatchWithWildcards("ABC","")); 

    assert(stringMatchWithWildcards("","")); 
    assert(stringMatchWithWildcards("","*")); 
    assert(!stringMatchWithWildcards("","ABC")); 
    */ 

Это не то, чем я действительно горжусь, но, похоже, работает до сих пор. Надеюсь, вы найдете это полезным.