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

这是一个修改后的字符串匹配问题。您有两种类型的输入：

  1. 像“BCD”这样的。如果你只有这个，可以在这里使用任何常规算法进行匹配

  2. 一行中任意数量的相同对象。

我想到了两个解决方案：

  1. 使用传统的字符串算法（KMP 或其他），但为第二种类型的输入制定例外规则。

  2. 构建一个有向图，如：

在此处输入图像描述

好吧，上图画得不好。如果您有任何问题，请告诉我。

于 2012-05-31T15:20:47.223 回答
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 回答
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
      }
}

搜索比较算法（其中最简单的，据我所知）使用这些概念，也使用了一些压缩算法，但它们从另一端工作（构建模板以通过创建模板索引来减少存储）

编辑
原来我实际上实现了简单的 Rabin-Karp 算法
，我记得它是这样的:)

于 2012-05-31T15:21:33.323 回答
1

在最基本的基础上，您可以构建一个状态机。它将有 6 个状态，“Init”、“alpha”、“B”、“C”、“charlie”和“epsilon”。

从初始化开始：

  • 如果下一个对象是“A”，则进入状态 alpha，将 alpha 计数器加 1。
  • 如果下一个 obj 是 B，则转到状态 B。
  • 如果下一个对象是“E”，则进入状态 epsilon，增加 Epsilon 计数器。
  • 如果有任何其他对象，则保持 init 状态。

在 aplha 州：

  • 如果下一个对象是 A，则保持状态 alpha。
  • 如果下一个对象是 B，则转到状态 B
  • 如果下一个 obj 是 E ，则进入状态 epsilon 并增加 epsilon 计数器。
  • 如果还有其他问题，请转到 init。

在状态 B：

  • 如果下一个是 A，则转到 alpha 和 inc 计数器
  • 如果下一个是 E，则转到 epsilon，inc 其计数器。
  • 如果next是C，则进入状态C
  • 其他任何东西->进入初始化

在状态 C：

  • 如果下一个是 A，则转到 alpha 和 inc 计数器
  • 如果下一个是 E，则转到 epsilon，inc 其计数器。
  • 如果下一个是D，去状态查理，增加查理计数器
  • 其他任何东西->进入初始化

在状态 D：

  • 如果下一个是 A，则转到 alpha 和 inc 计数器
  • 如果下一个是 E，则转到 epsilon，inc 其计数器。
  • 如果next是B，则进入状态B
  • 其他任何东西->进入初始化

在状态 epsilon 中：

  • 如果下一个对象是“A”，则进入状态 alpha，将 alpha 计数器加 1。
  • 如果下一个 obj 是 B，则转到状态 B。
  • 如果下一个对象是“E”，则什么也不做。
  • 如果有任何其他对象，则进入初始状态。

我知道它看起来很复杂，但实际上并非如此，至少在这一点上，尤其是在创建状态图时。当然，如果你想要更通用的东西，或者你想不断添加新的模式，或者你有更多的模式，它很快就会变得非常复杂。在这种情况下，我相信你最好的办法是让一种字符串匹配算法适应你的问题。

于 2012-05-31T15:27:40.440 回答