12

私は正規表現を知り始めたばかりですが、かなりの量の読書を行った (そしてかなり多くのことを学んだ) 後でも、この問題に対する適切な解決策を見つけることができませんでした。

はっきりさせておきますが、この特定の問題は正規表現を使用しない方が解決できることは理解していますが、簡潔にするために、正規表現を使用する必要があるとだけ言わせてください (信じてください。これを解決するためのより良い方法があることは知っています)。 ）。

これが問題です。各行の長さがちょうど 4 文字の大きなファイルが与えられました。

これは、「有効な」行を定義する正規表現です。

"/^[AB][CD][EF][GH]$/m"

英語では、各行の位置 0 に A または B、位置 1 に C または D、位置 2 に E または F、位置 3 に G または H のいずれかが含まれます。各行は正確に 4 文字になると想定できます。長いです。

私がやろうとしているのは、これらの行の 1 つを指定して、2 つ以上の一般的な文字を含む他のすべての行と一致させることです。

以下の例では、次のことを前提としています。

  1. $line常に有効な形式です
  2. BigFileOfLines.txt有効な行のみを含む

例：

// Matches all other lines in string that share 2 or more characters in common
// with "$line"
function findMatchingLines($line, $subject) {
    $regex = "magic regex I'm looking for here";
    $matchingLines = array();
    preg_match_all($regex, $subject, $matchingLines);
    return $matchingLines;
}

// Example Usage
$fileContents = file_get_contents("BigFileOfLines.txt");
$matchingLines = findMatchingLines("ACFG", $fileContents);

/*
 * Desired return value (Note: this is an example set, there 
 * could be more or less than this)
 * 
 * BCEG
 * ADFG
 * BCFG
 * BDFG
*/

それが機能することを私が知っている1つの方法は、次のような正規表現を使用することです(次の正規表現は「ACFG」でのみ機能します:

"/^(?:AC.{2}|.CF.|.{2}FG|A.F.|A.{2}G|.C.G)$/m"

これは問題なく動作し、パフォーマンスは許容範囲です。しかし、それについて気に$lineなるのは、特定のパラメーターが何であるかを知らないようにしたい場合に、 に基づいてこれを生成する必要があることです。また、このソリューションは、後でコードがたとえば 3 文字以上に一致するように変更された場合、または各行のサイズが 4 から 16 に大きくなった場合、うまくスケーリングされません。

私が見落としている非常に単純なものがあるように感じます. また、これは重複した質問である可能性があるようですが、私が見た他の質問はどれも、この特定の問題に実際に対処しているようには見えません.

前もって感謝します！

アップデート：

正規表現の回答の標準は、SO ユーザーが単に正規表現を投稿して「これでうまくいくはずです」と言うだけのようです。

中途半端な回答だと思います。私は本当に正規表現を理解したいので、その正規表現の理由の完全な（理由の範囲内で）説明を回答に含めることができれば：

  • A.作品
  • B. 最も効率的です (かなりの量の最適化を行うことができる対象文字列について行うことができる十分な数の仮定があると思います)。

もちろん、あなたがうまくいく答えを出し、他の誰も答えを*解決策とともに*投稿しない場合、私はそれを答えとしてマークします:)

更新 2:

素晴らしい回答、多くの有益な情報、そして有効な解決策を提供してくださった皆様に感謝します。私が行った回答を選択したのは、パフォーマンス テストを実行した後、それが最良のソリューションであり、他のソリューションと同等のランタイムを平均化したからです。

私がこの答えを支持する理由：

  1. 指定された正規表現は、長い行に対して優れたスケーラビリティを提供します
  2. 正規表現は非常にきれいに見え、私のような凡人でも解釈しやすくなっています。

ただし、以下の回答も、そのソリューションが最適である理由を非常に徹底的に説明しているため、多くの功績があります。理解しようとしているためにこの質問に出くわした場合は、すべて読んでください。

4

7 に答える 7

4

この正規表現を使用しないのはなぜ$regex = "/.*[$line].*[$line].*/m";ですか?

あなたの例では、それはに変換されます$regex = "/.*[ACFG].*[ACFG].*/m";

于 2012-04-22T23:38:23.027 に答える
2

これは、「有効な」行を定義する正規表現です。

/^[A|B]{1}|[C|D]{1}|[E|F]{1}|[G|H]{1}$/m

英語では、各行の位置 0 に A または B、位置 1 に C または D、位置 2 に E または F、位置 3 に G または H のいずれかが含まれます。各行は正確に 4 文字になると想定できます。長いです。

それはその正規表現が意味するものではありません。この正規表現は、各行の位置 0 に A または B またはパイプ、位置 1 に C または D またはパイプなどがあることを意味します。 [A|B]「「A」または「|」のいずれかを意味します または「B」」。「|」文字クラス 外の「または」のみを意味します。

また、{1}ノーオペレーションです。量指定子がないため、すべてが 1 回だけ出現する必要があります。したがって、上記の英語の正しい正規表現は次のとおりです。

/^[AB][CD][EF][GH]$/

または、代わりに:

/^(A|B)(C|D)(E|F)(G|H)$/

2 番目のものには、各位置で文字をキャプチャするという副作用があるため、最初にキャプチャされたグループは、最初の文字が A か B かなどを教えてくれます。キャプチャが必要ない場合は、非キャプチャ グループを使用できます。

/^(?:A|B)(?:C|D)(?:E|F)(?:G|H)$/

しかし、文字クラス バージョンは、これを記述する通常の方法です。

あなたの問題に関しては、正規表現には適していません。文字列を分解し、適切な正規表現構文に貼り付けて、正規表現をコンパイルし、テストを実行するまでには、おそらく文字ごとの比較を行う方がはるかに優れていたでしょう。

あなたの「ACFG」正規表現を次のように書き直します：/^(?:AC|A.F|A..G|.CF|.C.G|..FG)$/、しかしそれは単なる外観です。正規表現を使用したより良い解決策は考えられません。(Mike Ryan が示したように、それはまだより良いでしょう/^(?:A(?:C|.E|..G))|(?:.C(?:E|.G))|(?:..EG)$/- しかし、それは同じ解決策であり、より効率的に処理された形式です。)

于 2012-04-22T23:34:08.757 に答える
1

あなたはすでに正規表現でそれを行う方法に答えており、その欠点とスケーリングできないことに気付いたので、死んだ馬をむち打ちする必要はないと思います. 代わりに、正規表現を必要とせずに機能する方法を次に示します。

function findMatchingLines($line) {
    static $file = null;
    if( !$file) $file = file("BigFileOfLines.txt");

    $search = str_split($line);
    foreach($file as $l) {
        $test = str_split($l);
        $matches = count(array_intersect($search,$test));
        if( $matches > 2) // define number of matches required here - optionally make it an argument
            return true;
    }
    // no matches
    return false;
}
于 2012-04-22T23:39:19.070 に答える
1

最初の正規表現に混乱する人もいるでしょう。あなたが与える：

"/^[A|B]{1}|[C|D]{1}|[E|F]{1}|[G|H]{1}$/m"

そして次のように言います。

英語では、各行の位置 0 に A または B、位置 1 に C または D、位置 2 に E または F、位置 3 に G または H のいずれかが含まれます。各行は正確に 4 文字になると想定できます。長いです。

しかし、それはその正規表現が意味するものではありません。

これは、|ここでは演算子の優先順位が最も高いためです。したがって、その正規表現が英語で実際に言っていることは、次のとおりです。最初の位置に orまたは または 最初の位置に OR またはAまたは|最初の位置にORまたは'| 最初の位置に H`。BC|DE|FGor

これは、[A|B]指定された 3 つの文字 ( を含む . を含む) のいずれかを持つ文字クラスを意味する|ためです。また、{1}1 つの文字を意味するため (これも完全に不要であり、削除される可能性があります)、およびその|周りのすべての外側の代替が含まれているためです。上記の私の英語の表現では大文字の OR は、交互に続く の 1 つを表します|(また、位置を 0 ではなく 1 からカウントし始めました -- 0 番目の位置を入力する気がしませんでした)。

英語の説明を正規表現として取得するには、次のようにします。

/^[AB][CD][EF][GH]$/

正規表現は、(文字クラスの) Aorの最初の位置を調べてチェックし、次の位置でorをチェックします。BCD

--

編集：

これら 4 つの文字のうち 2 つだけが一致するかどうかをテストします。

非常に厳密に言えば、@Mark Reedの回答からピックアップすると、最速の正規表現（解析後）は次のようになります。

/^(A(C|.E|..G))|(.C(E)|(.G))|(..EG)$/

と比較して:

/^(AC|A.E|A..G|.CE|.C.G|..EG)$/

これは、正規表現の実装がテキストを処理する方法によるものです。Aが最初の位置にあるかどうかを最初にテストします。それが成功したら、サブケースをテストします。それが失敗した場合、考えられるすべてのケース (または 3 つあるケース) は完了です。まだ一致していない場合は、C が 2 番目の位置にあるかどうかをテストします。それが成功した場合は、2 つのサブケースをテストします。そして、どれも成功しない場合は、3 番目と 4 番目の位置で `EG をテストします。

この正規表現は、できるだけ早く失敗するように特別に作成されています。各ケースを個別にリストすると、失敗することを意味し、3 つのケース (少なくとも) ではなく、6 つの異なるケース (6 つの選択肢のそれぞれ) をテストすることになります。そしてA、1 位にならなかった場合は、あと 2 回ヒットすることなく、すぐに 2 位をテストします。等。

(PHP が正規表現をどのようにコンパイルするのか正確にはわからないことに注意してください。そうではないかもしれませんが、同じ内部表現にコンパイルされる可能性があります。)

--

編集：追加のポイントについて。最速の正規表現はややあいまいな用語です。最速で失敗？最速で成功？そして、成功した行と失敗した行のサンプルデータの可能な範囲はどれくらいですか? あなたが最速で意味する基準を実際に判断するには、これらすべてを明確にする必要があります。

于 2012-04-22T23:40:23.667 に答える
1

これは、正規表現の代わりにレーベンシュタイン距離を使用するものであり、要件に合わせて十分に拡張可能である必要があります。

$lines = array_map('rtrim', file('file.txt')); // load file into array removing \n
$common = 2; // number of common characters required
$match = 'ACFG'; // string to match

$matchingLines = array_filter($lines, function ($line) use ($common, $match) {
    // error checking here if necessary - $line and $match must be same length
    return (levenshtein($line, $match) <= (strlen($line) - $common));
});

var_dump($matchingLines);
于 2012-04-22T23:42:47.400 に答える
1

MM..、MM、 M..M 、.MM.、.MM、..MM ("M" は一致を意味し、"." は一致しないことを意味します) -マッチ）。

したがって、入力をこれらの可能性のいずれかに一致する正規表現に変換するだけで済みます。の入力にはACFG、次のように使用します。

"/^(AC..|A.F.|A..G|.CF.|.C.G|..FG)$/m"

もちろん、これはあなたが既にたどり着いた結論です。

重要な問題は、正規表現は比較のための言語ではなく、文字列をパターンtwo stringsと比較するための言語だということです。したがって、比較文字列は (既に見つけた) pattern の一部であるか、 input の一部である必要があります。後者の方法では、汎用の一致を使用できますが、入力をマングルする必要があります。

function findMatchingLines($line, $subject) {
  $regex = "/(?<=^([AB])([CD])([EF])([GH])[.\n]+)"
      + "(\1\2..|\1.\3.|\1..\4|.\2\3.|.\2.\4|..\3\4)/m";
  $matchingLines = array();
  preg_match_all($regex, $line + "\n" + $subject, $matchingLines);
  return $matchingLines;
}

この関数が行うことは、入力文字列の前に一致させたい行を追加し、最初の行の後の各行 (つまり作業+後[.\n]) を最初の行の 4 文字と比較するパターンを使用することです。

これらの一致する行も「ルール」に対して検証する場合は.、各パターンの を適切な文字クラス (\1\2[EF][GH]など) に置き換えるだけです。

于 2012-04-22T23:51:14.473 に答える
1

昨日の夕方に質問をブックマークして、今日回答を投稿しましたが、少し遅れているようです^^ とにかく、私の解決策は次のとおりです。

/^[^ACFG]*+(?:[ACFG][^ACFG]*+){2}$/m

ACFG他の文字に囲まれた文字の 1 つが 2 回出現するのを探します。ループは展開され、パフォーマンスを少し改善するために所有量指定子を使用します。

以下を使用して生成できます。

function getRegexMatchingNCharactersOfLine($line, $num) {
    return "/^[^$line]*+(?:[$line][^$line]*+){$num}$/m";
}
于 2012-04-23T17:47:28.813 に答える