円周率13兆桁から特定の数列を検索するプログラムを作りました

2017/07/25追記

　情報源(http://piworld.calico.jp/index.html)のサイトが消滅しまったことにより、以下のコードが使えなくなりました。新たな情報源を探しませんと……

概要

　ある方から「円周率から特定の数列を探せないか」という依頼がありました。1.6万桁・100万桁辺りまではWeb上で簡単にアクセスできますが、それ以上となると計算結果をlzhやzipなどでうｐしている場合が多いです。特に後者のサイト(http://piworld.calico.jp/index.html)だとギネス記録の13兆桁(2014年10月7日に達成)までアクセスできるのでオススメなのですが、いちいちzipファイルをダウンロードして検索するのは面倒ですよね？
　というわけで、全自動で行えるようにするツールを作成しました。

※円周率世界記録を達成したソフト「y-cruncher」はここからダウンロードできます。
http://www.numberworld.org/y-cruncher/

まずはzipをダウンロードしよう

　とりあえずRubyで実装することにしたわけですが、そもそもRubyでzipファイルはどう扱われるのでしょうか？
　そこでググッたところ、zipファイルを扱えるライブラリがあることが判明。「gem install rubyzip」で入るので早速導入しました。で、解凍自体は問題なく高速に行える……のですが、zipをダウンロードするのが辛かった。
　まずファイル自体のサイズが大きいので、光回線でダウンロードしようにも1ファイル20秒近くかかります。1ファイルには1億桁が収められているので、これが13万個もあると考えるだけで頭がくらくらしてきました。1ファイルの大きさは約57MBなので、円周率全体で7TB以上(全てダウンロードするのに30日)存在することになります！
　ちなみにダウンロードする際のURLですが、次のようなルールで決められているようです。

• ファイル名は、sprintf("pi-%04d.zip",k)
• ファイル名の1つ上の階層は、*"pi-"+(((k-1)/1000+1)100).to_s+"b"
• ファイル名の2つ上の階層は、k=1～34000まで**"value"、それ以降が"value"+((k-1)/34000+1)**

次にテキストを読み取ろう

　さて、zip内のテキストファイルは、次のように記録されています。

　つまり、10桁毎に半角空白・100桁毎に改行・1ファイルに100万改行というわけです。文字コードはShift_JIS・CRLFですが、どうせASCII文字しか無いので瑣末な問題でしょう。
　幸い、検索自体は遅くない(最初の1億桁から「1683139375」を探しだすのが一瞬だった)のですが、問題は加工。半角空白および改行部分をどう対処するか……と考えつつ適当にgsub!(/ |:.+|\n/, '')したところ、3秒ほどで置換が完了しました。ダウンロードの重さを考えると許容範囲内ですね。
　ただ、こうなると次に気になるのが、数列が複数ファイルに跨る際の対処です。流石に3ファイル以上に跨るケースは無視するとしても、2ファイルの境界に跨るケースは考慮する必要があります。そこで、ファイルを読み込んだ後、バッファに前のファイルの1億桁＋今のファイルの1億桁と足し合わせて検索することにしました。そこそこメモリを食うことになりますが仕方ありませんね。

完成したコードがこちらになります

　ダウンロードしたzipファイルを2度もダウンロードしないようにしたので、1回実行すれば2回目以降は高速に実行できます。もっとも、大量に・かつ高速に検索クエリが存在する場合は、ハッシュに格納する等の改造を加える必要がありますが。

search.rb

require 'open-uri'
require 'zip'

# 検索する終端(最大130000まで)
max_files = 5
# 検索したい文字列
str = '1234'

const_number = 100000000 #1億
txt_data = ''
1.upto(max_files){|k|
    puts k.to_s + '億桁目まで...'
    # ダウンロードするURLを生成する
    url = 'http://piworld.calico.jp/value'
    if k <= 34000 then
        url << '/'
    else
        url << "#{(k - 1) / 34000 + 1}/"
    end
    url << "pi-#{((k - 1) / 1000 + 1) * 100}b/"
    url << sprintf("pi-%04d.zip", k)
    # ダウンロードする
    file_name = File.basename(url)
    unless File.exist?(file_name)
        open(file_name, 'wb'){|output|open(url){|data|output.write(data.read)}}
    end
    # ZIPファイルを解凍し、中のファイルを読み取る
    txt_data_ = ''
    Zip::File.open(file_name) do |zip_file|
        zip_file.each do |f|
            txt_data_ = zip_file.read(f.name)
        end
    end
    # 整形処理
    txt_data_.gsub!(/ |:.+|\n/, '')
    txt_data = txt_data[const_number, const_number] if k > 2
    txt_data << txt_data_
    # 検索処理
    pos = txt_data.index(str)
    unless pos.nil? then
        puts "☆発見しました！　位置：小数点以下#{(k == 1 ? pos + 1 : (k - 2) * const_number + pos + 1)}桁目"
        break
    end
}
puts '検索終了'

参考

ファイルをWebからダウンロードして保存する