Index: /trunk/sources/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.4/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding-3.4.csproj
===================================================================
--- /trunk/sources/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.4/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding-3.4.csproj	(revision 10561)
+++ /trunk/sources/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.4/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding-3.4.csproj	(revision 10562)
@@ -140,4 +140,6 @@
     <Compile Include="Interfaces\ISymbolicExpressionGrammarBase.cs" />
     <Compile Include="Interfaces\ISymbolicExpressionTreeGrammar.cs" />
+    <Compile Include="Interfaces\ISymbolicExpressionTreeNodeComparer.cs" />
+    <Compile Include="Interfaces\ISymbolicExpressionTreeNodeSimilarityComparer.cs" />
     <Compile Include="Interfaces\Operators\ISymbolicExpressionTreeArchitectureAlteringOperator.cs" />
     <Compile Include="Interfaces\Operators\ISymbolicExpressionTreeGrammarBasedOperator.cs" />
Index: /trunk/sources/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.4/Interfaces/ISymbolicExpressionTreeNodeComparer.cs
===================================================================
--- /trunk/sources/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.4/Interfaces/ISymbolicExpressionTreeNodeComparer.cs	(revision 10562)
+++ /trunk/sources/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.4/Interfaces/ISymbolicExpressionTreeNodeComparer.cs	(revision 10562)
@@ -0,0 +1,5 @@
+﻿using System.Collections.Generic;
+
+namespace HeuristicLab.Encodings.SymbolicExpressionTreeEncoding {
+  public interface ISymbolicExpressionTreeNodeComparer : IComparer<ISymbolicExpressionTreeNode> { }
+}
Index: /trunk/sources/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.4/Interfaces/ISymbolicExpressionTreeNodeSimilarityComparer.cs
===================================================================
--- /trunk/sources/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.4/Interfaces/ISymbolicExpressionTreeNodeSimilarityComparer.cs	(revision 10562)
+++ /trunk/sources/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.4/Interfaces/ISymbolicExpressionTreeNodeSimilarityComparer.cs	(revision 10562)
@@ -0,0 +1,10 @@
+﻿using System.Collections.Generic;
+using HeuristicLab.Core;
+
+namespace HeuristicLab.Encodings.SymbolicExpressionTreeEncoding {
+  public interface ISymbolicExpressionTreeNodeSimilarityComparer : IEqualityComparer<ISymbolicExpressionTreeNode>, IItem {
+    bool MatchConstantValues { get; set; }
+    bool MatchVariableWeights { get; set; }
+    bool MatchVariableNames { get; set; }
+  }
+}
Index: /trunk/sources/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/HeuristicLab.Problems.DataAnalysis.Symbolic-3.4.csproj
===================================================================
--- /trunk/sources/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/HeuristicLab.Problems.DataAnalysis.Symbolic-3.4.csproj	(revision 10561)
+++ /trunk/sources/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/HeuristicLab.Problems.DataAnalysis.Symbolic-3.4.csproj	(revision 10562)
@@ -126,4 +126,10 @@
       <SubType>Code</SubType>
     </Compile>
+    <Compile Include="Matching\SymbolicExpressionTreeCanonicalSorter.cs" />
+    <Compile Include="Matching\SymbolicExpressionTreeEqualityComparer.cs" />
+    <Compile Include="Matching\SymbolicExpressionTreeMatching.cs" />
+    <Compile Include="Matching\SymbolicExpressionTreeMaxCommonSequenceCalculator.cs" />
+    <Compile Include="Matching\SymbolicExpressionTreeNodeComparer.cs" />
+    <Compile Include="Matching\SymbolicExpressionTreeNodeSimilarityComparer.cs" />
     <Compile Include="SymbolicDataAnalysisExpressionPruningOperator.cs" />
     <Compile Include="Analyzers\SymbolicDataAnalysisVariableFrequencyAnalyzer.cs" />
Index: /trunk/sources/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Matching/SymbolicExpressionTreeCanonicalSorter.cs
===================================================================
--- /trunk/sources/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Matching/SymbolicExpressionTreeCanonicalSorter.cs	(revision 10562)
+++ /trunk/sources/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Matching/SymbolicExpressionTreeCanonicalSorter.cs	(revision 10562)
@@ -0,0 +1,30 @@
+﻿
+using System;
+using System.Collections.Generic;
+using System.Linq;
+using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding;
+
+namespace HeuristicLab.Problems.DataAnalysis.Symbolic {
+  public class SymbolicExpressionTreeCanonicalSorter {
+    private readonly HashSet<Type> nonSymmetricSymbols = new HashSet<Type> { typeof(Subtraction), typeof(Division) };
+
+    public void SortSubtrees(ISymbolicExpressionTree tree) {
+      SortSubtrees(tree.Root);
+    }
+
+    public void SortSubtrees(ISymbolicExpressionTreeNode node) {
+      if (node.SubtreeCount == 0) return;
+      var subtrees = node.Subtrees as List<ISymbolicExpressionTreeNode> ?? node.Subtrees.ToList();
+      if (IsSymmetric(node.Symbol)) {
+        var comparer = new SymbolicExpressionTreeNodeComparer();
+        subtrees.Sort(comparer);
+      }
+      foreach (var s in subtrees)
+        SortSubtrees(s);
+    }
+
+    private bool IsSymmetric(ISymbol s) {
+      return !nonSymmetricSymbols.Contains(s.GetType());
+    }
+  }
+}
Index: /trunk/sources/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Matching/SymbolicExpressionTreeEqualityComparer.cs
===================================================================
--- /trunk/sources/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Matching/SymbolicExpressionTreeEqualityComparer.cs	(revision 10562)
+++ /trunk/sources/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Matching/SymbolicExpressionTreeEqualityComparer.cs	(revision 10562)
@@ -0,0 +1,19 @@
+﻿using System;
+using System.Collections.Generic;
+using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding;
+
+namespace HeuristicLab.Problems.DataAnalysis.Symbolic {
+  public class SymbolicExpressionTreeEqualityComparer : IEqualityComparer<ISymbolicExpressionTree> {
+    public SymbolicExpressionTreeNodeSimilarityComparer SimilarityComparer { get; set; }
+
+    public bool Equals(ISymbolicExpressionTree a, ISymbolicExpressionTree b) {
+      if (SimilarityComparer == null) throw new Exception("SimilarityComparer needs to be initialized first.");
+      return a.Length == b.Length &&
+             SymbolicExpressionTreeMatching.Match(a.Root, b.Root, SimilarityComparer) == Math.Min(a.Length, b.Length);
+    }
+
+    public int GetHashCode(ISymbolicExpressionTree tree) {
+      return (tree.Length << 8) % 12345;
+    }
+  }
+}
Index: /trunk/sources/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Matching/SymbolicExpressionTreeMatching.cs
===================================================================
--- /trunk/sources/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Matching/SymbolicExpressionTreeMatching.cs	(revision 10562)
+++ /trunk/sources/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Matching/SymbolicExpressionTreeMatching.cs	(revision 10562)
@@ -0,0 +1,48 @@
+﻿using System;
+using System.Collections.Generic;
+using System.Linq;
+using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding;
+//using HeuristicLab.EvolutionTracking;
+
+namespace HeuristicLab.Problems.DataAnalysis.Symbolic {
+  public static class SymbolicExpressionTreeMatching {
+    public static bool ContainsSubtree(this ISymbolicExpressionTreeNode root, ISymbolicExpressionTreeNode subtree, SymbolicExpressionTreeNodeSimilarityComparer comparer) {
+      return FindMatches(root, subtree, comparer).Any();
+    }
+    public static IEnumerable<ISymbolicExpressionTreeNode> FindMatches(ISymbolicExpressionTree tree, ISymbolicExpressionTreeNode subtree, SymbolicExpressionTreeNodeSimilarityComparer comparer) {
+      return FindMatches(tree.Root, subtree, comparer);
+    }
+
+    public static IEnumerable<ISymbolicExpressionTreeNode> FindMatches(ISymbolicExpressionTreeNode root, ISymbolicExpressionTreeNode subtree, SymbolicExpressionTreeNodeSimilarityComparer comp) {
+      var fragmentLength = subtree.GetLength();
+      // below, we use ">=" for Match(n, subtree, comp) >= fragmentLength because in case of relaxed conditions, 
+      // we can have multiple matches of the same node
+
+      return root.IterateNodesBreadth().Where(n => n.GetLength() >= fragmentLength && Match(n, subtree, comp) == fragmentLength);
+    }
+
+    ///<summary>
+    /// Finds the longest common subsequence in quadratic time and linear space
+    /// Variant of:
+    /// D. S. Hirschberg. A linear space algorithm for or computing maximal common subsequences. 1975.
+    /// http://dl.acm.org/citation.cfm?id=360861
+    /// </summary>
+    /// <returns>Number of pairs that were matched</returns>
+    public static int Match(ISymbolicExpressionTreeNode a, ISymbolicExpressionTreeNode b, SymbolicExpressionTreeNodeSimilarityComparer comp) {
+      if (!comp.Equals(a, b)) return 0;
+      int m = a.SubtreeCount;
+      int n = b.SubtreeCount;
+      if (m == 0 || n == 0) return 1;
+      var matrix = new int[m + 1, n + 1];
+      for (int i = 1; i <= m; ++i) {
+        var ai = a.GetSubtree(i - 1);
+        for (int j = 1; j <= n; ++j) {
+          var bj = b.GetSubtree(j - 1);
+          int match = Match(ai, bj, comp);
+          matrix[i, j] = Math.Max(Math.Max(matrix[i, j - 1], matrix[i - 1, j]), matrix[i - 1, j - 1] + match);
+        }
+      }
+      return matrix[m, n] + 1;
+    }
+  }
+}
Index: /trunk/sources/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Matching/SymbolicExpressionTreeMaxCommonSequenceCalculator.cs
===================================================================
--- /trunk/sources/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Matching/SymbolicExpressionTreeMaxCommonSequenceCalculator.cs	(revision 10562)
+++ /trunk/sources/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Matching/SymbolicExpressionTreeMaxCommonSequenceCalculator.cs	(revision 10562)
@@ -0,0 +1,59 @@
+﻿using System;
+using System.Collections.Generic;
+
+namespace HeuristicLab.Problems.DataAnalysis.Symbolic.Matching {
+  public class MaxCommonSequenceCalculator<T, U>
+    where T : class
+    where U : IEqualityComparer<T> {
+
+    public U Comparer { get; set; }
+    private int[,] matrix;
+    private List<T> sequence;
+
+    /// <summary>
+    /// Calculate the maximal common subsequence between arrays a and b and return it
+    /// </summary>
+    /// <param name="a"></param>
+    /// <param name="b"></param>
+    /// <returns></returns>
+    public IEnumerable<T> Calculate(T[] a, T[] b) {
+      int m = a.Length;
+      int n = b.Length;
+
+      if (m == 0 || n == 0) return null;
+      sequence = new List<T>();
+      matrix = new int[m + 1, n + 1];
+
+      for (int i = 0; i <= m; ++i) {
+        for (int j = 0; j <= n; ++j) {
+          if (i == 0 || j == 0) {
+            matrix[i, j] = 0;
+          } else if (Comparer.Equals(a[i - 1], b[j - 1])) {
+            matrix[i, j] = matrix[i - 1, j - 1] + 1;
+          } else {
+            matrix[i, j] = Math.Max(matrix[i - 1, j], matrix[i, j - 1]);
+          }
+        }
+      }
+      recon(a, b, n, m);
+      return sequence;
+    }
+
+    private void recon(T[] a, T[] b, int i, int j) {
+      while (true) {
+        if (i == 0 || j == 0) return;
+        if (Comparer.Equals(a[i - 1], b[j - 1])) {
+          recon(a, b, i - 1, j - 1);
+          sequence.Add(a[i - 1]);
+        } else if (matrix[i - 1, j] > matrix[i, j - 1]) {
+          i = i - 1;
+          continue;
+        } else {
+          j = j - 1;
+          continue;
+        }
+        break;
+      }
+    }
+  }
+}
Index: /trunk/sources/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Matching/SymbolicExpressionTreeNodeComparer.cs
===================================================================
--- /trunk/sources/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Matching/SymbolicExpressionTreeNodeComparer.cs	(revision 10562)
+++ /trunk/sources/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Matching/SymbolicExpressionTreeNodeComparer.cs	(revision 10562)
@@ -0,0 +1,33 @@
+﻿using System;
+using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding;
+
+namespace HeuristicLab.Problems.DataAnalysis.Symbolic {
+  // this comparer considers that a < b if the type of a is "greater" than the type of b, for example:
+  // - A function node is "greater" than a terminal node
+  // - A variable terminal is "greater" than a constant terminal
+  // - used for bringing subtrees to a "canonical" form when the operation allows reordering of arguments
+  public class SymbolicExpressionTreeNodeComparer : ISymbolicExpressionTreeNodeComparer {
+    public int Compare(ISymbolicExpressionTreeNode a, ISymbolicExpressionTreeNode b) {
+      if (!(a is SymbolicExpressionTreeTerminalNode)) {
+        return b is SymbolicExpressionTreeTerminalNode
+          ? -1
+          : string.Compare(a.Symbol.Name, b.Symbol.Name, StringComparison.Ordinal);
+      }
+      if (!(b is SymbolicExpressionTreeTerminalNode)) return 1;
+      // at this point we know a and b are terminal nodes
+      var va = a as VariableTreeNode;
+      if (va != null) {
+        if (b is ConstantTreeNode) return -1;
+        var vb = (VariableTreeNode)b;
+        return (va.VariableName.Equals(vb.VariableName)
+          ? va.Weight.CompareTo(vb.Weight)
+          : string.Compare(va.VariableName, vb.VariableName, StringComparison.Ordinal));
+      }
+      // at this point we know for sure that a is a constant tree node
+      if (b is VariableTreeNode) return 1;
+      var ca = (ConstantTreeNode)a;
+      var cb = (ConstantTreeNode)b;
+      return ca.Value.CompareTo(cb.Value);
+    }
+  }
+}
Index: /trunk/sources/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Matching/SymbolicExpressionTreeNodeSimilarityComparer.cs
===================================================================
--- /trunk/sources/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Matching/SymbolicExpressionTreeNodeSimilarityComparer.cs	(revision 10562)
+++ /trunk/sources/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Matching/SymbolicExpressionTreeNodeSimilarityComparer.cs	(revision 10562)
@@ -0,0 +1,76 @@
+﻿using HeuristicLab.Common;
+using HeuristicLab.Core;
+using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding;
+using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
+
+namespace HeuristicLab.Problems.DataAnalysis.Symbolic {
+  [Item("SymbolicExpressionTreeNodeSimilarityComparer", "A comparison operator that checks node equality based on different similarity measures.")]
+  [StorableClass]
+  public class SymbolicExpressionTreeNodeSimilarityComparer : Item, ISymbolicExpressionTreeNodeSimilarityComparer {
+    [StorableConstructor]
+    private SymbolicExpressionTreeNodeSimilarityComparer(bool deserializing) : base(deserializing) { }
+    private SymbolicExpressionTreeNodeSimilarityComparer(SymbolicExpressionTreeNodeSimilarityComparer original, Cloner cloner)
+      : base(original, cloner) {
+      matchConstantValues = original.matchConstantValues;
+      matchVariableNames = original.matchVariableNames;
+      matchVariableWeights = original.matchVariableWeights;
+    }
+    public override IDeepCloneable Clone(Cloner cloner) { return new SymbolicExpressionTreeNodeSimilarityComparer(this, cloner); }
+
+    // more flexible matching criteria 
+    [Storable]
+    private bool matchConstantValues;
+    public bool MatchConstantValues {
+      get { return matchConstantValues; }
+      set { matchConstantValues = value; }
+    }
+
+    [Storable]
+    private bool matchVariableNames;
+    public bool MatchVariableNames {
+      get { return matchVariableNames; }
+      set { matchVariableNames = value; }
+    }
+
+    [Storable]
+    private bool matchVariableWeights;
+    public bool MatchVariableWeights {
+      get { return matchVariableWeights; }
+      set { matchVariableWeights = value; }
+    }
+
+    [StorableHook(HookType.AfterDeserialization)]
+    private void AfterDeserialization() {
+    }
+
+    public SymbolicExpressionTreeNodeSimilarityComparer() {
+      matchConstantValues = true;
+      matchVariableNames = true;
+      matchVariableWeights = true;
+    }
+
+    public int GetHashCode(ISymbolicExpressionTreeNode n) {
+      return n.ToString().ToLower().GetHashCode();
+    }
+
+    public bool Equals(ISymbolicExpressionTreeNode a, ISymbolicExpressionTreeNode b) {
+      if (!(a is SymbolicExpressionTreeTerminalNode))
+        // if a and b are non terminal nodes, check equality of symbol names
+        return !(b is SymbolicExpressionTreeTerminalNode) && a.Symbol.Name.Equals(b.Symbol.Name);
+      var va = a as VariableTreeNode;
+      if (va != null) {
+        var vb = b as VariableTreeNode;
+        if (vb == null) return false;
+
+        return (!MatchVariableNames || va.VariableName.Equals(vb.VariableName)) && (!MatchVariableWeights || va.Weight.Equals(vb.Weight));
+      }
+      var ca = a as ConstantTreeNode;
+      if (ca != null) {
+        var cb = b as ConstantTreeNode;
+        if (cb == null) return false;
+        return (!MatchConstantValues || ca.Value.Equals(cb.Value));
+      }
+      return false;
+    }
+  }
+}
