nDiki : trie

AutomaticLink WiKicker 自動リンク InterWiki URI WikiName Wiki WikiForum 検索 DiKicker WikiPage PageName BracketName nDiki cron はてなダイアリー アルゴリズム WikiEngine hns 辞書 開発 キャッシュ Google NaneyOrgWiki CGI CafeWiki CGI プログラム IndexPage.txt PukiWiki HierarchicalWikiPage

■ [ 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 (2004-02-09)
• WiKicker / DiKicker の AutomaticLink 長... (2007-03-01)
• 私的10大ニュース2003 (2003-12-31)
• [ WiKicker ] 日記機能開発開始 (2003-12-27)
• WiKicker でソフトウェアかんばん (2007-03-01)

■ [ 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 再生成するのも辛いのでもう一工夫必要)。

• [ WiKicker ] 複数のキーワード集合による、AutomaticLink (2004-02-07)
• [ WiKicker ] 憧れのサイドバー (2004-01-23)
• Windows 上での Apache 2.0.53 では PATH_INF... (2005-04-10)
• はてなダイアリーキーワード自動リンクAPI (2004-02-05)
• [ WiKicker ] 「最近のアクセスログ」処理思案 (2004-01-17)

■ 過去の今ごろ

過去の6月16日より。

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

• [ WiKicker ] 自動InterWiki (2004-02-09)
• [ WiKicker ] 複数のキーワード集合による、AutomaticLink (2004-02-07)
• WiKicker / DiKicker の AutomaticLink 長... (2007-03-01)

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

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

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

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

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

• [ WiKicker ] 複数のキーワード集合による、AutomaticLink (2004-02-07)
• DiKicker に grep 検索機能を追加 (2007-02-02)
• WiKicker に Flickr 関連機能追加 (2005-02-11)
• WiKicker に JSON でのページ出力機能を追加 (2007-04-03)
• [ WiKicker ] 自動InterWiki (2004-02-09)