算法列表中的檢測和替換組

我有對象的列表：例如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')

這又如何能最好地實現？我的問題是否有已知的搜索算法/模式？我已經嘗試了一個非常基本的方式在列表中循環多次，並試圖從每個列表條目和匹配模式向前看，但由於複雜性而完全丟失了...

在此先感謝您的任何提示！！

來源

2012-05-31 SvenG

我不能完全肯定這是你所需要的，但這個小的代碼我可以創建你指定

輸出

簡單的使用（使用斷言）：由歸國

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);

我GroupResult類該ApplyCriteria方法是這樣的：

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-31 16:35:00 Jupaol

謝謝！我真的很喜歡你的答案，因爲使用了擴展方法和LINQ，這使得一個相當複雜的事情很容易理解和理解。我複製/粘貼你的代碼做了一些修改/擴展，它的作品就像一個魅力，再次感謝！ – SvenG

這是一個修改後的字符串匹配問題。你有兩種類型的輸入：

那些像「BCD」。如果您只有這一點，可以使用任何常規算法進行匹配here
行中同一對象的任意數量。

有2個解決方案，把我的頭頂部：

使用傳統的字符串變換算法（KMP或其他），但要爲第二類型的輸入的例外規則。
構建一個有向圖，如：

enter image description here

遠高於這個數字繪製很差。如果您有任何問題，請告訴我。

來源

2012-05-31 15:20:47

假設您有某種代碼來比較對象，並告訴什麼是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 
     } 
}

搜索比較算法（其中最簡單的，據我記得）使用這樣的概念，也有一些的壓縮算法，但他們進行這項工作從另一面（建築模板，以減少通過模板creatinbg索引）存儲

編輯
原來我實際執行的simple Rabin-Karp algorithm
我記得這是類似的東西：）

來源

2012-05-31 15:21:33 YavgenyP

在裸露的基礎知識，你可以建立一個state machine。它將有6個州，「Init」，「alpha」，「B」，「C」，「charlie」和「epsilon」。

由init開始：

如果下一個對象是「A」，轉到狀態α，由1
增量阿爾法計數器如果下一obj爲B，進入狀態B.
如果下一個對象是「E」，則進入狀態epsilon，增加Epsilon計數器。
如果有其他對象，則保持init狀態。

在狀態APLHA：

如果下一個目的是A，停留在狀態的α。
如果下一個對象是B，則轉到狀態B
如果下一個obj是E，則轉到狀態epsilon並增加epsilon計數器。
如果還有其他問題，請轉到init。

在狀態B：

如果下一個是A，去α和INC計數器
如果下一個是E，去ε，INC其計數器。
如果下一個是C，進入狀態C
別的 - >去初始化

在狀態C：

如果下一個是A，去α和INC計數器
如果下一個是E，則轉到epsilon，它的計數器。
如果下一個是d，進入狀態查理，提高查理計數器
別的 - >去初始化

在狀態d：

如果下一個是A，去阿爾法and inc counter
如果下一個是E，則轉到epsilon，它的計數器。
如果下一個是B，進入狀態B
別的 - >去初始化

在狀態小量：

如果下一個目標是「A」，進入狀態alpha，將alpha計數器增加1.
如果下一個obj是B，則轉到狀態B.
如果下一個對象是「E」，則不執行任何操作。
如果有其他對象，則轉到init狀態。

我知道它看起來很複雜，但至少在這一點上它確實不是這樣，尤其是如果你創建一個狀態圖。當然，如果你想要更通用的東西，或者如果你想不斷添加新的模式，或者如果你有更多的模式，它會很快變得非常複雜。在這種情況下，我認爲你最好的選擇是使string matching algorithms之一適應你的問題。

來源

2012-05-31 15:27:40

算法列表中的檢測和替換組

回答

相關問題