3.

(on Scrapbox)

Twitter
: #sfcid2017

Scrapbox
sfc-id2017-CNS

Gyazo



!?
/

1:
()
...

2:

3: GUI


(1995)
Information Retrieval
ACM SIGIR
使

(2000)
Lycos, AltaVista, Inktomi, ...

(2010)
Google!
=

(2020)
etc.
SVM, LSI, ...

AI (2030?)



Information Retrieval (IR)
ACM SIGIR (Special Interest Group on Information Retrieval
=
= IR

Precision ()
÷
Recall ()
÷

Gyazo
100%
F = 21Recall+1Precision2 \over {{ 1 \over {Recall}} + {1 \over {Precision}}}


AND/OR/NOT
e.g. Brutus AND Caesar but NOT Calpurnia


()
to be or not to be


tf-idf
tf: Term Frequency
idf: Inverse Document Frequency
Wij=TFij×IDFiW_{ij} = TF_{ij} \times IDF_i
TFij=TF_{ij} = ji
IDFi=log(N/DFi)IDF_i = \log(N / DF_i)
DFi=DF_i = i

Flash
GETA

GETA
/WAM(Word-Article Matrix)



(Relevance Feedback)


Web

tf-idf

LSI(Latent Semantic Indexing)
(Singular value decompositions, SVD)
SVD
/

(@)


T[1..n] P[1..m]
Knuth-Morris-Pratt (KMP)
Boyer-Moore
Shifter

T[1..m] P[1..m]
T: aaaaaaaaaaaaaaaaab
P: aaaaaab
T[2..m] P[1..m]
T: aaaaaaaaaaaaaaaaab
P: aaaaaab
...
T[n-m+1..n] P[1..m]
n×mn \times m

Knuth-Morris-Pratt
P[7] (= b )
aaaaaa
P[6] (= a )
P

Knuth-Morris-Pratt
P = abcaba
5 1
5 abca
2
56
b
1

Boyer-Moore
KMP
調
1 T[m] = c
c P2 T[m+1] 調

Boyer-Moore (Cont'd)
k
2
d1 -- []
d2 -- k []
d1['a'] = 1, d2['c'] = d1['d'] = ... = 8

mmmm
kk
e.g. 11101 = 2
c1 T[c] OR
T[c] ==c0
e.g. abac T['a'] = 0101
OR使

(Cont'd)
BM
agrep 使

e.g. ×
Unix

ab
a3

abc
(abc|def)
[abc]
ab*c

(||)([0-9]*)(||)
((()?)?)

(e.g. )(e.g. )

A aB (A/B: , a: )

e.g. a(b|cd)
A aS
B bA
C cA
B dC

Aho-Corasick
grep
egrep

Aho-Corasick
(1|2|...)
KMP
使(KMP)
fgrep使
: ac|baa|bacd|ba|bb

grep
UNIXgrep使
* ?
abc|def

egrep
UNIXegrep使
使
NFA()
NFADFA()
DFA

(SUB)*SECTION




()


0000000100000000
0000000000001000
OR
0000000100001000
AND




Emacs
Google Suggest


Migemo
Emacs

Demo: Migemo

Google?


Google(Larry Page)

Larry Page

X/2 Y2
X/2 2
X : Y : Z = 0.4 : 0.2 : 0.4

?




Scrapbox
Gyazo



Gyazo

Google
西 (2009)

EC
Gyazo