?

Log in

No account? Create an account

Entries by tag: wikipediaconv

WikipediaConv、その後
karino2
http://code.google.com/p/wikipediaconv/

ここ二週間くらいはずっとこのソフトの高速化をしていました。
ハードディスクが足りなくて途中までの結果しか分かりませんが、だいたい30時間ちょっとで終わる所までは来たと思います。一晩で終わる所まで持って行きたかったのですが、なかなか難しい。
もともと10日くらいかかっていた事を考えると良く頑張ったかなぁ、と思います。
ここから先は自分のPCのスペックのせい、という事で。

WikipediaConvはWikipediaのダンプデータをフォルダに分けてpdfに出力する、というプログラムです。
Wikipediaのデータは巨大で、だいたい150万ファイルくらいになります。
プログラム自体は単純だったのですが、ファイルの数がこれだけ多いと、小さい時には起こらなかった問題がたくさん起こり、それがパフォーマンスの障害となります。
大きいデータでしか起こらないので再現に時間がかかり、PCがずっとこの再現作業等で使えなくなってしまうのが、このプログラムの開発の主な問題点でした。PCが二台あれば...

今後はフォーマット回りを直そうかなぁ、と思っていますが、本当にやるかは未定。
現状のままでも便利に使えているので。

この手のプログラムはどっかにありそうだなぁ、と思っていたのですが、なんであまり無いのかをちょっと理解しました。
それなりに使える所まで持ってくのがかなり大変。結局一ヶ月くらいかかりっきりでしたよ...

Wikipediaは面白いなぁ
karino2
テストがてらEZ-Readerであてもなく適当なページを見たりしているのですが、Wikipediaは面白いですねぇ。
現状の挙動はなかなか使いにくいのですが、コンテンツが面白いので我慢して使う気になる。
データ自体に価値があるのでコンバータの出来は悪くても実用になるんですね。

AKBとかEXILEとかどうでもいい知識を得ている所です。実物は相変わらず見た事ありませんが…

一回目にきづいた事、だいたい修正終了
karino2
ファイルが5000を越えたらsplit、とか、必要無いフォルダwalkをskipなど、とりあえず実データを通すのに必要と思った変更をだいたい実装しました。
また実データに通してみておかしい所を直して、を、もう何周かする必要がありそうですが、大きな部分は固まったかな?
jawikipediaのフルデータが通るようになったら2chにでもアナウンスしてみようかなぁ、と思っています。
まだ読みの分からない物が1フォルダに入ってしまう、というのが完全に回避された訳では無いですが、症状は大分緩和しているはず。
出来上がったpdfも未フォーマットとはいえいい感じだし、なかなか満足度高いです。

それにしてもでかいですねぇ、Wikipedia。

PdfArchiveは結構CPU使ってるなぁ
karino2
SplitはIOばっかのようで(少なくともユーザープロセス内では)CPUを全然食わなかったのですが、PdfArchiveは割とCPUを使っています。
基本的にフォルダの数だけ並列化出来るので、並列化した方が良さそうですねぇ。
今のマシンはコアが一つなのでいまいちやる気も起こりませんが、Indexingがマルチスレッドになってるのにこっちがシングルスレッドなのはおかしい。
ほとんどバグる余地も無いので、ManyCoreなマシンで走らせる機会があったら並列化しようかな。
ちなみに恐れていたよりはPdfArchiveは速そう。まだ「0」と「a」が終わっただけで「あ」が終わってみないと本当の所は分からないけれど。
ここまでの所20分くらい。「あ」が20分くらいで終われば4時間くらいで終わりそうだが…さすがにそれは甘いか?
12:10 甘かった。一時間経過したがまだ「pdf/あ/か」のあたり。このペースだと「あ」だけで10時間くらいかかりそう。
「あ」行で始まる単語は一番多い気もするが、これはきついなぁ。ここは(iTextSharp以外)高速化の余地もあまり無さそうだし。
ただリリースビルドにすると速くなりそうな所ではある。

ただフォルダをwalkingするだけのオーバーヘッド
karino2
ほとんどsplitが終わっている状態のフォルダに対し、一回splitをかけてみました。
全てのフォルダを巡回し、splitの必要が無いのでただ戻ってくる、という挙動のはずです。
だいたい6万フォルダくらい回って24分かかりました。後半少し実際のsplitも入ってますがだいたいこの位のオーダーのようで。
6万フォルダ。最悪値が2万くらいだと思っていたのですが、大分悪いですね。
たぶん英語などバランスの悪い物が幾つかあるので、その辺が原因かなぁ。
splitの閾値を変えてフォルダ数は半分くらいにはなるので、時間も半分近くにはなるかなぁ、と思ってます。
とりあえず一回20分として、三回で一時間。結構馬鹿に出来ないですねぇ。
Splitは1万ファイル溜まるごとにしますかね。
原理的には、今回のMoveで移動しなかったフォルダはskipしてもいいはずなので、このロジックを組み込むと劇的に速くなる気はします。
試してみたいですが、まずはきちんと動く事が優先です。

現在の状況
karino2
まだ手作業による修正が必要ですが、一通り本データを流してみて、ひっかかる所を見て行く所までは来ました。
PdfにArchiveする手前までは、細かい修正は必要にせよだいたい動いている印象。
ただ、大規模なデータを相手にすると意外な所で修正はいる事が多いので、この作業はしばらく続きそうです。
PdfのArchiveのあたりがつけば、最初の日本語版リリースの目処はつくかなぁ、と思っています。

読みが無い場合の話
karino2
現状は読みはDEFAULTSORTの値を使います。
無ければ「わわわ」という使わなさそうな所に突っ込んでいたのですが、このファイルが意外と多い。
多くなってくると
1. わ/, わ/わ/, わ/わ/わ/ と三回もmoveするのが馬鹿にならない
2. わ/わ/わ/ でsplitした後にフォルダに分けても大量にこのフォルダに残り、この後の空のフォルダを削除する、が遅い
と問題があっていまいちに思っています。2は実装を変えてDirectoryInfoを持っておけばEnumerateする必要が無いので早く出来そうですが。
splitしないで専用フォルダにするかなぁ。
なお、DEFAULTSORTが無くてもWikiNameがそもそもカタカナやひらがなの場合はそれを使えばいいはずです。
また、Wikipedia:やCategory:、Template:などは「ういきへていあ」、「かてこり」、「てんふれいと」などに分けてしまえば、結構な数をこの辺に分散出来る気はします。
Wikipedia, Category, Templateはこの手の専用な物以外にもこの単語を使う物が多そうなので、少し違う名前にしたい気はする。
特別とかスペシャルとかをつけようかしら?スペシャルが良さそうな気がしてきたので「すへしやる」を先頭につけますか。
でもこの辺のファイルが多かった場合、かなり深いフォルダまでコピーを繰り返す事になるので無駄かもしれない。
しかもこの辺はそもそもあまり見ないという話もある。あまり参照しないスペシャルなフォルダに突っ込んで、あまりトラバース等はしない、という手はある。
やはりこの手の考察の為には、手軽にWikipediaのWikiNameの分布を調査出来る必要がありますなぁ。
WikiNameをSQL Serverに突っ込むかなぁ。
(追記)
Category: 割と膨大だった。中もつまらないし、スキップでいいかなぁ。
Template: 膨大だが中は価値が無いので要らないかなぁ。
Portal:はそこそこあるが、中には意味がありそうなので必要かなぁ。
Wikipedia:膨大だが有用なのも多い。削除依頼が多いがこれは同じフォルダになってしまうのでスキップでいいかなぁ。
  削除依頼はちょっと面白いという話もあるが。漢字ではじまるものもそれなりに多いがこの位は我慢か。
  削除依頼さえスキップすれば後は頑張れそうな気はする。
389364-503128ファイルが漢字から始まるWikiNameで読み無し。1万2千ってところか。これが同じ所に行くのは仕方ないかな。
これを目視で探すのは無理かなぁ。一ファイル16WikiNameに変更しても約1000ページネーション。
EZ-Readerが一回ページをめくるのに1秒かかるとすると最後まで行くのに1000秒。20分くらいページ送りボタン押さないといけない。
IMEの逆変換にかけてもいいが… 
ちなみに「pdf/わ/わ/わ/」に入るファイルは50万あった。jawiki全部で70万だった気がするが、これは多すぎじゃないか?
70万にスペシャルファイルは入ってないのかもしれない。
ちなみに#redirectというのがあるんだね。小文字は見てなかったなぁ。
序盤で
'''XXX''' (よみ)
の形で出てくる物の括弧内が読みなんだが、これはDEFAULTSORTと違って本当の読みなので「げ」とか「ゅ」とかが混ざってノーマライズがいるのと、
・とか変な記号が入る。
序盤っていうのも曖昧で難しい。先頭から読んで最初にあったこのフォーマットでいいかもしれないが。
こういうフォーマットもあるのかぁ。
'''耕耘機'''(こううんき、耕うん機、ティラー、英: ''Rotary tiller'' )
読みじゃない場合もあった…
'''03式空挺歩兵戦闘車'''(ZBD-03?兵??・ZBD-03)
これは捨ててもいいか。
Category:が読みになってる物も多いが、そうとは限らないんだよなぁ。
Categoryはトリッキーなので読みじゃないのも結構ある。
[[Category:日本の大学別人名一覧|おうてもんかくいん]]というのが通常の場合。
[[Category:島根県|*ほおたる]]が読みと関係ない場合。
区別はつかなさげ。
Categoryはcategoryの場合もあり。
やはりCategoryは紛れが多いな。
順番的には
1. '''なんか''' (よみ)のパターン
2. DEFAULTSORT
3. WikiName
で、この三つがダメなら読み無しと扱う方がマシな気はする。
Portal:は読みが無いが仕方ない。
これで1万程度まで減らせられそうな気はしてきた。

どの位時間がかかるか?
karino2
現在の一フォルダに全部展開する方法だと、ファイルにデコードするのに3日ほどかかりました。
ファイルをフォルダに分割していくのに現在24時間くらい経っていますがまだ終わっていません。
途中exceptionで止まっているのをedit and continueで直したりしているのでかなり誤差のある時間ですが、だいたい2日くらいで終わりそうです。
最後のpdfのarchiveはどの位かかる事か…
小さいデータセットだとほとんど全ての時間がデコードにかかっていたのですが、ファイル数が増えるとこれまでたいした事無かった要素が重くなってくるようで。
現状はとりあえず全データを通してみて動かない部分を直す事を優先しているのですが、この作業時間はさすがにちょっと開発に支障があるので、なんとかしないといけなさそうです。

パラメータの考察
karino2
現在、10 WikiName 1pdfにしてますが、この10という値に大した意味はありません。これをArchiveNumと呼びましょう。
また、フォルダの分割をするかどうかの閾値は100としています。この閾値の100をFileNumUpperLimitと呼ぶ事にします。
100なのは、100ファイルなら10ファイル1pdfとすると10pdfファイルくらいなので、電子ブックリーダで簡単に選べると思ったからです。
上記の値はどうも問題がある気がするので、少し考えてみたいと思います。
まず、FileNumUpperLimit。100ファイル以上だと分割する、という場合。
一回の分割で「0,a,あ,か,...,わ」で12個に分かれます。
例えば100ファイルの場合、分割後に均等に移動するとすると8ファイル程度になってしまいます。
最大では99ファイル、最小で8ファイルとすると、大雑把に考えると平均は45くらいになってしまい、目標の100よりも大分少ない値となっています。
平均を100にするなら、閾値は200くらいの方がいいかもしれません。
200ファイルをpdfにすると20ファイル。EZ-Readerは一画面で8ファイル選べるので、最大で2回ページを繰らないといけないけれど、それは一応めったに無い値です。
2回なら妥協範囲かもしれません。
次にArchiveNum、つまり10ファイル1pdfの10。これはまったく意味がありません。
EZ-Readerは基本的に1-8までのキーがファイル選択、0と9でページネーションなので、8の倍数であるべきです。
少し使ってみた所、ファイルを変更するよりファイル内で動く方が快適なので、一ファイルにはそれなりの数をまとめた方が良いかもしれません。
一ページネーションとするなら16ファイル。4ページくらいまでいけるなら32ファイルでもいいかもしれません。
次にフォルダ分割のタイミング。
現状は全てのファイルを一フォルダに展開した後に分割をしていますが、これではファイル数が多くなると非常に効率が落ちてしまうようです。
何ファイルかを確認するのも出来ない状態なので概算をしてみると、日本のWikipediaは70万ファイルくらいらしいです。
デバッガでちょこちょこ止めながら観察していると、12分割した後でもまだファイルが多すぎで、12分割を二回したあたりからそれなりな速度で動いているようです。
この辺の計測もしていこうとは思いますが、とりあえず今分かっている物で推測をしてみますと、5000~6万の間に遅くなる閾値があるようです。
とりあえず5000ファイルあたりに到達したらdecodeをやめて分割をする、という感じだとどうでしょう?
この5000というフォルダ分割開始の閾値をStartSplitLimitと呼びましょう。
一回の分割で全てのフォルダをトラバースするので、そのコストがかかります。
ファイル移動の回数はまとめてやっても細かくやっても変わらないのでオーバーヘッドはトラバースの物。
一回のトラバースはどのくらいのフォルダを回るのでしょうか?
70万を12で割っていくと4回で34くらいになるので、最悪で12の4乗くらいのフォルダがある事になります。
だいたい2万フォルダ。でもオーダー的には12の三乗の方が近くて、こっちは2000くらい。
まぁこの位ならすぐ終わる、、、かなぁ。
数分で収まるならStartSplitLimitは5000でいいと思いますが、数時間かかるならStartSplitLimitを2万とかにした方がいいかもしれません。
とりあえず以上の閾値をリソース化するのと、上記仮説を確かめられるような値を計測したい所。

フォルダ分けのルール
karino2
1フォルダが100ファイルを越えていたら、以下のようなルールでフォルダ分割します。
1. 「0,a,あ,か,さ,....,ら,わ」の12個のフォルダを作る
2. 先頭から一文字づつ、以下のルールでフォルダに移す
  [0-9] -> 0
  [a-zA-Z] -> a
  [あ-お] -> あ
  [か-こ] -> か
  ...
3. 「0,a,あ,...,わ」の各フォルダのうち、空のフォルダを削除
4. 1フォルダのファイルが100以下になるまで再帰的にフォルダをほっていく
例として、日本(読みは「にほん」とする)を三フォルダまで分割した時のパスの図を描いておきます。
日本のWikiNameを探すには、「pdf/な/は/わ/」 か、その途中にあるはずという事です。

From Drop Box


現在Wikiマークアップは解釈しません。epub版はhtmlに直しますがpdfは生データのまま。
読み仮名はDEFAULTSEARCHの値を使います(変更を検討中)。
小さいデータでうまくいったので現在jawikiの実データで試しています。
以下のような問題に遭遇中。
1. 一フォルダあたりのファイル数が多くなりすぎてファイル開くだけで凄い時間がかかる状態になってしまった(ので処理が凄い時間がかかる)
2. "TBS系ドラマ「花嫁は厄年ッ!」Original Soundtrack"でパス名が長くなりすぎる
3. DEFAULTSORTに「*,:,/」などパス禁止名がある(これらのファイルはスキップしてしまう)