nDiki : trie

[ WiKicker ] 複数のキーワード集合による、AutomaticLink

WiKicker の Wiki間連携の強化(および開発中の DiKicker との相互連携)のために、 AutomaticLink を実現しているtrieによるキーワード抽出クラスを拡張する。

本来は一つの trie に属性付きでキーワードを登録して lookup するのがよいのだろうが、

• キーワード集合に優先順位をつけたい (最長でなくても、キーワード集合の優先度の高い方に含まれるキーワードを優先して使用する)。
• 既存の(単独集合用の)クラスも性能低下させずに維持したい

ということでもっと簡単に実装。 単純に複数の trie を作って、それぞれ順番にキーワード抽出(2番目以降は先のキーワード抽出でマッチしなかった部分文字列に対して適用)するというようにした。 キーワード集合が増えるとどんどん遅くなるが、2つぐらいだったら耐えられるかな。

抽出した語のリンク先

通常の AutomaticLink はその WikiForum 内のページにリンクされるのだが、例えば他のWikiForum の WikiName 集合を第2キーワード集合とした場合はその WikiForum 内のページURIに resolve する必要がある。

WiKicker の設定ファイルでどうやって指定するようにするかな。 InterWikiDefinition で定義してある InterWiki にマップするのも手だな。

さらに一歩すすめて、 WRI (WiKicker Resource Identifier) に写像してしまえば InterWiki だけでなく、いろいろ活用の幅が広がるかもしれない。

[ WiKicker ] 自動InterWiki

一昨日実装した、 複数のキーワード集合による、AutomaticLinkモジュールを WiKicker CGI プログラムから使えるようにしてみた。

ローカルにおいておいたキーワードリストファイルを読み込み AutomaticLink 処理(WikiForum 内で AutomaticLink でマッチしていない部分文字列に対して)。 マッチした場合は InterWiki を使ってURIに変換しリンク化する。

あわせてIndexPage.txtでWiKicker WikiForum 内の PageName を取得できるようにした。

これで例えば、2つの WiKicker WikiForum が cron で互いの IndexPage.txt を定期的に取得し、AutomaticLink するようにすれば、相補的に連携する事ができるようになる(ただし AutomaticLink のみ。WikiName や BracketName は依然としてその WikiForum 内のみ)。

AutomaticLink でのリンク先は(指定した)任意の InterWiki で定義できるので、あるキーワード集合について Google の検索結果ページや「はてなダイアリーキーワード」への自動リンクも実現可能(はてなダイアリーキーワード自動リンクAPIはキーワードリストではなく正規表現を返してくるので、元に戻す必要有り。またあれだけ巨大なキーワードリストだと毎回 AutomaticLink のために、trie 再生成するのも辛いのでもう一工夫必要)。

過去の今ごろ

過去の6月16日より。

• trie を手直し
  • trie の実装部分は去年の7月に完成して以来、手をいれてないな。もうちょい性能があがらないか、トライしてみるか。

WiKicker / DiKicker の AutomaticLink 長を可変にした

「が」や「は」など頻出する文字の WikiPage を作ってしまった場合、それらに対して自動リンクが働いてしまうと大変なことになるので、WiKicker では2文字以上のみ対象とするようにしていた。

しかし nDiki を書いていて、1文字のキーワードも自動リンクしたいという風に思えてきていた。 誰でも書ける Wiki の場合には危険で制約が必要だけれど、全てのキーワードが著者のコントロール化にある DiKicker では1文字のキーワードに対して自動リンクが働いても問題ないだろう。

ということで自動リンクが働く最低文字列長をプロパティで設定できるようにした。 2004年ぐらいからほとんど手をつけていなかった、AutomaticLink 処理モジュールを久しぶりにメンテナンス。 もともと2文字以上を前提でコーディングしてあったので、trie 部分などが1文字できちんと動くか確認した上で、文字列長チェックを可変に修正。 WiKicker、DiKicker 両方で設定で変えられるようにした。

またあわせて、英単語の部分文字列に対して自動リンクしないようにする処理も改善。 今までは `downloaded' に対して `loaded' はマッチしないようにしていたものの、'download' はマッチしてしまっていた。 このあたりを改善。

今日のさえずり: 要は ε 遷移があるかないかですよ

2011年07月06日

• 08:44 Android の連絡先(Contacts)の auto aggregation は「名前」「電話番号」「メールアドレス」でマッチング。 http://bit.ly/n57wYi
• 08:52 初 Huddle。
• 09:00 妻と最初に観た映画は「ラスト・オブ・モヒカン」。モヒカンって……。
• 11:59 RT @mixi_engineers: mixi Engineers' Blogエントリ追加しました → mixi Hackathon in Kyotoのご報告 http://alpha.mixi.co.jp/blog/?p=3427
• 12:08 弁当と夕方用のパン 514円。 (@ ローソン渋谷東一丁目店) http://4sq.com/q9s3Mp
• 15:10 「○○さんウンコなんですよ」って、すごい紹介。
• 15:28 略称は魔開になりました。
• 17:43 ピンクのメーテル T シャツ着て Shibuya Perl Mongersテクニカルトーク#16 顔出します。 #shibuyapm
• 17:48 #shibuyapm Shibuya PerlMongersテクニカルトーク#16 リスト (ATND あたりから) http://bit.ly/r0r1ht
• 17:52 @britty それ冬服ですから!
• 18:14 RT @mixi_engineers: 本日は18:30から、Shibuya Perl Mongersテクニカルトーク#16を弊社7Fセミナールームで開催します → http://shibuya.pm.org/.../201107.html
• 18:14 RT @mixi_engineers: テクニカルトークの様子はustでも中継いたしますので、ATNDに漏れたかた、お仕事中のかた、お茶の間からご覧になりたいみなさま、ぜひどうぞ! http://www.ustream.tv/...
• 18:47 #shibuyapm スタート!
• 18:52 ゴメンなさい、最近のアニメよくわかんないです。 #shibuyapm
• 19:03 昔愚直に自分で trie モジュール作ってた。 #shibuyapm
• 19:08 e の数で挙動が変わるのは知らなかった。何か m4 思い出す。 #shibuyapm
• 19:08 RT @nipotan: 無駄に @Yappo のハードルがあげられててうける #shibuyapm
• 19:10 RT @__gfx__: perl -ce 'http://mixi.jp' # syntax ok っていうネタがあったね。 #shibuyapm
• 19:20 Emacs での正規表現はちょっと毛嫌い。 #shibuyapm
• 19:56 正規表現じゃなくて正則表現といえば OK。 #shibuyapm
• 20:03 困ったら状態遷移図書くよね。 #shibuyapm
• 20:24 やはり DFA とか NFA とかでてくるとワクワクしますね。 #shibuyapm
• 20:39 Plagger って最近下火なのかな。 #shibuyapm
• 20:41 今日初の TL 流し。 #shibuyapm
• 20:50 JSON で終わりそう。 #shibuyapm
• 22:34 #shibuyapm 懇親会おひらき。Twitter でお見かけしていた方と初めて直接お話させていただけたりしてなかなか楽しかった!
• 22:36 @makotokaga 今日はお会いできて楽しかったです。これからもよろしくお願いいたします。
• 22:39 @shamoshamo 今日は VBA の話とか楽しかったです。これからもよろしくお願いいたします。
• 22:45 @shamoshamo このアイコン知ってます知ってますってパターンはお互いよくあるので、最近ぶらさげるようにしてまーす。
• 23:27 会社出た。そういえば食いっぱぐれてる。
• 23:29 要は ε 遷移があるかないかですよ。
• 23:31 渋谷駅雨降ってきた。
• 24:06 RT @k12u: めずらしく書いた / Test::mysqld + perl -d を使うと SQLがそのまま叩けて便利 - k12uのアレ http://htn.to/L6sKf1
• 24:31 RT @riywo: やーmixiさんのオフィスすごいよかった。広いセミナールームの隣に広い懇親会場とか素敵。
• 24:37 ローソンのそうめん食べた。ほぐし水が井戸水だった。
• 24:47 それぞれ mixi やってるので非公開コミュニティ作ってやりとりしようとしたけど、マイミクシィどうしじゃなかったので mixi 内で出会えず断念したというケースがあったという話をうかがった。まだまだサポートの余地がある。