在字符网格中匹配加号

Question

我尝试使用正则表达式匹配字符串中的模式。想法是这样的。

我有一个大小为n*m的数组，每个条目都有G和非G。我必须找到加号(+)形式的G的模式，加号的所有四个臂都具有相同的大小。例如，在下面的示例中：

BGBBGB
GGGGGG
BGBBGB
GGGGGG
BGBBGB
BGBBGB

BGB
GGG
BGB

是加号(+)的形式，每个臂的大小为1。

我试着用正则表达式来解决这个模式，然而，它对我不起作用。

match = [(m.start(0), m.end(0)) for m in re.finditer(r'([GG]*G)',l[i])]

仅匹配水平轴上具有相同臂长且中心为G的图案。不确定如何匹配四边都有相同臂长的G的图案。感谢您的回复。

Answer 1

据我所知，正则表达式在一维数组上使用时很有用，而不是像你的问题那样在二维数组上使用。

所以我倾向于说使用正则表达式可能不是一个好的方法…我尝试将固定模式与+模式中的G位置进行匹配，每个手臂有1个单位长：

B = 0
G = 1

matrix = (
    (B, G, B, B, G, B),
    (G, G, G, G, G, G),
    (B, G, B, B, G, B),
    (B, G, B, B, G, B),
    (G, G, G, G, G, G),
    (B, G, B, B, G, B),
)

pattern = (
    (B, G, B),
    (G, G, G),
    (B, G, B),
)

def getMatrixSize(mat):
    # Return (width, height)
    return (len(mat[0]), len(mat))

def findPattern(mat, pat):
    matches = []

    matsize = getMatrixSize(mat)
    patsize = getMatrixSize(pat)

    for y in range(matsize[1] - patsize[1] + 1):
        for x in range(matsize[0] - patsize[0] + 1):

            submat_cols = mat[y:y+patsize[1]]
            for i in range(patsize[1]):
                submat_row = submat_cols[i][x:x+patsize[0]]
                if submat_row != pat[i]:
                    i = -1
                    break

            if i > 0:
                matches.append((x, y))

    return matches

# Run the thing
print(findPattern(matrix, pattern))

我的想法是在矩阵上滑动模式，并在矩阵的每个子段上比较模式的每个段……

对于某种模式，这是一种“硬编码”。

但你可以从这里开始，尝试让模式进化(不同的臂长)

注意：：问题是使用正则表达式，你不能做像\w{A}.\w{A}这样的事情，A将是一个共享的计数器……至少我从来没有听说过它。

Answer 2

我会选择使用类似矩阵的方法来解决这个问题，而不是使用正则表达式。在您的示例中，我假设l是一个类似列表的结构，包括数据的每一行。

import pandas as pd
import numpy as np


def findPlusSigh(data, pattern):
    # Find indexes which match the pattern
    data = data == pattern
    pattern_index = data.nonzero()
    # List to store result
    result = []
    center_index = []
    # Loop over each matched element
    for i, j in zip(pattern_index[0], pattern_index[1]):
        # Look for arm length from 1 to 100
        for m in range(1, 100):
            try:
                # Break the loop if it's out of range of the data
                if m > i or m > j:
                    break
                # check the matched pattern in 4 directions, i.e., up, left,
                # down, right
                if (all(data[([i-m, i, i+m, i], [j, j-m, j, j+m])])):
                    pass
                else:
                    break
            except:
                break
        # If arm length >= 1
        if m > 1:
            # When the loop breaks, m is 1 more than the actual arm length
            # So we need to minus 1
            # Record the arm length
            result.append(m-1)
            # Record the center index
            center_index.append((i, j))
    return(result, center_index)

# Test data
l = ['BGBBGB', 'GGGGGG', 'BGBBGB', 'GGGGGG', 'BGBBGB', 'BGBBGB']
# The pattern you are matching
pattern = 'G'
# Convert the n by m data into an array where each element is a character
data = np.array([np.array(list(x)) for x in l])
result, center_index = findPlusSigh(data, pattern)
for i, j in zip(result, center_index):
    print ("Data center (Row {}, Column{}) has a plus sign length of {}".format(
        j[0]+1, j[1]+1, i))