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

Question

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

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

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

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

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

Answer 1

[отредактировано, чтобы оправдать отсутствие RE после комментария OP при сравнении объектов]

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

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

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

Я бы рекомендовал преобразовать ['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'] можно преобразовать в ^Aa#Bs#.*#Dd$ и выполнить сопоставление.

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

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

У меня был этот кусок кода на 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"));
   */

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

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

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

import re

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

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

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

import re

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

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