タグ: ngram を抽出しています。
Total: 3

検索インデックスで省く文字

ブログ | 2012/2/12 17:14
3文字までの、ngramのインデックスも大きくなると、なかなか大変。
なので、少しでも文字を少なくして容量を削減したい。で、記号系はできるだけスルーする。

ngramの文字列配列を返す関数。
function ngramIndex($str,$wlen=3){
 $len = mb_strlen($str);
 $n = array();
 for($i=0; $i < $len; $i++){
   for($a=1; $a <= $wlen; $a++){
     $moji = mb_substr($str,$i,$a);
     if(preg_match('/[\r\n !"#$%()*+,-.:;<=>?¥ 、。,.・:;?!゛゜´`¨^ ̄_ヽヾゝゞ〃仝々〆〇―‐/\~∥|…‥‘’“”()〔〕[]{}〈〉《》「」『』【】+-±×÷=≠<>≦≧∞∴♂♀°′″℃¥$¢£%#*@§☆★○●◎◇◆□■△▲▽▼※→←↑↓〓∈∋⊆⊇⊂⊃∪∩∧∨¬⇒⇔∀∃∠⊥⌒∂∇≡≒≪≫√∽∝∵∫∬ʼn♯♭♪†‡¶◯ΑΒΓΔΕΖΗΘΙΚΛΜΝΞΟΠΡΣΤΥΦΧΨΩαβγδεζηθικλμνξοπρστυφχψωАБВГДЕЁЖЗИЙКЛМНОПРСТУФХЦЧШЩЪЫЬЭЮЯабвгдеёжзийклмнопрстуфхцчшщъыьэюя─│┌┐┘└├┬┤┴┼━┃┏┓┛┗┣┳┫┻╋┠┯┨┷┿┝┰┥┸╂①②③④⑤⑥⑦⑧⑨⑩⑪⑫⑬⑭⑮⑯⑰⑱⑲⑳ⅠⅡⅢⅣⅤⅥⅦⅧⅨⅩ㍉㌔㌢㍍㌘㌧㌃㌶㍑㍗㌍㌦㌣㌫㍊㌻㎜㎝㎞㎎㎏㏄㎡㍻〝〟№㏍℡㊤㊥㊦㊧㊨㈱㈲㈹㍾㍽㍼≒≡∫∮∑√⊥∠∟⊿∵∩∪]/u',$moji)) continue;
     if($a == 1 && preg_match('/[ぁ-ゞァ-ヾ!-~0-9ー&〒]/u',$moji)) continue;
     $n[] = $moji;
   }
 }
 $n = array_unique($n);
 return $n;
}

スルーしてない記号は、固有名詞に出てきそうな、「'」「&」「@」「/」「&」「ー」「〒」。
「。」はスルーする。「モーニング娘。」は無視する。

これでいいか。

MySQL,fulltextインデックス,Ngram化のまとめ。

ブログ | 2009/9/30 00:46
少し説明的に。
MySQLには、fulltextという全文検索用のインデックスがあります。
ただ、日本語は単語単位で区切られていないので、なんらかの方法で区切る必要があります。区切り方には、形態解析で区切る方法と、意味なんて考えずに1文字とか2文字とかで区切っていくNgramという方式があります。

(あ、その前に、検索対象が数万件くらいなら、「REGEXP」で検索するのがいいと思います。速いし、おそらく厳密だし。)

で、今までは形態解析の方でやってました(mecabなるものを利用)。
ただ、このインデックス化は、「アイスクリーム」を検索したい時に、インデックスに「アイスクリーム」しかないと、「アイス」という検索ではヒットしないというところが難点でした。

初期導入時は、、なんとなく意味で区切った方がインデックス文字列が少なくていいし、優れているのではないかというのが選択動機だったと思います。

さて、Ngram化。

1) まずインデックス文字列の作り方。PHPです。
function ngramIndex($str,$wlen){
 $str = preg_replace('/[\r\n  ]/u','',$str);
 $len = mb_strlen($str);
 $n = array();
 for($i=0; $i < $len; $i++){
   for($a=1; $a <= $wlen; $a++){
     $n[] = mb_substr($str,$i,$a);
   }
 }
 $n = array_unique($n);
 return $n;
}

$str がNgram化したい文字列。
$wlen は、何文字までインデックス化するか(僕は、5にしてみた)

で、配列が返ってくるので、
$str = ngramIndex($str,5);
$str = mysql_real_escape_string(implode(' ',$str));
こんな感じで、$strをMySQLにインサートします。

2) 検索文字列の作り方。PHPです。
function ngram($str){
 $len = mb_strlen($str);
 if($len > 5){
   $n[] = mb_substr($str,0,5);
   if($len > 10){
     for($i=5; $i <= $len-5; $i++){
       if($i%5 == 0){
         $n[] = mb_substr($str,$i,5);
       }
     }
   }
   $n[] = mb_substr($str,-5,5);
   $n = array_unique($n);
 }else{
   $n[] = $str;
 }
 return $n;
}
こんなことにしました。

「マルボロ」-> 「マルボロ」
「クリーニング」-> 「クリーニン, リーニング」
「トールラテで腹下ルのです」-> 「トールラテ, で腹下ルの,下ルのです」

このように配列が返ってくるので、これを展開して、
SELECT ~~~~ WHERE MATCH (ngram) AGAINST ('+クリーニン +リーニング' IN BOOLEAN MODE) ~~~
こんなクエリーにセット。

実際は、複数単語で、AND、OR、除外やらという検索をさせるから、そのあたりはグルグリ関数を書きました。

さて、結果はいかに。今、ポストマップのインデックスを再作成中。
現在、482,436件くらいのデータのようです。
http://postmap.org/list

Rottelも後日、変更していきます。
▼追記 2009/9/30 10:36
5文字までやってたら、longtext型の4294967295byteを超えてエラーで止まった。とりあえず4文字にして、insertする文字数をちゃんと容量内にするように書いて継続。

インデックス作りはもう少し研究が必要だ。
▼追記 2009/9/30 11:44
あー、インデックスづくりで、遅延だ、遅延だ。
▼追記 2009/9/30 15:15
インデックスづくりは休み休みやろう。

...
コメントの検索って、あれ使ってるのかな。
▼追記 2009/10/1 03:29
インデックス作りをなめてた。
朝までに終わるかな・・・。

ポストが終わったら、電話やって、Rottelに行こう。
▼追記 2009/10/2 00:29
なんか、検索スピードが納得いかない。
ヒット件数が少ないと速いみたいだけれど。

インデックスが大きすぎるのが原因のような気がするので、3文字に減らしてみる。
▼追記 2009/10/2 03:05
インデックス更新を回して寝る。
いろんなサイトでDBが遅延してしまいますが、すみません。(投稿したものがすぐに出てくなかったりすると思います)

朝までに終わらない気もする。
▼追記 2009/10/2 19:08
200件インデックス作成したら、30秒スリープしてDBの同期を待つ。これでいい感じ。FULLTEXTインデックスの更新はなかなか遅いらしく、テストするのも何かと大変だ。

文字列のNgram化

ブログ | 2009/9/29 02:43
function ngram($str){
 $str = preg_replace('/[\r\n  ]/u','',$str); //...(1)
 $len = mb_strlen($str);
 $n = array();
 for($i=0; $i < $len-1; $i++){
   $n[] = mb_substr($str,$i,2);  //....(2)
 }
 $n = array_unique($n);   //...(3)
 return $n;
}
こんな感じかな。

(1) 改行とスペースの削除
(2) 2文字ずつ配列に
(3) 重複をまとめる

で、配列で返す。
▼追記 2009/9/29 04:15
2文字のインデックスだけだと、「駅」みたいな1文字が検索できないんだな。
$n[] = mb_substr($str,$i,1);
も追加しとくか。
▼追記 2009/9/29 22:58
1文字2文字だけだと、長いフレーズが遅いと思う。
ということで、1〜5文字でインデックス化したる。
前 | 1 | 次

Rottel内コンテンツ

ユーザー一覧

Rottelとは?
利用規約
開発飲料
利用者の声
ヘルプ
close