人力検索はてな
モバイル版を表示しています。PC版はこちら
i-mobile

はてなダイアリーのようにキーワードを自動でリンクするアルゴリズムを知りたいです。単純に考えると、?キーワードのリストを持っておく。?対象となる文章に、あるキーワードが含まれているかを検索する。?「?」の検索をキーワードの数だけ繰り返す。ということになると思います。1万語のキーワードリストがある場合、1万回の検索を行うことになり、たとえば多数の投稿がある場合は効率も悪いですし負荷も掛かります。もっと効率のいいアルゴリズムがあるのでしょうか。

●質問者: hitoshih
●カテゴリ:コンピュータ
✍キーワード:いるか はてなダイアリー アルゴリズム キーワード リスト
○ 状態 :終了
└ 回答数 : 4/4件

▽最新の回答へ

1 ● ys_y
●30ポイント

http://ew.hitachi-system.co.jp/w/E3838FE38383E382B7E383A5E6B395....

ハッシュ法というアルゴリズムを使うと運が悪くない限り1回の検索でひっかかります。

◎質問者からの返答

ありがとうございます。調べてハッシュ法の基本は理解しましたが、これをどのように使用するのかよく分かりません。

自分なりに調べてみましたが、力不足です。うーーん、難しいです。


2 ● sasada
●100ポイント

http://www.zdnet.co.jp/news/0307/08/nj00_kiss.html

競争力向上にITを活用するすべての企業へ - ZDNet Japan

URLは参考程度のダミーです。

Web上にいい文献が見つかりません・・・。

この種の文字列マッチングは、(最長一致のみで)バックトラックが発生しませんから、素直に有限オートマトンによるマッチングを行っていると見て良いでしょう。

PerlやRubyの正規表現の簡易版です。

キーワード群に対応する有限オートマトンを一定時間毎(又はキーワード登録時)に生成し、全文検索の際に用いることによって、検索コストを減らすことも出来ますし。

はてなダイアリーのように、対象となる文章より キーワードの方が総量が多い場合、キーワードの接頭/接尾語でハッシュを作ると、効率が上がるかもしれません。

(接頭/接尾語別にオートマトンを作っておく)

つまり100文字の文章と10,000語のキーワードを比べるなら、100文字分だけ検索するほうが早い理屈です。

この辺に興味をお持ちなら、文字列検索の専門書か、Perlの実装に関する本などを読んでみると面白いと思います。(集合論などの知識を要します)

◎質問者からの返答

む、難しいですねー。どうにか書いて頂いたことは理解しました。

いろいろ調べながら理解しましたが奥が深いですね。ちょっとした疑問だったのですが、俄然興味がわいてきました。


3 ● frain
●100ポイント

http://www.hatena.ne.jp/1069991612

はてなダイアリーのようにキーワードを自動でリンクするアルゴリズムを知りたいです。単純に考えると、?キーワードのリストを持っておく。?対象となる文章に、あるキーワ.. - 人力検索はてな

URLはダミーです。

実際にどのようなアルゴリズムが使われているかはわかりませんが、単純な文字列検索でも検索回数を減らすことは可能だと思います。

例えば、

1.キーワードのリストを持っておく

この際、キーワードの1文字目も一緒に持っておく。

2.対象となる文章から1文字とってきて、その文字で始まるキーワードと一致するか確認する。

3. 2.の検索を文章の文字数分繰り返す。

このような検索方法であれば、既にキーワードとして認識された部分を検索しないことができますし、文字によっては検索をスキップできる部分もあるでしょう。

上記で、1文字のキーワードは認めないということであれば、先頭2文字を使用することによって検索するキーワード数を減らしたりする等の改良も行えるでしょう。

見当違いの回答だったらごめんなさい。

◎質問者からの返答

ありがとうございます。キーワードを一つずつ検索していくのではなく、対象となる文章を細切れにして検索していくというのがまずベースの考え方ということですね。文字列検索とは工夫の重ね合わせ何ですね。だんだんと理解してきました。


4 ● hmori
●100ポイント

http://www.kyoritsu-pub.co.jp/shinkan/shin0201_02.html

共立出版株式会社 新刊・近刊2002年1月『情報検索アルゴリズム』

文字列検索関係の有名な本です。

難しいので・・・・

http://alfin.mine.utsunomiya-u.ac.jp/~niy/algo/r/regMatch.html

1万語までできるかどうか怪しいですが,正規表現のプログラムソースがあります。

基本的には、この入力に

キー1|キー2|キー3という形で入力して、文字列を渡すと検索します。

これをキー1毎に出力するには、多少はソースを変更する必要があります.

www.google.com などで、文字列照合 DFA をキーにして探してみてください。

http://www.namazu.org/

Namazu: a Full-Text Search Engine

有名な全文検索エンジンです。

この方法は全く逆で、日本語を入力して、形態素分析という方法で文節に区切り、これをデーターベースに入れます。

検索時は、このデーターベースから検索します。

この方法では、形態素分析の制度が操作性を決めます。

もう1つ文節の区切りを気にしない方法として、Nグラム というアルゴリズムがあります。

http://www.ftsanet.com/dbtokyo99/3-2.pdf

FTSANET.COM

ま、使う用途によって、これ以外の方法もありますが。

上は、DFA を使った物は、キーが固定で、カスタマイズを思い切りしたい時に使う。

形態分析は、キーワードが予想できない時に使う。ヒットすると早い。

Nグラムは、時間がかかっても確実に調べたい時に使います。

◎質問者からの返答

ありがとうございます。非常に奥深いと言うことがよく分かりました。実際に作る際には腰を据えて作ってみます・・。

皆さんありがとうございました。

関連質問


●質問をもっと探す●



0.人力検索はてなトップ
8.このページを友達に紹介
9.このページの先頭へ
対応機種一覧
お問い合わせ
ヘルプ/お知らせ
ログイン
無料ユーザー登録
はてなトップ