簡単なパターンマッチに対応したRedis単語登録
よみの部分を簡単なパターンマッチ可能な形で辞書引きしてみます。
Redisはキーと値の組にしてに入れますが､そのままではパターンマッチできません。*1
まず、力ずくでパターン展開したすべての文字をキーにして入れてみました。
例えば「シズカ:静か」という辞書は次の様に展開します。
＊＊カ:静か
＊ズ＊:静か
＊ズカ:静か
シ＊＊:静か
シ＊カ:静か
シズ＊:静か
シズカ:静か
この様に展開したものをRedisのSET型で登録してみます｡
SET型ではキーが同じものは値が重複しない限り追加して登録できます。
SADD '＊＊カ', '{シズカ:静か}' SADD '＊＊カ', '{スイカ:西瓜}' SADD '＊＊カ', '{トミカ:トミカ}' SADD '＊＊カ', '{トミカ:トミカ}' #省略．．．．．． SADD '＊＊ン', '{シナン:至難}' SADD '＊＊ン', '{シナン:指南}' #するとこの様なイメージで登録されます ＊＊カ => {シズカ:静か}, {スイカ:西瓜}, {トミカ:トミカ} #省略．．．．．． シ＊＊ => {シズカ:静か}, {シナン:至難}, {シナン:指南} #この様に保管された辞書から＊＊カ（3文字目がカ）である単語を検索すると SMEMBERS '＊＊カ' #この様に3文字めにカを持つ単語すべてを取り出せます ["{シズカ:静か}", "{スイカ:西瓜}", "{トミカ:トミカ}"]
NAISTの辞書から、記号を除いて2文字から8文字の単語のみ登録してみました。
登録キー数： 5,359,281件
登録に掛かった時間： 約35分
格納メモリ容量： 2.2GByte
全然実用的じゃないです。（そりゃそうだ）
HASH型にした方がメモリの使用率が下がるとのことだったのでそちらをつかいメモリ使用量は半分位にはなりました。
メモリが潤沢なら良いですがまだまだ実用レベルではないです。
ただし、検索に関しては文句なしに早いです。
これじゃサーバ立てたくても立てられないので、別の方法を考えました。
Redisのメモリ容量は、キーの数に大きく依存するらしいので、キーの数を減らすことを考えました。
そこで考えた方法が次の方法です。
キーをｎ文字目に文字Ｘを持つ単語の集合として定義します。
- 1文字目がアになる単語の集合
- 1文字目がイになる単語の集合
- n文字目がＸになる単語の集合
- 8文字目がンになる単語の集合
こうすれば、先の例で8文字までの単語の場合８×５１（実際は濁音とかあるのでもう少し増えますが）で済むはず
キーには何文字目かを分かるようにして n:X とすると
SADD '1:シ', '{シズカ:静か}' SADD '2:ズ', '{シズカ:静か}' SADD '3:カ', '{シズカ:静か}' SADD '1:ス', '{スイカ:西瓜}' SADD '2:イ', '{スイカ:西瓜}' SADD '3:カ', '{スイカ:西瓜}' SADD '1:ト', '{トミカ:トミカ}' SADD '2:ミ', '{トミカ:トミカ}' SADD '3:カ', '{トミカ:トミカ}' SADD '1:シ', '{シナン:至難}' SADD '2:ナ', '{シナン:至難}' SADD '3:ン', '{シナン:至難}' SADD '1:シ', '{シナン:指南}' SADD '2:ナ', '{シナン:指南}' SADD '3:ン', '{シナン:指南}' #するとこの様なイメージで登録されます 1:シ => '{シズカ:静か}','{シナン:至難}','{シナン:指南}' 2:ズ => '{シズカ:静か}' 3:カ => '{シズカ:静か}','{スイカ:西瓜}','{トミカ:トミカ}' 1:ス => '{スイカ:西瓜}' 2:イ => '{スイカ:西瓜}' 1:ト => '{トミカ:トミカ}' 2:ミ => '{トミカ:トミカ}' 2:ナ => '{シナン:至難}','{シナン:指南}' 3:ン => '{シナン:至難}','{シナン:指南}'
これであれば「＊＊カ」という検索に対しては 「3:カ」をキーに持つ値を抽出できます。
「シ＊カ」という検索に対しては RedisのSET型は集合の演算ができます。
この場合は「1:シ」と「3:カ」の共通部分を演算させ
SINTER('1:シ', '3:カ')
とすることで{シズカ:静か}を得ることができます。
このやり方で、一つ問題点があります。すべてが同じ文字数なら良いのですが上記の例で「シズカゴゼン:静御前」が登録されたらどうなるでしょうか？
1:シ => '{シズカ:静か}','{シナン:至難}','{シナン:指南}','{シズカゴゼン:静御前}' 2:ズ => '{シズカ:静か}','{シズカゴゼン:静御前}' 3:カ => '{シズカ:静か}','{スイカ:西瓜}','{トミカ:トミカ}','{シズカゴゼン:静御前}' 1:ス => '{スイカ:西瓜}' 2:イ => '{スイカ:西瓜}' 1:ト => '{トミカ:トミカ}' 2:ミ => '{トミカ:トミカ}' 2:ナ => '{シナン:至難}','{シナン:指南}' 3:ン => '{シナン:至難}','{シナン:指南}' 4:ゴ => '{シズカゴゼン:静御前}' 5:ゼ => '{シズカゴゼン:静御前}' 6:ン => '{シズカゴゼン:静御前}'
この時 ＊＊カを検索させるつもりで、SINTER('1:シ', '3:カ')としても
'{シズカゴゼン:静御前}'もヒットしてしまいます。
これを対処するために各単語の最後にストップ文字を加えて登録する事にします。
シズカ=>シズカ＄
スイカ=>スイカ＄
トミカ=>トミカ＄
シナン=>シナン＄
シズカゴゼン=>シズカゴゼン＄
この様なデータになります｡
1:シ => '{シズカ:静か}','{シナン:至難}','{シナン:指南}','{シズカゴゼン:静御前}' 2:ズ => '{シズカ:静か}','{シズカゴゼン:静御前}' 3:カ => '{シズカ:静か}','{スイカ:西瓜}','{トミカ:トミカ}','{シズカゴゼン:静御前}' 1:ス => '{スイカ:西瓜}' 2:イ => '{スイカ:西瓜}' 1:ト => '{トミカ:トミカ}' 2:ミ => '{トミカ:トミカ}' 2:ナ => '{シナン:至難}','{シナン:指南}' 3:ン => '{シナン:至難}','{シナン:指南}' 4:＄ => '{シズカ:静か}','{スイカ:西瓜}','{トミカ:トミカ}','{シナン:至難}','{シナン:指南}' 4:ゴ => '{シズカゴゼン:静御前}' 5:ゼ => '{シズカゴゼン:静御前}' 6:ン => '{シズカゴゼン:静御前}' 7:＄ => '{シズカゴゼン:静御前}'
シ＊カを検索させる場合は、SINTER('1:シ', '3:カ', '4:＄')とする事で
目的とする {シズカ:静か} だけをマッチさせることができます。
これでDB作って見ました。先ほどと同じく
NAISTの辞書から、記号を除いて2文字から8文字の単語のみ登録してみました。
登録キー数： 591件
登録に掛かった時間： 191.8s
格納メモリ容量： 176.8MByte
メモリ使用量が激減しました。これなら使えるかな？
肝心の検索スピードも 0.2s位なのでまあ大丈夫かな
ちなみにこの方法の場合、５文字の単語検索させるとき
'ア＊＊＊＊'を検索させる場合と、'アイ＊エオ'を検索させる場合は
'ア＊＊＊＊'の方が検索に掛かるコストが少ない事になります。
*1:KEYSでパターンマッチはできますが、公式サイトの説明では管理用に使うべきで通常のコードでは使うなとあります
