按未知的初始前缀分组

Question

说我有以下字符串数组作为输入：

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

这里使用3个不同的前缀“ foo-”，“ barbaz”和“ baz”-但是这些前缀是未知的（它们可能完全不同）。

您如何确定不同的通用前缀是什么，以便随后将其分组？这有点棘手，因为在我提供的数据中，有两个以“ 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();