Как обнаружить отклонения в последовательности от шаблона?

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

Вы смотрели на цепочки Маркова?http://en.wikipedia.org/wiki/Markov_chain - звучит так, как будто вы хотите неожиданных переходов.возможно также скрытые марковские модели http://en.wikipedia.org/wiki/Hidden_Markov_Models

Answer 2

Найдите реализацию регулярных выражений с открытым исходным кодом и добавьте ловушку для возврата / установки / печати / сохранения индекса, в котором она не работает, если данное сравнение не соответствует.Кроме того, напишите свой собственный движок RE (не для слабонервных), чтобы он делал именно то, что вы хотите!

Answer 3

При совпадении с вашим вводом механизм регулярных выражений имеет информацию о местоположении несоответствия - однако он может не предоставлять его таким образом, чтобы вы могли легко получить к нему доступ.

Рассмотрим, например, DFA, реализующий выражение. Он выбирает символы последовательно, сопоставляя их с ожиданием, и вас интересует точка в последовательности, где нет действительного соответствия.

Другие реализации могут идти вперед и назад, и вам будет интересен максимальный адрес любого символа, который был выбран.

В Java это может быть сделано путем предоставления реализации CharSequence для

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

, где методы доступа отслеживают максимальный индекс.

Хотя я этого не пробовал. И это также не поможет вам классифицировать ошибки.