using matrices algebra to manipulate strings: is it feasible?

Question

I'm trying to use matrix algebra with the purpose of manipulating strings. This means being able to multiple matrix-like structures using concatenation and pasting of string or of arrays of strings.

I previously tried to implement the thing on R, but it was not possible as matrices can have only one dimensional entries.

I hope to be enough language-agnostic and abstract, but I'll use R-like code for sake of clarity. I should make explicit that I don't require real matrices, but matrix-like structure on which we can do matrices-like multiplication and retrieve the (ij) element of the structure.

{+,*} MATRICES MULTIPLICATION

The {+,*}-product of two square matrices A and B of dimension n is a matrix C defined by the elements: C_i,j = Sum_k=1,...,nA_i,k * B_k,j.

For example, consider the matrix M <- matrix(c(a,b,0,0,c,d,0,0,e),3,3). Then M times M is M <- matrix(c(a^2,a*b+b*c,b*d,0,c^2,c*d+d*e,0,0,e^2),3,3).

{c(,),paste0(,)} MATRICES MULTIPLICATION

The rule of this operation I would like to implement are the same of the previous stated multiplication with the essential mutation that the sum should be a concatenation and the product should be a paste. In other words, where in the previous formula we found a+b, now the output should be "c(a,b)", and when we found a*b, now we should read this as paste0(a,b).

Some of the usual properties have to be respected, namely the distributive properties and the 0 element properties. Hence, if a <- c("q",0,"w") and b <- c("e") then a*b <- c("qe",0,"we") (and we should freely forget the 0 element, dropping it as it won't affect the computation.

Moreover, we are multiplying equal-dimensioned matrices, hence each element C_i,j = Sum_k=1,...,nA_i,k * B_k,j is now to be read as c("A[i,1]B[1,j]",...,"A[i,n]B[n,j]").

Finally, the outcome matrix-like structure should be something that we can use again for computations (so for example to make more complex computation as mult(mult(A,B),C) and so on...).

A SIMPLER CASE

For simplicity sake, let's start from the computation of product of the form mult(A,A), mult(mult(A,A),A) and so on. We may also impose A to be a simple matrix, meaning that each of its elements are one dimensional string, and not concatenation of string.

Let's give an example. Let's be A a 3 dimensional matrix defined as A <- matrix(c("a","b",0,0,"c","d",0,0,"e"),3,3), then the multiplication of A times A should be mult(A,A) = matrix(c("aa",c("ab","bc"),"bd",0,"cc",c("cd","de"),0,0,"ee"),3,3) and A³ should be mult(mult(A,A),A) = matrix(c("aaa",c("aab","abc","bcc"),c("abd","bcd","bde"),0,"ccc",c("ccd","cde","dee"),0,0,"eee"),3,3).

Question

How would you implement this? Which language seems more fitting?

Answer 1

Here are some ideas for symbolic multlipication of matrices in R:

First we need to define the inner product of a row and a column. This can be done with:

wrap <- function(x) paste0("(",x,")")

rowcol <- function(row,col) paste(wrap(row),wrap(col),sep="*",collapse="+")

Example:

> rowcol(c("A","B","C"),c("D","E","F"))
[1] "(A)*(D)+(B)*(E)+(C)*(F)"

I had to "wrap" each element in parenthesis beacause the powers greater than 2 may have more comoplicated expressions than a single variable or number (zero). Also, note that zero will show up normally, i.e., it doesn't know (yet) that these can be simplified:

> rowcol(c("A","B"),c("0","X+Y"))
[1] "(A)*(0)+(B)*(X+Y)"

Since these are valid expressions in R, this fact can be used to write a simplification function to eliminate zeros and redundant parenthesis. I'll get there.

Now the matrix multiplication and powers are simply:

symprod <- function(A,B) sapply(1:ncol(B), function(j)sapply(1:nrow(A), function(i)rowcol(A[i,],B[,j])))

sympow <- function(A,n) { B <- A; for( i in seq_len(n-1) ) B <- symprod(B,A); B }

They create valid (although clumsy) expressions:

> A <- matrix(LETTERS[1:4],2,2)
> diag(A) <- 0
> sympow(A,3)
     [,1]                                          [,2]                                         
[1,] "((0)*(0)+(C)*(B))*(0)+((0)*(C)+(C)*(0))*(B)" "((0)*(0)+(C)*(B))*(C)+((0)*(C)+(C)*(0))*(0)"
[2,] "((B)*(0)+(0)*(B))*(0)+((B)*(C)+(0)*(0))*(B)" "((B)*(0)+(0)*(B))*(C)+((B)*(C)+(0)*(0))*(0)"

Now let's talk about simplification. These strings can be parsed into valid R expressions, since they comply to the R standard. The variables need not be defined, because we are not going to evaluate the expressions. Actually I only want to parse them to ease simplification.

Check the function below. It removes redundant parenthesis, replaces zero times anything with zero, and removes parcels (in additions) that are zero:

simplify <- function(e)
{
    if( mode(e) %in% c("name","numeric") ) return(e)

    if( as.character(e[[1]])=="+" )
    {
        x <- simplify(e[[2]])

        y <- simplify(e[[3]])

        if( identical(x,0) ) return(y)

        if( identical(y,0) ) return(x)

        return(call("+", x, y))
    }

    if( as.character(e[[1]])=="*" )
    {
        x <- simplify(e[[2]])

        if( identical(x,0) ) return(0)

        y <- simplify(e[[3]])

        if( identical(y,0) ) return(0)

        return(call("*", x, y))
    }

    if( as.character(e[[1]])=="(" )
    {
        x <- simplify(e[[2]])

        if( mode(x) %in% c("name","numeric") ) return(x)

        return(call("(", x))
    }
}

This function works with a call object. To use with strings we need

simplify_text <- function(s) deparse(simplify(parse(text=s)[[1]]))

Example:

> simplify_text("(x)+(0*(a+b))+(z)")
[1] "x + z"

If you want, you can use it as wrapper for rowcol:

rowcol <- function(row,col) simplify_text(paste(wrap(row),wrap(col),sep="*",collapse="+"))

The result is:

> sympow(A,3)
     [,1]          [,2]         
[1,] "0"           "(C * B) * C"
[2,] "(B * C) * B" "0"          

Some other simplifications can be written, it depends on how do plan to work with them. But, if the input matrices are strings of valid expressions, the final result remain valid.

---

EDIT: a different approch for rowcol:

Consider these functions:

cellprod <- function(r, s)
{
    z <- expand.grid(r,s, stringsAsFactors=FALSE)

    filter <- (z$Var1 != 0) & (z$Var2 != 0)

    paste(z$Var1[filter], z$Var2[filter], sep="*", collapse="+")
}

rowcol <- function(row,col)
{
    x <- strsplit(row, "\\+")

    y <- strsplit(col, "\\+")

    L <- vapply(seq_along(x), function(i) cellprod(x[[i]],y[[i]]), character(1))

    filter <- nzchar(L)

    if( ! any(filter) ) return("0")

    paste(L[filter], collapse="+")
}

Using these instead of the functions above, we can handle matrices with expressions of the form x*y*z+a*b+f, i. e., sums of products in each cell. The functions automatically applies the distributive law, preserving the form (sum-of-products) and also removes zeros automatically. The last example above becomes:

> sympow(A,3)
     [,1]    [,2]   
[1,] "0"     "C*B*C"
[2,] "B*C*B" "0"

No simplification required! Another example:

> A <- matrix(LETTERS[1:9],3,3)
> B <- matrix(LETTERS[10:18],3,3)
> A[2,3] <- 0
> A[3,2] <- 0
> B[1,3] <- 0
> B[3,1] <- 0
> A
     [,1] [,2] [,3]
[1,] "A"  "D"  "G" 
[2,] "B"  "E"  "0" 
[3,] "C"  "0"  "I" 
> B
     [,1] [,2] [,3]
[1,] "J"  "M"  "0" 
[2,] "K"  "N"  "Q" 
[3,] "0"  "O"  "R"
> symprod(A,B)
     [,1]      [,2]          [,3]     
[1,] "A*J+D*K" "A*M+D*N+G*O" "D*Q+G*R"
[2,] "B*J+E*K" "B*M+E*N"     "E*Q"    
[3,] "C*J"     "C*M+I*O"     "I*R"