1 | using System.Collections.Generic;
|
---|
2 | using System.Linq;
|
---|
3 | using HeuristicLab.Problems.DataAnalysis.Symbolic;
|
---|
4 |
|
---|
5 | namespace 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() as List<ISymbolicExpressionTreeNode>;
|
---|
73 | var fragments = fragment.IterateNodesPostfix() as List<ISymbolicExpressionTreeNode>;
|
---|
74 | return FindMatch(nodes, fragments, mode) != -1;
|
---|
75 | }
|
---|
76 |
|
---|
77 | // convenience methods for less typing :)
|
---|
78 | private static IEnumerator<ISymbolicExpressionTreeNode> Enumerator(this ISymbolicExpressionTree tree) {
|
---|
79 | return tree.IterateNodesPostfix().GetEnumerator();
|
---|
80 | }
|
---|
81 | private static IEnumerator<ISymbolicExpressionTreeNode> Enumerator(this ISymbolicExpressionTreeNode tree) {
|
---|
82 | return tree.IterateNodesPostfix().GetEnumerator();
|
---|
83 | }
|
---|
84 | public static int FindMatch(ISymbolicExpressionTree a, ISymbolicExpressionTree b, int mode) {
|
---|
85 | var nodesA = a.IterateNodesPostfix() as List<ISymbolicExpressionTreeNode>;
|
---|
86 | var nodesB = b.IterateNodesPostfix() as List<ISymbolicExpressionTreeNode>;
|
---|
87 | return FindMatch(nodesA, nodesB, mode);
|
---|
88 | }
|
---|
89 | public static int FindMatch(ISymbolicExpressionTreeNode a, ISymbolicExpressionTreeNode b, int mode) {
|
---|
90 | var nodesA = a.IterateNodesPostfix() as List<ISymbolicExpressionTreeNode>;
|
---|
91 | var nodesB = b.IterateNodesPostfix() as List<ISymbolicExpressionTreeNode>;
|
---|
92 | return FindMatch(nodesA, nodesB, mode);
|
---|
93 | }
|
---|
94 | // returns the index in the sequence 'seq', where pattern 'pat' is matched, or -1 for no match
|
---|
95 | // -1 means no match, 0 means perfect match (the sequences overlap, hence the match index is 0)
|
---|
96 | public static int FindMatch(List<ISymbolicExpressionTreeNode> seq, List<ISymbolicExpressionTreeNode> pat, int mode) {
|
---|
97 | int patlen = pat.Count;
|
---|
98 | int seqlen = seq.Count;
|
---|
99 | if (patlen == 0 || seqlen == 0) return -1;
|
---|
100 | var comparer = new SymbolicExpressionTreeNodeComparer(mode);
|
---|
101 | if (patlen == seqlen) return seq.SequenceEqual(pat, comparer) ? 0 : -1;
|
---|
102 | for (int i = patlen; i <= seqlen; ++i) {
|
---|
103 | if (comparer.Equals(seq[i - 1], pat.Last())) // first check if last element is a match
|
---|
104 | if (seq.Skip(i - patlen).Take(patlen).SequenceEqual(pat, comparer)) // then check the whole sequence
|
---|
105 | return i - patlen;
|
---|
106 | }
|
---|
107 | return -1;
|
---|
108 | }
|
---|
109 | }
|
---|
110 | }
|
---|