Двумерное сопоставление шаблонов с символами подстановки в массивах Numpy

Question

Во-первых, мне известно о этом , этом и этом сообщении о сопоставлении двухмерных шаблонов, однако эти сообщения не включают сопоставление по шаблону. Кроме того, я знаю, что есть несколько статей, таких как , эта , которые решили проблему, с которой я столкнулся. Тем не менее, я только знакомлюсь с сопоставлением с образцом в двухмерных массивах, и попытка реализовать алгоритмы в статьях для меня на данный момент нетривиальна.

Таким образом, передо мной стоит следующая проблема.

Имеется двумерный массив:

[[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]]

И следующий пример шаблона (где a? Указывает на совпадение с подстановочным знаком):

[[? ? 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

Answer 2

Поскольку ваше пространство поиска очень мало, нам не нужно беспокоиться об ошибках памяти, просто расправляя окно.

Сначала вам понадобится маска , где есть значения в вашем шаблоне

mask

array([[False, False,  True,  True, False, False],
       [False, False,  True,  True, False, False],
       [ True,  True,  True,  True,  True,  True],
       [ True,  True,  True,  True,  True,  True],
       [False, False,  True,  True, False, False],
       [False, False,  True,  True, False, False]], dtype=bool)

Тогда вам нужен массив Что значения находятся в этих позициях:

val = np.array([ 3.,  4.,  3.,  4.,  3.,  3.,  3.,  4.,  4.,  4.,
                 3.,  3.,  3.,  4.,  4.,  4.,  3.,  4.,  3.,  4.])

Тогда вам нужно скользящее окно через ваш ввод. Самая простая реализация - это skimage.util.view_as_windows, но вы можете использовать мою чистую пустышку здесь

windows = skimage.util.view_as_windows(input, pattern.shape)
# or
windows = window_nd(input, pattern.shape)

Теперь, обычно делать windows[mask] здесь было бы опасно - он может создать огромный массив, если вы свернетесь во многих окнах. Но большинство окон, которые у нас когда-либо были, это 12 * 6 = 72, нам не нужно об этом беспокоиться.

loc = np.where(np.all(window[mask] == val, axis = -1))

Теперь loc - это координаты верхнего левого угла соответствующих окон.

Или так и должно быть. Может быть, предоставить тестовый пример, который можно скопировать / вставить в интерпретатор?