3

考虑以下简单的数据结构：

data Step =
  Match Char |
  Options [Pattern]

type Pattern = [Step]

这与一个小功能一起使用

match :: Pattern -> String -> Bool
match [] _ = True
match _  "" = False
match (s:ss) (c:cs) =
  case s of
    Match   c0 -> (c == c0) && (match ss cs)
    Options ps -> any (\ p -> match (p ++ ss) (c:cs)) ps

这里发生的事情应该很明显；a根据包含的步骤，Pattern要么匹配给定，要么不匹配。String每个Step要么匹配单个字符 ( Match)，要么由可能的子模式列表组成。（注意：子模式不一定是等长的！）

假设我们有这样的模式：

[
  Match '*',
  Options
    [
      [Match 'F', Match 'o', Match 'o'],
      [Match 'F', Match 'o', Match 'b']
    ],
  Match '*'
]

此模式匹配两个可能的字符串，*Foo*并且*Fob*. 显然我们可以将其“优化”为

[Match '*', Match 'F', Match 'o', Options [[Match 'o'], [Match 'b']], Match '*']

我的问题：我该如何编写函数来做到这一点？

更一般地说，一个给定的Options构造函数可能有任意数量的子路径，它们的长度完全不同，有些有共同的前缀和后缀，有些没有。甚至可以有空的子路径，甚至可以做类似的事情Options []（这当然是无操作的）。我正在努力编写一个可以正确减少所有可能输入的函数......

4

1 回答 1

4

粗略检查一下，这看起来就像您定义了一个不确定的有限状态自动机。NFA 最初是由 Michael O. Rabin 和所有人——Dana Scott 定义的，他也给我们带来了很多其他东西！

这是一个自动机，因为它是由步骤构建的，它们之间有基于接受状态的转换。在每个步骤中，您都有许多可能的转换。因此，您的自动机是不确定的。现在你想优化它。优化它的一种方法（不是您要求的方式，而是相关的方式）是消除回溯。您可以通过将到达状态的方式与状态本身结合起来来实现这一点。这被称为 powerset 构造：http ://en.wikipedia.org/wiki/Powerset_construction

维基百科的文章实际上非常好——在像 Haskell 这样的语言中，我们可以首先定义完整的 powerset DFA，然后懒惰地遍历所有真正的路径以“去除”大部分无法访问的垃圾。这让我们得到了一个不错的 DFA，但不一定是最小的 DFA。

如文章底部所述，我们可以使用 Brzozowski 的算法，翻转所有箭头并获得描述从结束状态到初始状态的新 NFA。现在，如果我们要最小化 DFA，我们需要从那里再次回到 DFA，然后翻转箭头并再次执行所有操作。这不一定是最快的方法，但它很简单，并且在很多情况下都足够好用。还有很多更好的算法可用：http ://en.wikipedia.org/wiki/DFA_minimization

为了最小化 NFA，有多种方法，但问题通常是 np-hard，所以你必须选择一些毒药:-)

当然，所有这些都是假设您拥有完整的 NFA。如果您有相互递归的定义，那么您可以在其自身“内部”放置一个模式，您肯定会这样做。也就是说，您需要使用巧妙的技巧来恢复显式共享结构，以便以这种形式开始使用 NFA——否则您将永远循环。

如果您插入“不共享”规则 - 即您的 NFA 的有向图不仅是无环的，而且分支永远不会“合并回来”，除非您退出“选项”集，那么我想简化是非常重要的更直接的事情，只是“分解”常见的字符。由于这涉及思考而不仅仅是提供参考，所以我暂时将其留在那里，只是指出这篇文章可能会以某种方式引起人们的兴趣： http: //matt.might.net/articles/parsing-with-derivatives/

ps

“分解”解决方案的尝试是具有以下类型的函数：

factor :: [Pattern] -> (Maybe Step, [Pattern])
factor = -- pulls out a common element of the pattern head, should one exist. shallow.

factorTail = -- same, but pulling out of the pattern tail

simplify :: [Pattern] -> [Pattern]
simplify = -- remove redundant constructs, such as options composed only of other options, which can be flattened out, options with no elements that are the "only" option, etc. should run "deep" all levels down.

现在您可以从最低级别开始并循环(simplify . factor)，直到您没有新的因素。然后使用(simplify . factorTail). 然后再上一层，做同样的事情。如果你不能将它“欺骗”成一个非最小的解决方案，我不会感到震惊，但我认为在大多数情况下它会很好地工作。

更新：这个解决方案没有解决的问题是您拥有的东西，例如 Options ["--DD--", "++DD++"] （将字符串读取为匹配列表），因此您在两个头部都有不常见的结构和尾巴，但不在中间。在这种情况下，更通用的解决方案是提取列表中所有匹配项之间最不常见的子字符串，并将其用作“框架”，并在不同的部分插入选项。

于 2013-05-28T04:41:29.833 回答