Changeset 9293 for branches/HeuristicLab.EvolutionaryTracking/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4

Timestamp:

03/07/13 14:53:43 (11 years ago)

Author:

bburlacu

Message:

#1772: Added new similarity measures and moved them to separate class SymbolicDataAnalysisExpressionTreeSimilarity.cs.

Location:

branches/HeuristicLab.EvolutionaryTracking/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4

Files:

• HeuristicLab.Problems.DataAnalysis.Symbolic-3.4.csproj (modified) (4 diffs)
• SymbolicDataAnalysisExpressionTreeMatching.cs (modified) (3 diffs)
• SymbolicDataAnalysisExpressionTreeSimilarity.cs (added)

branches/HeuristicLab.EvolutionaryTracking/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/HeuristicLab.Problems.DataAnalysis.Symbolic-3.4.csproj

@@ -50 +50 @@
     <DebugType>pdbonly</DebugType>
     <Optimize>true</Optimize>
-    <OutputPath>..\..\..\..\Trunk\sources\bin\</OutputPath>
+    <OutputPath>..\..\..\..\trunk\sources\bin\</OutputPath>
     <DefineConstants>TRACE</DefineConstants>
     <ErrorReport>prompt</ErrorReport>
@@ -66 +66 @@
   </PropertyGroup>
   <PropertyGroup Condition=" '$(Configuration)|$(Platform)' == 'Release|x64' ">
-    <OutputPath>$(SolutionDir)\bin\</OutputPath>
+    <OutputPath>..\..\..\..\trunk\sources\bin\</OutputPath>
     <DefineConstants>TRACE</DefineConstants>
     <Optimize>true</Optimize>
@@ -84 +84 @@
   </PropertyGroup>
   <PropertyGroup Condition=" '$(Configuration)|$(Platform)' == 'Release|x86' ">
-    <OutputPath>$(SolutionDir)\bin\</OutputPath>
+    <OutputPath>..\..\..\..\trunk\sources\bin\</OutputPath>
     <DefineConstants>TRACE</DefineConstants>
     <Optimize>true</Optimize>
@@ -200 +200 @@
     <Compile Include="Interfaces\ISymbolicDataAnalysisProblem.cs" />
     <Compile Include="SymbolicDataAnalysisExpressionTreeMatching.cs" />
+    <Compile Include="SymbolicDataAnalysisExpressionTreeSimilarity.cs" />
     <Compile Include="SymbolicDataAnalysisModel.cs">
       <SubType>Code</SubType>

branches/HeuristicLab.EvolutionaryTracking/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/SymbolicDataAnalysisExpressionTreeMatching.cs

@@ -161 +161 @@
 
 public static class SymbolicExpressionTreeMatching {
-  public static bool IsSimilarTo(this ISymbolicExpressionTree t1, ISymbolicExpressionTree t2, SymbolicExpressionTreeNodeSimilarityComparer comparer) {
-    return t1.Root.IsSimilarTo(t2.Root, comparer);
-  }
-  public static bool IsSimilarTo(this ISymbolicExpressionTreeNode t1, ISymbolicExpressionTreeNode t2, SymbolicExpressionTreeNodeSimilarityComparer comparer) {
-    return Match(t1, t2, comparer) == Math.Min(t1.GetLength(), t2.GetLength());
-  }
   public static bool ContainsFragment(this ISymbolicExpressionTreeNode root, IFragment fragment, SymbolicExpressionTreeNodeSimilarityComparer comparer) {
     return FindMatches(root, fragment.Root, comparer).Any();
@@ -179 +173 @@
     // below, we use ">=" for Match(n, fragment, 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, fragment, comp) == fragmentLength);
   }
@@ -206 +201 @@
   }
 }
+
+public class MaximalCommonSubsequenceCalculator {
+  private ISymbolicExpressionTreeNode[] x;
+  private ISymbolicExpressionTreeNode[] y;
+  private List<ISymbolicExpressionTreeNode> maxCommonSubseq;
+  private double[,] matrix;
+
+  public SymbolicExpressionTreeNodeSimilarityComparer comparer;
+
+  public List<ISymbolicExpressionTreeNode> Calculate(ISymbolicExpressionTreeNode n1, ISymbolicExpressionTreeNode n2) {
+    if (comparer == null) throw new Exception("Comparer cannot be null.");
+
+    x = n1.IterateNodesPrefix().ToArray();
+    y = n2.IterateNodesPrefix().ToArray();
+
+    if (maxCommonSubseq == null) maxCommonSubseq = new List<ISymbolicExpressionTreeNode>();
+    else maxCommonSubseq.Clear();
+
+    int n = x.Length;
+    int m = y.Length;
+
+    matrix = new double[n + 1, m + 1];
+
+    for (int i = 0; i <= n; ++i) {
+      for (int j = 0; j <= m; ++j) {
+        if (i == 0 || j == 0) {
+          matrix[i, j] = 0;
+        } else if (comparer.Equals(x[i - 1], y[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(n, m);
+    return new List<ISymbolicExpressionTreeNode>(maxCommonSubseq);
+  }
+
+  private void recon(int i, int j) {
+    if (i == 0 || j == 0) return;
+    if (comparer.Equals(x[i - 1], y[j - 1])) {
+      recon(i - 1, j - 1);
+      maxCommonSubseq.Add(x[i - 1]);
+    } else if (matrix[i - 1, j] > matrix[i, j - 1]) {
+      recon(i - 1, j);
+    } else recon(i, j - 1);
+  }
+}