共起関係を使おうとしたけどいまいちいい方法が分からず、「共起相手が多い語ほど評価を低く」なるようにした。特定の語としか共起しない場合は評価を下げないように。
コード(Perl)
use utf8; use strict; use feature qw/switch/; use Encode; use Fcntl qw/:flock/; use Memoize; use Algorithm::Diff::XS qw/sdiff/; #use Algorithm::Diff qw/sdiff/; use Smart::Comments; my %worddict; my %cooccurrencedict; my %sentencedict; unless ($ARGV[0]){ print "usage: $0 datafile\n"; exit 0; } sub num_of { scalar @_; } memoize('unigrams'); sub unigrams { # リスト（高速化のため） [split //, $_[0]]; } #memoize('bigrams'); sub bigrams { my($str) = @_; my @ret = (); if (length $str >= 2){ my @letters = split //, $str; ### assert: 1 <= $#letters for my $i (1 .. $#letters){ my $g = join '', @letters[$i - 1 .. $i]; push @ret, $g; } } ### assert: (@ret == 0 and length $str == 0) or (@ret == length($str) - 1) @ret; # 重複あり } sub learn { my($sentence) = @_; ### assert: not ref $sentence my @bigrams = bigrams($sentence); my @sentences2 = do { my %s; foreach my $bi (@bigrams){ foreach (@{$sentencedict{$bi}}){ $s{$_} = undef; } } keys %s; }; foreach my $sentence2 (@sentences2){ # diff my $sdiff = sdiff(unigrams($sentence), unigrams($sentence2)); my @words; my @unmodified; my $push_to_words = sub { push @words, join('', @unmodified); @unmodified = (); }; foreach my $elem (@$sdiff){ given ($elem->[0]){ when ('u'){ ### assert: $elem->[1] eq $elem->[2] push @unmodified, $elem->[1]; } default { $push_to_words->() if (@unmodified); } } } $push_to_words->() if (@unmodified); # store foreach my $w (@words){ $worddict{$w}++; $cooccurrencedict{$w}->{$_}++ foreach (grep { $_ ne $w } @words); } } foreach my $bi (@bigrams){ push @{$sentencedict{$bi}}, $sentence; } return; } { print STDERR scalar localtime, "\n"; open my $fh, '<', $ARGV[0] or die; flock $fh, LOCK_SH or die; my $c; foreach (<$fh>){ print STDERR "\r", ++$c; chomp $_; $_ = decode 'utf8', $_; learn($_); } close $fh or die; print STDERR " done.\n", scalar localtime, "\n"; } { # 評価 my %score; foreach my $w (keys %worddict){ $score{$w} = $worddict{$w} * (length($w) - 1); } foreach my $w ( grep { exists $cooccurrencedict{$_} } keys %worddict ){ # 共起相手が広いほど低評価（共起回数の少ない相手が多いほど低評価） my %cooccur_to_freq = %{$cooccurrencedict{$w}}; my $ave; $ave += $_ foreach (values %cooccur_to_freq); $ave /= num_of keys %cooccur_to_freq; foreach my $oc (keys %cooccur_to_freq){ $score{$w} -= ($ave / $cooccur_to_freq{$oc} - 1); } } # 出力 my $c = my $num = num_of keys %score; foreach my $w ( sort { $score{$a} <=> $score{$b} } keys %score ){ print sprintf('%d/%d(%.1f%%): %s', $c, $num, $c / $num * 100, encode('utf8', $w)), ", $score{$w}\n"; $c--; } print "#: word, score\n"; }
高速化のためのインデックス作り（bigramとか書いてるあたり）、”side by side”なdiff(sdiff)から共通点を得るところ、共起数の評価（co-occurrenceなんとかかんとか）がごちゃごちゃしてる。
高速化
bi-gramでインデックス作成。2文字連続で合わない文はdiffにさえかけない。
1文字の共通部分は検出されなくていい。検出されても評価を下げる。
これでちょっと処理量が減った。
メモ化 (Memoize)
uni-gramを作る処理をメモ化。
bi-gram生成もメモ化できるけど同じパラメーターで2度も呼ばないのでメモ化不要。
これでちょっと処理量が減った。
でも相変わらず遅いのはdiffのアルゴリズム自体が高価だからなようでAlgorithm::Diff::XSを使ってもまだ遅い。
とは言っても実用的な出力が得られなきゃ重いも何もないんですけどね。
どの程度の入力件数でどんな出力が得られるかを調べないと重さの基準も分からない…でも入力が都合のいい共通部分を持っているかなんて分からないのでどうにも調べようがない。
結果
#: word, score 1/344(0.3%): 忍たま, 1245.06247794074 2/344(0.6%): 忍たま乱太郎, 692.95863613892 3/344(0.9%): です。, 133.820075757576 4/344(1.2%): 五年生, 128.948099858877 5/344(1.5%): たま乱太郎, 114.021429859126 6/344(1.7%): 鉢屋三郎×不破雷蔵, 109.84375 7/344(2.0%): サークル, 108.924422799423 8/344(2.3%): 中心, 108.06973124868 9/344(2.6%): 落第忍者乱太郎, 104.207676767677 10/344(2.9%): サークルです。, 97.7073891625615 11/344(3.2%): ほのぼの, 86.5019391089771 12/344(3.5%): 中心です。, 61.45 13/344(3.8%): 中心です, 60.669696969697 14/344(4.1%): 忍たま , 58.1652777777778 15/344(4.4%): オールキャラ, 50.0666666666667 16/344(4.7%): ます。, 45.8563847429518 17/344(4.9%): ギャグ, 42.9037280701754 18/344(5.2%): サークルです, 38.5 19/344(5.5%): 年生中心, 35.9416666666667 20/344(5.8%): 中心に, 34.6793650793651 21/344(6.1%): 中心で, 34.229510685393 22/344(6.4%): 中心。, 33.3571428571429 23/344(6.7%): 忍たま乱太郎／落第忍者乱太郎、五年生中心ギャグ・竹谷八左ヱ門, 29 24/344(7.0%): タソガレドキ, 27.75 25/344(7.3%): です, 25.8829721362229 26/344(7.6%): 善法寺伊作, 25.4810606060606 27/344(7.8%): ています。, 24.7179487179487 28/344(8.1%): 乱太郎, 24.1356388878127 29/344(8.4%): 活動しています, 23.5833333333333 30/344(8.7%): 中心サークル, 22.96 31/344(9.0%): 三郎, 21.6394557823129 32/344(9.3%): で活動しています, 21 33/344(9.6%): サークルで, 20.6666666666667 34/344(9.9%): ×食満留三郎, 19.6666666666667 35/344(10.2%): 五年生中心, 18.8557692307692 36/344(10.5%): ています, 18.75 37/344(10.8%): を中心に, 16.875 38/344(11.0%): 落乱, 15.2863636363636 39/344(11.3%): 食満, 14.8875 40/344(11.6%): 生中心, 14.3611111111111 41/344(11.9%): 食満留三郎, 14.2083333333333 42/344(12.2%): てます。, 14.0625 43/344(12.5%): 落第忍者乱太郎（忍たま乱太郎）, 14 44/344(12.8%): ります。, 13.875 45/344(13.1%): 活動しています。, 13.625 46/344(13.4%): もあります。, 13.5166666666667 47/344(13.7%): 生オールキャラ, 11.6666666666667 48/344(14.0%): 忍たま乱太郎／, 11.6 49/344(14.2%): もあります, 11.1666666666667 50/344(14.5%): サークル。, 10.9333333333333 51/344(14.8%): 留三郎, 10.75 52/344(15.1%): 鉢雷, 10.7058823529412 53/344(15.4%): 、五年生, 10.6714285714286 54/344(15.7%): 中心。マンガ、ほのぼの, 10 55/344(16.0%): 善法寺伊作×食満留三郎, 10 ……（続く）……
それと…
C80ROM.TXTにある31850件のサークル紹介文から単語抽出した結果
やっぱり「です」「ます」が強かった。
これは評価方法によるものだけど、です／ますとコモディティ化してもいいくらいの固有名詞とは区別できなかった。ひらがなだけかとか、語尾にあるかとか、そういった日本語だけの法則を取り入れればふるい落とすことは出来るだろうけど。
とりあえずおしまい。
おまけ(Perl)
さっきの31850件の結果を使って、文章を切ってみる。
use utf8; use strict; use Encode; use Memoize; use Smart::Comments; my @words = do { open my $fhdict, '<', 'out31850.txt' or die; my @dict; while (my $l = decode 'utf8', <$fhdict>){ chomp $l; push @dict, $1 if ($l =~ /: ([^,]+), /); } close $fhdict; ### words: scalar @dict reverse @dict; }; @words = map { quotemeta } @words; memoize('split_by_word'); sub split_by_word { my($sentence) = @_; my @r; foreach my $re (@words){ if ($sentence =~ /$re/){ my @m = ($`, $&, $'); push @r, ( split_by_word($m[0]), $m[1], split_by_word($m[2]) ); last; } } if (@r == 0){ push @r, $sentence; } @r; } print "blank line => quit\n> "; while ((my $in = decode 'utf8', <STDIN>) ne "\n"){ chomp $in; print encode 'utf8', join(' / ', grep { $_ } split_by_word($in)); print "\n\n> "; }
区切り対象で先に出現するものではなく、辞書に書かれている順で抽出、区切りたいのでちょっとややこしいコード。
例えばこうなる。
### words: 172605 blank line => quit > オリジナルボーカロイドイラスト創作系創作絵サークル活動中です。 オリジナル / ボーカロイド / イラスト / 創作系 / 創作絵 / サークル / 活動中 / です。 > 主に男性向け同人誌を配布しています。 主に / 男性向け / 同人誌を / 配布し / ています。 > すーぱーそに子セーラームーンコスプレサークルです。 すーぱーそに子 / セーラームーン / コスプレ / サークルです。 > ちゅちゅっちゅちゅっちゅちゅちゅっちゅ ちゅ / ちゅっちゅ / ちゅっちゅ / ちゅ / ちゅっちゅ > もふもふもふもふももふふもふもふふわふわふわーふわふわふわふーわふーわふわふだらだらだららんだだらだらゆっくりゆゆっくりゆっくり もふもふ / もふもふ / も / もふ / ふ / もふもふ / ふわふわ / ふ / わー / ふわふわ / ふ / わふー / わふー / わ / ふわ / ふ / だらだら / だ / らら / んだ / だらだら / ゆっくり / ゆ / ゆっくり / ゆっくり > 魔まマ魔まママママま魔マま魔魔魔魔法少女魔女魔法少女 魔まマ / 魔まマ / ママ / マま / 魔 / マま / 魔 / 魔 / 魔 / 魔法少女 / 魔女 / 魔法少女 > ロロナトトリメルルトトロトロロロナルトトトリコロロナルトリコロコロココロコネクトトリトバスターリトルバスターズ！！！！！ ロロナ / トトリ / メルル / トト / ロト / ロロ / ロ / ナルト / ト / トリコ / ロロナ / ル / トリコ / ロコ / ロ / ココ / ロコ / ネク / トトリ / トバ / スター / リトルバスターズ！ / ！！！ / ！ > イールシルシイー イールシ / ルシイー > モンスターハンターモンハンポケモンハン モンスターハンター / モンハン / ポケモン / ハン > 同人創作絵音楽活動などなんでもござれのごちゃまぜサークルです。 同人 / 創作絵 / 音楽活動 / など / なんでも / ござ / れの / ごちゃまぜ / サークルです。
最後の例なんか、辞書には「なんでもござれ」はあるんだけど、先に「なんでも」で切ってしまうので細切れになってる。短い単語のほうが出現数が多いので高評価…なのでこうなる。
辞書内の包含関係を解決できれば精度が上がるかも。長いほうが正しいというわけではないので一工夫必要だけど。
