序列化前缀树

Question

我得到一个ProtoException("可能的递归检测到(偏移:4级):o EOW")序列化树结构时如下:

var tree = new PrefixTree();
        tree.Add("racket".ToCharArray());
        tree.Add("rambo".ToCharArray());
        using (var stream = File.Open("test.prefix", FileMode.Create))
        {
            Serializer.Serialize(stream, tree);
        }

树实现:

[ProtoContract]
public class PrefixTree
{
    public PrefixTree()
    {
        _nodes = new Dictionary<char, PrefixTree>();
    }

    public PrefixTree(char[] chars, PrefixTree parent)
    {
        if (chars == null) throw new ArgumentNullException("chars");
        if (parent == null) throw new ArgumentNullException("parent");
        if (chars.Length == 0) throw new ArgumentException();

        _parent = parent;
        _nodes = new Dictionary<char, PrefixTree>();
        _value = chars[0];

        var overflow = chars.SubSet(1);
        if (!overflow.Any()) _endOfWord = true;
        else Add(overflow.ToArray());
    }

    [ProtoMember(1)]
    private readonly char _value;
    [ProtoMember(2)]
    private readonly bool _endOfWord;
    [ProtoMember(3)]
    private readonly IDictionary<char, PrefixTree> _nodes;
    [ProtoMember(4, AsReference = true)]
    private readonly PrefixTree _parent;

    public void Add(char[] word)
    {
        if (word == null) throw new ArgumentNullException("word");
        if (word.Length == 0) return;

        var character = word[0];
        PrefixTree node;
        if (_nodes.TryGetValue(character, out node))
        {
            node.Add(word.SubSet(1));
        }
        else
        {
            node = new PrefixTree(word, this);
            _nodes.Add(character, node);
        }
    }

    public override string ToString()
    {
        return _endOfWord ? _value + " EOW" : _value.ToString();
    }
}

public static class ListHelper
{
    public static char[] SubSet(this char[] source, int start)
    {
        return source.SubSet(start, source.Length - start);
    }

    public static char[] SubSet(this char[] source, int start, int length)
    {
        if (start < 0) throw new ArgumentOutOfRangeException();
        if (start > source.Length) throw new ArgumentOutOfRangeException();
        if (length < 0) throw new ArgumentOutOfRangeException();

        var result = new char[length];
        Array.Copy(source, start, result, 0, length);
        return result;
    }
}

我是用错误的属性装饰还是只是设计了一个不可序列化的树？

编辑:试过这个无济于事:

var typeModel = RuntimeTypeModel.Default;
        var type = typeModel.Add(typeof(PrefixTree), false);
        type.AsReferenceDefault = true;
        type.Add("_value", "_endOfWord", "_nodes", "_parent");

        var tree = new PrefixTree();
        tree.Add("racket".ToCharArray());
        tree.Add("rambo".ToCharArray());
        using (var stream = File.Open("test.prefix", FileMode.Create))
        {
            typeModel.Serialize(stream, tree);
        }

Answer 1

_node 的 _parent 和 Value 都指向相同的类型 ( PrefixTree )，但只有 _parent 被标记为“AsReference”。

如果您遍历序列化堆栈，您将看到字典值的值是独立于 _parent 项进行序列化的，并且不会检查重复实例。

当它遍历树时，会进行 25 的内部序列化深度检查，此时它开始检测重复实例。如果这个值更大，它不会抛出异常，如果它更小，它会在树上更高的节点上抛出异常。

我也不认为这将是可反序列化的，当然，如果这样做的话，每个子节点的 _parent 字段的值将不会与 _nodes 容器是同一实例。

您需要创建自己的字典类型（子类 Dictionary<,> 或实现 IDictionary<,> ），以便可以添加 [ProtoContract] 属性并控制字典项目的序列化。

IE

[ProtoContract]
public class NodeItem
{
    [ProtoMember(1)]
    public char Key { get; set; }
    [ProtoMember(2, AsReference = true)]
    public PrefixTree Value { get; set; }
}

[ProtoContract]
public class Nodes : IDictionary<char, PrefixTree>
{
    private readonly IDictionary<char, PrefixTree> inner;

    [ProtoMember(1)]
    public NodeItem[] Items
    {
        get
        {
            return this.inner.Select(item => new NodeItem() {Key = item.Key, Value = item.Value}).ToArray();
        }
        set
        {
            foreach( NodeItem item in value)
            {
                this.inner.Add(item.Key, item.Value);
            }
        }
    }
    ... // Omitted IDictionary members for clarity

这里的关键是获取附加到节点的 PrefixTree 的 AsReference 元数据。另请注意，Items 返回一个数组，如果您希望将其作为列表，则需要使用设置 OverwriteList 属性成员。

我还需要删除 PrefixTree 类型中每个字段的 readonly 关键字。这个单元测试对我来说通过了。

        [TestMethod]
    public void TestMethod1()
    {
        var tree = new PrefixTree();
        tree.Add("racket".ToCharArray());
        tree.Add("rambo".ToCharArray());

        PrefixTree tree2 = null;

        using (var stream = new MemoryStream())
        {
            Serializer.Serialize(stream, tree);
            stream.Position = 0;
            tree2 = Serializer.Deserialize<PrefixTree>(stream);
        }


        Assert.IsNotNull(tree2);
        Assert.AreEqual(tree._nodes.Count, tree2._nodes.Count);
        Assert.AreEqual(2, tree2._nodes['r']._nodes['a']._nodes.Count);      // 'c' and 'm'
        Assert.AreEqual('c', tree2._nodes['r']._nodes['a']._nodes.Values.First().Value);
        Assert.AreEqual('m', tree2._nodes['r']._nodes['a']._nodes.Values.Last().Value);
    }