在已经包含通配符的字符串上进行模式匹配

Question

在已经包含通配符的字符串上进行模式匹配

c#regexwildcard

8

我有一个场景，想在已经包含通配符的字符串上使用通配符模式进行搜索。简而言之，我会说这是一种双向模式匹配要求。

输入和模式字符串都可以包含以下任意一个或两个通配符 - ?表示一个字符，%表示零个或多个字符。假设它们是输入和模式字符串中唯一允许的2个通配符。

例如：

bool IsMatch(string input, string pattern) // 如果输入字符串与模式匹配则返回True，否则返回False。

IsMatch("XYZ%", "?Y%") // 应返回True IsMatch("YY?", "?Y%") // 应返回True - 输入字符串中的最后一个字符要求单个字符匹配，而模式匹配Y后的0个或多个字符（这也意味着它包括单个字符匹配）

IsMatch("X123", "?Y%") // 应返回False - 输入字符串中缺少模式期望的Y

IsMatch("?Y%", "?Y%")// 应返回True IsMatch("%", "?Y%")// 应返回True - 输入字符串有一个通配符%，表示任意数量的任意字符。在某种程度上，它本身就代表了任意大小的任何内容。

我能够找到涉及非通配符字符串的通配符模式匹配的文章（例如：正则表达式）。我正在寻找关于算法的指针/思路，因为我开始尝试写下它时，发现这种匹配变得困难了。感谢您的建议。

- PKumar

你如何确定这些匹配？X和Y匹配，%（通常在数据库中使用但不在正则表达式中使用的通配符）与输入的其余部分（Z5％）匹配，但在此之后，您的搜索模式要求一个HH？123，而该输入中没有找到。或者你认为这些是由你输入末尾的通配符匹配的吗？这使得你的问题变成了“是否有一个输入可以同时匹配这些正则表达式？”这不容易回答。 - SQB

1

@iamnotmaynard 是的，我也担心这点。就像我所说的那样，这使得真正的问题是“这两个正则表达式是否存在任何可以匹配的输入？” - SQB

@SQB 输入字符串存储在数据库中，我会提取并与搜索/模式字符串进行比较。期望的是，在我的应用程序UI中，如果用户使用此搜索/模式字符串进行搜索，我的应用程序（C＃.net）应该匹配从数据库中获取的输入字符串，并将此输入字符串显示给用户。 - PKumar

你需要清晰地定义你所使用的模式匹配语言（或者指向在线资源），并为每个模式提供一些搜索输入，以及解释为什么它被认为是匹配或不匹配。只有这样，任何人才能告诉你是否可以使用正则表达式完成此任务。 - Phil Perry

@SQB 是正确的。回答这个[真正的]问题的一种方法是将其中一种模式语言转换为另一种语言，然后对两种模式进行词法分析。这远非万无一失 - 但你正在问一个非常难回答的问题。 - Sam Axe

显示剩余5条评论

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- hawk · Accepted Answer

正如我在评论中所写的，对于最一般的情况，您需要创建两个表达式的最小确定有限状态自动机并比较这两个自动机。话虽如此，您的问题可能有一个暴力/简单粗暴的解决方案。

根据您的示例，似乎您想知道输入/模式是否与另一个生成的所有字符串匹配。

IsMatch("XYZ%", "?Y%") // returns true because ?Y% matches a superset of strings matched by "XYZ%"
IsMatch("%", "?Y%") // returns true because "%" matches a superset of "?Y%"

只要满足以下条件：

您只使用 % 和 ? 运算符
您的输入和模式字符串相对较短，具体来说，% 的出现次数不到 20 次左右。

您可以检查 input 是否确实与由 pattern 生成的字符串子集匹配。基本思想是，您为 input 生成一组代表字符串，并使用您喜欢的正则表达式引擎将每个字符串与模式匹配。如果所有代表都匹配，则 input 匹配 pattern 的子集。这种 IsSubset 算法可以描述如下：

let c = some character not in `pattern` (lexically speaking)
let searchString = replace all occurences of '?' in input with c
add searchString to setOfSearchStrings
foreach occurence of '%' in input
    foreach str in setOfSearchStrings
        replace str with two strings - {str with c in place of '%', str without the '%'}

foreach str in setOfSearchStrings
   if str doesn't "regex" match with pattern 
       return false

return true

例如，如果输入为?X％YZ％，并且“pattern”不包含字符A，则生成的列表将是：

AXYZ AXYZA AXAYZ AXAYZA

很容易看出，此列表中的字符串数量为2^n，其中n是输入中“％”的数量。

同样，很容易交换参数顺序并找出另一种方式的关系。因此，在实际效果中，您的

IsMatch(input,pattern) = IsSubset(input,pattern) || IsSubset(pattern,input)