C++でバイナリ行列の重複行を効率的に検出する方法(Trie活用)

2値行列(バイナリ行列)を想定してみましょう。本記事では、行列の中から重複する行を効率よく見つける方法を解説します。例として、次のような行列を考えます。

この行列では、0始まりで数えて位置3、4、5の行が互いに重複しています(1行目と4行目、2行目・5行目・6行目がそれぞれ同じ内容です)。

解決のアプローチ:Trie(トライ木)を活用する

この問題を解くには、Trie(トライ木)と呼ばれるデータ構造を利用します。Trieは、扱う値の種類が少ないデータの格納と検索に適した効率的な構造で、検索の計算量はキーの長さに対してほぼ最適になります。バイナリ行列の場合、各ノードが持つ子は「0」と「1」の2つだけなので、Trieとの相性は抜群です。

アルゴリズムの流れはシンプルです。まず空のTrieを用意し、行列の各行を先頭から順に挿入していきます。挿入の際に、その行がすでにTrie内に登録済みであれば、その行は重複行であると判定できます。この方法なら行列全体を1回走査するだけで済み、時間計算量はO(行数×列数)に収まります。

サンプルコード

#include<iostream>
using namespace std;
const int MAX = 100;
class Trie {
    public:
    bool leaf_node;
    Trie* children[2];
};
Trie* getNode() {
    Trie* node = new Trie;
    node->children[0] = node->children[1] = NULL;
    node->leaf_node = false;
    return node;
}
bool insert(Trie*& head, bool* arr, int N) {
    Trie* curr = head;
    for (int i = 0; i < N; i++) {
        if (curr->children[arr[i]] == NULL)
            curr->children[arr[i]] = getNode();
        curr = curr->children[arr[i]];
    }
    if (curr->leaf_node)
        return false;
    return (curr->leaf_node = true);
}
void displayDuplicateRows(bool matrix[][MAX], int M, int N) {
    Trie* head = getNode();
    for (int i = 0; i < M; i++)
        if (!insert(head, matrix[i], N))
            cout << "重複する行の位置: " << i << endl;
}
int main() {
    bool mat[][MAX] = {
        {1, 1, 0, 1, 0, 1},
        {0, 0, 1, 0, 0, 1},
        {1, 0, 1, 1, 0, 0},
        {1, 1, 0, 1, 0, 1},
        {0, 0, 1, 0, 0, 1},
        {0, 0, 1, 0, 0, 1},
    };
    displayDuplicateRows(mat, 6, 6);
}

出力

重複する行の位置: 3
重複する行の位置: 4
重複する行の位置: 5

計算量のまとめ

この手法の時間計算量はO(M×N)(Mは行数、Nは列数)で、空間計算量も最悪の場合O(M×N)となります。各行を文字列化してソートやハッシュ集合で比較する方法でも同じ結果は得られますが、Trieを使えば挿入しながら重複を即座に検出できるため、1回の走査で処理が完結する点が大きな利点です。