kmjp's blog

競技プログラミング参加記です

Advent Calendar 2018 : ブログを書く速度を少しだけ上げる

この記事は、Competitive Programming (1) Advent Calendar 2018 - Adventarの19日目の記事です。
昨年は(前編)とタイトルを付けましたが、残念ながら今年は力尽きたので続編ではありません。
読んでも競技プログラミングの腕は上がりませんので、ご注意ください。

ちなみに昨年分・一昨年分はこちらです。

はじめに

今回のAdvent Calendarでもいくつか記事がある通り、コンテスト後ブログを書く人が増えてきて喜ばしい限りである。

ブログを書いているとしばしばイラっと来ることがある。それは競技プログラミング関連用語の漢字変換。
例えば以下の単語は皆さんの環境で一発で漢字変換できるだろうか?うちはできない。

ほうじょげんり → 幇助原理
とつほう → 凸方
きょうれんけつせいぶんぶんかい → 今日連結成分分解

快適なブログ記事作成環境を保つために、対策として競技プログラミング用の辞書を作ることを考えてみる。
辞書を広く公開して皆でメンテナンスしてもよいのだが、辞書の目的を以下の2つとおくと、前者はともかく後者は自前で管理した方が効果が大きい。

  • 競技プログラミング固有の単語の漢字変換の精度改善
  • 略称を登録しておくことで、記事作成におけるキータイプ数削減

辞書を作成するとき、単語をどう選べばいいだろうか。労力に対し効果を最大化したいと考えたら、当然登場頻度が高いものから作っていくのがよい。
よって、以下ブログの単語の登場頻度を数えてみることにする。

本文の取得

まずは本文を取得しよう。このブログははてなブログ上で書いているし、文字の装飾など最小限の方がよいので以下のツールを利用した。
はてなブログ用ツール - 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&amp;pm=14587


*問題

根付き木が与えられる。
(略)
</body>
  </day>
</diary>

あとは以下の通り若干整形して使うことにした。

  • タイトル行は削除
  • コード部分は削除
  • 句点で文単位に分割、数式のある文は削除

単語の分割

行・文単位までは分割できたので、ここから単語単位に分割する。
良くある単語分割のアプローチにはN-gram形態素解析がある。(形態素解析向けの)よい辞書さえあれば形態素解析の方が精度よく単語単位で分割できる。幸い、形態素解析用の高精度な辞書はNEologd競技プログラミング向けの単語も含んでいるのでこちらを使おう。

Python形態素解析を行うため、形態素解析エンジンとしてMeCab、追加辞書として上記NEologdを導入することにする。これらはWindows+Cygwin, CentOS, Ubuntu, Mac OSいずれの環境でも可能である。幸い、昨今のAIブーム・自然言語解析ブームのおかげか、巷に記事も豊富に存在するためここでは導入方法の説明は省略する。

実際UbuntuMeCab+NEologdを導入し、競技プログラミング系の単語が解析可能か確認してみた。mecabコマンドは入力文に対し、形態素解析後の品詞などを返してくれる。

  • 凸包・包除原理が固有名詞として認識されている。あいにく強連結成分分解は一般的な複数の単語に分割されてしまった。
  • AtCoderSRMCodeforcesあたりが固有名詞判定された。英単語も割と行けるようだ。
$ mecab -d /usr/lib/x86_64-linux-gnu/mecab/dic/mecab-ipadic-neologd/
凸包を包除原理で強連結成分分解した

凸包    名詞,固有名詞,一般,*,*,*,凸包,トツホウ,トツホー
を      助詞,格助詞,一般,*,*,*,を,ヲ,ヲ
包除原理        名詞,固有名詞,一般,*,*,*,包除原理,ホウジョゲンリ,ホウジョゲンリ
で      助詞,格助詞,一般,*,*,*,で,デ,デ
強      形容詞,自立,*,*,形容詞・アウオ段,ガル接続,強い,ツヨ,ツヨ
連結    名詞,サ変接続,*,*,*,*,連結,レンケツ,レンケツ
成分    名詞,一般,*,*,*,*,成分,セイブン,セイブン
分解    名詞,サ変接続,*,*,*,*,分解,ブンカイ,ブンカイ
し      動詞,自立,*,*,サ変・スル,連用形,する,シ,シ
た      助動詞,*,*,*,特殊・タ,基本形,た,タ,タ

AtCoderSRMCodeforcesした

AtCoder 名詞,固有名詞,一般,*,*,*,AtCoder,アットコーダー,アットコーダー
で      助詞,格助詞,一般,*,*,*,で,デ,デ
SRM     名詞,固有名詞,一般,*,*,*,SRM,エスアールエム,エスアールエム
に      助詞,格助詞,一般,*,*,*,に,ニ,ニ
Codeforces      名詞,固有名詞,一般,*,*,*,Codeforces,コードフォーシズ,コードフォーシズ
し      動詞,自立,*,*,サ変・スル,連用形,する,シ,シ
た      助動詞,*,*,*,特殊・タ,基本形,た,タ,タ

余談だが、"mecab neologd python"あたりのキーワードで検索して見つかるサイトのほとんどは、「環境構築→ちょっと試す→終わり」というものが多い。というのもしょうがない話で、通常形態素解析してみたい文章を個人で大量に手に入れるのが難しい。だが、今回の場合これまでしっかりとブログ記事を書き溜めていれば、わずか数MB程度とはいえ自分だけのデータセットがあるはずだ。

結果

「こと」「これ」などあまり意味のない単語や、1文字の英数字などを除いて名詞を集計し、登場頻度の多い順に並べてみた。1位は…

頂点 4597

「頂点」でした。頂点って単語を4600回近くも入力するの、学校の数学の先生でもそうそうないんじゃないかね。
毎日頂点をいじくり倒しそうな、グラフ理論とかの研究者や3DCG/CADの技術者ぐらい?

他に上位に並んだのは以下の単語だった(上位50個から、「これ」「こと」みたいな意味の薄い単語を削ったもの)。
タイトルを除いているので、CodeforcesSRMAtCoder等の単語は上位には入らない。

頂点 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さんの記事です。どちらもどんな記事を書いてくるかわかりませんね…。