Rabin-Karp Frobenius Approximation of Sub-Matrices Matches

karp_frobenius_approximation.py

#!/usr/bin/env python3
"""
Copyright Dayton Pidhirney
"""

import numpy as np
import matplotlib.pyplot  as plt
import matplotlib.patches as patches

# Sliding Window for Submatrices
def generate_submatrices(matrix, size):
    submatrices = []
    positions = []
    for i in range(matrix.shape[0] - size + 1):
        for j in range(matrix.shape[1] - size + 1):
            submatrix = matrix[i : i + size, j : j + size]
            submatrices.append(submatrix)
            positions.append((i, j))
    return submatrices, positions


# Polynomial Rolling Hash for 2D Matrices with Arbitrary Precision
def compute_polynomial_hash(matrix, prime_base=31, modulus=2**61 - 1):
    hash_value = 0
    rows, cols = matrix.shape
    for i in range(rows):
        for j in range(cols):
            hash_value = (hash_value * prime_base + int(matrix[i, j])) % modulus
    return hash_value


# Rabin-Karp Algorithm for 2D Matrices with Approximation
def rabin_karp_2d(matrix_a, matrix_b, threshold=0.3):
    matches = []
    max_submatrix_size = min(matrix_a.shape[0], matrix_a.shape[1])

    for submatrix_size in range(1, max_submatrix_size + 1):
        submatrices_a, positions_a = generate_submatrices(matrix_a, submatrix_size)
        submatrices_b, positions_b = generate_submatrices(matrix_b, submatrix_size)

        hash_table_b = {}
        for submatrix_b, pos_b in zip(submatrices_b, positions_b):
            hash_value = compute_polynomial_hash(submatrix_b)
            if hash_value not in hash_table_b:
                hash_table_b[hash_value] = []
            hash_table_b[hash_value].append((submatrix_b, pos_b))

        for submatrix_a, pos_a in zip(submatrices_a, positions_a):
            hash_value = compute_polynomial_hash(submatrix_a)
            if hash_value in hash_table_b:
                for submatrix_b, pos_b in hash_table_b[hash_value]:
                    if np.allclose(submatrix_a, submatrix_b, atol=threshold):
                        matches.append((pos_a, pos_b, submatrix_a))
                        break

    return matches


# Create predefined matrices with visually pleasing shapes and slight overlaps
matrix_a = np.array(
    [
        [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
        [0, 1, 1, 0, 0, 0, 1, 1, 0, 0],
        [0, 1, 1, 0, 0, 0, 1, 1, 0, 0],
        [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
        [0, 0, 0, 1, 1, 1, 1, 0, 0, 0],
        [0, 0, 0, 1, 0, 0, 1, 1, 0, 0],
        [0, 0, 0, 1, 1, 1, 1, 0, 0, 0],
        [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
        [1, 1, 0, 0, 0, 0, 1, 1, 1, 1],
        [1, 1, 0, 0, 0, 0, 1, 0, 0, 0],
    ]
)

matrix_b = np.array(
    [
        [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
        [0, 0, 1, 1, 0, 0, 0, 1, 1, 0],
        [0, 0, 1, 1, 0, 0, 0, 1, 1, 0],
        [0, 0, 0, 0, 0, 0, 0, 1, 0, 0],
        [0, 0, 0, 0, 1, 1, 1, 1, 0, 0],
        [0, 0, 0, 0, 1, 0, 0, 1, 0, 0],
        [0, 0, 0, 0, 1, 1, 1, 1, 0, 0],
        [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
        [1, 1, 0, 0, 0, 1, 1, 1, 1, 1],
        [0, 1, 0, 0, 0, 1, 1, 0, 0, 0],
    ]
)

# Find matches using Rabin-Karp
matches = rabin_karp_2d(matrix_a, matrix_b, threshold=0.5)

# Visualization
fig, ax = plt.subplots(1, 2, figsize=(14, 6))

# Display the first matrix with matched submatrices highlighted
ax[0].imshow(matrix_a, cmap="viridis")
ax[0].set_title("Matrix A with Submatrix Matches")
for pos_a, pos_b, submatrix_a in matches:
    for (i, j), value in np.ndenumerate(submatrix_a):
        if value == 1:
            ax[0].add_patch(
                patches.Rectangle(
                    (pos_a[1] + j - 0.5, pos_a[0] + i - 0.5),
                    1,
                    1,
                    edgecolor="r",
                    facecolor="none",
                )
            )

# Display the second matrix with matched submatrices highlighted
ax[1].imshow(matrix_b, cmap="viridis")
ax[1].set_title("Matrix B with Submatrix Matches")
for pos_a, pos_b, submatrix_b in matches:
    for (i, j), value in np.ndenumerate(submatrix_b):
        if value == 1:
            ax[1].add_patch(
                patches.Rectangle(
                    (pos_b[1] + j - 0.5, pos_b[0] + i - 0.5),
                    1,
                    1,
                    edgecolor="r",
                    facecolor="none",
                )
            )

plt.show()