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

回答の条件
  • URL必須
  • 1人2回まで
  • 登録:2003/11/28 12:53:32
  • 終了:--

回答(4件)

id:ys_y No.1

ys_y回答回数2ベストアンサー獲得回数02003/11/28 13:22:15

ポイント30pt

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

id:hitoshih

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

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

2003/11/28 14:07:00
id:sasada No.2

sasada回答回数1482ベストアンサー獲得回数1332003/11/28 14:47:25

ポイント100pt

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

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

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

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

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

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

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

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

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

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

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

id:hitoshih

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

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

2003/11/28 15:13:19
id:frain No.3

frain回答回数45ベストアンサー獲得回数12003/11/28 15:18:10

ポイント100pt

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

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

URLはダミーです。

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

例えば、

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

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

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

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

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

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

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

id:hitoshih

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

2003/11/28 15:43:45
id:hmori No.4

hmori回答回数18ベストアンサー獲得回数12003/11/29 08:43:00

ポイント100pt

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

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

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

難しいので・・・・

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

基本的には、この入力に

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

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

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

http://www.namazu.org/

Namazu: a Full-Text Search Engine

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

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

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

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

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

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

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

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

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

id:hitoshih

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

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

2003/12/01 13:35:14

コメントはまだありません

この質問への反応(ブックマークコメント)

トラックバック

「あの人に答えてほしい」「この質問はあの人が答えられそう」というときに、回答リクエストを送ってみてましょう。

これ以上回答リクエストを送信することはできません。制限について

絞り込み :
はてなココの「ともだち」を表示します。
回答リクエストを送信したユーザーはいません