source: branches/2886_SymRegGrammarEnumeration/Test/TreeHashingTest.cs @ 16193

using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Security.Cryptography;
using HeuristicLab.Algorithms.DataAnalysis.SymRegGrammarEnumeration;
using Microsoft.VisualStudio.TestTools.UnitTesting;
using HierarchicalFormatter = HeuristicLab.Encodings.SymbolicExpressionTreeEncoding.SymbolicExpressionTreeHierarchicalFormatter;

namespace Test {
  [TestClass]
  public class TreeHashingTest {

    private Grammar grammar;
    private TerminalSymbol varA;
    private TerminalSymbol varB;
    private TerminalSymbol varC;
    private TerminalSymbol c;

    Func<Grammar, SymbolList, int> ComputeHash = (grammar, sentence) => grammar.ComputeHash(null, sentence);

    [TestInitialize]
    public void InitTest() {
      grammar = new Grammar(new[] { "a", "b", "c" });

      varA = grammar.VarTerminals.First(s => s.StringRepresentation == "a");
      varB = grammar.VarTerminals.First(s => s.StringRepresentation == "b");
      varC = grammar.VarTerminals.First(s => s.StringRepresentation == "c");
      c = grammar.Const;
    }

    [TestMethod]
    [TestCategory("TreeHashing")]
    public void SimpleEqualityAddition() {
      SymbolList s1 = new SymbolList(new[] { varA, varB, grammar.Addition, varC, grammar.Addition });
      SymbolList s2 = new SymbolList(new[] { varA, varB, grammar.Addition, varC, grammar.Addition });

      int hash1 = ComputeHash(grammar, s1);
      int hash2 = ComputeHash(grammar, s2);

      Assert.AreEqual(hash1, hash2);
    }

    [TestMethod]
    [TestCategory("TreeHashing")]
    public void SimpleInequalityAddition() {
      SymbolList s1 = new SymbolList(new[] { varA, varB, grammar.Addition, varC, grammar.Addition });
      SymbolList s2 = new SymbolList(new[] { varB, varB, grammar.Addition, varB, grammar.Addition });

      int hash1 = ComputeHash(grammar, s1);
      int hash2 = ComputeHash(grammar, s2);

      Assert.AreNotEqual(hash1, hash2);
    }

    [TestMethod]
    [TestCategory("TreeHashing")]
    public void CommutativityAddition() {
      SymbolList s1 = new SymbolList(new[] { varA, varB, grammar.Addition });
      SymbolList s2 = new SymbolList(new[] { varB, varA, grammar.Addition });

      int hash1 = ComputeHash(grammar, s1);
      int hash2 = ComputeHash(grammar, s2);

      Assert.AreEqual(hash1, hash2);
    }

    [TestMethod]
    [TestCategory("TreeHashing")]
    public void AssociativityAddition() {
      SymbolList s1 = new SymbolList(new[] { varA, varB, grammar.Addition, varA, grammar.Addition });
      SymbolList s2 = new SymbolList(new[] { varA, varB, varA, grammar.Addition, grammar.Addition });

      int hash1 = ComputeHash(grammar, s1);
      int hash2 = ComputeHash(grammar, s2);

      Assert.AreEqual(hash1, hash2);
    }

    [TestMethod]
    [TestCategory("TreeHashing")]
    public void RepeatedAddition() {
      SymbolList s1 = new SymbolList(new[] { varA, varA, grammar.Addition, varA, grammar.Addition });
      SymbolList s2 = new SymbolList(new[] { varA });

      int hash1 = ComputeHash(grammar, s1);
      int hash2 = ComputeHash(grammar, s2);

      Assert.AreEqual(hash1, hash2);
    }

    [TestMethod]
    [TestCategory("TreeHashing")]
    public void ComplexInequality() {
      SymbolList s1 = new SymbolList(new[] { varA, varA, varA, grammar.Multiplication, grammar.Multiplication });
      SymbolList s2 = new SymbolList(new[] { varA, varA, varA, grammar.Multiplication, grammar.Addition });

      int hash1 = ComputeHash(grammar, s1);
      int hash2 = ComputeHash(grammar, s2);

      Assert.AreNotEqual(hash1, hash2);
    }

    [TestMethod]
    [TestCategory("TreeHashing")]
    public void NonterminalHashing() {
      SymbolList s1 = new SymbolList(new Symbol[] { varA, varA, grammar.Expr, grammar.Addition, grammar.Addition });
      SymbolList s2 = new SymbolList(new Symbol[] { varA, grammar.Expr, grammar.Addition });

      int hash1 = ComputeHash(grammar, s1);
      int hash2 = ComputeHash(grammar, s2);

      Assert.AreEqual(hash1, hash2);
    }

    [TestMethod]
    [TestCategory("TreeHashing")]
    public void InverseFactorCancelationSimple() {
      // 1/a * b * a * a
      SymbolList s1 = new SymbolList(new Symbol[] { varA, grammar.Inv, varB, grammar.Multiplication, varA, grammar.Multiplication, varA, grammar.Multiplication });
      // a * b
      SymbolList s2 = new SymbolList(new Symbol[] { varA, varB, grammar.Multiplication });

      int hash1 = ComputeHash(grammar, s1);
      int hash2 = ComputeHash(grammar, s2);

      Assert.AreEqual(hash1, hash2);
    }

    [TestMethod]
    [TestCategory("TreeHashing")]
    public void InverseFactorCancelationComplex() {
      SymbolList s1 = new SymbolList(new Symbol[] { varA, grammar.Sin, varA, varA, grammar.Multiplication, varA, grammar.Addition, grammar.Sin, grammar.Addition });
      SymbolList s2 = new SymbolList(new Symbol[] { varA, varA, varA, grammar.Multiplication, grammar.Addition, grammar.Sin, varA, grammar.Inv, varA, grammar.Sin, varA, grammar.Multiplication, grammar.Multiplication, grammar.Addition });

      int hash1 = ComputeHash(grammar, s1);
      int hash2 = ComputeHash(grammar, s2);

      Console.WriteLine(s1);
      Console.WriteLine(PrintTree(s1));
      Console.WriteLine(grammar.Simplify(null, s1));
      Console.WriteLine(hash1);
      Console.WriteLine();
      Console.WriteLine(s2);
      Console.WriteLine(PrintTree(s2));
      Console.WriteLine(grammar.Simplify(null, s2));
      Console.WriteLine(hash2);


      Assert.AreEqual(hash1, hash2);
    }

    // Constants
    [TestMethod]
    [TestCategory("TreeHashing")]
    public void SimpleConst() {
      SymbolList s1 = new SymbolList(new Symbol[] { c, varA, grammar.Multiplication, c, grammar.Addition });
      SymbolList s2 = new SymbolList(new Symbol[] { c, varA, grammar.Multiplication, c, varA, grammar.Multiplication, grammar.Addition, c, grammar.Addition });

      int hash1 = ComputeHash(grammar, s1);
      int hash2 = ComputeHash(grammar, s2);

      Assert.AreEqual(hash1, hash2);
    }

    [TestMethod]
    [TestCategory("TreeHashing")]
    public void EnumerateGrammarTest() {
      //const int nvars = 1;
      //var variables = Enumerable.Range(1, nvars).Select(x => $"x{x}").ToArray();
      var variables = new[] { "a", "b" };
      var grammar = new Grammar(variables, Enum.GetValues(typeof(GrammarRule)).Cast<GrammarRule>());

      Func<SymbolList, int> hash = s => grammar.Hasher.CalcHashCode(s);
      int length = 100;
      int depth = 20;

      //List<SymbolList> sentences = EnumerateGrammarBreadth(grammar, length: length, hashPhrases: false).ToList();
      //Console.WriteLine("Breadth: {0} generated, {1} distinct sentences", sentences.Count, sentences.GroupBy(hash).Count());

      //var sentences = EnumerateGrammarBreadth(grammar, length: length, hashPhrases: true).ToList();
      //Console.WriteLine("Breadth (hashed): {0} generated, {1} distinct sentences", sentences.Count, sentences.GroupBy(hash).Count());

      var sentences = EnumerateGrammarDepth(grammar, length: length, depth: depth, hashPhrases: false).ToList();
      Console.WriteLine("Depth: {0} generated, {1} distinct sentences", sentences.Count, sentences.GroupBy(hash).Count());

      sentences = EnumerateGrammarDepth(grammar, length: length, depth: depth, hashPhrases: true).ToList();
      Console.WriteLine("Depth (hashed): {0} generated, {1} distinct sentences", sentences.Count, sentences.GroupBy(hash).Count());
    }

    [TestMethod]
    [TestCategory("TreeHashing")]
    public void HashExtensionsTest() {
      var variables = new[] { "x", "y", "z" };
      var rules = Enum.GetValues(typeof(GrammarRule)).Cast<GrammarRule>();
      var grammar = new Grammar(variables, rules);
      var add = grammar.Addition;
      var mul = grammar.Multiplication;
      var exp = grammar.Exp;
      var log = grammar.Log;
      var inv = grammar.Inv;
      var sin = grammar.Sin;

      var c = grammar.Const;
      var x = grammar.VarTerminals.Single(v => v.StringRepresentation == "x");
      var y = grammar.VarTerminals.Single(v => v.StringRepresentation == "y");
      var z = grammar.VarTerminals.Single(v => v.StringRepresentation == "z");


      var ha = SHA512.Create();

      var sentences = new[] {
        new SymbolList(c, c, x, mul, c, add, inv, mul, c, add),
        new SymbolList(c, c, x, mul, c, add, log, mul, c, add),
        new SymbolList(x, x, add),
        new SymbolList(x, x, add, x, add),
        new SymbolList(x, x, add, y, add),
        new SymbolList(x, x, add, x, add, x, add),
        new SymbolList(x, x, add, y, add, x, add),
        new SymbolList(x, y, mul, x, y, mul, add),
        new SymbolList(x, y, mul, y, x, mul, add),
        new SymbolList(x, y, mul, z, y, mul, add),
        new SymbolList(x, x, add, y, mul),
        new SymbolList(x, x, add, y, mul, y, mul),
        new SymbolList(x, x, inv, mul),
        new SymbolList(x, inv, x, inv, mul, x, mul, x, mul),
        new SymbolList(c, x, x, x, x, x, x, mul, mul, mul, mul, mul, mul, c, x, mul, c, add, add),
        new SymbolList(c, x, x, x, x, x, x, mul, mul, mul, mul, mul, mul, c, x, mul, c, add, add),
        new SymbolList(c, x, mul, c, x, x, x, x, x, x, mul, mul, mul, mul, mul, mul, c, add, add),
        new SymbolList(c, x, x, x, x, mul, mul, mul, mul, c, x, mul, c, x, mul, c, add, add, add),
        new SymbolList(c, x, mul, c, x, x, x, x, mul, mul, mul, mul, c, x, mul, c, add, add, add)
    };

      foreach (var sentence in sentences) {
        var simplified = grammar.Simplify(ha, sentence);
        Console.WriteLine($"{sentence} -> {simplified} {grammar.Hasher.CalcHashCode(sentence)} {grammar.ComputeHash(ha, sentence)}");
        Console.WriteLine();
      }
    }

    string PrintTree(SymbolList s) {
      var t = grammar.ParseSymbolicExpressionTree(s);
      return HierarchicalFormatter.Format(t.Root.GetSubtree(0).GetSubtree(0));
    }

    [TestMethod]
    [TestCategory("TreeHashing")]
    public void HashCollisionsTest() {
      var variables = new[] { "x", "y", "z", "w" };
      //var rules = Enum.GetValues(typeof(GrammarRule)).Cast<GrammarRule>().Except(new[] { GrammarRule.InverseTerm, GrammarRule.Exponentiation, GrammarRule.Logarithm, GrammarRule.Sine });
      var rules = Enum.GetValues(typeof(GrammarRule)).Cast<GrammarRule>();
      var grammar = new Grammar(variables, rules);

      int maxLength = 20, maxDepth = int.MaxValue;
      var sentences = EnumerateGrammarDepth(grammar, length: maxLength, depth: maxDepth, hashPhrases: false).ToList();
      var count = sentences.Count;

      var sw = new Stopwatch();
      sw.Start();
      var hashes = sentences.Select(grammar.Hasher.CalcHashCode).ToList();
      sw.Stop();
      Console.WriteLine($"Old hash: {sentences.Count} ({hashes.Distinct().Count()}) hashed in {sw.ElapsedMilliseconds / 1000.0} seconds ({1000d * sentences.Count / sw.ElapsedMilliseconds} hashes/s)");

      var ha = SHA512.Create();
      sw.Restart();
      var hashes_new = sentences.Select(x => grammar.ComputeHash(ha, x)).ToList();
      sw.Stop();
      Console.WriteLine($"New hash: {sentences.Count} ({hashes_new.Distinct().Count()}) hashed in {sw.ElapsedMilliseconds / 1000.0} seconds ({1000.0 * sentences.Count / sw.ElapsedMilliseconds} hashes/s)");

      var distinct = Enumerable.Range(0, count).GroupBy(x => hashes_new[x]).Select(g => g.OrderBy(x => x).First()).ToList();
      var collisions = distinct.ToLookup(x => hashes[x], x => Tuple.Create(hashes_new[x], sentences[x]));

      foreach (var pair in collisions) {
        if (pair.Count() > 1) {
          Console.WriteLine(pair.Key);
          foreach (var t in pair) {
            Console.WriteLine($"\t{t}");
            Console.WriteLine($"\t{grammar.ToInfixString(t.Item2)}");
            var simplified = grammar.Simplify(ha, t.Item2);
            Console.WriteLine($"\t{simplified}");
            Console.Write($"\t");
            PrintTree(t.Item2);
            Console.WriteLine();
          }
        }
      }
    }

    [TestMethod]
    [TestCategory("TreeHashing")]
    public void HashPerformance() {
      var nvars = 4;
      var variables = Enumerable.Range(0, nvars).Select(x => $"X{x}").ToArray();
      //var rules = Enum.GetValues(typeof(GrammarRule)).Cast<GrammarRule>().Except(new[] { GrammarRule.InverseTerm, GrammarRule.Exponentiation, GrammarRule.Logarithm, GrammarRule.Sine });
      var rules = Enum.GetValues(typeof(GrammarRule)).Cast<GrammarRule>();
      var grammar = new Grammar(variables, rules);

      int maxLength = 20, maxDepth = int.MaxValue;
      var sentences = EnumerateGrammarDepth(grammar, length: maxLength, depth: maxDepth, hashPhrases: false).ToList();
      var count = sentences.Count;

      var ha = SHA512.Create();

      var sw = new Stopwatch();
      sw.Start();
      var hashes = sentences.Select(x => grammar.ComputeHash(ha, x)).ToList();
      sw.Stop();

      Console.WriteLine($"New: {sentences.Count} ({hashes.Distinct().Count()}) hashed in {sw.ElapsedMilliseconds / 1000.0} seconds ({1000d * sentences.Count / sw.ElapsedMilliseconds} hashes/s)");

      sw.Restart();
      var hashes_old = sentences.Select(x => grammar.Hasher.CalcHashCode(x)).ToList();
      sw.Stop();

      Console.WriteLine($"Old: {sentences.Count} ({hashes_old.Distinct().Count()}) hashed in {sw.ElapsedMilliseconds / 1000.0} seconds ({1000d * sentences.Count / sw.ElapsedMilliseconds} hashes/s)");
    }

    #region enumerate the grammar
    private static IEnumerable<SymbolList> EnumerateGrammarBreadth(Grammar grammar, int length, bool hashPhrases = true) {
      var phrases = new Queue<SymbolList>();
      phrases.Enqueue(new SymbolList(grammar.StartSymbol));
      var sentences = new List<SymbolList>();
      var archive = new HashSet<int>();

      while (phrases.Any()) {
        var phrase = phrases.Dequeue();

        if (phrase.Count > length)
          continue;

        if (phrase.IsSentence()) {
          sentences.Add(phrase);
          continue;
        }

        if (hashPhrases && !archive.Add(grammar.Hasher.CalcHashCode(phrase))) {
          continue;
        }

        var idx = phrase.NextNonterminalIndex();
        var productions = grammar.Productions[phrase[idx]];
        var derived = productions.Select(p => phrase.DerivePhrase(idx, p)).Where(p => p.Count <= length);
        foreach (var d in derived)
          phrases.Enqueue(d);
      }
      return sentences;
    }

    private static IEnumerable<SymbolList> EnumerateGrammarDepth(Grammar grammar, int length, int depth, bool hashPhrases = true) {
      return Expand(new SymbolList(grammar.StartSymbol), grammar, length, 0, depth, hashPhrases ? new HashSet<int>() : null);
    }

    private static IEnumerable<SymbolList> Expand(SymbolList phrase, Grammar grammar, int maxLength, int depth, int maxDepth, HashSet<int> visited) {
      if (maxDepth < depth || maxLength < phrase.Count) {
        yield break;
      }

      if (phrase.IsSentence()) {
        yield return phrase;
        yield break;
      }

      if (visited != null && !visited.Add(HashExtensions.ComputeHash(grammar, null, phrase))) {
        yield break;
      }

      var i = phrase.NextNonterminalIndex();
      var productions = grammar.Productions[phrase[i]];

      foreach (var s in productions.SelectMany(p => Expand(phrase.DerivePhrase(i, p), grammar, maxLength, depth + 1, maxDepth, visited)))
        yield return s;
    }
    #endregion
  }
}