按最近日期和聚类（组）相似标题排序

Question

寻找 LINQ 需要对日期字段进行排序，但也有类似的标题进行分组和排序。考虑类似以下所需的顺序：

Title                Date
"Some Title 1/3"     2009/1/3     "note1: even this is old title 3/3 causes this group to be 1st"
"Some Title 2/3"     2011/1/31    "note2: dates may not be in sequence with titles"
"Some Title 3/3"     2011/1/1     "note3: this date is most recent between "groups" of titles
"Title XYZ 1of2"     2010/2/1
"Title XYz 2of2"     2010/2/21

我已经显示了因某些后缀而异的标题。如果海报使用类似以下内容的标题会怎样？

"1 LINQ Tutorial"
"2 LINQ Tutorial"
"3 LINQ Tutorial"

查询如何识别这些相似的标题？ 您不必解决所有问题，非常感谢第一个示例的解决方案。

谢谢。

附录 #1 20110605 @svick 还有，当标题作者的编号方案超过 9 时，通常不会考虑使用 2 位数字。例如 01,02...10,11 等。

我见过的典型模式往往是前缀或后缀或甚至埋藏在诸如

1/10 1-10 ...
(1/10) (2/10) ...
1 of 10   2 of 10
Part 1  Part 2 ...

您也指出了一个有效模式：

xxxx Tutorial : first session,  xxxx Tutorial : second session, ....

如果我有一个 Levenshtein 函数 StringDistance( s1, s2 ) 我将如何适应 LINQ 查询:)

Answer 1

LINQ（以及 SQL，但这与此处无关）中的正常分组是通过为集合中的每个元素选择某个键来工作的。你没有这样的键，所以我不会使用 LINQ，而是使用两个嵌套的 foreaches：

var groups = new List<List<Book>>();

foreach (var book in books)
{
    bool found = false;

    foreach (var g in groups)
    {
        if (sameGroup(book.Title, g[0].Title))
        {
            found = true;
            g.Add(book);
            break;
        }
    }

    if (!found)
        groups.Add(new List<Book> { book });
}

var result = groups.Select(g => g.OrderBy(b => b.Date).ToArray()).ToArray();

这会逐渐创建一个组列表。每本书都与每组中的第一本书进行比较。如果匹配，则将其添加到组中。如果没有匹配的组，本书将创建一个新组。最后，我们使用带有点表示法的 LINQ 对结果进行排序。

如果将书籍与一组中的每本书进行比较，而不仅仅是第一本书，那就更正确了。但无论如何你可能不会得到完全正确的结果，所以我认为这种优化是值得的。

这具有时间复杂度O(N²)，因此如果您有数百万本书，它可能不是最好的解决方案。

编辑：要对组进行排序，请使用类似

groups.OrderBy(g => g.Max(b => b.Date))

Answer 2

要按日期订购，您应该使用 OrderBy 运算符。

示例：

//Assuming your table is called Table in datacontext ctx
var data = from t in ctx.Table
           order by t.Date
           select t;

要根据相似性对字符串进行分组，您应该考虑诸如 汉明距离 或 Metaphone 算法。 （虽然我不知道.Net 中这些的任何直接实现）。

编辑：正如 svick 的评论中所建议的，Levenstein 距离可能也可以考虑作为汉明距离的更好替代方案。

Answer 3

假设您的标题和日期字段包含在名为 model 的类中，请考虑以下类定义
除了日期和标题属性之外，公共类模型

{
    public DateTime Date{get;set;}
    public string Title{get;set;}
    public string Prefix
    {get
        {
            return Title.Substring(0,Title.LastIndexOf(' '));
        }
    }
}

我还创建了一个没有设置器的前缀属性，它使用子字符串返回我们的公共前缀。您可以在此属性的 getter 中使用您选择的任何方法。剩下的工作就很简单了。考虑这个 Linqpad 程序

void Main()
{
    var model = new List<Model>{new Model{Date = new DateTime(2011,1,3), Title = "Some Title 1/3"},
                new Model{Date = new DateTime(2011,1,1), Title = "Some Title 2/3"},
                    new Model{Date = new DateTime(2011,1,1), Title = "Some Title 3/3"},
                    new Model{Date = new DateTime(2011,1,31), Title = "Title XYZ 1of2"},
                    new Model{Date = new DateTime(2011,1,31), Title = "Title XYZ 2of2"}};
            var result = model.OrderBy(x => x.Date).GroupBy(x => x.Prefix);
            Console.WriteLine(result);
}

编辑 >>>
如果我们将前缀放在一边，查询本身不会返回我想要的结果，即：1）按最近的日期对组进行排序2）按簇内的标题排序。尝试以下操作

var model = new List<Model>{

                new Model{Date = new DateTime(2009,1,3), Title = "BTitle 1/3"},
                new Model{Date = new DateTime(2011,1,31), Title = "BTitle 2/3"},
                new Model{Date = new DateTime(2011,1,1), Title = "BTitle 3/3"},

                new Model{Date = new DateTime(2011,1,31), Title = "ATitle XYZ 2of2"},
                new Model{Date = new DateTime(2011,1,31), Title = "ATitle XYZ 1of2"}
                };
        var result = model.OrderBy(x => x.Date).GroupBy(x => x.Prefix);
        Console.WriteLine(result);