5

不完全なシーケンスを照合するのに役立つアルゴリズムを実装しようとしています。

ABBABABBA のシーケンスが保存されていて、大量の文字列から「似ている」ものを見つけたいとします。

アルゴリズムに 2 つのワイルドカード (違い) を許可する場合、どのように正規表現を使用して次のようなものに一致させることができますか: ( と ) は違いをマークします:

A(A)BABAB(A)A 
or 
(B)BBA(A)ABBA

私のジレンマは、これらの潜在的なターゲットの一致 (不完全さを伴う) を大きな文字列で見つけようとしているということです。したがって、次のようになります。

ABBDBABDBCBDBABDB(A(A)BABAB(A)A)DBDBABDBCBDBAB
ADBDBABDBDBDBCBDBABCBDBABCBDBABCBDBABABBBDBABABBCD
DBABCBDABDBABCBCBDBABABDABDBABCBDBABABDDABCBDBABAB

これらの「十分に近い」一致を検索できなければなりません。
角かっこは次を示します: ((違い) との十分な一致)

編集：この例でより正式にするには、N-2文字が元と同じ場合、長さNの一致を受け入れることができます（2つの違い）

以前に正規表現を使用したことがありますが、完全なシーケンスを見つけるためだけに使用しました。「似ている」ものではありません。

これがいくつかのアドバイスを得るのに十分明確であることを願っています. 読んでくれてありがとう！

4

7 に答える 7

3

LINQ を使用して、表現力を高めることができます。

これを使用するにusing System.Linqは、コードの先頭に があることを確認してください。

仮定して

  • sourceは格納されたターゲット パターンです。
  • testテストする文字列です。

それからあなたはすることができます

public static bool IsValid(string source, string test) 
{
  return test != null  
         && source != null 
         && test.Length == source.Length 
         && test.Where((x,i) => source[i] != x).Count() <=2
}

失敗した瞬間に false を終了するショートカット バージョンもあり、残りの文字列の繰り返しを節約します。

public static bool IsValid(string source, string test) 
{
   return test != null  
          && source != null 
          && test.Length == source.Length 
          && !test.Where((x,i) => source[i] != x).Skip(2).Any();
}

コメントで要求されたように、これがどのように機能するかについての簡単な説明

C# では、文字列を文字の配列として扱うことができます。これは、Linq メソッドを使用できることを意味します。

test.Where((x,i) => source[i] != x)

これは、テスト内の各文字に対して Where のオーバーロードを使用しx、文字iに割り当てられ、インデックスに割り当てられます。ソースの位置 i にある条件文字が x と等しくない場合、結果に出力されます。

Skip(2)

これにより、最初の 2 つの結果がスキップされます。

Any()

結果が残っている場合は true を返し、そうでない場合は false を返します。linq はこれが false である瞬間に実行を延期するため、関数は残りの文字列を評価するのではなく終了します。

次に、「!」をプレフィックスとして付けることで、テスト全体を否定します。これ以上結果がない場所を知りたいことを示します。

部分文字列として一致させるには、正規表現のバックトラッキングと同様に動作する必要があります...

public static IEnumerable<int> GetMatches(string source, string test)
{
   return from i in Enumerable.Range(0,test.Length - source.Length)
      where IsValid(source, !test.Skip(i).Take(source.Length))
          select i;
}

public static bool IsValid(string source, IEnumerable<char> test) 
{
   return test.Where((x,i) => source[i] != x).Skip(2).Any();
}

更新の説明

Enumerable.Range(0,test.Length - source.Length)

これにより、0 から test.Length - source.Length までの一連の数値が作成されます。長さが短くなると答えが無効になるため、テストのすべての文字から開始してチェックする必要はありません。

私から....

基本的に、i を割り当ててコレクションを反復処理し、毎回現在の値にします。

where IsValid(source, !test.Skip(i).Take(source.Length))

結果をフィルター処理して、インデックス i から始まり (したがってスキップ)、source.Length 文字 (したがって、テイク.

私を選択

私を返す

これは、一致するテストのインデックスに対して列挙可能なものを返します。それらを抽出するには、

GetMatches(source,test).Select(i => 
                      new string(test.Skip(i).Take(source.Length).ToArray()));
于 2013-06-27T14:46:16.387 に答える
2

正規表現でそれを行う方法は考えられませんが、コーディングは非常に簡単なはずです。

おそらく、文字列を分割して、文字ごとに比較するだけです。差が出たら数えて次のキャラクターに移ります。2 つの差を超えた場合は、次の完全な文字列に進みます。

于 2013-06-27T13:40:32.810 に答える
2

このケースを処理するための適切な正規表現はないと思います。(または、少なくとも、3 行のテキストを十分に消費せず、足に複数の弾丸が発生するものはありません。) ただし、だからといって、この問題を解決できないわけではありません。

文字列の大きさにもよりますが（それぞれ数百万文字にはならないと思います）、単一のループを使用して個々の文字を順番に比較し、違いを集計することを妨げるものは何もありません。

int differences = 0;    // Count of discrepancies you've detected
int tolerance = 7;    // Limit of discrepancies you'll allow

CheckStrings(int differences, int tolerance) {
    for (i = 0; i < StringA.Length; i++)
    {
        if (StringA[i] != StringB[i]) {
            differences++;
            if (differences > tolerance) {
                return false;
            }
        }
    }
    return true;
}

ほとんどの場合、文字列がループに入れるには長すぎることを心配する必要はありません。舞台裏では、文字列のすべての文字を評価するコードは何らかの形でループします。文字通り何百万もの文字を処理するまでは、ループでうまくいくはずです。

于 2013-06-27T13:40:36.563 に答える
0

A、B、(および機能する組み合わせはあり)ますか?

bool isMatch = Regex.IsMatch(inputString, "^[AB()]+$")
于 2013-06-27T13:18:13.143 に答える