nDiki : AutomaticLink

AutomaticLink (自動リンク)

WikiPage 中に既存のページ名が出現した場合に、(WikiName や BracketName でなくても)自動的にそのページへのリンクにする機能。

自動リンク規則

WiKicker では次の規則によりページ名を抽出する:

テキスト中から非最左最長一致する既存ページ名を自動的にリンクにする。
- ページ名がテキスト中にオーバーラップして出現した場合は長い方を優先する。
同じ長さのページ名が複数出現している場合は、先に現われた方を優先的にリンクにする。
1文字以上あけずにページ名が連続して出現した場合は、片方は自動的にリンクにしない。
'/' で区切られたページ名は('/' で区切られた単位で)接尾辞がマッチすれば自動的にリンクになる。ただし複数のページ名がマッチする場合は自動的にリンクにしない。'/'を含まないページ名があれば、そちらを優先する。

自動リンク規則

英単語の一部だけの場合は自動リンクしない。
除外リストにある文字列は自動リンクしない。
数字で終わるページ名をAutomaticLinkすると、連続する数字列が分断される場合は自動リンクしない。

サーバ負荷状態による AutomaticLink の無効化

サーバの負荷が高い時はレスポンスの低下を避けるため自動的に AutomaticLink が無効化されるように設定する事が可能(WiKicker 0.17 より)。 NaneyOrgWiki では load average が 3 を越えている場合は AutomaticLink が一時的に無効化される。

AutomaticLink の他のプログラムでの利用 (experimental)

WiKicker で運用されている WikiForum への AutomaticLink を他のCGIプログラムなどで行う事が可能。

Naney's Diary (hns) と現在連携中。 hns の記事中に、存在するPageName があると自動的に WikiPage へのリンクになる (load average 3未満で有効)

外部ページリストの利用

WiKicker 0.22 より、指定したキーワードファイルに含まれている文字列を、AutomaticLink に使用できるようになる予定。この文字列がページ中に現れた場合は指定したInterWiki でURIに変換してリンク化される。

WiKicker/AutomaticInterWiki

スポンサードリンク

実装

「文字列から、辞書中に含まれる語を非最左最長一致のものから順に、各語が重ならないように検索する」のに最適なアルゴリズムを検討する。特に Wiki に適した時間・空間効率のものを。

文字列: WikiPage 中の各テキスト。途中WikiNameがあった場合は、そこで分割されているので比較的短い。
辞書: PageName の集合 (数百～数万語を想定)
語: PageName (あるいはそれに準ずるもの)

現在の実装

変形trieを利用してページ名の集合を受理するオートマトンを構築
後方一致でAutomaticLinkできるようにページ名をreverseしたものを受理する文字列とする
最初の1文字毎に別のオートマトンを構築する
AutomaticLinkマークアップ時、最初の遷移文字に対するオートマトンがまだ未構築であればその時点で構築する(遅延構築)
対象テキストの全文字を開始文字としてAutomaticLink可能な文字列を取得。その中から最長のものを順に選択する

辞書はtrieが定番だと思うんですが、trie 構築・管理のコストと検索時間での係数を考えると、力技で各接頭辞をhash検索してもあまり変わらない感じもします。辞書中の語の最大長にもよりますが。

HierarchicalWikiPage への略記を自動的にリンクさせたりするために、trie を使うようにしました。現在はページ表示毎にページリストから trie を構築しているため、出力が遅くなってしまっています。近日中に trie はキャッシュするようにする予定。

trie を利用してのキーワード抽出自体はそれほど大きく処理時間に影響を与えていないようです。

現在は trie を遅延構築するようにし、AutomaticLink のための初期化処理時間を大幅に節約しています。

2004年2月9日 (月)

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

スポンサードリンク

[ permalink ]

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

[ 2月9日全て ]

2004年2月15日 (日)

■ [ WiKicker ] Memcachedのメモリ使用量

現在 NaneyOrgWiki には946のページあるのだがHTMLフラグメントをMemcachedにキャッシュさせて、メモリ使用量が 24MBぐらい(検索結果キャッシュも含まれる)。キャッシュの expires は2時間(AutomaticLinkが無効な時にキャッシュした場合は30分)。こんなものかな。現在 max 32MB で Memcached を起動しているけど、20MBぐらいにして積極的に古いのは削除させてもいいかもしれない。

[ permalink ]

[ WiKicker ] Memcached を使った検索結果のキャッシング (2004-01-15)
[ WiKicker ] 古くても検索キャッシュを返す (2004-01-20)
[ WiKicker ] キャッシュまわりにバグ (2004-06-05)
[ WiKicker ] プレビューをレンダリング中も逐次出力するように (2004-05-03)
DiKicker に grep 検索機能を追加 (2007-02-02)

[ 2月15日全て ]

2004年2月26日 (木)

■ [ DiKicker ] AutomaticLink・転置インデックス自動更新

日記の記事が追加・更新されると、キーワード集合(索引語集合)も変更される(ことがある)。当然過去の記事すべて再インデックス化する必要が出てくる。

このあたりをCGI プログラムの呼び出し毎にちょっとずつ更新していく処理を実装。

[ permalink ]

[ 2月26日全て ]

2004年3月3日 (水)

■ hnsのキャッシュを有効に

Naney's Diaryの方、NaneyOrgWiki からエクスポートしたページをインクルードしたり、AutomaticLink をしたりなどいろいろ動的処理をつけ加えてあるのでハイパー日記システムのキャッシュ機能をオフにしてあった。

しかし最近日に日にレスポンスが悪くなっている感じ。最新日記の公開はこのnDikiに移行したのにともない、Naney's Diary の方は過去ログ表示専用になるためキャッシュ有効に戻しておくことにした。

これでレスポンスがよくなるかな?

[ permalink ]

DiKicker に n 年日記機能を追加 (2006-11-03)
はいぱー日記システムで日記を開始 (2001-05-11)
私的10大ニュース2004 [ web ] (2004-12-31)
21:00 [ nDiki ] hnsからDiKickerへ (2004-02-22)
[ WiKicker ] Memcachedのメモリ使用量 (2004-02-15)

[ 3月3日全て ]

2004年5月3日 (月)

■ [ WiKicker ] プレビューをレンダリング中も逐次出力するように

WiKicker での編集プレビューが「HTMLフラグメントを生成し終わってから出力する」ようになっていたためサーバの負荷が高い時にかなり待たされてしまっていたので、これを修正。それからプレビューでも AutomaticLink を有効にしておいた。

その他HTMLフラグメントのキャッシュバグ(目次部分をキャッシュしていなかった)を修正。

[ permalink ]

[ WiKicker ] Memcachedのメモリ使用量 (2004-02-15)
[ DiKicker ] くっつき BBSをくっつけてみた。 (2004-05-04)
[ WiKicker ] WikiPage のHTMLレンダリング結果のキ... (2004-02-14)
[ WiKicker ] spam と検索エンジン対応に noindex、... (2007-01-13)
hnsのキャッシュを有効に (2004-03-03)

[ 5月3日全て ]

2004年6月20日 (日)

■ [ WiKicker ] NaneyOrgWiki でも AutomaticInterLink を使ってみる

処理時間が長くなるので NaneyOrgWiki では使っていなかった AutomaticInterLink を使ってみる。

通常の AutomaticLink と同様 Load Average が低い時のみ機能するように設定。
nDiki の term リストを対象に。

[ permalink ]

[ Perl ] Log::Log4perlのはまりどころ (2004-03-02)
[ WiKicker ] Memcachedのメモリ使用量 (2004-02-15)
mixiに登録 (2004-11-19)
hnsのキャッシュを有効に (2004-03-03)
www.naney.org サーバ断続的にダウン (2006-04-30)

[ 6月20日全て ]

2004年10月7日 (木)

■ 過去の今ごろ

過去の10月7日より。

負荷軽減のための改造
- AutomaticLink の自動無効化はかなり効果的に機能している様子。検索機能の強化がずっと先送りになっていたな。

[ permalink ]

[ WiKicker ] 自動InterWiki (2004-02-09)
[ WiKicker ] Memcachedのメモリ使用量 (2004-02-15)
WiKicker 0.420 リリース - 変更いろいろ (2007-05-30)
Spurl に登録してブックマークしてみる (2005-02-05)
飲めば飲むほど強くなる Spurl (2005-02-06)

[ 10月7日全て ]

2005年1月26日 (水)

■ DiKicker にそろそろコメント機能を実装するか

@ くっつき BBS

nDiki では、たつを氏が公開しているくっつき BBSを利用してコメント機能をつけている。くっつき BBSは自前でBBS機能を実装しなくても、JavaScript Include を使うことでコメントをページに貼りつけられるという優れもの。

@ CGI プログラム経由の JavaScript Include 方式は遅い/負荷がかかる

nDiki では JavaScript Include する際、コメントがない(=JavaScriptファイルがない)場合でも404にならないようにCGI プログラム経由で貼りつけていた。しかし、この方法だと1ページに多くのコメント領域があると何度もCGI プログラムが実行されるのでサーバへ負荷がかかる。

また Web ブラウザもHTMLの途中でscript要素が出てくると、そのスクリプトファイルを読み込んで処理するまで残りをレンダリングできない。このためサーバが重かったりして、途中スクリプトファイルの読み込みでひっかかるとユーザ側でのページ表示完了が遅くなってしまう。

ということでこの方式をやめて、単純にコメントJavaScriptファイルのURIを指定するようにした。その使わなくなったCGI プログラムで、tDiaryテーマ用の「commentshortクラスdiv要素」を書き出していたので、この部分は DiKicker に戻す。現在のコードでは、コメントが無くてもこのdiv要素が出力されてしまうので、ちょっとみぐるしいがしばらくご容赦。

@ やはりDiKickerでネイティブにコメント機能を実装しよう

コメント内の AutomaticLink 処理や cookie の連動など、前からやりたいとは思っていたのでこれを機会に実装するかな。いろいろ決めないといかん。

[ permalink ]

速度改善のため nDiki からくっつき BBS を外す (2005-10-16)
nDiki に「はてなスター」をつけてみた (2007-07-11)
[ DiKicker ] くっつき BBSをくっつけてみた。 (2004-05-04)
[ WiKicker ] 憧れのサイドバー (2004-01-23)
Plagger のインストールが大変なので XML::RSS で RSS ... (2006-06-10)

[ 1月26日全て ]

2007年3月1日 (木)

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

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

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

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

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

[ permalink ]

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

[ 3月1日全て ]

2007年5月30日 (水)

■ WiKicker 0.420 リリース - 変更いろいろ

去年の12月3日以来、約半年ぶりのリリース。リリースしそびれて、随分変更を累積してしまった。以下主な変更点。

@ バージョン番号形式を変更

前回の 0.41 に対して、今回は 0.420 とした。浮動小数点数的には、増分 0.01 で今まで通り。

今後 version.pm が普及した時のことと、developer release を出す時のことを考えて小数点以下3桁ずつのスタイルに移行することにした (関連記事)。

@ <meta name="robots" content="noindex,nofollow">

2007年1月に実装。編集ページや履歴ページが検索エンジンに登録されないようにするための機能。

@ <a rel="nofollow">

2007年1月に実装。リンク spam 対応。

@ AutomaticLink 長を可変にした

2007年3月に実装。特に DiKicker で1文字キーワードによる自動リンクを有効にするために追加した。

@ '/' の前を省略した自動リンクを有効にするか無効にするかを設定できるように

前述の機能で1文字での自動リンクを有効にしたら、不便な面が出た。

WiKicker / DiKicker では '/' を階層の区切り文字としても扱うことができるようになっていて、サフィックス部分だけでも自動リンクするようになっている。自動リンクを1文字にしたら「OS/2」というキーワードに対して '2' でも自動リンクが働き、望まないリンクが張られるようになってしまった。 DiKicker では階層的キーワードは無くてもあまり困らないので、'/' の前を省略した自動リンクを無効にできるようにした。