18

编辑：哎呀！大承认，我搞砸了?infnmatch模式语法的定义，似乎已经提出（并且可能解决了）一个更困难的问题，它的行为就像.?在正则表达式中一样。当然，它实际上应该表现得像.正则表达式（只匹配一个字符，而不是零或一）。这反过来意味着我最初的减少问题的工作足以解决（现在相当无聊的）原始问题。解决更难的问题仍然很有趣。有时间我可能会写出来。

从好的方面来说，这意味着像 2way/SMOA 针分解这样的东西更有可能适用于这些模式，这反过来可能会产生比最初想要的O(n)甚至更好的O(n/m)性能。

在问题标题中，设m图案/针n的长度和与之匹配的字符串的长度。

我对这个问题很感兴趣，因为我见过/使用的所有算法要么性能不佳，要么由于回溯而可能存在堆栈溢出漏洞，或者需要动态内存分配（例如，对于 DFA 方法或只是避免在调用上进行回溯stack），因此如果程序fnmatch用于授予/拒绝某种访问权限，则失败情况也可能很危险。

我愿意相信正则表达式匹配不存在这样的算法，但文件名模式语言比正则表达式简单得多。我已经将问题简化到可以假设模式不使用*字符的程度，并且在这个修改后的问题中，您不是匹配整个字符串，而是在字符串中搜索模式的出现（如子字符串匹配问题）。如果进一步简化语言并去掉?字符，语言只是由固定字符串和括号表达式的串联组成，这可以很容易地在O(mn)时间和 O(1) 空间上匹配，也许可以改进为O(n)如果 2way 和 SMOA 子字符串搜索中使用的针分解技术可以扩展到这种括号模式。然而，天真地每个都?需要使用或不?使用字符的试验，带来一个时间因素，2^q即模式中的字符q数。?

任何人都知道这个问题是否已经解决，或者有解决它的想法？

注意：在定义 O(1) 空间时，我使用的是Transdichotomous_model。

注 2：本网站详细介绍了我引用的 2way 和 SMOA 算法：http ://www-igm.univ-mlv.fr/~lecroq/string/index.html

4

5 回答 5

2

您是否研究re2过 Russ Cox（来自 Google）的正则表达式引擎？

它是一个基于确定性有限自动机的正则表达式匹配引擎，不同于通常的实现（Perl、PCRE）使用回溯来模拟非确定性有限自动机。具体设计目标之一是消除您提到的灾难性回溯行为。

它不允许某些 Perl 扩展，例如搜索模式中的反向引用，但对于 glob 匹配，您不需要它。

我不确定它是否特别保证O(mn)了时间和O(1)内存限制，但它足以在存在时运行 Google 代码搜索服务。

至少看看里面看看它是如何工作的应该很酷。Russ Cox 写了三篇关于re2一、二、三的文章，并且代码是开源的。re2

于 2012-04-27T08:22:17.757 回答
1

编辑：哎呀！大承认，我搞砸了?infnmatch模式语法的定义，似乎已经解决了一个更困难的问题，它的行为就像.?在正则表达式中一样。当然，它实际上应该表现得像.正则表达式（只匹配一个字符，而不是零或一）。这反过来意味着我最初的减少问题的工作足以解决（现在相当无聊的）原始问题。解决更难的问题仍然很有趣。有时间我可能会写出来。

更难的问题的可能解决方案如下。

我已经计算出似乎是O(log q)空间中的解决方案（q模式中问号的数量在哪里，因此q< m）以及不确定但似乎优于指数的时间。

首先，快速解释一下问题的减少。首先在每个处打破模式*；它分解为（可能为零长度）初始和最终组件，以及两侧两侧为 a 的许多内部组件*。这意味着一旦我们确定初始/最终组件是否匹配，我们可以应用以下算法进行内部匹配：从最后一个组件开始，在字符串中搜索从最新偏移量开始的匹配。这使得最可能的“干草堆”字符可以自由地匹配早期的组件；如果它们不是全部都需要，那没问题，因为*干预的事实允许我们以后根据需要扔掉尽可能多的东西，所以尝试“使用更多?最后一个组件的标记”或找到它的较早出现。然后可以对每个组件重复此过程。请注意，在这里我强烈利用了fnmatch表达式中唯一的“重复运算符”是*匹配的事实任何字符出现零次或多次。同样的减少不适用于正则表达式。

解决了这个问题，我开始寻找如何有效地匹配单个组件。我允许时间因子为n，这意味着可以在字符串中的每个可能位置开始尝试，如果失败则放弃并移至下一个位置。这是我们将采用的一般程序（还没有类似 Boyer-Moore 的技巧；也许以后可以引入）。

对于给定的组件（不包含*，仅包含文字字符、与给定集合中的一个字符完全匹配的括号和?），它具有可以匹配的最小和最大长度字符串。如果省略所有?字符并将括号表达式计为一个字符，则最小值是长度，如果包含?字符，则最大值是长度。在每个位置，我们将尝试模式组件可以匹配的每个可能的长度。这意味着我们进行q+1试验。对于以下解释，假设长度保持固定（它是最外层循环，在即将引入的递归之外）。这也修复了我们将要与此时的模式进行比较的字符串的长度（以字符为单位）。

现在这是有趣的部分。我不想遍历所有可能使用?/不使用哪些字符的组合。迭代器太大而无法存储。所以我作弊。我将模式组件分成两个“半”，L并且R，其中每个包含一半的?字符。然后我简单地迭代使用多少个?字符的所有可能性L（从 0 到将根据上面固定的长度使用的总数），然后也确定?使用的字符数。R这也将我们尝试匹配的字符串划分为将与 patternL和 pattern匹配的部分R。

现在，我们将检查带有字符的模式组件是否匹配特定的固定长度字符串的问题减少为检查带有字符的模式组件是否匹配特定的较小固定长度q ?字符串的两个实例。q/2 ?应用递归。并且由于每一步都将?涉及的字符数减半，因此递归级别的数量为log q.

于 2012-04-27T23:17:33.483 回答
0

好的，这就是我解决问题的方法。

  1. 尝试将模式的初始部分匹配到*字符串的第一个部分。如果这失败了，保释。如果成功，则丢弃模式和字符串的初始部分；我们已经完成了他们的工作。（如果我们在点击 a 之前点击了模式的结尾，那么*如果我们也到达了字符串的结尾，我们就有了一个匹配项。）

  2. 一直跳到模式的结尾（最后一个 之后的所有内容*，如果模式以 a 结尾，则可能是零长度模式*）。计算匹配它所需的字符数，并从字符串末尾检查那么多字符。如果他们不匹配，我们就完成了。如果它们匹配，则丢弃模式和字符串的这个组件。

  3. 现在，我们留下了一个（可能是空的）子模式序列，所有这些子模式的两侧都有*'s. 我们尝试在字符串的剩余部分中按顺序搜索它们，为每个匹配获取第一个匹配项，并在匹配项中丢弃字符串的开头。如果我们以这种方式找到每个组件的匹配项，我们就有了整个模式的匹配项。如果任何组件搜索失败，则整个模式将无法匹配。

该算法没有递归，并且仅在字符串/模式中存储有限数量的偏移量，因此在跨二分模型中它是 O(1) 空间。第 1 步是 O(m) 时间，第 2 步是 O(n+m) 时间（或者 O(m)，如果我们假设输入字符串长度已知，但我假设一个 C 字符串），并且步骤3 是（使用朴素搜索算法）O(nm)。因此，整个算法在时间上是 O(nm)。可以将第 3 步改进为 O(n)，但我还没有尝试过。

最后，请注意最初的更难的问题可能仍然有用解决。那是因为我没有考虑多字符整理元素，大多数实现正则表达式的人往往会忽略这些元素，因为它们很难正确正确，并且没有标准 API 可以与系统语言环境交互并获取必要的信息来获取他们。但话虽如此，这里有一个例子：假设ch是一个多字符整理元素。然后[c[.ch.]]可以消耗 1 或 2 个字符。我们又回到了需要我在原始答案中描述的更高级的算法，我认为这需要O(log m)空间，而且可能比O(nm)时间还多（我猜O(n²m)最好）。目前我对实现多字符整理元素支持没有兴趣，但它确实留下了一个很好的悬而未决的问题......

于 2012-05-02T04:16:02.927 回答
0

您可以创建两个字符串的哈希值，然后进行比较。哈希计算将在 O(m) 中完成，而搜索在 O(m + n) 中完成

您可以使用类似这样的方法来计算 s[i] 是字符的字符串的哈希值

s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1]

正如您所说，这是用于文件名匹配的，您不能在字符串中有通配符的情况下使用它。祝你好运！

于 2012-04-27T07:37:19.357 回答
0

我的感觉是这是不可能的。

虽然我不能提供一个无懈可击的论点，但我的直觉是，您将始终能够构建包含 q=Theta(m)?字符的模式，在某种意义上，算法需要考虑所有 2 ^q 个可能性。这将需要 O(q)=O(m) 空间来跟踪您当前正在查看的可能性。例如，NFA 算法使用这个空间来跟踪它当前所处的状态集；蛮力回溯方法使用空间作为堆栈（为了增加伤害，除了空间的 O(q) 之外，它还使用 O(2^q) 时间）。

于 2012-04-27T12:09:14.070 回答