假设我有以下字符串数组作为输入:
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”将被丢弃,因为它是独立的.
最佳答案
好吧,这是一个快速的技巧,可能是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();
关于c# - 按未知的初始前缀分组,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/16398644/