Fuzzy Highlight.ppt

Size: px

Start display at page:

Download "Fuzzy Highlight.ppt"

依仪秦
5 years ago
Views:

1 Fuzzy Highlight

2 high light Openfind O(kn) n k O(nm) m Knuth O(n) m Knuth Unix grep regular expression exact match Yahoo agrep fuzzy match Gais agrep Openfind gais

3 exact match fuzzy match fuzzy match O(kn) fuzzy match dynamic programming

4 1/3 fuzzy highlight FuzzyHighlight.zip highlight Perl, 0, :\>perl -s fuzzymatch5.pl " " " esult: :\>perl -s fuzzymatch5.pl 1 esult: :\>perl -s fuzzymatch5.pl CD-R cdr 1 esult: cd-r :\>perl -s fuzzymatch5.pl "My name is 'sam Tseng'" "sam esult:my name is 'sam Tseng' Tseng"

5 highlight 2/3 D:\>perl -s fuzzymatch5.pl " ", " 1 Result: D:\>perl -s fuzzymatch5.pl " ", " 1 Result: highlight D:\>perl -s fuzzymatch5.pl " computer " " camputorization " Result: computer

6 high light 3/3 D:\>perl -s fuzzymatch5.pl " computer " " camputorization" Result: computer high light D:\>perl -s fuzzymatch5.pl " computer " " camputorization" 1 Result: computer

7 highlight substitution highlight Perl sub FuzzyHighLight { my($doc, $Query, $OSoundex) # given 3 arguments $Query =~ s/\s+(\w)/$1/g; # delete white spaces = FuzzyMatchTerms($Doc, $Query, $OSoundex); # High light longer term first, e.g. : 'DVD', 'DVD Player' # so that 'DVD player' can be correctly high lighted. foreach $w (sort { $Doc =~ s \Q$w\E $w g; } # return $Doc; } # End of &FuzzyHighLight()

8 Fuzzy Match: highlight fuzzy match highlight token token word token token token Computer white space Computer ( byte ) comput lowercase and stem Computer ( byte ) C513 ( C513 Knuth soundex code soundex code) ( Perl use Text::Soundex; soundex() ) dynamic programming

9 HTML HTML HTML tag <font-family: Times New Roman > highlight new party HTML tag HTML tag <...> space space In function &DocToken() of FuzzyHighlight.pm } elsif ($c =~ /\s/) { # if white space, do nothing $space.= $c; } elsif ($c eq '<') { # if an HTML tag $c; # Find next balanced '>' for ($wb=$i+1; $wb < $strlen; $wb++) { if (substr($str, $wb, 1) eq '<') { substr($str, $wb, 1); } elsif (substr($str, $wb, 1) eq '>') { last == 0 ; # if empty } } $space.= substr($str, $i, $wb-$i); $i = $wb - 1;

10 Dynamic Programming for Fuzzy Match DP algorithm: d[i, j] = min( d[i-1, j] + w(a[i], 0), d[i-1, j-1] + w(a[i], B[j]), d[i, j-1] + w(0, B[j]) ) d[i, j] : accumulated distance between sequence A and B w(a[i], B[j]) : cost of substituting A[i]with B[j] w(a[i], 0) : cost of inserting A[i] w(0, B[j]) : cost of deleting B[j] d[0, 0] = 0 (i-1,j-1) (i, j-1) d[i, 0] = d[i-1, 0] + w(a[i], 0), 1<= i <= m d[0, j] = d[0, j-1] + w(0, B[j]), 1<= j <= n Complexity: O(n * m), m : length of A, n : length of B (i-1, j) ( i, j )

11 Basic Dynamic Programming: Examples B=adecdecf A=adec d[4,4] 0 d[4,4] d[3,3] d[2,2] d[1,1], 0, match adec match adec B 0 DP 0 B A a d e c d e c f a d e c B A a c d a d e c f a d e c

12 Improved Dynamic Programming 0 d[0, j] = d[0, j-1] + w(0, B[j]), 1<= j <= n d[0, j] = 0, 1<= j <= n d( m) = 0 m exp min m min min d(m) 0 1 m if ($min == $lenq) { $dm = 0; } else { $dm = 1/exp($min/($lenq-$min)); } if (($lenq < 5 && $dm < 0.7) or ($dm < 0.54)) { } #The No Match threshold 1 B a c d a d e c f A a d e c

13 fuzzymatch5.pl exact match high light match match match O(mn) O(n) fuzzy match

嘉義市政府暨附（所）屬機關電話禮貌測試實施要點

嘉義市政府暨附（所）屬機關電話禮貌測試實施要點嘉義市政府暨所屬機關電話禮貌測試實施要點 83 年 8 月 17 日 83 府計研字第 50337 號函頒 90 年 10 月 12 日 90 府企研字第 87210 號修訂 95 年 12 月 20 日 95 府企研字第 0950141214 號函修訂 97 年 3 月 21 日 97 府企研字第 0970110046