用于用通配符验证参考文件的算法

Question

我有一个像下面的文件，我想验证正确性。该文件用作处理某些数据的参考文件。我将输入数据与该文件的COLA，COLB和COLC匹配，并从顶部返回第一场比赛的OUTA。通配符'*'匹配任何东西。例如，如果我的输入数据具有X4 Y2 Z3，则将从文件中返回13。

Seq  ColA  ColB  ColC  OutA
1    X1    Y1    Z1    10
2    X2    Y2    *     11
3    X3    *     Z2    12
4    *     Y2    Z3    13
5    *     *     Z4    14
6    *     Y3    Z4    15
7    *     *     *     16

现在，该文件可以具有一些从未使用或无法访问的条目。例如，如果我收到X9 Y3 Z4作为输入，它将与第5行匹配，尽管第6行也与我的输入匹配，但永远不会看第6行。如果我们交换第5行和第6行的位置，则可以按预期工作。我想在实际过程运行之前找到这种无法实现的记录。

关于如何在文件中找到此类条目的任何想法。我正在寻找算法。请注意，在此示例中，我减少了列和行的数量。实际文件有大约10列和50行。

Answer 1

假设通配符与每个字符串匹配（特别是对于每列，存在一个有效的符号，并不以字面形式出现），则足以检查每对行以查看是否是否第一匹配第二次匹配的超集。当且仅在每列，第二行具有字面意义，然后第一行具有相同的字面或通配符，而第二行具有通配符时，则是这种情况。

Answer 2

我将采用大多数Web服务器将请求URL与控制器匹配的方法。他们完全采用了最适合资源URL的控制器。

/users
/users/{userId}

如果您看到像/users/2这样的请求，当然，您会更喜欢第二个资源控制器。

现在回到您的问题，Varibale部分（您想匹配最好）与*的使用有关。如果您想实现最佳拟合度，则必须对所有条目进行排序，即*量最低的条目，底部最高的条目。（因为您从上到下迭代并在第一场比赛中返回。）

但是，对于所有具有相同数量*的条目，可以有utliple拟合行，并且有 no 可以防止这种情况。您必须决定，这是一个。

一个简单的示例证明了这一点：

Seq  ColA  ColB  ColC  OutA
20   X3    *     Z3    12
21   *     Y2    Z3    13

您如何处理X3, Y2, Z3？输出不清楚，将取决于排序顺序。我的广告：使用稳定的排序算法使输出可预测。

用于实施，只需创建一个自定义比较器，该比较器计算使用的*的数量。

快速查看List#sort还表明，已经使用了稳定的排序算法，因此您不必担心它。（参考）

此实现是一种稳定，自适应，迭代的Mergesort [...]