7

我正在尝试在表示为字符串的 2D 矩阵中搜索模式。如下图：

// horizontal line
String pat1 =
    "............." +
    "............." +
    "............." +
    "....XXXX....." +
    "............." +
    ".............";

// vertical line
String pat2 =
    "............." +
    "......X......" +
    "......X......" +
    "......X......" +
    "......X......" +
    ".............";

搜索第一个模式将是微不足道的，正则表达式将类似于：

X+

在第二种情况下，它有点棘手但可行，因为我知道矩阵的列数和行数：

(X.{`WIDTH - 1`})+

当我遇到问题以提出正确的正则表达式时，我正在尝试找出一种识别以下模式的方法：

// fixed but unknown number of columns
String pat3 =
    "............." +
    ".....XXX....." +
    ".....XXX....." +
    ".....XXX....." +
    ".....XXX....." +
    ".............";

// variable number of columns
String pat4 =
    "............." +
    ".....XXX....." +
    "....XXXXX...." +
    "...XXXXXXX..." +
    ".....XXX....." +
    ".............";

我正在寻找的是一种创建正则表达式模式的方法，相当于：

(X.{`WIDTH - PREVCOUNT`})+

最后一个匹配模式的长度在哪里PREVCOUNT（我知道我会丢失 pat4 中第 4 行的第一个 X，但我可以忍受）。我知道正则表达式中有前瞻，但我想知道我想要实现的目标是否可能。即使有可能，我也担心使用前瞻对性能的影响，因为我不完全了解它们在内部是如何工作的。

有没有办法通过单个正则表达式验证来做到这一点，还是我必须逐行搜索然后尝试查看 X 是否都是连续的？

编辑：作为澄清，我正在尝试搜索 X 的“斑点”。只要跨列/行有连续的 X，它就可以被认为属于一个 blob。几个例子：

String blob1 =
    "............." +
    "......XX....." +
    "....XXXX....." +
    "...XXXXX....." +
    ".....XXX....." +
    ".............";

String blob2 =
    "............." +
    ".....XXX....." +
    "....XXXXX....." +
    "...XXXXXXX..." +
    "....XXXXX...." +
    ".....XXX.....";


String blob3 =
    "............." +
    ".....XXX....." +
    ".....XXX......" +
    ".....XXX....." +
    "............." +
    ".............";


String notblob =
    "............." +
    "..XXX........" +
    "......XXX....." +
    "..XXX........." +
    ".............." +
    ".............";

我的解决方案不需要精确，因此我尝试使用可能很糟糕的正则表达式方法。

4

3 回答 3

2

这是无法使用正则表达式解决的。

基本上，您可以这样定义一个矩阵：

0^k1 X^l1 0^m1
0^k2 X^l2 0^m2
0^k3 X^l3 0^m3

000XX000
 ^  ^ ^
 k  l m

其中，0^a 表示“字符 '0' 重复 a 次”，
k 表示 X 之前的 0 重复
l 表示 X 的重复
m 表示 X
ki + li + mi = row_width 之后的 0 重复，对于任何 i

现在，您的 blob 标准是这样的：

mi + k(i+1) < row_width
ki + m(i+1) < row_width
these two conditions should meet for any i

正则语言无法匹配这样的模式，它们没有记忆，因此没有正则表达式解决您的问题。

一个适当的解决方案将涉及连接组件计算有多少单独的组件。

于 2013-12-19T11:31:09.970 回答
1

我认为一个优雅的解决方案是首先抑制水平和垂直的所有单 X 序列，例如：

String blob = ".....";
blob.replaceAll("([^X])X([^X])", "$1.$2")
    .replaceAll("([^X].....)X(.....[^X])","$1.$2");

然后所有剩余的至少 2 个 X 的序列都是 blob。请注意，要克服 sdanzig 提到的相同问题，您应该首先使用非 Xes 的“边界”“扩展”blob。

于 2013-12-16T11:00:44.020 回答
0

我想我知道你在这里想要做什么。您定义的“prevcount”信息不足以匹配模式。您必须考虑“下一个宽度”以确定要检查的点数。但是，我不确定您是否真的在验证微不足道的模式。X+ 也会连续匹配 5 个 X。在您的第二个模式中，第一行或最后一行可能是两个 X，您不会检测到这一点。

也就是说，这是一种使用 pat3 提供类似验证的方法：

(X{3}.{`WIDTH-3`})+

我可能通过重复 X 模式打破了另一个禁忌，但你需要这样做以使重复模式与“X-block”的开始和停止保持一致。

pat4 更棘手。没有真正的方法可以保留一次检查一行的验证顺序。你可以这样做：

(X{3}.{`WIDTH-4`}|X{5}.{`WIDTH-6`}|X{5}.{`WIDTH-6`}|X{3}.{`WIDTH-5`})+

但是，您将很容易在行切换时验证矩阵，并且 X 块的每一侧上的点都会发生变化以适应。但是，您可以尝试一次检查所有行：

(X{3}.{`WIDTH-4`}X{5}.{`WIDTH-6`}X{5}.{`WIDTH-6`}X{3}.{`WIDTH-5`})

这不会对性能产生任何额外的影响。它可能会更有效，因为您只会产生启动正则表达式模式编译+匹配一次的开销。

琐碎的旁注：如果您将矩阵的宽度用于多行字符串，它将不起作用。您需要添加一个，以说明换行符。然后你需要确保你的“。” 也捕获换行符。在 Java 中，您可以为此使用 Pattern.DOTALL。

于 2013-11-03T06:33:33.663 回答