如何从模式中检测序列中的偏差？

Question

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

该模式的目标是以某种方式描述一个正常的序列。更具体的说：“行动顺序和顺序中应该包含或不应该包含哪些行为？”然后，我想根据模式匹配动作序列并检测偏差及其位置。

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

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这样的订购工具。但我不知道他们是否能解决我的问题。 我想检测遗漏和佣金错误，并给予用户创建自己的模式的可能性。你知道这样做的好方法吗？

Answer 1

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

考虑例如执行该表达式的DFA。它按顺序提取字符，将它们与期望进行匹配，并且您对序列中没有有效匹配的位置感兴趣。

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

在Java中，这也可能会被提供一个实施的CharSequence做

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

在访问方法跟踪最大指数。

虽然我还没有尝试过。而且它也无助于你分类错误。

Answer 2

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

Answer 3

找到一个正则表达式的开源实现，并添加一个钩子来返回/设置/打印/保存失败的索引，如果给定的比较不匹配。或者，编写你自己的RE引擎（不适合心脏不好），这样它就可以完成你想要的东西！