1

私はオブジェクトのリストを持っています：例えばA, A, B, C, D, E, E

そして、オブジェクトタイプをグループ化する方法を示すテンプレートを定義しました。

 Group Alpha --> A 1..n --> any number of 'A's can be grouped
 Group Charlie --> Sequences of 'BCD' can be grouped
 Group Epsilon --> E 1..n --> any number of 'E's can be grouped

これらのグループ定義を元のリストに適用すると、次の結果が得られます。

 Group Alpha (2x'A'), Group Charlie (1x'BCD'), Group Epsilon (2x'E')

これをどのように達成するのが最善でしょうか? 私の問題に対する既知の検索アルゴリズム/パターンはありますか? リストを何度もループし、各リストエントリから先を見てパターンに一致させるという非常に基本的な方法を試しましたが、複雑さのために完全に失われました...

ヒントを事前にありがとう!!!

4

4 に答える 4

2

これが必要なものかどうかは完全にはわかりませんが、この小さなコードを使用して、指定した出力を作成できます

簡単な使い方 (アサーションあり):

var a1 = new List<string> { "A", "A", "B", "C", "D", "E", "E" };

a1.ApplyCriteria("A").Criteria.Should().Be("A");
a1.ApplyCriteria("A").Count.Should().Be(2);

a1.ApplyCriteria("E").Criteria.Should().Be("E");
a1.ApplyCriteria("E").Count.Should().Be(2);

a1.ApplyCriteria("BCD").Criteria.Should().Be("BCD");
a1.ApplyCriteria("BCD").Count.Should().Be(1);

a1.ApplyCriteria("CD").Criteria.Should().Be("CD");
a1.ApplyCriteria("CD").Count.Should().Be(1);

// not found
a1.ApplyCriteria("CDA").Criteria.Should().Be("CDA");
a1.ApplyCriteria("CDA").Count.Should().Be(0);

ApplyCriteria メソッドによって返される GroupResult クラスは次のようになります。

class GroupResult
{
    public string Criteria { get; set; }
    public int Count { get; set; }
}

そして、これらは実際の作業を行っている拡張メソッドです

static class Ext
{
    public static GroupResult ApplyCriteria(this IEnumerable<string> source, string criteria)
    {
        var elements = source.ToConcatenedString();

        return new GroupResult { Criteria = criteria, Count = elements.CountOcurrences(criteria) };
    }

    public static int CountOcurrences(this string source, string phrase)
    {
        return source
            .Select((c, i) => source.Substring(i))
            .Count(sub => sub.StartsWith(phrase));
    }

    public static string ToConcatenedString<TSource>(this IEnumerable<TSource> source)
    {
        var sb = new StringBuilder();

        foreach (var value in source)
        {
            sb.Append(value);
        }

        return sb.ToString();
    }
}
于 2012-05-31T16:35:00.560 に答える
2

これは、修正された文字列一致の問題です。次の 2 種類の入力があります。

  1. 「BCD」のようなもの。これだけあれば、ここで従来の任意のアルゴリズムを使用してマッチングできます

  2. 行内の同じオブジェクトの任意の数。

私の頭の上には2つの解決策があります：

  1. 従来の文字列アルゴリズム (KMP など) を使用しますが、2 番目のタイプの入力には例外規則を作成します。

  2. 次のような有向グラフを作成します。

ここに画像の説明を入力

さて、上の図はうまく描かれていません。ご不明な点がございましたら、お知らせください。

于 2012-05-31T15:20:47.223 に答える
1

オブジェクト間で比較し、何が A で何が B であるかを伝える何らかのコードがあると仮定すると、テンプレートを配列として定義し、元のリストを反復処理して、テンプレートの出現箇所を検索できます。 

CustomObj[] template = new CustomObj[]{B,C,D};
for (int i=0; i< originalList.Length- template.Length + 1; i++)
{
     bool found= true;
     for(int j=0; j< template.Length;j++)
     {
        found = template[j] == originalList[i +j];
     }
     if (found)
     {
        //add to results list
      }
}

検索比較アルゴリズム (私が覚えている限り、それらの中で最も単純なもの) はそのような概念を使用し、いくつかの圧縮アルゴリズムも使用しますが、反対側から作業します (テンプレートを作成して、テンプレートの bg インデックスを作成することによりストレージを削減します)。

編集
私は実際に単純なRabin-Karpアルゴリズム
を実装したことがわかりました。私 はそれがそのようなものだったことを思い出しました:)

于 2012-05-31T15:21:33.323 に答える
1

基本的には、ステート マシンを構築できます。「Init」、「alpha」、「B」、「C」、「charlie」、「epsilon」の 6 つの状態があります。

初期化から開始:

  • 次のオブジェクトが「A」の場合、状態アルファに移動し、アルファ カウンターを 1 増やします。
  • 次の obj が B の場合、状態 B に移動します。
  • 次のオブジェクトが「E」の場合、状態イプシロンに進み、イプシロン カウンターをインクリメントします。
  • 他のオブジェクトの場合は、init 状態のままにします。

状態 aplha で:

  • 次のオブジェクトが A の場合、状態アルファにとどまります。
  • 次のオブジェクトが B の場合、ステート B に移動
  • 次の obj が E の場合、ステート イプシロンに進み、イプシロン カウンターをインクリメントします。
  • それ以外の場合は、init に進みます。

状態 B:

  • 次がAの場合、アルファとインクカウンタに移動
  • 次が E の場合、イプシロン社のカウンターに移動します。
  • 次が C の場合、状態 C に移動
  • その他 -> 初期化に進む

状態 C:

  • 次がAの場合、アルファとインクカウンタに移動
  • 次が E の場合、イプシロン社のカウンターに移動します。
  • 次が D の場合、状態 charlie に移動し、charlie カウンターを増やします
  • その他 -> 初期化に進む

状態 D:

  • 次がAの場合、アルファとインクカウンタに移動
  • 次が E の場合、イプシロン社のカウンターに移動します。
  • 次がBの場合、状態Bへ
  • その他 -> 初期化に進む

状態イプシロン:

  • 次のオブジェクトが「A」の場合、状態アルファに移動し、アルファ カウンターを 1 増やします。
  • 次の obj が B の場合、状態 B に移動します。
  • 次のオブジェクトが「E」の場合、何もしません。
  • 他のオブジェクトの場合は、init 状態に移動します。

複雑に見えることはわかっていますが、少なくとも現時点では、特に状態図を作成する場合はそうではありません。もちろん、より一般的なものが必要な場合、または新しいパターンを追加し続けたい場合、またはパターンがさらにある場合は、すぐに非常に複雑になります。その場合、最善の方法は、文字列マッチング アルゴリズムの 1 つを問題に適応させることだと思います。

于 2012-05-31T15:27:40.440 に答える