Free cookie consent management tool by TermsFeed Policy Generator

source: branches/HeuristicLab.EvolutionaryTracking/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.4/SymbolicExpressionTreeMatching.cs @ 7785

Last change on this file since 7785 was 7785, checked in by bburlacu, 12 years ago

#1772: Moved tree matching functionality in separate class, implemented new tree fragments analyzer. Fixed bug in GetCutIndex method.

File size: 7.6 KB
Line 
1using System.Collections.Generic;
2using System.Linq;
3using HeuristicLab.Problems.DataAnalysis.Symbolic;
4
5namespace HeuristicLab.Encodings.SymbolicExpressionTreeEncoding {
6  public class SymbolicExpressionTreeNodeComparer : IEqualityComparer<ISymbolicExpressionTreeNode> {
7
8    public SymbolicExpressionTreeNodeComparer(int similarityLevel) {
9      _similarityLevel = similarityLevel;
10    }
11
12    public int GetHashCode(ISymbolicExpressionTreeNode n) {
13      return n.ToString().ToLower().GetHashCode();
14    }
15
16    public bool Equals(ISymbolicExpressionTreeNode a, ISymbolicExpressionTreeNode b) {
17      if (a.SubtreeCount != b.SubtreeCount) { return false; }
18      if (a.SubtreeCount > 0) { return a.Symbol.ToString().Equals(b.Symbol.ToString()); }
19      // compare leaf nodes according to desired similarity level
20      switch (_similarityLevel) {
21        case ((int)SymbolicExpressionTreeMatching.SimilarityLevel.Exact):
22          if (a is ConstantTreeNode && b is ConstantTreeNode) {
23            return ((ConstantTreeNode)a).Value.Equals(((ConstantTreeNode)b).Value);
24          }
25          if (a is VariableTreeNode && b is VariableTreeNode) {
26            return (a as VariableTreeNode).Weight.Equals((b as VariableTreeNode).Weight);
27          }
28          return false;
29        case ((int)SymbolicExpressionTreeMatching.SimilarityLevel.High):
30          return (a is ConstantTreeNode && b is ConstantTreeNode) || (a is VariableTreeNode && b is VariableTreeNode);
31        case ((int)SymbolicExpressionTreeMatching.SimilarityLevel.Relaxed):
32          return true;
33        default:
34          return false;
35      }
36    }
37
38    private readonly int _similarityLevel;
39  }
40
41  // tree equality
42  public class SymbolicExpressionTreeComparer : IEqualityComparer<ISymbolicExpressionTree> {
43    public bool Equals(ISymbolicExpressionTree a, ISymbolicExpressionTree b) {
44      return SymbolicExpressionTreeMatching.FindMatch(a, b, _mode) == 0;
45    }
46
47    public int GetHashCode(ISymbolicExpressionTree tree) {
48      return tree.Length;
49    }
50
51    private int _mode;
52    public void SetComparisonMode(int mode) {
53      _mode = mode;
54    }
55  }
56
57  public static class SymbolicExpressionTreeMatching {
58    public enum SimilarityLevel {
59      Exact,   // everything is matched bit by bit (functions and terminals)
60      High,    // symbols are matched. leaf node types are matched
61      Relaxed  // only symbols are matched, leafs count as wildcards
62    }
63
64    public static bool IsSimilarTo(this ISymbolicExpressionTree t1, ISymbolicExpressionTree t2, int mode) {
65      return FindMatch(t1, t2, mode) == 0;
66    }
67    public static bool IsSimilarTo(this ISymbolicExpressionTreeNode t1, ISymbolicExpressionTreeNode t2, int mode) {
68      return FindMatch(t1, t2, mode) == 0;
69    }
70
71    public static bool ContainsFragment(this ISymbolicExpressionTree tree, ISymbolicExpressionTreeNode fragment, int mode) {
72      var nodes = tree.IterateNodesPostfix().ToArray();
73      var fragments = fragment.IterateNodesPostfix().ToArray();
74      return FindMatch(nodes, fragments, mode) != -1;
75    }
76
77    #region FindMatch signatures
78    public static int FindMatch(ISymbolicExpressionTree t0, ISymbolicExpressionTree t1, int mode) {
79      return FindMatch(t0.IterateNodesPostfix().ToArray(), t1.IterateNodesPostfix().ToArray(), mode);
80    }
81    private static int FindMatch(ISymbolicExpressionTreeNode t0, ISymbolicExpressionTreeNode t1, int mode) {
82      return FindMatch(t0.IterateNodesPostfix().ToArray(), t1.IterateNodesPostfix().ToArray(), mode);
83    }
84    private static int FindMatch(ISymbolicExpressionTree t0, ISymbolicExpressionTreeNode t1, int mode) {
85      return FindMatch(t0.IterateNodesPostfix().ToArray(), t1.IterateNodesPostfix().ToArray(), mode);
86    }
87    private static int FindMatch(ISymbolicExpressionTreeNode t0, ISymbolicExpressionTree t1, int mode) {
88      return FindMatch(t0.IterateNodesPostfix().ToArray(), t1.IterateNodesPostfix().ToArray(), mode);
89    }
90    #endregion
91
92    // convenience methods for less typing :)
93    private static IEnumerator<ISymbolicExpressionTreeNode> Enumerator(this ISymbolicExpressionTree tree) {
94      return tree.IterateNodesPostfix().GetEnumerator();
95    }
96    private static IEnumerator<ISymbolicExpressionTreeNode> Enumerator(this ISymbolicExpressionTreeNode tree) {
97      return tree.IterateNodesPostfix().GetEnumerator();
98    }
99    // method for breath-width iteration of nodes
100    private static IEnumerable<ISymbolicExpressionTreeNode> IterateNodes(this ISymbolicExpressionTree tree) {
101      return IterateNodes(tree.Root);
102    }
103
104    private static IEnumerable<ISymbolicExpressionTreeNode> IterateNodes(this ISymbolicExpressionTreeNode root) {
105      var list = new List<ISymbolicExpressionTreeNode> { root };
106      int offset = 0, count = 1;
107      while (offset != count) {
108        var c = count;
109        for (int i = offset; i != count; ++i) {
110          yield return list[i]; // TODO: look into yield performance (vs returning the whole list at the end)
111          if (!list[i].Subtrees.Any()) continue;
112          list.AddRange(list[i].Subtrees);
113        }
114        offset = c;
115        count = list.Count;
116      }
117      //return list;
118    }
119
120    /// <summary>
121    /// This method finds the point where parent and child differ. For instance in the case of crossover,
122    /// it will return the node that was swapped into parent0 from parent1
123    /// Prerequisites: as the naming implies, heredity should exist between parent and child,
124    /// otherwise this method would not make much sense (it would always return the root of child)
125    /// </summary>
126    /// <param name="parent">The individual from the previous generation that was crossed over or mutated to produce child</param>
127    /// <param name="child">The result of a genetic operation applied on parent</param>
128    /// <returns>A symbolic expression tree node representing the difference fragment between parent and child</returns>
129    public static ISymbolicExpressionTreeNode GetFragmentDiff(ISymbolicExpressionTree parent, ISymbolicExpressionTree child) {
130      var e1 = parent.Enumerator();
131      var e2 = child.Enumerator();
132      while (e1.MoveNext() && e2.MoveNext()) {
133        var comparer = new SymbolicExpressionTreeNodeComparer((int)SimilarityLevel.Exact);
134        if (!comparer.Equals(e1.Current, e2.Current)) { return e2.Current; } // return the fragment by which child differs from parent
135      }
136      return null;
137    }
138
139    // returns the index in the sequence 'seq', where pattern 'pat' is matched, or -1 for no match
140    // -1 means no match, 0 means perfect match (the sequences overlap, hence the match index is 0)
141    public static int FindMatch(ISymbolicExpressionTreeNode[] seq, ISymbolicExpressionTreeNode[] pat, int mode) {
142      int patlen = pat.Length;
143      int seqlen = seq.Length;
144      if (patlen == 0 || seqlen == 0) return -1;
145      var comparer = new SymbolicExpressionTreeNodeComparer(mode);
146      if (patlen == seqlen) return seq.SequenceEqual(pat, comparer) ? 0 : -1;
147      //int i = patlen;           
148      //while (i <= seqlen) {
149      //  var ch = seq[i - 1];
150      //  if (comparer.Equals(ch, pat.Last()))
151      //    if (seq.Skip(i - patlen).Take(patlen).SequenceEqual(pat, comparer))
152      //      return i - patlen;
153      //  ++i;
154      //}
155      for (int i = patlen; i <= seqlen; ++i) {
156        if (comparer.Equals(seq[i - 1], pat.Last())) // first check if last element is a match
157          if (seq.Skip(i - patlen).Take(patlen).SequenceEqual(pat, comparer)) // then check the whole sequence
158            return i - patlen;
159      }
160      return -1;
161    }
162  }
163}
Note: See TracBrowser for help on using the repository browser.