Serialize tiền tố cây

Question

tôi nhận được một ProtoException ("Có thể đệ quy phát hiện (offset: 4 mức (s)): o EOW") khi tuần tự một cấu trúc cây như vậy:

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

Việc thực hiện cây:

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

Tôi có trang trí với các thuộc tính sai hoặc tôi đã thiết kế đơn giản cây không có thể tuần tự không?

Edit: cố gắng này không có kết quả:

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

Các _parent và giá trị của _nodes cả điểm đến cùng loại (PrefixTree), nhưng chỉ có _parent được đánh dấu là "AsReference".

Nếu bạn đi bộ ngăn xếp tuần tự, bạn sẽ thấy rằng Giá trị của giá trị Từ điển được tuần tự hóa độc lập với mục _parent và không được chọn cho một bản sao trùng lặp.

Khi nó đi bộ trên cây có kiểm tra độ sâu tuần tự hóa nội bộ 25, tại đó nó bắt đầu phát hiện các bản sao trùng lặp. Nếu giá trị này lớn hơn, nó sẽ không ném một ngoại lệ, nếu nó nhỏ hơn nó sẽ ném lên một nút cao hơn cây.

Tôi cũng không nghĩ rằng điều này có thể được deserializable, và chắc chắn nếu nó đã làm cho giá trị của trường _parent của mỗi nút con sẽ không giống với container _nodes.

Bạn cần tạo loại từ điển của riêng bạn (subclass Dictionary <,> hoặc thực hiện IDictionary <,>) để bạn có thể thêm thuộc tính [ProtoContract] và điều khiển tuần tự hóa các mục của từ điển.

tức

[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 

chìa khóa ở đây là để có được các siêu dữ liệu AsReference gắn liền với PrefixTree của nút. Cũng lưu ý rằng các mục sẽ trả về một mảng, nếu bạn muốn nó như là một danh sách, thì bạn cần sử dụng thiết lập thành viên thuộc tính OverwriteList.

Tôi cũng cần xóa từ khóa chỉ đọc cho từng trường trong loại PrefixTree. Kiểm tra đơn vị này được chuyển cho tôi.

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