二维子矩阵快速计数withing大，密集的二维矩阵？ [英] Fast counting of 2D sub-matrices withing a large, dense 2D matrix?

问题描述

什么是好的算法放大，稠密矩阵内计数子矩阵？如果我有数据的单行线，我可以用一个后缀树，但我不知道，如果概括一个后缀树到更高层面是完全直接的，或在这里的最佳方法。

What's a good algorithm for counting submatrices within a larger, dense matrix? If I had a single line of data, I could use a suffix tree, but I'm not sure if generalizing a suffix tree into higher dimensions is exactly straightforward or the best approach here.

思考？

我的幼稚溶液来索引稠密矩阵的第一个元素和消除全矩阵搜索提供只有适度改进全矩阵扫描

My naive solution to index the first element of the dense matrix and eliminate full-matrix searching provided only a modest improvement over full-matrix scanning.

什么是解决这个问题的最好方法是什么？

What's the best way to solve this problem?

Example:

Input:

Full matrix:
123
212
421

Search matrix:
12  
21  

Output:
2

该子矩阵发生的两次在全矩阵，所以输出为2全矩阵可能是1000×1000，但是，与搜索矩阵一样大，100×100（可变大小），以及我需要处理成一排的一些搜索矩阵。人机工程学，这个问题的蛮力过于低效，以满足我的亚秒级的搜索时间为几个矩阵。

This sub-matrix occurs twice in the full matrix, so the output is 2. The full matrix could be 1000x1000, however, with a search matrix as large as 100x100 (variable size), and I need to process a number of search matrices in a row. Ergo, a brute force of this problem is far too inefficient to meet my sub-second search time for several matrices.

推荐答案

对于算法的过程中，我曾经的运动，其中的拉宾-卡普的串搜索算法必须被稍微延伸以搜索在您所描述的方式相匹配的二维子矩阵

For an algorithms course, I once worked an exercise in which the Rabin-Karp string-search algorithm had to be extended slightly to search for a matching two-dimensional submatrix in the way you describe.

我认为，如果你花时间去了解，因为它是在维基百科上，将其扩展到两个方面是清楚的，你的自然的方式描述的算法的时间。从本质上讲，你只要把几个越过矩阵，同时沿一列爬行。有一些小动作保持的时间复杂度尽可能低，但你可能甚至不需要他们。

I think if you take the time to understand the algorithm as it is described on Wikipedia, the natural way of extending it to two dimensions will be clear to you. In essence, you just make several passes over the matrix, creeping along one column at a time. There are some little tricks to keep the time complexity as low as possible, but you probably won't even need them.

在搜索一个N×N矩阵的M×M矩阵，这种方法应该给你一个O（N²⋅M）算法。诡计，我相信它可以细化到O（N²）。

Searching an N×N matrix for a M×M matrix, this approach should give you an O(N²⋅M) algorithm. With tricks, I believe it can be refined to O(N²).

这篇关于二维子矩阵快速计数withing大，密集的二维矩阵？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！