Соответствующие последовательности токенов

Question

У меня есть набор из n токенов (например, a, b, c), распределенных среди множества других токенов.Я хотел бы знать, все ли члены моего набора находятся в пределах определенного числа позиций (размер окна).Мне пришло в голову, что может быть возможно написать RegEx для захвата этого состояния, но точный синтаксис ускользает от меня.

          11111
012345678901234
ab ab bc  a cba

В этом примере, учитывая размер окна = 5, я хотел бы соответствовать1004 * в позициях 12-14 и abc в позициях 3-7.

Есть ли способ сделать это с помощью RegEx или есть какой-то другой вид грамматики, который я могу использовать для захвата этой логики?

Я надеюсь реализовать это на Java.

Answer 1

Вот регулярное выражение, которое соответствует 5-буквенным последовательностям, которые включают все «a», «b» и «c»:

(?=.{0,4}a)(?=.{0,4}b)(?=.{0,4}c).{5}

Итак, хотя в основном совпадают любые 5 символов (с .{5}), существует три предварительных условия, которым должны соответствовать соответствия. Каждый из них требует наличия одного из токенов / букв (до 4 символов, за которыми следует «а» и т. Д.). (?=X) соответствует «X с положительным прогнозом нулевой ширины», где нулевая ширина означает, что позиция символа не изменяется при сопоставлении.

Делать это с регулярными выражениями довольно медленно, хотя ... Вот более прямая версия (кажется, примерно в 15 раз быстрее, чем при использовании регулярных выражений):

public static void find(String haystack, String tokens, int windowLen) {
    char[] tokenChars = tokens.toCharArray();
    int hayLen = haystack.length();

    int pos = 0;
    nextPos:
    while (pos + windowLen <= hayLen) {
        for (char c : tokenChars) {
            int i = haystack.indexOf(c, pos);
            if (i < 0) return;

            if (i - pos >= windowLen) {
                pos = i - windowLen + 1;
                continue nextPos;
            }
        }

        // match found at pos
        System.out.println(pos + ".." + (pos + windowLen - 1) + ": " + haystack.substring(pos, pos + windowLen));
        pos++;
    }
}

Answer 2

Эта протестированная Java-программа имеет закомментированное регулярное выражение, которое помогает:

import java.util.regex.*;
public class TEST {
    public static void main(String[] args) {
        String s = "ab ab bc  a cba";
        Pattern p = Pattern.compile(
            "# Match 5 char sequences containing: a and b and c\n" +
            "(?=[abc])     # Assert first char is a, b or c.\n" +
            "(?=.{0,4}a)   # Assert an 'a' within 5 chars.\n" +
            "(?=.{0,4}b)   # Assert an 'b' within 5 chars.\n" +
            "(?=.{0,4}c)   # Assert an 'c' within 5 chars.\n" +
            ".{5}          # If so, match the 5 chers.", 
            Pattern.COMMENTS);
        Matcher m = p.matcher(s);
        while (m.find()) {
            System.out.print("Match = \""+ m.group() +"\"\n");
        } 
   }
}

Обратите внимание, что в ваших тестовых данных есть еще одна действительная последовательность S9:13" a cb" (до S12:14"cba". Предполагая, что вы этого не сделаличтобы соответствовать этому, я добавил дополнительное ограничение для его фильтрации, которое требует, чтобы окно из 5 символов начиналось с a, b или c.

Вот вывод изскрипт:

Match = "ab bc"
Match = "a cba"

Answer 3

Что ж, одна из возможностей (хотя и совершенно неосуществимая) заключается в простом сопоставлении со всеми перестановками:

abc..|ab.c.|ab..c| .... etc.

Это можно несколько раз учесть:

ab(c..|.c.|..c)|a.(bc.|b.c .... etc.

Я не уверен, что вы можете добиться большего успеха с помощью регулярных выражений.

Answer 4

Pattern p = Pattern.compile("(?:a()|b()|c()|.){5}\\1\\2\\3");
String s = "ab ab bc  a cba";
Matcher m = p.matcher(s);
while (m.find())
{
  System.out.println(m.group());
}

выход:

ab bc
 a cb

Это вдохновлено рецептом № 5.7 в Поваренная книга регулярных выражений . Каждая обратная ссылка (\1, \2, \3) действует как утверждение нулевой ширины, указывая на то, что соответствующая группа захвата участвовала в совпадении, даже если сама группа не использовала никаких символов.

Авторы предупреждают, что этот прием основан на поведении, которое недокументировано в большинстве разновидностей. Он работает на Java, .NET, Perl, PHP, Python и Ruby (оригинал и Oniguruma), но не на JavaScript или ActionScript.