2

他のトークンの束に分散されたn個のトークン（たとえば、a、b、c）のセットがあります。セットのすべてのメンバーが指定された数の位置（ウィンドウサイズ）内にあるかどうかを知りたいです。この状態をキャプチャするために正規表現を書くことが可能かもしれないと私は思いましたが、正確な構文は私にはわかりません。

          11111
012345678901234
ab ab bc a cba

cbaこの例では、ウィンドウサイズ= 5の場合、位置12〜14とabc位置3〜7で一致させたいと思います。

RegExでこれを行う方法はありますか、またはこのロジックをキャプチャするために使用できる他の種類の文法はありますか？

これをJavaで実装したいと思っています。

4

4 に答える 4

2

'a'、'b'、および'c'のすべてを含む5文字のシーケンスに一致する正規表現は次のとおりです。

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

したがって、基本的に任意の5文字（と.{5}）を一致させる一方で、一致が遵守しなければならない3つの前提条件があります。それらのそれぞれは、トークン/文字の1つが存在する必要があります（最大4文字の後に「a」などが続きます）。(?=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++;
    }
}
于 2011-04-30T01:18:03.390 に答える
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"

于 2011-04-30T04:14:13.830 に答える
1

ええと、1つの可能性（完全に非現実的なものではありますが）は、単にすべての順列と照合することです。

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

これはある程度因数分解できます：

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

正規表現でもっとうまくできるかどうかはわかりません。

于 2011-04-30T00:14:24.207 に答える
0 
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

これは、 Regular Expressions Cookbookのレシピ＃5.7に触発されています。各後方参照（、、\1）は\2、\3幅がゼロのアサーションのように機能し、グループ自体が文字を消費していなくても、対応するキャプチャグループが一致に参加したことを示します。

著者は、このトリックはほとんどのフレーバーで文書化されていない動作に依存していると警告しています。Java、.NET、Perl、PHP、Python、Ruby（オリジナルと鬼車）で動作しますが、JavaScriptやActionScriptでは動作しません。

于 2011-04-30T08:27:31.147 に答える