C# 2.0 泛型可重用前缀树

• 下载源文件 - 27.97 KB

更新

查看 Sébastien 的第二条评论，有一个更简洁的实现。我将其用作另一个需要它的算法的一部分。如果您只需要存储和检索，可能更倾向于使用他的解决方案。对于由此造成的困惑，我深表歉意。

引言

您是否曾经遇到过需要存储键值对，但您的键是某种列表的情况？我知道我遇到过。C# 中大多数内置集合都足够好，如果您想存储即使是复杂的对象，但当涉及到复杂对象的列表（甚至是 int[]）时，似乎没有什么能够胜任。这时前缀树就派上用场了。此实现将允许您轻松存储各种有趣的各种对象列表。我还利用了 .NET 2.0 的两个新功能：**泛型**和 **yield return**。

数据结构

让我们首先研究该结构的使用，因为这就是您在这里的原因。
假设我们有一个 int[]，并想将其用作键。我们可能会这样想：

List<int[]> arr = new List<int[]>();
arr.Add(new int[] { 1, 2, 3 });
bool b = arr.Contains(new int[] { 1, 2, 3 });

但这样做时，我们会得到 b = false。事实上，如果我们尝试

SortedList<int[], int> arr = new SortedList<int[], int>();
arr.Add(new int[] { 1, 2, 3 },1);
bool b = arr.ContainsKey(new int[] { 1, 2, 3 });

我们会得到以下异常

System.InvalidOperationException{"Failed to compare two elements in the array."}

问题就在这里。底层 int[] 实际上是一个名为 System.Array 的类，它不知道如何比较 int。为了解决这个问题，我们可以这样做：

PrefixTree<int,int> arr = new PrefixTree<int,int>();
arr.Add(new int[] { 1, 2, 3 },1);
bool b = arr.ContainsKey(new int[] { 1, 2, 3 });

这样做后，我们会得到 b = true，这就是我们在集合中寻找的。

我们正在创建一个结构，该结构知道我们正在处理一个对象数组，而不是单个对象 Array。通过这种方式，我们可以让 C# 对单个对象的比较进行神奇的操作。

了解泛型

让我们看一眼类定义。

public class PrefixTree<TListKey, TValue> : 
IEnumerable<KeyValuePair<IList<TListKey>, TValue>> 
where TListKey : IComparable<TListKey>

哎呀。这一切意味着什么？嗯，public class PrefixTree 部分应该相当直接，所以我们继续看 <TListKey, TValue>。
<TListKey, TValue> 指示 .NET 允许我们在声明类时，在它们的位置上使用任何类型（引用类型或值类型），如下所示。

PrefixTree mytree = new PrefixTree<char, string>();

这意味着我们所有的代码将在编译时由编译器进行强类型检查。根据我的经验，这可以减少运行系统中的错误。而且这些错误通常非常糟糕。它们通过了 QA，因为它们没有考虑到所有可能的愚蠢组合。
: IEnumerable<KeyValuePair<IList<TListKey>, TValue>> 是 C# 2.0 的新特性。除了 System.Collections 命名空间之外，还有一个 System.Collections.Generic 命名空间。它包含 System.Collections.Generic.IEnumerable<T>。它就像我们熟悉的 System.Collections.IEnumerable 一样，只是它是强类型的。同时请注意，我们可以有嵌套的泛型声明，甚至可以有一个泛型接口 IList<TListKey>。

最后，我们有了一个新关键字 where。where TListKey : IComparable<TListKey> 对我们使用泛型施加了“约束”。这意味着当我们为通用类型 TListKey 替换类型时，它必须实现 IComparable<TListKey> 接口，否则编译器会通知我们。这样，我们就不必等到第一个对象被添加到数据结构中才收到错误。

您还可以对泛型可以做什么和不能做什么施加许多其他约束。有关更多信息，您可以从 Microsoft 在此找到：类型参数的约束（C# 编程指南）。

了解 Yield Return

yield return 是一种比较奇特的机制。它的目的是简化代码，这样当我们有一个数据集并想用 foreach 语句遍历它时，它应该尽可能容易。其思想是，当您有一个扁平列表时，任何人都可以编写一个迭代器，保持位置很简单。但是，当您有一个分层数据结构时，即使遍历起来相当容易，但编写一个迭代器可能非常困难，尤其是跨越所有递归调用。所以这里的技巧是：您可以创建一个带有递归参数的 private IEnumerable<T>。然后，您只需使用 yield return 输出当前节点，并调用递归调用。就这么简单。不过有一个高级的陷阱。IEnumerable<T> 要求您实现 IEnumerator<T> GetEnumerator() 方法。但是，您不能像您想要的那样将一个 IEnumerator 放入 foreach 循环中进行递归，但您可以这样做：

public IEnumerator<KeyValuePair<IList<TListKey>, TValue>> GetEnumerator()
{
    return GetEnumeratorHelper(new LinkedList<TListKey>(),root).GetEnumerator();
}

private IEnumerable<KeyValuePair<IList<TListKey>, TValue>> 
	GetEnumeratorHelper(LinkedList<TListKey> keylist,
 PrefixTreeNode<TListKey, TValue> node)
{
    keylist.AddLast(node.key);
    if (node.hasvalue)
        yield return new KeyValuePair<IList<TListKey>, TValue>
        (BuildIList(keylist), node.value);


    foreach (KeyValuePair<TListKey, PrefixTreeNode<TListKey, TValue>> 
    kvp1 in node.childern)
        foreach (KeyValuePair<IList<TListKey>, TValue> kvp2 in 
        GetEnumeratorHelper(keylist,kvp1.Value))
            yield return new KeyValuePair<IList<TListKey>, TValue>
           (BuildIList(keylist), kvp2.Value);
    keylist.RemoveLast();
}

请注意，顶层调用是 IEnumerator，而递归调用是 IEnumerable？由于 IEnumerable<T> 有一个名为 GetEnumerator() 的方法，因此我们想要的返回值很容易获得。不过，这一点很难发现，因为 IEnumerator 和 IEnumerable 之间的区别非常小。

哦，对于那些想知道 yield return 听起来像是多线程的东西的人来说，它不是。我和一位同事去参加了一个微软关于 C# 2.0 新功能的活动。他们向我们保证这与多线程无关。我不知道如何测试这一点，但就供参考而言……

演示应用程序

演示应用程序没什么特别之处。它只是允许您添加、删除、清除和枚举字符串集合。但是等等，我以为这应该针对对象列表，而不是一个对象。嗯，确实如此。string 也是一个 char[]，而且由于字符串的排序正是我们想要对前缀树进行的，因此我们可以使用一个内置类（微软在制造这些类时非常出色，而且很少出错）来测试我们的代码是否能产生相同的结果。一旦演示应用程序加载，它就会运行一个包含几百个随机生成字符串的自检，并将枚举结果与 SortedList<string, string> 表示以及新的 PrefixTree<char, string> 表示进行比较。如果一切正常，应用程序会告知您，否则也会通知您。我建议，如果您想实际单步调试代码，请清除列表并只添加几个条目。

我还包括了指向维基百科关于前缀树页面的链接，如果您想查找更多信息。它不完全相同，但已经足够接近了。