#region License Information
/* HeuristicLab
* Copyright (C) Heuristic and Evolutionary Algorithms Laboratory (HEAL)
*
* This file is part of HeuristicLab.
*
* HeuristicLab is free software: you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
* the Free Software Foundation, either version 3 of the License, or
* (at your option) any later version.
*
* HeuristicLab is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with HeuristicLab. If not, see .
*/
#endregion
using System;
using System.Collections.Generic;
using System.Linq;
using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding;
using static HeuristicLab.Problems.DataAnalysis.Symbolic.SymbolicExpressionHashExtensions;
namespace HeuristicLab.Problems.DataAnalysis.Symbolic {
public static class SymbolicExpressionTreeHash {
private static readonly Number number = new Number();
private static ISymbolicExpressionTreeNode ActualRoot(this ISymbolicExpressionTree tree) => tree.Root.GetSubtree(0).GetSubtree(0);
public static ulong HashFunction(byte[] input) => HashUtil.DJBHash(input);
#region tree hashing
public static ulong[] Hash(this ISymbolicExpressionTree tree, bool simplify = false, bool strict = false) {
return tree.ActualRoot().Hash(simplify, strict);
}
public static ulong[] Hash(this ISymbolicExpressionTreeNode node, bool simplify = false, bool strict = false) {
var hashNodes = simplify ? node.MakeNodes(strict).Simplify(HashFunction) : node.MakeNodes(strict).Sort(HashFunction);
var hashes = new ulong[hashNodes.Length];
for (int i = 0; i < hashes.Length; ++i) {
hashes[i] = hashNodes[i].CalculatedHashValue;
}
return hashes;
}
public static ulong ComputeHash(this ISymbolicExpressionTree tree, bool simplify = false, bool strict = false) {
return ComputeHash(tree.ActualRoot(), simplify, strict);
}
public static ulong ComputeHash(this ISymbolicExpressionTreeNode treeNode, bool simplify = false, bool strict = false) {
return treeNode.Hash(simplify, strict).Last();
}
public static HashNode ToHashNode(this ISymbolicExpressionTreeNode node, bool strict = false) {
var symbol = node.Symbol;
var name = symbol.Name;
if (node is INumericTreeNode numNode) {
name = strict ? numNode.Value.ToString() : "Number";
} else if (node is VariableTreeNode variableNode) {
name = strict ? variableNode.Weight.ToString() + variableNode.VariableName : variableNode.VariableName;
}
var hash = (ulong)name.GetHashCode();
var hashNode = new HashNode {
Data = node,
Arity = node.SubtreeCount,
Size = node.SubtreeCount,
IsCommutative = node.Symbol is Addition || node.Symbol is Multiplication,
Enabled = true,
HashValue = hash,
CalculatedHashValue = hash
};
if (symbol is Addition) {
hashNode.Simplify = SimplifyAddition;
} else if (symbol is Multiplication) {
hashNode.Simplify = SimplifyMultiplication;
} else if (symbol is Division) {
hashNode.Simplify = SimplifyDivision;
} else if (symbol is Logarithm || symbol is Exponential || symbol is Sine || symbol is Cosine) {
hashNode.Simplify = SimplifyUnaryNode;
} else if (symbol is Subtraction) {
hashNode.Simplify = SimplifyBinaryNode;
}
return hashNode;
}
public static HashNode[] MakeNodes(this ISymbolicExpressionTree tree, bool strict = false) {
return MakeNodes(tree.ActualRoot(), strict);
}
public static HashNode[] MakeNodes(this ISymbolicExpressionTreeNode node, bool strict = false) {
return node.IterateNodesPostfix().Select(x => x.ToHashNode(strict)).ToArray().UpdateNodeSizes();
}
#endregion
#region tree similarity
public static double ComputeSimilarity(ISymbolicExpressionTree t1, ISymbolicExpressionTree t2, bool simplify = false, bool strict = false) {
return ComputeSimilarity(t1.ActualRoot(), t2.ActualRoot(), simplify, strict);
}
public static double ComputeSimilarity(ISymbolicExpressionTreeNode t1, ISymbolicExpressionTreeNode t2, bool simplify = false, bool strict = false) {
var lh = t1.Hash(simplify, strict);
var rh = t2.Hash(simplify, strict);
Array.Sort(lh);
Array.Sort(rh);
return ComputeSimilarity(lh, rh);
}
// requires lhs and rhs to be sorted
public static int IntersectCount(this ulong[] lh, ulong[] rh) {
int count = 0;
for (int i = 0, j = 0; i < lh.Length && j < rh.Length;) {
var h1 = lh[i];
var h2 = rh[j];
if (h1 == h2) {
++count;
++i;
++j;
} else if (h1 < h2) {
++i;
} else if (h1 > h2) {
++j;
}
}
return count;
}
public static IEnumerable Intersect(this ulong[] lh, ulong[] rh) {
for (int i = 0, j = 0; i < lh.Length && j < rh.Length;) {
var h1 = lh[i];
var h2 = rh[j];
if (h1 == h2) {
yield return h1;
++i;
++j;
} else if (h1 < h2) {
++i;
} else if (h1 > h2) {
++j;
}
}
}
// this will only work if lh and rh are sorted
public static double ComputeSimilarity(ulong[] lh, ulong[] rh) {
return 2d * IntersectCount(lh, rh) / (lh.Length + rh.Length);
}
public static double ComputeAverageSimilarity(IList trees, bool simplify = false, bool strict = false) {
var total = trees.Count * (trees.Count - 1) / 2;
double avg = 0;
var hashes = new ulong[trees.Count][];
// build hash arrays
for (int i = 0; i < trees.Count; ++i) {
var nodes = trees[i].MakeNodes(strict);
hashes[i] = (simplify ? nodes.Simplify(HashFunction) : nodes.Sort(HashFunction)).Select(x => x.CalculatedHashValue).ToArray();
Array.Sort(hashes[i]);
}
// compute similarity matrix
for (int i = 0; i < trees.Count - 1; ++i) {
for (int j = i + 1; j < trees.Count; ++j) {
avg += ComputeSimilarity(hashes[i], hashes[j]);
}
}
return avg / total;
}
public static double[,] ComputeSimilarityMatrix(IList hashes) {
// compute similarity matrix
var n = hashes.Count;
var sim = new double[n, n];
for (int i = 0; i < n - 1; ++i) {
for (int j = i + 1; j < n; ++j) {
sim[i, j] = sim[j, i] = ComputeSimilarity(hashes[i], hashes[j]);
}
}
return sim;
}
public static double[,] ComputeSimilarityMatrix(IList trees, bool simplify = false, bool strict = false) {
var hashes = new ulong[trees.Count][];
// build hash arrays
for (int i = 0; i < trees.Count; ++i) {
var nodes = trees[i].MakeNodes(strict);
hashes[i] = (simplify ? nodes.Simplify(HashFunction) : nodes.Sort(HashFunction)).Select(x => x.CalculatedHashValue).ToArray();
Array.Sort(hashes[i]);
}
return ComputeSimilarityMatrix(hashes);
}
#endregion
#region parse a nodes array back into a tree
public static ISymbolicExpressionTree ToTree(this HashNode[] nodes) {
var root = new ProgramRootSymbol().CreateTreeNode();
var start = new StartSymbol().CreateTreeNode();
root.AddSubtree(start);
start.AddSubtree(nodes.ToSubtree());
return new SymbolicExpressionTree(root);
}
public static ISymbolicExpressionTreeNode ToSubtree(this HashNode[] nodes) {
var treeNodes = nodes.Select(x => x.Data.Symbol.CreateTreeNode()).ToArray();
for (int i = nodes.Length - 1; i >= 0; --i) {
var node = nodes[i];
if (node.IsLeaf) {
if (node.Data is VariableTreeNode variable) {
var variableTreeNode = (VariableTreeNode)treeNodes[i];
variableTreeNode.VariableName = variable.VariableName;
variableTreeNode.Weight = variable.Weight;
} else if (node.Data is INumericTreeNode existingNumNode) {
var newNumNode = (NumberTreeNode)treeNodes[i];
newNumNode.Value = existingNumNode.Value;
}
continue;
}
var treeNode = treeNodes[i];
foreach (var j in nodes.IterateChildren(i)) {
treeNode.AddSubtree(treeNodes[j]);
}
}
return treeNodes.Last();
}
private static T CreateTreeNode(this ISymbol symbol) where T : class, ISymbolicExpressionTreeNode {
return (T)symbol.CreateTreeNode();
}
#endregion
#region tree simplification
// these simplification methods rely on the assumption that child nodes of the current node have already been simplified
// (in other words simplification should be applied in a bottom-up fashion)
public static ISymbolicExpressionTree Simplify(ISymbolicExpressionTree tree) {
return tree.MakeNodes().Simplify(HashFunction).ToTree();
}
public static void SimplifyAddition(ref HashNode[] nodes, int i) {
// simplify additions of terms by eliminating terms with the same symbol and hash
var children = nodes.IterateChildren(i);
// we always assume the child nodes are sorted
var curr = children[0];
var node = nodes[i];
foreach (var j in children.Skip(1)) {
if (nodes[j] == nodes[curr]) {
nodes.SetEnabled(j, false);
node.Arity--;
} else {
curr = j;
}
}
if (node.Arity == 1) { // if the arity is 1 we don't need the addition node at all
node.Enabled = false;
}
}
// simplify multiplications by reducing numbers and div terms
public static void SimplifyMultiplication(ref HashNode[] nodes, int i) {
var node = nodes[i];
var children = nodes.IterateChildren(i);
for (int j = 0; j < children.Length; ++j) {
var c = children[j];
var child = nodes[c];
if (!child.Enabled)
continue;
var symbol = child.Data.Symbol;
if (child.Data is NumberTreeNode firstNum) {
// fold sibling number nodes into the first number
for (int k = j + 1; k < children.Length; ++k) {
var sibling = nodes[children[k]];
if (sibling.Data is INumericTreeNode otherNum) {
sibling.Enabled = false;
node.Arity--;
firstNum.Value *= otherNum.Value;
} else {
break;
}
}
} else if (child.Data is VariableTreeNode variable) {
// fold sibling number nodes into the variable weight
for (int k = j + 1; k < children.Length; ++k) {
var sibling = nodes[children[k]];
if (sibling.Data is INumericTreeNode numNode) {
sibling.Enabled = false;
node.Arity--;
variable.Weight *= numNode.Value;
} else {
break;
}
}
} else if (symbol is Division) {
// 1/x is expressed as div(x) (with a single child)
// we assume division always has arity 1 or 2
var d = child.Arity == 1 ? c - 1 : c - nodes[c - 1].Size - 2;
var denominator = nodes[d];
// iterate children of node i to see if any of them matches the denominator of div node c
for (int k = 0; k < children.Length; ++k) {
var sibling = nodes[children[k]];
if (sibling.Enabled && sibling == denominator) {
nodes.SetEnabled(children[j], false); // disable the div subtree
nodes.SetEnabled(children[k], false); // disable the sibling matching the denominator
node.Arity -= 2; // matching child + division node
break;
}
}
}
if (node.Arity == 0) { // if everything is simplified this node becomes a number
var numNode = number.CreateTreeNode();
numNode.Value = 1;
nodes[i] = numNode.ToHashNode();
} else if (node.Arity == 1) { // when i have only 1 arg left i can skip this node
node.Enabled = false;
}
}
}
public static void SimplifyDivision(ref HashNode[] nodes, int i) {
var node = nodes[i];
var children = nodes.IterateChildren(i);
var tmp = nodes;
if (children.All(x => tmp[x].Data.Symbol is INumericSymbol)) {
var v = ((INumericTreeNode)nodes[children.First()].Data).Value;
if (node.Arity == 1) {
v = 1 / v;
} else if (node.Arity > 1) {
foreach (var j in children.Skip(1)) {
v /= ((INumericTreeNode)nodes[j].Data).Value;
}
}
var numNode = number.CreateTreeNode();
numNode.Value = v;
nodes[i] = numNode.ToHashNode();
return;
}
var nominator = nodes[children[0]];
foreach (var j in children.Skip(1)) {
var denominator = nodes[j];
if (nominator == denominator) {
// disable all the children of the division node (nominator and children + denominator and children)
nominator.Enabled = denominator.Enabled = false;
node.Arity -= 2; // nominator + denominator
}
if (node.Arity == 0) {
var numNode = number.CreateTreeNode();
numNode.Value = 1; // x / x = 1
nodes[i] = numNode.ToHashNode();
}
}
}
public static void SimplifyUnaryNode(ref HashNode[] nodes, int i) {
// check if the child of the unary node is a number, then the whole node can be simplified
var parent = nodes[i];
var child = nodes[i - 1];
var parentSymbol = parent.Data.Symbol;
var childSymbol = child.Data.Symbol;
if (childSymbol is INumericSymbol) {
nodes[i].Enabled = false;
} else if ((parentSymbol is Exponential && childSymbol is Logarithm) || (parentSymbol is Logarithm && childSymbol is Exponential)) {
child.Enabled = parent.Enabled = false;
}
}
public static void SimplifyBinaryNode(ref HashNode[] nodes, int i) {
var children = nodes.IterateChildren(i);
var tmp = nodes;
if (children.All(x => tmp[x].Data.Symbol is INumericSymbol)) {
foreach (var j in children) {
nodes[j].Enabled = false;
}
nodes[i] = number.CreateTreeNode().ToHashNode();
}
}
#endregion
}
}