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

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

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

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

# まずはzipをダウンロードしよう
　とりあえずRubyで実装することにしたわけですが、そもそもRubyでzipファイルはどう扱われるのでしょうか？
　そこでググッたところ、[zipファイルを扱えるライブラリがある](http://blawat2015.no-ip.com/~mieki256/diary/201312292.html)ことが判明。「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内のテキストファイルは、次のように記録されています。
![cap.png](https://qiita-image-store.s3.amazonaws.com/0/29802/87fef236-4522-fb40-72d6-e9adddda5c88.png)
　つまり、**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からダウンロードして保存する](http://qiita.com/ima0123/items/a7c252a45f91eb807930)