大量データの重複検出をUnionFindと逆引きインデックスで劇的に高速化した話 – Techouse Developers Blog

はてなブログ

ogp

先日、業務で重複判定を実装する機会がありました。その中でUnionFindと逆引きインデックスという技術を使ったのですが、実際に導入してみると非常に効果的だったので、今回は商品マスタの重複検出を例にこれらの技術を用いて重複検出の課題を解決した話をします。

想定する問題

ECサイトの商品マスタ管理において、同一商品が複数のレコードとして登録されてしまう問題があるとします。これは、異なる仕入先からの商品情報や、データ入力時の表記揺れなどが原因で起こります。重複した商品データは在庫管理の混乱や顧客体験の悪化を招くため、正確な重複検出と統合が必要になります。

重複判定条件

今回の商品マスタの例では、以下のいずれかの条件を満たせば「重複」とみなします。

  1. JANコードが一致：jan_codeが同じ
  2. 型番が一致：model_numberが同じ
  3. ブランド名 + 容量が一致：brandとcapacityの組み合わせが同じ
  4. ブランド名 + モデル名が一致：brandとmodelの組み合わせが同じ
  5. モデル名 + 容量が一致：modelとcapacityの組み合わせが同じ

前提条件

  • null値の扱い：nullや空文字列は重複判定の対象外とします。つまり、null == nullは重複とはみなしません
  • 推移的関係：商品A=商品B、商品B=商品Cの場合、商品A=商品Cとして扱います

想定データ・判定パターン

以下のような商品データを例に考えます：

商品A: {
  jan_code: "4901234567890",
  brand: "TechCorp",
  model: "SmartPhone X Pro",
  capacity: "128GB"
}

商品B: {
  jan_code: null,
  brand: "TechCorp",
  model: "SmartPhone X Pro",
  capacity: "128GB"
}

商品C: {
  jan_code: null,
  brand: "TechCorp",
  model: "SmartPhone X Pro",
  capacity: "128GB"
}

この場合、商品A・B・Cは全て「ブランド名+モデル名が一致」の条件により重複とみなされます。

重複検出の基本的なアプローチ

重複を検出するには、以下の手順が必要です。

  1. 重複判定条件を定義する：どのような条件で「重複」とみなすかを決める
  2. データ同士を比較する：2つのデータが重複判定条件を満たすかチェック
  3. 全てのペアを調べる：漏れなく重複を検出するため、全ての組み合わせを調べる

最初は、この愚直なアプローチで実装しようと考えていました。

products = [
  Product.new(id: '1', jan_code: '123', brand: "TechCorp"),
  Product.new(id: '2', jan_code: '456', brand: "TechCorp"),
  Product.new(id: '3', jan_code: '789', brand: "OtherCorp")
]

duplicate_groups = []
products.each do |product1|
  products.each do |product2|
    next if product1.id == product2.id  
    
    if product1.duplicate?(product2)
      duplicate_groups end
  end
end


puts duplicate_groups.flatten.uniq

しかし、実際に検討を進める中で、以下の2つの深刻な課題に直面しました。

直面した2つの課題

課題1：間接的な重複を見逃してしまう

具体例で見る間接的重複の問題

商品A: {
  jan_code: "4901234567890",
  brand: "TechCorp",
  model: "SmartPhone X Pro",
  capacity: "128GB"
}

商品B: {
  jan_code: null,
  brand: "TechCorp",
  model: "SmartPhone X Pro",
  capacity: "128GB"
}

商品C: {
  jan_code: null,
  brand: "TechCorp",
  model: "SmartPhone X Pro",
  capacity: "128GB"
}

判定結果：

  • 商品A ≠ 商品B：JANコード不一致、ブランド名+モデル名が一致 → 重複
  • 商品B ≠ 商品C：ブランド名+モデル名が一致 → 重複
  • 商品A ≠ 商品C：JANコード不一致、ブランド名+モデル名が一致 → 重複

しかし、単純にペア同士を直接比較するだけでは、商品Aと商品Cの間接的な重複を検出できません。

本来は 商品A=商品B=商品C として扱うべきなのに、間接的な重複関係を検出できないのです。

課題2：O(n²)の計算量で現実的でない処理時間

全ての組み合わせに対して愚直に重複判定をするアプローチでは、データをn件とすると組み合わせ数は

n × (n-1) ÷ 2

これはO(n²)の計算量になります。

データ件数に応じた比較回数は以下のようになります。

  • 1万件: 約5000万回の比較
  • 10万件: 約50億回の比較
  • 100万件: 約5000億回の比較

1回の比較処理にかかる時間がわずかでも、10万件のデータでは処理完了まで膨大な時間が必要になります。実際の重複判定処理はより複雑な条件判定を含むため、さらに長時間の処理が必要です。

データ量が増えるほど処理時間が二次関数的に増加するのは、深刻な問題でした。

この2つの課題を解決するために選択した技術が、UnionFindと逆引きインデックスでした。

結果として、間接重複も検知できるようにしつつ、計算量をO(n²)からO(n)に改善し、大幅な高速化を実現できました。

これらの改善に用いた手法について解説します。

課題1の解決：UnionFindによる間接的重複の自動検出

推移的な関係を手動で管理する複雑さ

間接的な重複を検出するために、最初は推移的な関係を手動で管理しようと考えました。

def find_transitive_duplicates(data)
  direct_pairs = find_direct_duplicates(data)

  
  
end

しかし、この実装は複雑すぎて現実的ではありませんでした。

UnionFind：グループ化問題の救世主

そんな時に出会ったのがUnionFindというデータ構造でした。

UnionFindとは？

UnionFindは要素をグループに分けて管理することに特化したデータ構造です。

基本的な操作：

  1. find(x)：要素xが属するグループの代表元を取得
  2. union(x, y)：要素xとyのグループを統合
  3. same(x, y)：要素xとyが同じグループかを判定

重複検出における威力を簡単な例で示すと

uf = UnionFind.new(3)  

uf.union(0, 1)  
uf.union(1, 2)  

uf.same?(0, 2)

UnionFindが解決してくれること：

  • 推移性の自動処理：A=B、B=Cならば自動的にA=Cとなる
  • シンプルな実装：複雑な条件分岐が不要
  • 高速な操作：適切な最適化により大量データでも高速処理

UnionFindの詳細な実装方法や経路圧縮・ランクによる最適化については、以下のスライドで分かりやすく解説されています。こちらは社内LTで今回の話を発表した際のスライドの一部を抜粋したものです。

これで間接的な重複の問題は一気に解決しました。

課題2の解決：逆引きインデックスによる計算量削減

UnionFindだけでは解決しない計算量問題

UnionFindで実装は簡単になりましたが、まだ全ての組み合わせを比較している状況は変わりません。

10万件 × (10万-1) ÷ 2 = 約50億回の比較

これでは処理時間が現実的ではありません。

値の一致に着目した効率化のアプローチ

ここで重要な気づきがありました。

重複条件は何かしらの値が一致することが前提

この特性を活用すれば、逆引きインデックスという手法で計算量を劇的に削減できます。

逆引きインデックスとは？

逆引きインデックスは、値から該当するデータを高速に検索するためのデータ構造です。

身近な例で説明すると、辞書の索引がまさに逆引きインデックスです。

例えば、辞書で「コンピュータ」という単語の意味を調べたいとき、2つの方法があります。

方法1：全探索（非効率）

  • 1ページ目から順番にめくって「コンピュータ」という単語を探す
  • 数百ページある辞書では非常に時間がかかる

方法2：逆引きインデックス（効率的）

  • 巻末の索引で「コンピュータ → 123ページ」を確認
  • 123ページを直接開いて瞬時に単語の説明を見つける

この索引こそが逆引きインデックスです。「単語 → ページ数」という関係を事前に整理しておくことで、全探索することなく目的の情報を瞬時に見つけることができます。

通常のインデックスが「データID → 値」の関係を持つのに対し、逆引きインデックスは「値 → データIDの配列」の関係を持ちます。

基本的な仕組み。

reverse_index = {
  "TechCorp" => [商品A, 商品B, 商品C],     
  "128GB" => [商品A, 商品D],              
  "4901234567890" => [商品A]              
}

逆引きインデックスの威力

重複検出において逆引きインデックスが発揮する威力は以下の通りです。

  • 同じ値を持つデータを瞬時にグループ化：ハッシュのキーが同じデータは自動的に同じ配列に格納される
  • 比較処理の完全な排除：値が一致するデータ同士は比較不要で重複確定
  • O(1)での高速検索：ハッシュテーブルにより定数時間でのアクセスが可能

つまり、全てのデータの重複判定条件となる値を逆引きインデックスのハッシュに格納すれば、同じ値を持つデータは自動的に同じグループに分類されます。比較処理そのものが不要になるのです。

補足：なぜUnionFindも必要なのか

ここまでの説明を読んで「逆引きインデックスだけで十分では？」と思われる方もいるかもしれません。

確かに、重複条件が1つだけであれば、UnionFindは不要です。逆引きインデックスで同じ値を持つデータをグループ化するだけで重複検出が完了します。

しかし、今回の例では複数の重複条件があります。

  • JANコードが一致
  • 型番が一致
  • ブランド名+容量が一致
  • ブランド名+モデル名が一致
  • モデル名+容量が一致

各条件で作成された逆引きインデックスは独立しているため、異なる条件で重複したデータ同士を統合する仕組みが必要になります。これがUnionFindの役割です。

UnionFindにより、「JANコードで重複した商品Aと商品B」「ブランド名+モデルで重複した商品Bと商品C」という情報から、自動的に「商品A=商品B=商品C」という推移的な関係を導出できるのです。




jan_index = {
  "4901234567890" => [商品A, 商品C],    
  "4901234567891" => [商品B]           
}


brand_model_index = {
  "TechCorp:SmartPhone X Pro" => [商品A, 商品B, 商品C],  
  "OtherCorp:Device Y" => [商品D]                      
}


[jan_index, brand_model_index, ...].each do |index|
  index.each_value do |data_ids|
    next if data_ids.size 2  

    
    data_ids.combination(2).each do |id1, id2|
      union_find.union(id1, id2)
    end
  end
end

計算量の劇的な改善

この手法により、計算量がO(n²) から O(n) に改善されました。

  • 従来：10万件 × 10万件 = 100億回の処理
  • 改善後：10万件の1回ずつの処理 = 10万回の処理

大幅な計算量削減を実現できました。

実装

UnionFindと逆引きインデックスを組み合わせた実装の核心部分を紹介します。

逆引きインデックスの構築

DUPLICATE_CONDITIONS = [
  :jan_code,
  :model_number,
  { name: :brand_model, fields: [:brand, :model] },
  { name: :brand_capacity, fields: [:brand, :capacity] },
  { name: :model_capacity, fields: [:model, :capacity] }
]


def build_indexes(entries)
  indexes = {}

  entries.each_with_index do |entry, index|
    DUPLICATE_CONDITIONS.each do |condition|
      case condition
      when Symbol
        
        add_to_index(indexes, condition, entry[condition], index)
      when Hash
        
        composite_value = condition[:fields].map { |field| entry[field] }.compact.join(':')
        add_to_index(indexes, condition[:name], composite_value, index)
      end
    end
  end

  indexes
end


def add_to_index(indexes, key, value, index)
  return if value.nil? || value.to_s.strip.empty?

  indexes[key] ||= {}
  indexes[key][value] ||= []
  indexes[key][value] end

UnionFindでの統合処理

def group_duplicates(entries, indexes)
  union_find = UnionFind.new(entries.size)

  
  indexes.each_value do |value_map|
    value_map.each_value do |data_indices|
      next if data_indices.size 2  

      
      data_indices.combination(2).each do |index1, index2|
        union_find.union(index1, index2)
      end
    end
  end

  union_find
end

メイン処理

def detect_duplicates(entries)
  
  indexes = build_indexes(entries)

  
  union_find = group_duplicates(entries, indexes)

  
  groups = {}
  entries.each_with_index do |entry, index|
    root = union_find.find(index)
    groups[root] ||= []
    groups[root] end

  
  groups.values.select { |group| group.size > 1 }
end

この実装により、O(n²)の全件比較からO(n)の効率的な処理に改善されました。逆引きインデックスで同じ値を持つデータを直接グループ化し、UnionFindで推移的な関係を自動処理することで、大量データでも高速な重複検出が可能になります。

まとめ

今回紹介したUnionFindと逆引きインデックスを組み合わせた手法により、重複検出処理の2つの課題を解決できました。

  1. 間接的重複の自動検出：UnionFindの推移性により、商品A=商品B、商品B=商品Cから自動的に商品A=商品Cが導出される
  2. 計算量の劇的改善：逆引きインデックスにより、O(n²)からO(n)への改善を実現

この手法は、顧客データ統合や商品マスタ統合など、大量データの重複検出が必要な場面で威力を発揮します。特に、複数の判定条件を持つ複雑な重複関係や、推移的な関係を扱う必要がある場合に有効です。

重要なのは、問題を「比較問題」ではなく「グループ化問題」として捉え直すことでした。この視点の転換により、適切なデータ構造とアルゴリズムの選択が可能になり、実用的な処理時間での大量データ処理を実現できました。

Techouseでは、社会課題の解決に一緒に取り組むエンジニアを募集しております。
ご応募お待ちしております。

jp.techouse.com




元の記事を確認する

【TypeScript】カスタムエラーのすすめ | PrAhaのフィード 前の記事 AI時代にVimを学ぶ意味 - Vim初心者が過ごした夏の記録 | スペースマーケット Engineer Blogのフィード 次の記事

関連記事