序列化前綴樹

Question

我得到一個ProtoException（ 「檢測到可能的遞歸（偏移：4級（S））：○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

的_nodes的_parent和價值都指向相同的類型（PrefixTree），但只有_parent被標記爲「AsReference」。

如果您使用序列化堆棧，將會看到Dictionary值的值獨立於_parent項目進行序列化，並且不會檢查重複實例。

當它走過樹時，有一個25的內部序列化深度檢查，在此處它開始檢測重複的實例。如果此值較大，則不會拋出異常，如果它較小，則會拋出樹上較高的節點。

我也不認爲這將是反序列化的，當然，如果它確實每個子節點的_parent字段的值不會與_nodes容器是同一個實例。您需要創建自己的字典類型（子類字典<，>或實現IDictionary <，>），以便您可以添加[ProtoContract]屬性並控制字典項目的序列化。

即

[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); 
    }