rookiemaster
V2EX  ›  算法

有什么 3 维矩阵匹配算法吗?

  •  
  •   rookiemaster · Sep 24, 2024 · 3255 views
    This topic created in 785 days ago, the information mentioned may be changed or developed.

    一个大 3 维矩阵,一个小 3 维矩阵,要在大矩阵中找到与小矩阵相同的子矩阵。矩阵元素都是 0/1

    7 replies  •  2024-09-25 09:46:18 +08:00
    NoOneNoBody
    NoOneNoBody
    Sep 24, 2024
    1
    这个很容易降维啊
    rookiemaster
    rookiemaster
    OP
    Sep 24, 2024
    2
    @NoOneNoBody 不太理解,可以详细点吗,谢谢您
    NoOneNoBody
    NoOneNoBody
    Sep 24, 2024
    3
    @rookiemaster #2
    这个,还需要怎么解释呢
    小矩阵的类型非常单一,降维到一维很难?小矩阵降维后,大矩阵就是二维了,二维匹配算法很多吧
    甚至你说的这个例子,直接三维降一维也不是难事,0/1 换成 bit ,小矩阵就是 bytes 串,大矩阵就是 bytes 作为元素的一维数组了
    NoOneNoBody
    NoOneNoBody
    Sep 24, 2024
    4
    @NoOneNoBody #3
    PS: 看漏了,大小矩阵都是三维,但上述方法也是适用的,分步、逐级或者递归处理应该都行,看需求
    passive
    passive
    Sep 24, 2024 via Android
    5
    如果是整数元素,在每个维度上投影(求和),能粗略筛选出可能的匹配。在这几个可能性里面挨个匹配一遍。
    biz
    biz
    Sep 25, 2024
    6
    OP 了解字符串匹配的 KMP 算法吗?把 KMP 算法改造一下,时间复杂度可以做到线性,想不明白再问我
    rookiemaster
    rookiemaster
    OP
    Sep 25, 2024
    7
    @biz 谢谢,我了解一下
    About   ·   Help   ·   Advertise   ·   Blog   ·   API   ·   FAQ   ·   Privacy   ·   Solana   ·   3658 Online   Highest 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 32ms · UTC 09:59 · PVG 17:59 · LAX 01:59 · JFK 04:59
    ♥ Do have faith in what you're doing.