python - Numpy 数组中与通配符的二维模式匹配

Question

首先，我知道 this , this和 this关于二维模式匹配的帖子，但是这些帖子都不包含通配符匹配。此外，我知道有几篇论文，例如this one这已经解决了我面临的问题。然而，我刚刚熟悉二维数组中的模式匹配，目前尝试实现论文中的算法对我来说并不简单。

因此，我面临以下问题。

给定一个二维数组:

[[1 3 4 5 3 3]
 [4 1 4 5 5 2]
 [5 4 3 4 4 2] # pattern
 [4 5 3 4 1 3] # pattern
 [3 3 3 4 4 4] # pattern
 [3 4 3 4 2 5] # pattern
 [4 5 3 4 1 2] # pattern
 [5 1 1 2 4 2]
 [2 1 3 2 1 5]
 [4 4 1 3 3 1]
 [1 4 3 4 4 1]
 [5 2 4 4 4 1]]

以及以下示例模式(其中 ? 表示通配符匹配):

[[? ? 3 4 ? ?]
 [? ? 3 4 ? ?]
 [3 3 3 4 4 4]
 [? ? 3 4 ? ?]
 [? ? 3 4 ? ?]]

如何编写一个函数来接收二维数组和模式，如果数组中存在模式则返回 True，如果不存在则返回 False？

如果可能的话，我们将非常感谢这个问题的通用解决方案，因为我正在尝试匹配许多不同的模式。如果需要，我非常愿意提供更多示例。

Answer 1

此函数采用一个 input_array、一个pattern 和一个可让您识别通配符的函数。在这里，我使用 np.nan 作为通配符，但它可以是任何东西，因为您可以创建自己的 wildcard_function。

它适用于任何维度(1 或更多)的数组。我已经针对你的示例进行了测试，看起来没问题。

from itertools import product
import numpy as np


def match_pattern(input_array, pattern, wildcard_function=np.isnan):

    pattern_shape = pattern.shape
    input_shape = input_array.shape

    is_wildcard = wildcard_function(pattern) # This gets a boolean N-dim array

    if len(pattern_shape) != len(input_shape):
        raise ValueError("Input array and pattern must have the same dimension")

    shape_difference = [i_s - p_s for i_s, p_s in zip(input_shape, pattern_shape)]

    if any((diff < -1 for diff in shape_difference)):
        raise ValueError("Input array cannot be smaller than pattern in any dimension")

    dimension_iterators = [range(0, s_diff + 1) for s_diff in shape_difference]

    # This loop will iterate over every possible "window" given the shape of the pattern
    for start_indexes in product(*dimension_iterators):
        range_indexes = [slice(start_i, start_i + p_s) for start_i, p_s in zip(start_indexes, pattern_shape)]
        input_match_candidate = input_array[range_indexes]

        # This checks that for the current "window" - the candidate - every element is equal 
        #  to the pattern OR the element in the pattern is a wildcard
        if np.all(
            np.logical_or(
                is_wildcard, (input_match_candidate == pattern)
            )
        ):
            return True

    return False