■[はてな][J] キーワード置換アルゴリズム

http://d.hatena.ne.jp/hatenadiary/20060119/1137667217

うわーこれはこまったね。いままでは長いキーワードから抜き出していってたけど、TRIE 構造を使って文の前方からマッチを探して行くから短いのが優先されたりする。たとえば

本文：あいうえおかきくけこさしすせそ
KW1     いう
KW2       うえおかき
KW3             かきく
KW4               きくけこさし

という文でKW1-KW4のキーワードがマッチする場合、新しくなった方法では「いう」と「かきく」が抽出される。マッチがあっても何文字か進む間保留しとくとかの方法で解決できるのかな。LZ圧縮とかも辞書にマッチするパターンを番号で置き換えるとかしてると思ったんで、標準的なアルゴリズム何かあるんじゃないかねぇ。

追記：LZ系は保留はしない模様。ふーむ。

とりあえず、n文字のマッチがあった場合、これを候補１として仮採用し、こいつの2文字目からn文字目までを基点として、もっと長いマッチがないか調べる。あった場合は候補１を捨てて最長のものを候補２として採用、かつ候補１と先頭が一致するもっと短いキーワード候補１’があって候補２とオーバーラップしてなかったらそれを採用、て感じでいけないかな。必要であれば候補２について同じ処理を再帰的に行うと。

いやーしかし絶対文献調査すれば誰かやってる話だろうな、これは。しっかり調査してヘナチョコ車輪の再発明しないようにたのんますよ＞はてな担当者

追記：うは社長にブクマされた http://b.hatena.ne.jp/entry/http://d.hatena.ne.jp/ita/20060119/p1

トラバいただきました: http://chasen.org/~taku/blog/archives/2006/01/autolink.html

なるほど、評価関数を設定して最適なのを選ぶんですね。キーワードのオーバーラップがすごく多かったりしたらナップサック問題っぽくなって死ぬかなとか思ったけど、それほど大変ではないようで。

追記：キーワード置換のAC法は Aho-Corasick法の略らしい。初め冗談かと思ってた。昔NetHackのコードとかいじった時、変数名とかバッティングしないように適当に aho_x とか付けてたけど（さすがに沼田さんに送った時は変数名を変えた）気を付けねば。

ツイートする

Permalink | コメント(0) | トラックバック(0)