3

我想检测一系列动作偏离给定模式的段落，并且无法找出一个聪明的解决方案来做到这一点，尽管问题听起来很简单。

该模式的目的是描述某种正常的序列。更具体：“动作序列中应该或不应该包含哪些动作以及以什么顺序？” 然后我想将动作序列与模式匹配并检测偏差及其位置。

我的第一种方法是使用正则表达式来做到这一点。这是一个例子：

Example 1:
Pattern: A.*BC
Sequence: AGDBC (matches)
Sequence: AGEDC (does not match)

Example 2:
Pattern: ABCD
Sequence: ABD (does not match)
Sequence: ABED (does not match)
Sequence: ABCED (does not match)

Example 3:
Pattern: ABCDEF
Sequence: ABXDXF (does not match)

使用正则表达式很容易检测到错误，但检测不到错误发生的位置。我的方法是连续删除最后一个正则表达式块，直到我可以在序列中找到模式。然后我会知道最后正确的动作，并且至少找到了第一个偏差。但这对我来说似乎不是最好的解决方案。此外我不能所有的偏差。

我心中的其他想法是使用状态机，像 ANTLR 这样的命令工具。但我不知道他们是否能解决我的问题。我想检测遗漏和委托错误，并让用户有可能创建自己的模式。你知道这样做的好方法吗？

4

3 回答 3

0

你看过马尔可夫链吗？ http://en.wikipedia.org/wiki/Markov_chain - 听起来你想要意想不到的过渡。也许还有隐藏的马尔可夫模型http://en.wikipedia.org/wiki/Hidden_​​Markov_Models

于 2011-07-23T22:56:14.717 回答
0

在匹配您的输入时，正则表达式引擎会提供有关不匹配位置的信息——但它可能无法以您可以轻松访问它的方式提供它。

考虑例如实现表达式的 DFA。它按顺序获取字符，将它们与期望匹配，并且您对序列中没有有效匹配的点感兴趣。

其他实现可能会来回切换，您可能会对获取的任何字符的最大地址感兴趣。

在 Java 中，这可以通过提供 CharSequence 实现来完成

   java.util.regex.Pattern.matches(String regex, CharSequence input)

其中访问器方法跟踪最大索引。

不过，我还没有尝试过。它也不能帮助您对错误进行分类。

于 2011-05-08T12:37:29.620 回答
0

找到一个正则表达式的开源实现，如果给定的比较不匹配，则添加一个挂钩以返回/设置/打印/保存失败的索引。或者，编写您自己的 RE 引擎（不适合胆小的人），这样它就会完全按照您的意愿行事！

于 2012-02-09T00:50:05.473 回答