たつをの ChangeLog

15 件 見つかりました。

1 2 3 [ 次へ ]

Modern Information Retrieval 第二版をゲット!
  • https://chalow.net/2011-02-23-1.html
  • Modern Information Retrieval 第二版をゲット![Book][NLP] 発売がのびのびになっていた Modern Information Retrieval (MIR) の Second Edition ですが、やっと入手しましたよ![MIRのSecond Editionがメタボな件]初版と比べて厚さ3倍!参考文献のページのフォントが大きくなってて余分にページ数を食っており、そこを除けば厚さは2倍ほど。■Berthier Ribeiro-Neto,Ricardo Baeza-Yates / Modern Information Retrievalref.- [を] Modern Information Retrieval 第二版が2008年5月に出るみたい[2007-10-17-2]- [を] Modern Information Retrieval 第二版の発売が2009年5月にのびたみたい[2008-12-21-3]
Modern Information Retrieval 第二版の発売が2009年5月にのびたみたい
  • https://chalow.net/2008-12-21-3.html
  • Modern Information Retrieval 第二版の発売が2009年5月にのびたみたい[Book][NLP] Modern Information Retrieval の第二版が出るみたい、という話[2007-10-17-2]の続報です。ええと、発売予定がのびていました。2009年5月だそうです。1年延期になったのですね。先は長いなあ…。■Berthier Ribeiro-Neto,Ricardo Baeza-Yates / Modern Information Retrievalref.- [を] Modern Information Retrieval 第二版が2008年5月に出るみたい[2007-10-17-2]
転置インデックスの構成とブーリアン検索
  • https://chalow.net/2008-01-18-1.html
  • 転置インデックスの構成とブーリアン検索[IIR][Algorithm] 「Introduction to Information Retrieval」[1]の第一章[2008-01-12-1]の転置インデックスまわりの用語と検索手順などの解説です。ちょっと前に書いた『ウェブ検索を「本の索引」で説明する試み』[2007-06-17-6]という記事の続きでもあります。「転置インデックスによる検索システムを作ってみよう!」[2007-11-26-5]もご参考に。§転置インデックス (inverted index または inverted file) は、dictionary と postings の二つの部分から構成されます。dictionary は索引語 (term) の集合です。term が登場する文書の ID を posting と呼びます。ある term の posting のリストが postings list (または inverted list)、postings list の集合が postings と呼ばれています[1](posting と postings がちょっとややこしいのですが、IIR[1]の記述に従いました)。これらの関係を図に示しました。[画像]MIR[2]では、dictionary を vocabulary、postings を occurrences と呼ばれています。特に「正しい」名称はないのでしょうね。一般的な実装では、dictionary をメモリ展開し、postings を外部ファイルとすることで、効率化が図られています。この転置インデックスをベースに、AND, OR, NOT のオペレータを用いたブーリアン検索 (boolean retrieval)について解説します。「恵比寿 AND ビール」は「恵比寿」と「ビール」の両方を含む文書を検索するクエリーです。処理は、まず「恵比寿」「ビール」の postings list を取り出してそれぞれの先頭にポインタを置き、ポインタが指す posting 同士を比較しながらポインタを進め(posting が小さい側のポインタを進めることを繰り返す)、一致した posting だけを取り出す、というものです。例では、1, 47, 209 が取り出せます。「恵比寿 OR ビール」は「恵比寿」か「ビール」のどちらかまたは両方が含まれている文書を検索するクエリーです。それぞれの postings list を posting を重複しないようにマージすることで適合する文書を取り出します。「恵比寿 AND NOT スイーツ」は「恵比寿」を含むが「スイーツ」は含まない文書を検索するクエリーです。これもAND検索と同様にそれぞれのポインタが指す posting 同士を比較しながらポインタ進めます。このとき「スイーツ」の posting に一致しない「恵比寿」の posting のみを取り出します。例では、1, 2, 47, 209 が取り出せます。なお、これらの処置を効率的に行うために、転置インデックス構築時には、各 postings list の posting は ID 順に格納しておくことが望まれます。参考文献:[1] Christopher D. Manning, Prabhakar Raghavan and Hinrich Schu"tze: Introduction to Information Retrieval, Cambridge University Press, 2008. (http://www-csli.stanford.edu/~hinrich/information-retrieval-book.html)[2] Ricardo Baeza-Yates, Berthier Ribeiro-Neto: Modern Information Retrieval, Addison Wesley, 1999.(間違いや補足などありましたら下記フォームからご連絡頂けると幸いです)
Modern Information Retrieval 第二版が2008年5月に出るみたい
  • https://chalow.net/2007-10-17-2.html
  • Modern Information Retrieval 第二版が2008年5月に出るみたい[Book][NLP][Algorithm] だいぶ前に情報を頂いていたのですが(ありがとうございます)、埋もれてました。Modern Information Retrieval の第二版が出るみたいです。■Berthier Ribeiro-Neto,Ricardo Baeza-Yates / Modern Information Retrieval2008年5月って、かなり先ですね…。
Dynamic Programming による類似文字列マッチの実装例
  • https://chalow.net/2007-01-22-4.html
  • Dynamic Programming による類似文字列マッチの実装例[Programming][Algorithm] 「Modern Information Retrieval」(8.6.1 p.216) でのDynamic Programming (DP) の解説のところのアルゴリズムを素直に Perl で実装したみた。さらにマッチ箇所取り出しロジックも実装してみた。[asin:020139829X]DP はいわゆる「類似文字列検索(あいまい検索)」に使うと便利なalgorithm。実は、大学院でも前の会社でも、PerlやらC++やらで実装して使ってた。単純ながら使い勝手もよく、まさに現場向きかと。grep 式に頭から見ていくので計算量的にはイマイチなのだが、転置インデックス検索などで範囲を絞ってから適用すれば実用上問題ない。■定義みたいなのQ1. 二つの文字列 "home" と "ahoge" はどれだけ類似しているか?A1. こう考えてみる。home の m を g に置き換えて、先頭に a と追加すると ahoge になる。つまり「置き換え」と「追加・挿入」とで操作を計 2 回行ったわけだ。てなわけで、この二つの文字列の「距離」を 2 と定義し、どれだけ類似しているかの尺度として用いる。Q2. "hemi" と "gome" はどちらがより "home" と似ているか?A2. home の o を e に、 e を i に置き換えると hemi になるので操作は 2 回(距離 = 2)。home の h を g に置き換えると gome になるので操作は 1 回(距離 = 1)。よって、"gome" の方が "hemi" よりも "home" に似ていると言える。で、こういう類似文字列マッチをやるのが DP。■説明まずは、スコアテーブル C[i,j] を作成する。Modern Information Retrieval での説明を一部改変して引用。P[i]はパターン(キーワード)、T[j]は検索・マッチ対象のテキスト。C[0,j] = 0C[i,0] = iC[i,j] = if (P[i] = T[j]) then C[i-1,j-1] else 1 + min(C[i-1,j],C[i,j-1],C[i-1,j-1]) P = "survey", T = "surgery" で作ったテーブルはこんな感じになる。右下のマスの数字は、PとTが何文字違いかを表すもの(と、とりあえず考えておこう)。 surgery 00000000s10111111u21012222r32101223v43211233e54322123y65433222テーブルができてしまえばあとは簡単。右下からスタートし、上・左・左上の中から最小スコアのマスを選んで左上までたどっていけば、キーとテキストがどうマッチしたかが分かる。上への移動はキー側の一文字を削除することを意味する。左への移動はキー側へ一文字挿入することを意味する。左上への移動は同じ文字か文字の置き換えを意味する。コードでは関数 traverse の再帰呼び出しで実現している。テーブルを見ながら確認してもらいたいのだが、survey を surgery にするには、(1) r を e と y の間に「挿入」し (または y を末尾に挿入し、その前の y を r に「置き換え」る)、(2) v を g に「置き換え」る、という操作をすればよいことが分かる。通り道を図で表すとこんな感じ。 surgery 0 s 0 u 0 r 0 v 1 e 12 y 2T が長い場合はスタート位置を工夫して、無駄な再帰が避けるとよいかと。コード中で $start を設定している箇所と、P = "survey", T = "foosurgerybar" でのテーブル(下記)を見ながら考えてみよう! foosurgerybar 00000000000000s11110111111111u22221012222222r33332101223332v44443211233443e55554322123454y66665433222345はい、一番下の行の中で一番小さい数字のマスからスタートすればOK。こんな感じに。 foosurgerybar 0 s 0 u 0 r 0 v 1 e 12 y 2 ■コード#!/usr/bin/perluse strict;use warnings;my @key = qw/ s u r v e y /;my @text = qw/ f o o s u r g e r y b a r /;unshift @key, ""; # BKunshift @text, ""; # BK# スコアテーブルの作成my @C;for (my $j = 0; $j < @text; $j++) { $C[0][$j] = 0;}for (my $i = 0; $i < @key; $i++) { $C[$i][0] = $i;}for (my $i = 1; $i < @key; $i++) { for (my $j = 1; $j < @text; $j++) { my ($u, $l, $d) = ($C[$i-1][$j], $C[$i][$j-1], $C[$i-1][$j-1]); if ($key[$i] eq $text[$j]) { $C[$i][$j] = $d; } else { my $min = (sort {$a <=> $b} ($u, $l, $d))[0]; $C[$i][$j] = 1 + $min; } }}# スコアテーブルの表示print " ".join(" ", @text),"\n";for (my $i = 0; $i < @key; $i++) { printf " %1s ", $key[$i]; for (my $j = 0; $j < @text; $j++) { printf " %-3d", $C[$i][$j]; } print "\n";}# マッチ箇所取り出し処理のスタート位置決定my $start = $#text;for (my $j = $#text; $j > 0; $j--) { if ($C[$#key][$j] < $C[$#key][$start]) { $start = $j; }}# マッチ箇所取り出しmy @results = traverse($#key, $start);sub traverse { my ($i, $j) = @_; return if ($i == 0 or $j == 0); my ($u, $l, $d) = ($C[$i-1][$j], $C[$i][$j-1], $C[$i-1][$j-1]); my $min = (sort {$a <=> $b} ($u, $l, $d))[0]; if ($min == $d) { my @rv = traverse($i-1, $j-1); return @rv, {token => $text[$j], tag => ($d == $C[$i][$j]) ? "match" : "replace"}; } elsif ($min == $l) { my @rv = traverse($i, $j-1); return @rv, {token => $text[$j], tag => "insert"}; } else { my @rv = traverse($i-1, $j); return @rv, {token => "", tag => "delete"}; }}# 結果表示print join("", map {$_->{token}} @results),"\n";print join(", ", map {"$_->{token}:$_->{tag}"} @results),"\n";■実行例% ./dp.pl f o o s u r g e r y b a r 0 0 0 0 0 0 0 0 0 0 0 0 0 0 s 1 1 1 1 0 1 1 1 1 1 1 1 1 1 u 2 2 2 2 1 0 1 2 2 2 2 2 2 2 r 3 3 3 3 2 1 0 1 2 2 3 3 3 2 v 4 4 4 4 3 2 1 1 2 3 3 4 4 3 e 5 5 5 5 4 3 2 2 1 2 3 4 5 4 y 6 6 6 6 5 4 3 3 2 2 2 3 4 5surgerys:match, u:match, r:match, g:replace, e:match, r:insert, y:match追記070123: 説明不足だったので「定義みたいなの」を追加。

1 2 3 [ 次へ ]

たつをの ChangeLog
Powered by chalow