c# - 按未知的初始前缀分组

Question

假设我有以下字符串数组作为输入:

foo-139875913
foo-aeuefhaiu
foo-95hw9ghes
barbazabejgoiagjaegioea
barbaz8gs98ghsgh9es8h
9a8efa098fea0
barbaza98fyae9fghaefag
bazfa90eufa0e9u
bazgeajga8ugae89u
bazguea9guae
aifeaufhiuafhe

这里使用了 3 种不同的前缀，“foo-”、“barbaz”和“baz”——但是这些前缀是事先不知道的(它们可能是完全不同的东西)。

您如何确定不同的公共(public)前缀是什么，然后才能将它们分组？这有点棘手，因为在我提供的数据中，有两个以“bazg”开头，一个以“bazf”开头，当然“baz”是前缀。

到目前为止，我尝试过的是将它们按字母顺序排序，然后按顺序遍历它们并计算一行中有多少个字符与前一个相同。如果数字不同或当 0 个字符相同时，它会开始一个新组。这个问题是它落在了我之前提到的“bazg”和“bazf”问题上，并将它们分为两个不同的组(一个只有一个元素)

编辑:好的，让我们再添加一些规则:

• 较长的潜在组通常应优先于较短的组，除非存在长度差异小于 X 个字符的紧密匹配组。 (所以当 X 为 2 时，baz 优于 bazg)
• 一个组必须至少有 Y 个元素，否则根本不是一个组
• 可以简单地丢弃不符合上述规则的任何“组”的元素。

为了阐明与第二条规则相关的第一条规则，如果 X 为 0 且 Y 为 2，则两个“bazg”条目将在一个组中，并且“bazf”将被丢弃，因为它是独立的.

Answer 1

好吧，这是一个快速的技巧，可能是O(something_bad):

IEnumerable<Tuple<String, IEnumerable<string>>> GuessGroups(IEnumerable<string> source, int minNameLength=0, int minGroupSize=1)
{
    // TODO: error checking
    return InnerGuessGroups(new Stack<string>(source.OrderByDescending(x => x)), minNameLength, minGroupSize);
}

IEnumerable<Tuple<String, IEnumerable<string>>> InnerGuessGroups(Stack<string> source, int minNameLength, int minGroupSize)
{
    if(source.Any())
    {
        var tuple = ExtractTuple(GetBestGroup(source, minNameLength), source);
        if (tuple.Item2.Count() >= minGroupSize)
            yield return tuple;
        foreach (var element in GuessGroups(source, minNameLength, minGroupSize))
            yield return element;   
    }
}

Tuple<String, IEnumerable<string>> ExtractTuple(string prefix, Stack<string> source)
{
    return Tuple.Create(prefix, PopWithPrefix(prefix, source).ToList().AsEnumerable());
}

IEnumerable<string> PopWithPrefix(string prefix, Stack<string> source)
{
    while (source.Any() && source.Peek().StartsWith(prefix))
        yield return source.Pop();
}

string GetBestGroup(IEnumerable<string> source, int minNameLength)
{
    var s = new Stack<string>(source);
    var counter = new DictionaryWithDefault<string, int>(0);
    while(s.Any())
    {
        var g = GetCommonPrefix(s);
        if(!string.IsNullOrEmpty(g) && g.Length >= minNameLength)
            counter[g]++;
        s.Pop();
    }
    return counter.OrderBy(c => c.Value).Last().Key;
}

string GetCommonPrefix(IEnumerable<string> coll)
{
    return (from len in Enumerable.Range(0, coll.Min(s => s.Length)).Reverse()
            let possibleMatch = coll.First().Substring(0, len)
            where coll.All(f => f.StartsWith(possibleMatch))
            select possibleMatch).FirstOrDefault();
}

public class DictionaryWithDefault<TKey, TValue> : Dictionary<TKey, TValue>
{
  TValue _default;
  public TValue DefaultValue {
    get { return _default; }
    set { _default = value; }
  }
  public DictionaryWithDefault() : base() { }
  public DictionaryWithDefault(TValue defaultValue) : base() {
    _default = defaultValue;
  }
  public new TValue this[TKey key]
  {
    get { return base.ContainsKey(key) ? base[key] : _default; }
    set { base[key] = value; }
  }
}

示例用法:

string[] input = {
    "foo-139875913",
    "foo-aeuefhaiu",
    "foo-95hw9ghes",
    "barbazabejgoiagjaegioea",
    "barbaz8gs98ghsgh9es8h",
    "barbaza98fyae9fghaefag",
    "bazfa90eufa0e9u",
    "bazgeajga8ugae89u",
    "bazguea9guae",
    "9a8efa098fea0",
    "aifeaufhiuafhe"
};

GuessGroups(input, 3, 2).Dump();