string - 使用矩阵代数来操作字符串: is it feasible?

Question

我正在尝试使用矩阵代数来操作字符串。这意味着能够使用字符串或字符串数​​组的串联和粘贴来实现多个类似矩阵的结构。

我之前尝试在 R 上实现这个东西，但这是不可能的，因为矩阵只能有一维条目。

我希望足够的与语言无关和抽象，但为了清楚起见，我将使用类似 R 的代码。我应该明确表示，我不需要真正的矩阵，而是需要类似矩阵的结构，我们可以在其上进行类似矩阵的乘法并检索结构的 (ij) 元素。

{+,*} 矩阵乘法

两个维度为 n 的方阵 A 和 B 的 {+,*}-乘积是由元素定义的矩阵 C : C_i,j = Sum_k=1,...,nA_{i, k} * B_k,j。

例如，考虑矩阵 M <- matrix(c(a,b,0,0,c,d,0,0,e),3,3) 。那么M乘M就是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(,)} 矩阵乘法

我想要实现的这个运算的规则与前面所说的乘法相同，但基本的变化是和应该是一个串联，而乘积应该是一个粘贴。换句话说，在前面的公式中我们发现 a+b ，现在输出应该是“c(a,b)”，当我们找到a*b时，现在我们应该将其读作 paste0(a,b) .

必须尊重一些常见的属性，即分布属性和 0 元素属性。因此，如果a <- c("q",0,"w")和b <- c("e")然后a*b <- c("qe",0,"we") (我们应该随意忘记 0 元素，将其删除，因为它不会影响计算。

此外，我们将等维矩阵相乘，因此每个元素C_i,j = Sum_k=1,...,nA_i,k * B_k,j 现在读作 c("A[i,1]B[1,j]",...,"A[i,n]B[n,j]") .

最后，类似结果矩阵的结构应该是我们可以再次用于计算的东西(例如，进行更复杂的计算，如 mult(mult(A,B),C) 等等......)。

更简单的情况

为了简单起见，让我们从 mult(A,A) 形式的乘积计算开始, mult(mult(A,A),A)等等。我们还可以将 A 强加为一个简单矩阵，这意味着它的每个元素都是一维字符串，而不是字符串的串联。

举个例子吧。让我们定义一个 3 维矩阵 A <- matrix(c("a","b",0,0,"c","d",0,0,"e"),3,3) ，那么 A 乘以 A 应该是 mult(A,A) = matrix(c("aa",c("ab","bc"),"bd",0,"cc",c("cd","de"),0,0,"ee"),3,3)和 A³ 应该是 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) .

问题

您将如何实现这一点？哪种语言似乎更合适？

Answer 1

以下是 R 中矩阵符号乘法的一些想法:

首先我们需要定义行和列的内积。这可以通过以下方式完成:

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

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

示例:

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

我必须将每个元素“包裹”在括号中，因为大于 2 的幂可能比单个变量或数字(零)具有更复杂的表达式。另外，请注意，零将正常显示，即，它(尚)不知道这些可以被简化:

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

由于这些是 R 中的有效表达式，因此可以使用这一事实编写一个简化函数来消除零和多余的括号。我会到达那里。

现在矩阵乘法和幂很简单:

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 }

他们创建有效的(尽管笨拙)表达式:

> 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)"

现在我们来谈谈简化。这些字符串可以解析为有效的 R 表达式，因为它们符合 R 标准。不需要定义变量，因为我们不会计算表达式。实际上我只是想解析它们以方便简化。

检查下面的函数。它删除了多余的括号，用零替换零乘以任何值，并删除零的地 block (另外):

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))
    }
}

此函数与call对象一起使用。要与我们需要的字符串一起使用

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

示例:

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

如果需要，您可以将其用作 rowcol 的包装:

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

结果是:

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

可以编写其他一些简化，这取决于计划如何使用它们。但是，如果输入矩阵是有效表达式的字符串，则最终结果仍然有效。

<小时/>

编辑:rowcol的不同方法:

考虑这些函数:

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="+")
}

使用这些函数代替上面的函数，我们可以处理具有 x*y*z+a*b+f 形式的表达式的矩阵，i。即每个单元格中的乘积之和。这些函数自动应用分配律，保留形式(乘积和)并自动删除零。上面的最后一个例子变成:

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

无需简化!另一个例子:

> 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"