List-based Tree Unification Algorithms

Question

I need a unification algorithm to handle the following situation.

Each node in my expression tree has a list (associative) or a set of (associative and commutative) children. I would like to get all possible matches for a specific template.

Here is an example. Suppose we are dealing with matrices, so that + is commutative and * non-commutative

expression: A + B*C*D + E

alternatively: Add(A, Mul(B, C, D), E)

pattern: X + Y*Z

I see two matches

 X: A + E Y: B Z: C * D X: A + E Y: B * C Z: D 

Question: Are there any standard algorithms that handle this?

Answer 1

All that comes to mind when I see this is sections and subsets to match commutative terms. If you match n terms with m> n terms, you must break m into n parts, p.

Then you need subsets of length p_i, which can then be tested against your original template. Perhaps it makes sense to find the most restrictive term and match the first. for example, if mul matches, you can see if there is muls present ... if then your original problem was divided into two parts: the mul part and the rest. The most restrictive is the term with the highest number of operations. so X + X * Y * Z + X * (Y + Z) are two mul members of tie; a tie can be broken to make it more complex. Thus, it is possible that op_count and the number of types of operations can be a measure of complexity.

In SymPy:

 >>> pat = X + X*Y*Z + X*(Y+Z) >>> [(p.count_ops(), p.count_ops(visual=True).free_symbols) for p in Add.make_args(pat)] [(0, set([])), (2, set([MUL])), (2, set([ADD, MUL]))] 

Regarding the design of matching, letting binary digits select the elements you could work on. SymPy uses again from sympy.utilities.iterables import reshape, runs, permutations :

 >>> N=list('ABC') >>> M=list('abcde') >>> n=[1]*len(N) >>> m=[1]*len(M) >>> n.extend([0]*(len(m) - len(n))) >>> grouper = lambda x, xx: x==xx==0 or x==0 and xx==1 >>> demo = [1, 0, 0, 1, 1] >>> runs(demo, grouper) [[1, 0, 0], [1], [1]] >>> nn=n[1:] # the first one will stay put; shuffle the rest >>> for p in permutations(nn): ... P = [1]+list(p) ... shape = [[len(r)] for r in runs(P, grouper)] ... print dict(zip(N, reshape(M, shape)[0])) {'A': ['a'], 'C': ['c', 'd', 'e'], 'B': ['b']} {'A': ['a'], 'C': ['c', 'd', 'e'], 'B': ['b']} {'A': ['a'], 'C': ['d', 'e'], 'B': ['b', 'c']} {'A': ['a'], 'C': ['e'], 'B': ['b', 'c', 'd']} {'A': ['a'], 'C': ['d', 'e'], 'B': ['b', 'c']} {'A': ['a'], 'C': ['e'], 'B': ['b', 'c', 'd']} {'A': ['a'], 'C': ['c', 'd', 'e'], 'B': ['b']} {'A': ['a'], 'C': ['c', 'd', 'e'], 'B': ['b']} {'A': ['a'], 'C': ['d', 'e'], 'B': ['b', 'c']} {'A': ['a'], 'C': ['e'], 'B': ['b', 'c', 'd']} {'A': ['a'], 'C': ['d', 'e'], 'B': ['b', 'c']} {'A': ['a'], 'C': ['e'], 'B': ['b', 'c', 'd']} {'A': ['a', 'b'], 'C': ['d', 'e'], 'B': ['c']} {'A': ['a', 'b'], 'C': ['e'], 'B': ['c', 'd']} {'A': ['a', 'b'], 'C': ['d', 'e'], 'B': ['c']} {'A': ['a', 'b'], 'C': ['e'], 'B': ['c', 'd']} {'A': ['a', 'b', 'c'], 'C': ['e'], 'B': ['d']} {'A': ['a', 'b', 'c'], 'C': ['e'], 'B': ['d']} {'A': ['a', 'b'], 'C': ['d', 'e'], 'B': ['c']} {'A': ['a', 'b'], 'C': ['e'], 'B': ['c', 'd']} {'A': ['a', 'b'], 'C': ['d', 'e'], 'B': ['c']} {'A': ['a', 'b'], 'C': ['e'], 'B': ['c', 'd']} {'A': ['a', 'b', 'c'], 'C': ['e'], 'B': ['d']} {'A': ['a', 'b', 'c'], 'C': ['e'], 'B': ['d']} 

Chris