ネストの深いhashのパスを再帰的に取得したい

Question

###前提・実現したいこと
ネストの深いhashのパスを再帰的に取得したい

以下のようなネストのあるHashのパスをネストがなくなるまで再帰的に取得したいと考えています

 sample_hash = 
{"nest1-1"=>"value1-1",
 "nest1-2"=>
    {"nest2-1"=>{"nest3-1a"=>"26513", 
                "nest3-1b"=>"3"
                },
     "nest2-2"=>{"nest3-2a"=>"317829", 
                 "nest3-2b"=>"50"
                 }
    }
 }
#ほしい結果
result_array
[
["nest1-1"],
["nest1-2"]["nest2-1"]["nest3-1a"],
["nest1-2"]["nest2-1"]["nest3-1b"],
["nest1-2"]["nest2-2"]["nest3-2a"],
["nest1-2"]["nest2-2"]["nest3-2b"]
]

#上記結果を用いて、ネストしたHashのKey一覧をだし、valueを一意に特定できるようにしたい
sample_hash[result_array[4]] =>"50"
=> sample_hash["nest1-2"]["nest2-2"]["nest3-2b"] 
=>"50"

###試したこと
以下のようなメソッドを作り実行しました。

  def get_nested_path(target_hash, *current_path)
    target = target_hash
    path = current_path || []
    target.each do |k,v|
      if target[k].instance_of?(Hash)
        path << target[k]
        get_nested_path(target[k], path)
      else
        path << target[k]
        return path
      end
    end
  end

get_nested_path(sample_hash,nil)
=> [nil, "value1-1"]

上記メソッド自体、1回目のkeyを拾った時点でreturnしてしまうのでうまくいかないことは
理解していますが、上記に記載した結果を得られるようなメソッドの書き方が思いつきません

また、実際に扱うHashはネストの深さが確定していないため、N階層ネストしたHashで実行可能な
メソッドを作れればと思っています。

どなたかわかる方、ご教授ください

Answer 1

こんにちは。

以下のような感じで、いかがでしょうか？

# coding: utf-8

sample_hash =
  {"nest1-1" => "value1-1",
   "nest1-2" =>
    {
      "nest2-1" => {
        "nest3-1a" => "26513",
        "nest3-1b" => "3"
      },
      "nest2-2" => {
        "nest3-2a" => "317829",
        "nest3-2b" => "50"
      }
    }
  }

def recursive_traverse(h, paths, pref='')
  h.each do |k, v|
    if v.is_a? String
      paths["#{pref}#{k}"] = v
    elsif v.is_a? Hash
      recursive_traverse(v, paths, "#{pref}#{k}/")
    end
  end
end

paths = {}

recursive_traverse(sample_hash, paths)

paths.each do |k, v|
  puts "#{k}: #{v}"
end

上記を実行すると、以下が出力されます。

nest1-1: value1-1

nest1-2/nest2-1/nest3-1a: 26513
nest1-2/nest2-1/nest3-1b: 3
nest1-2/nest2-2/nest3-2a: 317829
nest1-2/nest2-2/nest3-2b: 50

参考になりましたら幸いです。

---

追記

以下のような別解を考えました。
（ただし、質問で問われている本題から離れてしまうと思うので、あくまで参考に留めて頂ければと思います）

所与のハッシュsample_hashは、構造的に次のXMLと等価です。

<?xml version="1.0" encoding="UTF-8"?>
<root>
    <nest1-1>value1-1</nest1-1>
    <nest1-2>
        <nest2-1>
            <nest3-1a>26513</nest3-1a>
            <nest3-1b>3</nest3-1b>
        </nest2-1>
        <nest2-2>
            <nest3-2a>317829</nest3-2a>
            <nest3-2b>50</nest3-2b>
        </nest2-2>
    </nest1-2>
</root>

ただしXMLにするためには、最上位のノードは１つなので、上記では
便宜的に <root> 要素をトップに追加しています。

XMLを扱う問題に置き換えれば、value1-1 や 26513は XMLのテキストノードで、
これらはXPath で //text() という指定でまとめて取得できます。
あとは、テキストノードのそれぞれについて、XPathを逆に求めれば、
テキストノードとそれに至るXPathの組を得ることができます。

この考えで作成したスクリプトが以下です。

# coding: utf-8

require 'nokogiri'

sample_hash =
    {'nest1-1' => 'value1-1',
     'nest1-2' =>
         {
             'nest2-1' => {
                 'nest3-1a' => '26513',
                 'nest3-1b' => '3'
             },
             'nest2-2' => {
                 'nest3-2a' => '317829',
                 'nest3-2b' => '50'
             }
         }
    }

class Hash
  def to_xml
    map do |k, v|
      text = Hash === v ? v.to_xml : v
      '<%s>%s</%s>' % [k, text, k]
    end.join
  end
end

xml ='<?xml version="1.0" encoding="UTF-8"?><root>%s</root>' % [sample_hash.to_xml]

Nokogiri::XML(xml).xpath('//text()').each do |item|
    xpath = Nokogiri::CSS.xpath_for item.css_path
    puts '%s=%s' % [xpath[0], item]
end

上記では、XMLをパース（解析）するために、nokogiri を使っており、
このスクリプトを実行すると以下が表示されます。

//root/nest1-1/child::text()=value1-1

//root/nest1-2/nest2-1/nest3-1a/child::text()=26513
//root/nest1-2/nest2-1/nest3-1b/child::text()=3
//root/nest1-2/nest2-2/nest3-2a/child::text()=317829
//root/nest1-2/nest2-2/nest3-2b/child::text()=50

このように与題をXMLのテキストノードの走査と考えて、//text() でテキストノードをまとめて
取ってこれるパーサーを使えば、自分で再帰的にテキストノードを探すメソッドを作らなくても
よくなります。

上記のコードで、Hash#to_xml を再帰メソッドとして実装しているので
「結局手間としては同じでは？」とお思いになるかもしれませんが、
ハッシュをXMLにするメソッドも自分で書かなくても、
以下のようなgemがあります。

• ActiveSupport::CoreExtensions::Array::Conversions#to_xml

• Gyoku

この別解で、何が言いたいかと言えば、与件を
「XMLのテキストノードへのパスを取得する」問題と置き換えれば、
自分で再帰メソッドを書く手間をかけなくても欲しい情報が得られるのでは？
ということでした。

ご参考になれば幸いです。

Answer 2

valueを無名再帰を用いて列挙してみると

sample_hash = 
 {"nest1-1"=>"value1-1",
  "nest1-2"=>
    {"nest2-1"=>{"nest3-1a"=>"26513", 
                "nest3-1b"=>"3"
                },
     "nest2-2"=>{"nest3-2a"=>"317829", 
                 "nest3-2b"=>"50"
                 }
    }
 }

func = proc{|f, (k, v), memo|
  if v.is_a? Hash
    v.each_with_object(memo, &f.curry[f])
  else
    memo << v
  end
}

sample_hash.each_with_object([], &func.curry[func])
# => ["value1-1", "26513", "3", "317829", "50"]

Answer 3

まず，「ほしい結果」ですが，本当は

[["nest1-1"],
 ["nest1-2", "nest2-1", "nest3-1a"],
 ["nest1-2", "nest2-1", "nest3-1b"],
 ["nest1-2", "nest2-2", "nest3-2a"],
 ["nest1-2", "nest2-2", "nest3-2b"]]

ではありませんか？

そういうものを得るメソッドは，こんなふうに書けます。

def paths_of_hash(hash)
  result = []
  hash.each do |k, v|
    if v.is_a?(Hash)
      result.concat paths_of_hash(v).map{ |path| path.unshift(k) }
    else
      result << [k]
    end
  end
  result
end

paths = paths_of_hash(sample_hash)

そして，特定のパスを使って入れ子ハッシュの値を得るには，Hash#dig が使えます。

p sample_hash.dig(*paths[4])
# => "50"

以上のコードでわからない点があったらお尋ねください。

Comments

[ykomuro0719]

解答ありがとうございます！
今回まさにやりたいことが上記でできました！