18
2 984 WWW
1 1 1.1................................. 1 2 3 2.1............................ 3 2.1.1......................... 3 2.1.2......................... 4 2.1.3........................ 5 2.2........ 6 2.2.1.............. 6 2.2.2............................. 8 3 9 3.1............................ 9 3.1.1........................ 9 3.1.2................ 10 3.2............................ 10 3.3............................ 12 4 14 4.1................................... 14 4.1.1..................... 14 4.2.................................. 18 4.2.1............. 18 4.2.2.......................... 18 4.3....................................... 20 4.3.1............................. 20 4.3.2............................... 21 5 23 5.1.................................... 23 5.2................................... 23 5.2.1........................ 23 i
5.3.................................. 24 5.3.1........................ 24 5.3.2............. 25 5.3.3...................... 27................................ 27.................................. 27.............................. 28 5.4....................................... 29 5.4.1................. 29 5.4.2.............. 30 6 32 A 34 35 ii
1.1................................. 2 2.1............................. 3 2.2............................. 4 2.3............................ 5 2.4................................. 7 4.1............................... 17 4.2............................... 17 4.3.................. 19 4.4............................. 20 4.5...................... 22 iii
3.1.............................. 9 3.2................. 10 3.3............................. 10 3.4............................. 12 3.5............................... 13 4.1......................... 14 4.2...................... 18 5.1................................. 23 5.2........................ 24 5.3........................ 24 5.4....................... 25 5.5....................... 25 5.6............ 25 5.7............ 26 5.8.................................. 27 5.9......................... 27 5.10...................................... 28 5.11 Wikipedia Abstract.................. 28 5.12........................ 28 5.13 Excite...................... 29 5.14................. 29 5.15...................................... 30 5.16 Wikipedia Abstract......... 30 5.17.............. 30 5.18 Excite............ 30 A.1............................... 34 iv
1 1.1 () 1913 FUN 1922 1925 [1] 1.1 ( ) ( ) [2][3][4][12] 2 1999 Proverb [2][3][4] New York Times 1 95.3% [12] 44%Proverb 1)Proverb 5142 2) 2 1 2 1
2 1 [5][8] 1 [9] [6] WWW blog 2 3 4 5 6 1.1: 2
2 2.1 2.1.1 2.1: 2.1 1 1 http://en.wikipedia.org/wiki/image:american crossword.png 3
A1. A2. 3 A3. A4. A5. A6. 1 6 (A3) 1 (A6) 6 2.1 Web CrossDown 2 2.1.2 2.2: 2.2 3 2 http://www.crossdown.com/howtomake.htm 3 http://en.wikipedia.org/wiki/image:british crossword.png 4
B1. B2. 3 B3. B4. B5. B6. (B3) (B5) 2 2.1.3 2.3: 2.3 4 4 5
J1. 2 J2. J3. J4. J5. 4 J6. (J2) (J4)(J5) 2.2 2.2.1 1 2.4 4 1. 2. WordNet [6] 6
2.4: [10][11] 3. 2 1 1 (2.1) 2 4 [5][8] 4. [9] 7
2.2.2 8
3 3.1 3.1.1 3.1: ID 01 Day 6 Q18 420 02 Day 7 Q1 420 03 Day 7 Q8 420 04 8 Q41 420 05 10 Q30 420 06 8 Q5 420 07 10 Q3 420 08 10 Q4 420 09 vol.2 Q32 480 10 9 Q38 420 11 11 Q37 420 12 8 Q3 420 13 vol.1 Q37 420 14 Q21 420 12 14 3.1 9
3.1.2 (3.1.1) 14 984 :984 () ( ) % 3.2 3.2: % Day,Q1... % Day,Q8... 3.2 3.3: A ( ) B ( ) C ( ) 3.3 C A 1 B C 2 10
A B C (3.1) (3.1) 3.4 3.4 ID 3.1 ID 3.4 ID 1 ( + ) 2 3 23.85% (2.1) 1 6 (16.67%) 16.67% 9.17 2.5 [7] 1.13 1 1 1 1 () () 2 http://chasen.naist.jp/hiki/chasen/ 3 ( ) 1 11
3.4: ID / 01 11 11 21.49%(26/121) 51 3.43 1.06 7.43 02 13 13 23.67%(40/169) 78 3.05 1.01 8.51 03 13 13 23.08%(39/169) 73 3.23 1.36 11.42 04 14 14 23.47%(46/196) 85 3.21 1.08 8.91 05 (196) 18.88%(37/196) 83 3.11 1.23 11.51 06 (169) 40.83%(69/169) 96 3.23 1.02 4.38 07 13 13 23.67%(40/169) 83 2.93 1.05 10.19 08 13 13 22.49%(38/169) 79 3.09 1.15 10.65 09 14 14 24.49%(48/196) 81 3.20 1.32 12.95 10 13 13 21.89%(37/169) 79 3.14 1.08 7.35 11 12 12 29.75%(36/121) 61 3.26 1.23 11.16 12 8 8 18.75%(12/64) 28 3.34 1.17 9.17 13 12 12 20.83%(30/144) 59 3.56 1.0 5.69 14 11 11 20.66%(25/121) 51 3.43 1.06 9.08 - - 987 - - - - 23.85% - 3.23 1.13 9.17 3.3 1 1 4 3.5 3.5 3 679 7 4 12
3.5: 1 - () 364 2 - ( ) 34 3-49 4-49 5 - ( ) 12 6 283 6.1 - ( ) 51 6.2 - ( ) 121 6.3 - ( ) 111 7 - ( ) 37 8 167 8.1 - ( ) 14 8.2 DNA - () 153 9 29 9.1 - ( ) 17 9.2 - ( ) 5 9.3 - = - ( ) 7 13
4 4.1 A. ( ) (3.2) 4.1.1 4.1:... - -... () 4.1 1. 2. 14
1 2...... 2 1...... 1 1 3....... 1. 2. 3. 3 3 1. 2. 3. 1 1 2 3 2 3 3 2 1 984 15
4. 1. - ( ) 2. - ( ) 3. - ( ) 1. 2. 2 1 2 3 1. - 2. - ( ) 3. - () 3 16
...... 1 1 4.1: 4.2: 17
4.2 4.2.1 4.2: 1100g - 12-18 18. 1 85 25 4.2 2 4.3 1) 2) 1-4.2.2. ( ) 1 1 2 http://download.wikimedia.org/jawikinews/20061222/ 18
4.3: 1. 2. 2 ( ) 4.4 2 19
- 1) 2) 1 4.4: 4.3 4.3.1 C. ( ) 3 20
I(x, y) = log P (x, y) P (x)p (y) = log DF (x, y) N DF (x) N DF (y) N = log N DF (x, y) DF (x)df (y) P (x, y) x, y P (x) x P (y) y N DF (x, y) x, y DF (x), DF (y) x, y 1) 2 2) 3 4.3.2 C. ( ) C 1) 2) (4.4) (4.2)(4.3) sh(i, k) = 1 h k I + (x, y) = { w j h k I + (w i, w j ) (4.1) I(x, y) I(x, y) 0 0 I(x, y) < 0 w i h k k (4.4) h k w i sh(i, k) h k w i w i ( (4.2) 21
0 ) h k h k sh(i, k) 1 w i 4.5: 22
5 5.1 5.1: Wikipedia Abstract - 1787 709101 98,211 127,456 65,000 1-126,150 132,772 1,547,914 4 (3.1) 100 100 2 Wikipedia Abstract 3 1999 CD-ROM Excite 5 5.1 5.2 5.2.1 (c)1994 () 65000 ( ) 5.2 100 69 437 2 http://download.wikimedia.org/jawikinews/20061222/ 3 http://download.wikimedia.org/jawiki/20061220/jawiki-20061220-abstract.xml 23
5.2: ( ) () ( ) G 5.3: 1 ( ) 2 ( ) 3 () 437 249 1 ( ) ( ) ( ) 2 3 5.3 5.3.1 5.4 (4.1) 100 47 1 213 24
5.4: ( ) () ( ) 5.5: 1 ( ) 2 ( ) 3 ( ) 134 5.5 1 1 2 3 5.3.2 1 12 22 5.6: 2008 7 ( ) () - 140 ( ) 25
5.7: 1 ( ) 2 ( ) 3 ( ) 4 1762 (4.2) 100 23 1 1 73 5.6 3 1 5.7 1 1 2 ( ) 3 51 15 7 4 http://download.wikimedia.org/jawikinews/20061222/ 26
5.3.3 Wikipedia Abstract 12 20 5 1999 CD-ROM Excite 6 3 3 Excite wget 2005 8 4 1 1 20,275 690,184 body html 5.8: + 3489 20/100 37205 76/100 + 39845 70/100 5.9: 1 NU 2 UN 3 UN 4 UN (4.3) 1) 2) 3 3 + 5 http://download.wikimedia.org/jawiki/20061220/jawiki-20061220-abstract.xml 6 http:www.exblog.jp/ 27
+ Wikipedia Abstract 12 20 5.8 + 5.9 U N 1 2 3 4 1 1 Wikipedia Abstract excite 5.10 5.11 5.12 5.13 5.10: /100 Wikipedia Abstract 57/100 34/57 7/57 14/57 67/100 49/67 8/67 9/67 Excite 77/100 49/77 13/77 15/77 5.11: Wikipedia Abstract 1 ( ) 2 ( ) 3 ( ) 5.12: 1 14 ( ) 2 () 3 ( ) 28
5.13: Excite 1 ( ) 2 CM ( ) 3!! ( ) ( : ( ) 2 9 --( : ( )) - ( : ( )) 7 5.4 5.4.1 5.14: () ( ) ( ) (4.1) 3 8 3 100 22 8 5.14 ( : ( )) 7 ( ) 8 3 29
5.4.2 5.15: /100 Wikipedia Abstract 26/100 11/28 50/100 22/50 Excite 56/100 27/56 5.16: Wikipedia Abstract 1 ( ) 2 () 3 () 5.17: 1 ( ) 2 OS ( ) 3 () 5.18: Excite 1 ( ) 2 () 3 () Wikipedia Abstract 12 20 1999 CD-ROM Excite 3 (4.4) 5.15 5.16 5.17 5.18 3 30
1 31
6 984 1 1) 2) 3) 4) 5) 1) 4) 5) 32
33
A A.1: ( ) 001 002 003 004 005 006 007 008 009 010 011 012 013 014 015 016 017 018 019 020 021 022 023 024 025 026 027 028 029 030 031 032 033 034 035 036 037 038 039 040 041 042 043 044 045 046 047 048 049 050 ( ) 051 052 053 054 055 056 057 058 059 060 061 062 063 064 065 066 067 068 069 070 071 072 073 074 075 076 077 078 079 080 081 082 083 084 085 086 087 088 089 090 091 092 093 094 095 096 097 098 099 100 34
[1]..,2002.11 [2] Keim,G.A.,Shazeer,N.M.,Littman,M.L,Agarwal,S.,Cheves,C.M.,Fitzgerald,J.,Grosland,J.Jiang,F.,Pollard,S. and Weinmeister,K. PROVERB;The Probabilistic Cruciverbalist Proceedings of the Sixteenth National Conference on Artificial Intelligence, pp.710-717(1999). [3] Shazeer,N.M.,Littman,M.L. and Keim,G.A. Solving Crossword Puzzles as Probabilistic Constraint Satisfaction Proceedings of the Sixteenth National Conference on Artificial Intelligence,pp.156-162(1999). [4] Litttman,M.L.,Keim,G.A. and Shazeer,N.M. Solving Crossword with PROVERB Proceedings of the Sixteenth National Conference on Artificial Intelligence,pp.914-915(1999). [5] Berghel,H.,Yi,C. Crossword compiler compilation. The Computer Journal 30, pp.276-280, 1989. [6] Aoife Aherne and Carl Vogel. Crossing WordNet with Crosswords,Netting Enhanced Automatic Crossword Generation. Trinity College technical report, 05-July-2005. [7] Keim,G.A.,Shazeer,N.M.,Littman,M.L.,Agarwal,S.,Cheves,C.M.,Fitzgerald,J.,Grosland,J.,Jiang,F.,Pollard,S. and Weinmeister,K. PROVERB:The Probablistic Cruciverbalist. Proceedings of the Sixteenth National Conference on Artificial Intelligence,pp.710-717(1999). [8],.. 52 8,No.2,pp.133-134,1996. [9],,.. 56 10,No.2,pp.312-313,1998. [10],,. Web. 9,pp.129-132,2003. [11]. 52,pp.113-116,2004. [12]..,Vol.2002,No.4,2002- NL-147-. 11,pp69-76,2002. 35