「きんいろモザイク中に登場する台詞と類似したツイートを検知して、類似部分の台詞とメタデータをリプライするボット」を作りました。@kinmoza_quotes

アルゴリズムと twitter streaming api / REST api の使い方を簡単にまとめておきます。

類似文字列検索アルゴリズム

類似文字列検索のライブラリとしては SimString などいろいろあるようですが、今回のケースでは辞書サイズはどんなに大きくても10000レコードくらいで収まりそうであることと、簡単な方法でも十分速そうなことから勉強も兼ねて自分で書くことにしました。

文字列同士の類似度の評価には「それぞれの文字列の bi-gram をとって集合としての類似度を計算し、それを文字列の類似度とする」方針を取りました。

str1 = 'hogefuga'; -- bi-gramize --> {ho, og, ge, ef, fu, ug, ga}
str2 = 'abcdef';   -- bi-gramize --> {ab, bc, cd, de, ef}

{ho, og, ge, ef, fu, ug, ga} AND {ab, bc, cd, de, ef}
 = {ef}

{ho, og, ge, ef, fu, ug, ga} OR {ab, bc, cd, de, ef}
 = {ho, og, ge, ef, fu, ug, ga, ab, bc, cd, de}

ここで

(bi-gram の積集合の要素数) / (bi-gram の和集合の要素数) = 1 / 11

を str1 と str2 の類似度と定義します。あとで知りましたが、Jaccard 係数というそうです。

この類似度の定義だと ‘hogehoge’ と ‘hogeh’ の類似度が 1 になってしまうといった欠点があります(繰り返しに弱い)。しかし繰り返しを含んだ単語の出現頻度はそれほど高くない気がするのでとりあえずこれでやってみることにしました。

実際の処理内容は以下のような感じです。

(1) bi-gram の転置インデックスを前処理で作る

dict = ['hoge', 'hage'] とするとき、これの bi-gram による転置インデックスtdictは
tdict = {
    'ho': [0],
    'og': [0],
    'ge': [0, 1],
    'ha': [1],
    'ag': [1]
}
となって、tdict['ge'] とアクセスすると 'ge' を bi-gram
として含む単語のインデックスの配列 [0, 1] を返す。

(2) input (ツイート) が来たら、それを bi-gramize した集合の各要素について転置インデックスを引く

(3) 転置インデックスを引いた時の戻り値(単語のインデックスの配列)それぞれに対して出現回数を数える

擬似コードで書くとこんな感じです。

bigramize(input).forEach(function (one_bigram_element) {
    tdict[one_bigram_element].forEach(function (dict_index) {
        count[dict_index]++;
    });
});

これが終了すると count[dict_index] には dict の dict_index 番目の文字列を bi-gramize した集合と input を bi-gramize した集合の共通部分の要素数が入るので、

count[dict_index] / (bigramize(input).length
                     + bigramize(dict[dict_index]).length
                     - count[dict_index])

を計算すれば類似度が得られます。bigramize(input), bigramize(dict[dict_index]) はすでに求められているのでこの部分は定数で計算できます。Node.js (V8) のハッシュテーブルの foreach がどんな実装かは知りませんが、仮に同じ要素数分詰まっている密な配列を舐める時間と同じとすればナイーブに辞書の全要素を舐めるより速く計算可能です。

O( (入力文字列長) * (転置インデックスの平均配列長 (tdict[hoge]の長さの平均)) )

ソースコードは https://github.com/arcturu/kinmoza_quotes/blob/master/qs_server.js の search() です。

TODO: bi-gramize で位置情報使うように改善する

(もっといいアルゴリズム、教えてください(>_<))

twitter streaming api / REST api

初期設定

コンソールで

npm install twitter

スクリプトで

var twitter = require('twitter');
bot = new twitter({
    'consumer_key': '**************',
    'consumer_secret': '**************',
    'access_token_key': '**************',
    'access_token_secret': '**************'
});

全世界のツイートを垂れ流してもらう

bot.stream('statuses/sample', function (stream) {
    stream.on('data', function (data) {
        console.log(data); // json でツイートのメタデータ全部吐く
        console.log(data.text); // ツイートの内容だけ
    });
});

自分のタイムラインを取得

bot.stream('user', function (stream) {
    stream.on('data', function (data) {
        console.log(data);
    });
});

ツイート

bot.post('statuses/update', {
    status: tweet, // ツイート文言
    in_reply_to_status_id: status_id // リプライ先のツイートの id
}, function (e, data) {
        console.log(e); // エラーメッセージ(あれば)
        console.log(data); // ツイートのメタデータ
    });
});
bot.post('statuses/hogehoge', options, function ()...

のhogehoge, optionsには

https://dev.twitter.com/rest/public

の対応する文言を入れればいいみたいです。例えば GET statuses/retweets/:id を叩きたいときは

bot.post('statuses/retweets', {
    id: id_to_be_retweeted
}, callback);

とします。

ソースコード

https://github.com/arcturu/kinmoza_quotes

twio.js が twitter streaming api を使っている twitter とのやりとり用のサーバで、qs_server.js が検索サーバです。cli.js で簡単に検索することもできます。

comments powered by Disqus