Thuật toán để khớp 2 danh sách với ký tự đại diện

Question

Tôi đang tìm cách hiệu quả để khớp 2 danh sách, một danh sách chứa thông tin đầy đủ và một danh sách chứa ký tự đại diện. Tôi đã có thể thực hiện điều này với các ký tự đại diện có độ dài cố định, nhưng hiện tại tôi đang cố gắng làm điều đó với các ký tự đại diện có độ dài thay đổi.

Như vậy:

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

sẽ trở lại Đúng miễn là tất cả các yếu tố này là theo thứ tự trong cả hai danh sách.

Tôi đang làm việc với danh sách các đối tượng, nhưng sử dụng các chuỗi ở trên để đơn giản.

Answer 1

[chỉnh sửa để biện minh cho không RE sau OP bình luận trên các đối tượng so sánh]

Có vẻ bạn không sử dụng dây, mà đúng hơn là so sánh các đối tượng.Do đó tôi đưa ra một thuật toán rõ ràng - các biểu thức chính quy cung cấp giải pháp phù hợp cho chuỗi, không hiểu sai, nhưng từ những gì bạn nói là nhận xét cho câu hỏi của mình, có vẻ như thuật toán đơn giản, rõ ràng có thể giúp bạn dễ dàng hơn .

Nó chỉ ra rằng điều này có thể được giải quyết với một thuật toán đơn giản hơn nhiều so với 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 

Ý tưởng quan trọng là khi bạn gặp một ký tự đại diện, bạn có thể khám phá hai lựa chọn:

• hoặc tạm ứng trong danh sách chứa ký tự đại diện (và xem xét ký tự đại diện khớp với bất kỳ điều gì cho đến bây giờ)
• hoặc trước trong danh sách không chứa ký tự đại diện (và xem xét bất kỳ điều gì người đứng đầu danh sách phải khớp với ký tự đại diện).

Answer 2

Tôi đồng ý với nhận xét về việc này có thể được thực hiện bằng cụm từ thông dụng. Ví dụ:

import re 

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

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

Chỉnh sửa: Như được chỉ ra bởi nhận xét, có thể bạn biết trước rằng một số ký tự phải khớp, chứ không phải là ký tự nào. Trong trường hợp đó, biểu thức thông thường là hữu ích vẫn:

import re 

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

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

Answer 3

Làm thế nào về những điều sau đây:

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']) 

Nó sử dụng biểu thức thông thường. Ký tự đại diện (*) được đổi thành .* và tất cả các cụm từ tìm kiếm khác được giữ nguyên.

Một lưu ý là nếu cụm từ tìm kiếm của bạn có thể chứa những thứ có ý nghĩa đặc biệt trong ngôn ngữ regex, những cụm từ đó sẽ cần phải được thoát đúng cách. Nó khá dễ dàng để xử lý điều này trong chức năng match, tôi chỉ không chắc chắn nếu điều này là một cái gì đó bạn yêu cầu.

Answer 4

Tôi khuyên bạn nên chuyển đổi ['A', 'B', '*', 'D'] thành '^AB.*D$', ['A', 'B', 'C', 'C', 'C', 'D'] thành 'ABCCCD' và sau đó sử dụng mô-đun re (biểu thức chính quy) để thực hiện đối sánh.

Điều này sẽ hợp lệ nếu các yếu tố trong danh sách của bạn chỉ là một ký tự và mỗi chuỗi là các ký tự.

cái gì đó như:

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) 

Nếu danh sách chứa các số hoặc nhiều từ chọn một nhân vật mà bạn sẽ không mong đợi để được ở một trong hai, ví dụ #. Sau đó, ['Aa','Bs','Ce','Cc','CC','Dd'] có thể được chuyển đổi thành Aa#Bs#Ce#Cc#CC#Dd, mẫu ký tự đại diện có thể được chuyển đổi thành ^Aa#Bs#.*#Dd$ và khớp được thực hiện.

Thực tế, điều này chỉ có nghĩa là tất cả các ''.join(...) trở thành '#'.join(...) trong myMatch.

Answer 5

Tôi đồng ý, cụm từ thông dụng thường là cách để đi với loại điều này. Thuật toán này hoạt động, nhưng nó chỉ có vẻ phức tạp với tôi. Thật là vui khi viết.

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

Tôi đã có đoạn mã C++ này dường như đang làm những gì bạn đang cố gắng làm (đầu vào là chuỗi thay vì mảng ký tự nhưng bạn sẽ phải điều chỉnh mọi thứ).

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")); 
    */ 

Đó không phải là điều tôi thực sự tự hào nhưng có vẻ như nó đang hoạt động cho đến nay. Tôi hy vọng bạn có thể thấy nó hữu ích.