Rubyの多次元hashから目的の値がある位置を検索する方法

エンジニアのohkabeです。
多次元構造のjson、複雑ですよね。
深いネストの中から特定の値を取り出したいと思ったことはありませんか？
そしてその階層に至るまでのkeyの連続を知りたいと思ったことはないですか？
例えば以下のjsonがあるとして。

src_json = <<EOS
[
  {
    "id": "0001",
    "type": "donut",
    "name": "Cake",
    "ppu": 0.55,
    "batters":
      {
        "batter":
          [
            { "id": "1001", "type": "Regular" },
            { "id": "1002", "type": "Chocolate" },
            { "id": "1003", "type": "Blueberry" },
            { "id": "1004", "type": "Devil's Food" }
          ]
      },
    "topping":
      [
        { "id": "5001", "type": "None" },
        { "id": "5002", "type": "Glazed" },
        { "id": "5005", "type": "Sugar" },
        { "id": "5007", "type": "Powdered Sugar" },
        { "id": "5006", "type": "Chocolate with Sprinkles" },
        { "id": "5003", "type": "Chocolate" },
        { "id": "5004", "type": "Maple" }
      ]
  },
  {
    "id": "0002",
    "type": "donut",
    "name": "Raised",
    "ppu": 0.55,
    "batters":
      {
        "batter":
          [
            { "id": "1001", "type": "Regular" }
          ]
      },
    "topping":
      [
        { "id": "5001", "type": "None" },
        { "id": "5002", "type": "Glazed" },
        { "id": "5005", "type": "Sugar" },
        { "id": "5003", "type": "Chocolate" },
        { "id": "5004", "type": "Maple" }
      ]
  },
  {
    "id": "0003",
    "type": "donut",
    "name": "Old Fashioned",
    "ppu": 0.55,
    "batters":
      {
        "batter":
          [
            { "id": "1001", "type": "Regular" },
            { "id": "1002", "type": "Chocolate" }
          ]
      },
    "topping":
      [
        { "id": "5001", "type": "None" },
        { "id": "5002", "type": "Glazed" },
        { "id": "5003", "type": "Chocolate" },
        { "id": "5004", "type": "Maple" }
      ]
  }
]
EOS

このjsonからvalueが"Sugar"であるものを探します。
すると0 => "topping" => 2 => "type"の階層と1 => "topping" => 2 => "type"の階層に"Sugar"がありますね。
これと同じように、さらに巨大なjsonから探し出そうというのが今回のテーマです。

再帰関数で実装

require "json"

class HashParser
  attr_accessor :nodes

  def parse(src_hash)
    @key_path = []
    @nodes = []
    recursive_parse(src_hash)
  end

  def recursive_parse(parent)
    if parent.is_a?(Array)
      parent.each_with_index do |index, key|
        add_node(key, index)
      end
    elsif parent.is_a?(Hash)
      parent.each do |key, val|
        add_node(key, val)
      end
    end
    @key_path.pop
  end

  def add_node(key, val)
    @key_path << key
    node = {
      key: key,
      val: val,
      key_path: @key_path.clone
    }
    @nodes << node
    recursive_parse(val)
  end
end

深さ優先探索で多次元ハッシュを掘っていきます。
要素がハッシュか配列だった場合、中に入り
さらにその要素がハッシュか配列だった場合、中に入り...
という処理を繰り返していきます。

↓パースするには

src_hash = JSON.parse(src_json)
hsp = HashParser.new

hsp.parse(src_hash)
nodes = hsp.nodes

要素を抽出

↓パース結果

[
  . # 途中省略
  .
  .
  {:key=>0, :val=>{"id"=>"5001", "type"=>"None"}, :key_path=>[0, "topping", 0]},
  {:key=>"id", :val=>"5001", :key_path=>[0, "topping", 0, "id"]},
  {:key=>"type", :val=>"None", :key_path=>[0, "topping", 0, "type"]},
  {:key=>1, :val=>{"id"=>"5002", "type"=>"Glazed"}, :key_path=>[0, "topping", 1]},
  {:key=>"id", :val=>"5002", :key_path=>[0, "topping", 1, "id"]},
  {:key=>"type", :val=>"Glazed", :key_path=>[0, "topping", 1, "type"]},
  {:key=>2, :val=>{"id"=>"5005", "type"=>"Sugar"}, :key_path=>[0, "topping", 2]},
  {:key=>"id", :val=>"5005", :key_path=>[0, "topping", 2, "id"]},
  {:key=>"type", :val=>"Sugar", :key_path=>[0, "topping", 2, "type"]},
  {:key=>3, :val=>{"id"=>"5007", "type"=>"Powdered Sugar"}, :key_path=>[0, "topping", 3]},
  {:key=>"id", :val=>"5007", :key_path=>[0, "topping", 3, "id"]},
  {:key=>"type", :val=>"Powdered Sugar", :key_path=>[0, "topping", 3, "type"]},
  {:key=>4, :val=>{"id"=>"5006", "type"=>"Chocolate with Sprinkles"}, :key_path=>[0, "topping", 4]},
  .
  .
  .
]

↓keyがbatterのものを抽出にはselectを使用します

nodes.select{|v| v[:key] == 'batter'}

[
  {:key=>"batter", :val=>
   [{"id"=>"1001", "type"=>"Regular"},
    {"id"=>"1002", "type"=>"Chocolate"},
    {"id"=>"1003", "type"=>"Blueberry"},
    {"id"=>"1004", "type"=>"Devil's Food"}],
  :key_path=>[0, "batters", "batter"]},
 {:key=>"batter", :val=>[{"id"=>"1001", "type"=>"Regular"}], :key_path=>[1, "batters", "batter"]},
 {:key=>"batter", :val=>[{"id"=>"1001", "type"=>"Regular"}, {"id"=>"1002", "type"=>"Chocolate"}], :key_path=>[2, "batters", "batter"]}
]

↓同様にvalueがsugarのものを抽出してみます

nodes.select{|v| v[:val] == 'Sugar'}

[
  {:key=>"type", :val=>"Sugar", :key_path=>[0, "topping", 2, "type"]},
  {:key=>"type", :val=>"Sugar", :key_path=>[1, "topping", 2, "type"]}
]

keyを取得する

valueがsugarのものを一つ取ってきて、その要素に至るまでの連続したkeyを取得します(key_pathと呼んでいます)

target_nodes = nodes.select{|v| v[:val] == 'Sugar'}
# => [{:key=>"type", :val=>"Sugar", :key_path=>[0, "topping", 2, "type"]},
#     {:key=>"type", :val=>"Sugar", :key_path=>[1, "topping", 2, "type"]}]

target_nodes[0]
# => {:key=>"type", :val=>"Sugar", :key_path=>[0, "topping", 2, "type"]}

key_path = target_nodes[0][:key_path]
# => [0, "topping", 2, "type"]

↓一つ上の階層が欲しいときはkey_pathの最後の要素以外を順にsrc_hash渡していきます

src_hash[0]["topping"][2]
# => {"id"=>"5005", "type"=>"Sugar"}

↓よってpopしてからeachで代入していけば良いです

key_path.pop
key_path
# => [0, "topping", 2]

tmp = src_hash.clone
key_path.each{|k| tmp = tmp[k]}
tmp
# => {"id"=>"5005", "type"=>"Sugar"}

終わりに

意外となかったハッシュ内の検索機能を実装してみました。
まだまだ改良の余地ありなので、便利なメソッドを考えて拡張してみてください。
それでは

MAGAZINE