在一个大矩阵中找到一个小矩阵

Question

在一个大矩阵中找到一个小矩阵

8

我有一个非常大的 n*m 矩阵 S。我希望能够高效地确定是否存在一个子矩阵 F 在 S 中。这个大矩阵 S 的大小可以达到 500*500。

为了澄清，考虑以下情况：

在这种情况下：

- F1 在 S 中 - F2 不在 S 中

矩阵中的每个元素都是一个32位整数。我只能想到使用暴力方法来查找F 是否为S 的子矩阵。我谷歌搜索了一下，但没有找到有效的算法。

是否有一些算法或原则可以更快地完成它？（或者可能有一些方法来优化暴力方法？）

附：统计数据

A total of 8 S
On average, each S will be matched against about 44 F.
The probability of success match (i.e. F appears in a S) is 
19%.

- Jason

在你的例子中，矩阵[1,3;7,9]（即仅为角落）是否被认为是在S内？ - Peter de Rivaz

不，它必须被收集在一个矩阵中。 - Jason

矩阵应该是连续且聚集的。 - Jason

9个回答

2

这涉及对矩阵进行预处理。这将会占用大量内存，但在计算时间方面应该更好。

在检查之前，请检查子矩阵的大小是否小于矩阵的大小。
在构建矩阵时，建立一个构造，将矩阵中的值映射到矩阵中(x,y)位置的数组。这将允许您检查可能存在候选项的子矩阵的存在。您将使用子矩阵中(0,0)处的值，并获取较大矩阵中此值的可能位置。如果位置列表为空，则没有候选项，因此子矩阵不存在。这是一个开始（更有经验的人可能认为这是一种天真的方法）。

- user123

1

由于您将问题标记为 C++，因此我提供此代码。这是一种暴力技术，绝对不是此问题的理想解决方案。对于一个 S X T 主矩阵和一个 M X N 子矩阵，算法的时间复杂度为 O(STMN)。

cout<<"\nEnter the order of the Main Matrix";
cin>>S>>T;
cout<<"\nEnter the order of the Sub Matrix";
cin>>M>>N;

// Read the Main Matrix into MAT[S][T]

// Read the Sub Matrix into SUB[M][N]

for(i=0; i<(S-M); i++)
{
   for(j=0; j<(T-N); j++)
   {
      flag=0;
      for(p=0; p<M; p++)
      {
         for(q=0; q<N; q++)
         {
            if(MAT[i+p][j+q] != SUB[p][q])
            {
               flag=1;
               break; 
            }
         }
         if(flag==0)
         {
            cout<<"Match Found in the Main Matrix at starting location "<<(i+1) <<"X"<<(j+1);
            break;
         }
      }
      if(flag==0)
      {
         break;
      }
   }            
   if(flag==0)
   {
      break;
   }
}

- Deepu

1

如果您想要查询同一个大矩阵和相同大小的子矩阵多次，有很多预处理大矩阵的解决方案。

这里有一个类似（甚至相同）的问题。在M X N矩阵中查找m x n子矩阵的最快方法

- konjac

1

既然您只想知道一个给定矩阵是否在另一个大矩阵中。如果您知道如何从C ++使用Matlab代码，那么可以直接使用Matlab中的ismember。另一种方法可能是尝试弄清楚Matlab中的ismember的工作原理，然后在C++中实现相同的功能。

请参见查找子矩阵的位置

- taocp

0

很大程度上取决于您正在重复执行什么操作。您是否正在测试一堆巨大的矩阵以查找相同的子矩阵？还是正在测试一个巨大的矩阵以查找许多不同的子矩阵？

任何矩阵中是否有重复模式，或者它们是随机的，还是您无法对数据做出任何假设？

此外，子矩阵是否必须是连续的？ S是否包含？

F3 = 1 3
     7 9

- NovaDenizen

矩阵应该是连续的并且被收集起来，我拥有的其他信息将添加在问题的底部。 - Jason

0

这可以在O(N*M*(logN+logM))内完成。

相等可以表示为平方差之和为0：

sum[i,j](square(S(n+i,m+j)-F(i,j)))=0
sum[i,j]square(S(n+i,m+j))+sum[i,j](square(F(i,j))-2*sum[i,j](S(n+i,m+j)*F(i,j))=0

第一部分可以针对所有 (n,m) 在 O(N*M) 中计算，类似于运行平均值。

第二部分通常在 O(sizeof(F)) 中计算，这比 O(N*M) 小。

第三部分最有趣。使用快速傅里叶变换，可以在 O(N*M*(logN+logM)) 中计算卷积: http://en.wikipedia.org/wiki/Convolution#Fast_convolution_algorithms

- maxim1000

0

我的原始答案在分割线下方，考虑到有几个优化，这些优化是指原始答案的步骤。

对于步骤B），不要搜索整个S：可以排除所有不允许F适合的列和行。(在下面的例子中，只搜索左上角的2x2矩阵)。在F是S的重要比例的情况下，这将节省相当多的时间。

如果S内的值范围很低，那么创建查找表将极大地减少步骤B）所需的时间。

处理这2个矩阵

在 mat1 中查找 mat2

A）从较小的矩阵中选择一个值：

mat4

B) 将其定位在更大的范围内

mat3

C) 检查相邻的单元格是否匹配

mat6 - mat5

- Ian

他正在处理一个500*500的矩阵。 - user123

0

如果矩阵中的数据不是随机分布的，运行一些统计分析将会很有帮助。然后，您可以通过比较其元素的逆概率范围来找到子矩阵。这可能比简单的暴力方法更快。

例如，假设您有一些正态分布整数的矩阵，其高斯中心为0。您想要找到子矩阵，比如：

1 3 -12
-3 43 -1
198 2 2

你需要从198开始搜索，然后检查右上角的元素是否为43，然后再检查它右上方的元素是否为-12，接着任何3或-3都可以；以此类推。这将大大减少与最暴力解决方案相比的比较次数。

- akalenuk

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Singhak · Accepted Answer

深度-本森修改后的代码

int Ma[][5]= {
        {0, 0, 1, 0, 0},
        {0, 0, 1, 0, 0},
        {0, 1, 0, 0, 0},
        {0, 1, 0, 0, 0},
        {1, 1, 1, 1, 0}
    };


    int Su[][3]= {
        {1, 0, 0},
        {1, 0, 0},


    };

    int S = 5;// Size of main matrix row
    int T = 5;//Size of main matrix column
    int M = 2; // size of desire matrix row
    int N = 3; // Size of desire matrix column

int flag, i,j,p,q;

for(i=0; i<=(S-M); i++)
{
   for(j=0; j<=(T-N); j++)
   {
      flag=0;
      for(p=0; p<M; p++)
      {
         for(int q=0; q<N; q++)
         {
            if(Ma[i+p][j+q] != Su[p][q])
            {
               flag=1;

               break;
            }
         }
      }
      if(flag==0)
      {
           printf("Match Found in the Main Matrix at starting location %d, %d",(i+1) ,(j+1));
         break;
      }
   }
   if(flag==0)
   {
        printf("Match Found in the Main Matrix at starting location %d, %d",(i+1) ,(j+1));
      break;
   }
}