この記事は、Competitive Programming (1) Advent Calendar 2018 - Adventarの19日目の記事です。
昨年は(前編)とタイトルを付けましたが、残念ながら今年は力尽きたので続編ではありません。
読んでも競技プログラミングの腕は上がりませんので、ご注意ください。
ちなみに昨年分・一昨年分はこちらです。
- Advent Calendar 2016 : ABC#001のA問題をコンパクトに解く - kmjp's blog
- Advent Calendar 2017 : CPHBを少しだけ和訳してみた(前編) - kmjp's blog
はじめに
今回のAdvent Calendarでもいくつか記事がある通り、コンテスト後ブログを書く人が増えてきて喜ばしい限りである。
ブログを書いているとしばしばイラっと来ることがある。それは競技プログラミング関連用語の漢字変換。
例えば以下の単語は皆さんの環境で一発で漢字変換できるだろうか？うちはできない。
ほうじょげんり → 幇助原理 とつほう → 凸方 きょうれんけつせいぶんぶんかい → 今日連結成分分解
快適なブログ記事作成環境を保つために、対策として競技プログラミング用の辞書を作ることを考えてみる。
辞書を広く公開して皆でメンテナンスしてもよいのだが、辞書の目的を以下の２つとおくと、前者はともかく後者は自前で管理した方が効果が大きい。
- 競技プログラミング固有の単語の漢字変換の精度改善
- 略称を登録しておくことで、記事作成におけるキータイプ数削減
辞書を作成するとき、単語をどう選べばいいだろうか。労力に対し効果を最大化したいと考えたら、当然登場頻度が高いものから作っていくのがよい。
よって、以下ブログの単語の登場頻度を数えてみることにする。
本文の取得
まずは本文を取得しよう。このブログははてなブログ上で書いているし、文字の装飾など最小限の方がよいので以下のツールを利用した。
はてなブログ用ツール - Works/Tools - 総武ソフトウェア推進所
まずはてなブログ形式で出力する。
DumpAllEntries.exe -id kmjp -blogid kmjp.hatenablog.jp -apikey (apikey) -format hatena hatena.txt
出力ファイルはXML形式である。日付ごとにbodyタグが設定されはてなブログ形式でタイトル・本文が記述されるので、bodyタグの中身を抽出していけば本文が得られる。
<?xml version="1.0" encoding="UTF-8"?> <diary> <day date="2018-12-16" title=""> <body>*1544922000*[SRM]TopCoder SRM 744 Div1 Hard CoverTreePaths これはもうちょっと考えていくべきだった…。 https://community.topcoder.com/stat?c=problem_statement&pm=14587 *問題 根付き木が与えられる。 （略） </body> </day> </diary>
あとは以下の通り若干整形して使うことにした。
- タイトル行は削除
- コード部分は削除
- 句点で文単位に分割、数式のある文は削除
単語の分割
行・文単位までは分割できたので、ここから単語単位に分割する。
良くある単語分割のアプローチにはN-gramと形態素解析がある。(形態素解析向けの)よい辞書さえあれば形態素解析の方が精度よく単語単位で分割できる。幸い、形態素解析用の高精度な辞書はNEologdが競技プログラミング向けの単語も含んでいるのでこちらを使おう。
Pythonで形態素解析を行うため、形態素解析エンジンとしてMeCab、追加辞書として上記NEologdを導入することにする。これらはWindows+Cygwin, CentOS, Ubuntu, Mac OSいずれの環境でも可能である。幸い、昨今のAIブーム・自然言語解析ブームのおかげか、巷に記事も豊富に存在するためここでは導入方法の説明は省略する。
実際UbuntuにMeCab+NEologdを導入し、競技プログラミング系の単語が解析可能か確認してみた。mecabコマンドは入力文に対し、形態素解析後の品詞などを返してくれる。
- 凸包・包除原理が固有名詞として認識されている。あいにく強連結成分分解は一般的な複数の単語に分割されてしまった。
- AtCoder、SRM、Codeforcesあたりが固有名詞判定された。英単語も割と行けるようだ。
$ mecab -d /usr/lib/x86_64-linux-gnu/mecab/dic/mecab-ipadic-neologd/ 凸包を包除原理で強連結成分分解した 凸包 名詞,固有名詞,一般,*,*,*,凸包,トツホウ,トツホー を 助詞,格助詞,一般,*,*,*,を,ヲ,ヲ 包除原理 名詞,固有名詞,一般,*,*,*,包除原理,ホウジョゲンリ,ホウジョゲンリ で 助詞,格助詞,一般,*,*,*,で,デ,デ 強 形容詞,自立,*,*,形容詞・アウオ段,ガル接続,強い,ツヨ,ツヨ 連結 名詞,サ変接続,*,*,*,*,連結,レンケツ,レンケツ 成分 名詞,一般,*,*,*,*,成分,セイブン,セイブン 分解 名詞,サ変接続,*,*,*,*,分解,ブンカイ,ブンカイ し 動詞,自立,*,*,サ変・スル,連用形,する,シ,シ た 助動詞,*,*,*,特殊・タ,基本形,た,タ,タ AtCoderでSRMにCodeforcesした AtCoder 名詞,固有名詞,一般,*,*,*,AtCoder,アットコーダー,アットコーダー で 助詞,格助詞,一般,*,*,*,で,デ,デ SRM 名詞,固有名詞,一般,*,*,*,SRM,エスアールエム,エスアールエム に 助詞,格助詞,一般,*,*,*,に,ニ,ニ Codeforces 名詞,固有名詞,一般,*,*,*,Codeforces,コードフォーシズ,コードフォーシズ し 動詞,自立,*,*,サ変・スル,連用形,する,シ,シ た 助動詞,*,*,*,特殊・タ,基本形,た,タ,タ
余談だが、"mecab neologd python"あたりのキーワードで検索して見つかるサイトのほとんどは、「環境構築→ちょっと試す→終わり」というものが多い。というのもしょうがない話で、通常形態素解析してみたい文章を個人で大量に手に入れるのが難しい。だが、今回の場合これまでしっかりとブログ記事を書き溜めていれば、わずか数MB程度とはいえ自分だけのデータセットがあるはずだ。
結果
「こと」「これ」などあまり意味のない単語や、1文字の英数字などを除いて名詞を集計し、登場頻度の多い順に並べてみた。1位は…
頂点 4597
「頂点」でした。頂点って単語を4600回近くも入力するの、学校の数学の先生でもそうそうないんじゃないかね。
毎日頂点をいじくり倒しそうな、グラフ理論とかの研究者や3DCG/CADの技術者ぐらい？
他に上位に並んだのは以下の単語だった（上位50個から、「これ」「こと」みたいな意味の薄い単語を削ったもの）。
タイトルを除いているので、Codeforces・SRM・AtCoder等の単語は上位には入らない。
頂点 4597 整数 1552 コスト 1038 要素 2664 クエリ 1385 連結 1024 最大 2581 条件 1371 本番 1014 処理 2328 グラフ 1194 Div 957 マス 2002 位置 1181 時間 922 移動 2000 座標 1176 総和 916 文字列 1976 DP 1153 セル 912 最小 1945 数列 1089 距離 904 文字 1753 部分 1080 組み合わせ 877 状態 1641 計算 1060 回数 811
- 頻度の高いアルゴリズム・データ構造名。BITとかはbitと混同するので除外している。
SegTree 261 Grundy 68 トポロジカルソート 46 マッチング 149 最大公約数 63 ダイクストラ法 36 Union 134 ダブリング 59 SuffixArray 26 素因数分解 81 最小全域木 49 FFT 26 包除原理 71 ダイクストラ 48 SAT 23
- 逆に頻度の低いアルゴリズム・データ構造名。もっと出てきてもよさそうな気がするものもある。
最大フロー最小カット定理 2 平方剰余の相互法則 1 ラグランジュ 2 完全数 1 モンテカルロ法 2 ラングトンのアリ 1 メビウス変換 2 モンゴメリ乗算 1 マクローリン展開 2 メビウス関数 1 ケイリーの公式 2 マンハッタン 1 オイラーのトーシェント関数 2 ボロノイ 1 行列の平方根 1 フロベニウス 1 最大クリーク問題 1 パップス・ギュルダン 1 排他的論理和 1 ディオファントス方程式 1 平衡二分探索木 1 ゴールドバッハの予想 1
- なんでこんな単語こんな頻度で打ったんだろうシリーズ。
モンスター 125 カンガルー 9 ギアッチョ 1 びっくり 37 ウナギ 7 コナミゲー 1 たこ焼き 32 魔法少女 4 アクトレイザー 1 ピラミッド 24 湯たんぽ 2 トルクメニスタン 1 アイドル 22 麻雀大会 1 ookayama 1
- ひどい誤字。でも思ったほど見つからなかった（概ね形態素解析に失敗するため）
びちじみの 1 → 「伸び縮み」を何度も間違えたため変なところで切れたと思われる びちじみする 1 びちじみさせる 1 びちじみさせつつ 1 マンタッハン 1 → マンハッタン サブプラミッド 1 → サブピラミッドと書きたかったらしい
コード
参考までにコードを置いておきます。
github.com
まとめ
こんなことやってますが、まだ辞書は作成していないので、書く速度は向上していません。
明日はskyaozoraさんとei1333さんの記事です。どちらもどんな記事を書いてくるかわかりませんね…。
