ここでは，辞書のキーについて n-gram を用いたインデックスを作成して検索を行う方法について説明します．まず，検索したい辞書を次のとおり作成します．
# 辞書の作成
members = {"加藤太郎": "かとうたろう", "佐藤次郎": "さとうじろう", "藤田太郎": "ふじたたろう", "武藤太": "むとうふとし", "藤": "ふじ"}
print(members)
{'加藤太郎': 'かとうたろう', '佐藤次郎': 'さとうじろう', '藤田太郎': 'ふじたたろう', '武藤太': 'むとうふとし', '藤': 'ふじ'}
なお，n-gram は文字列を連続するn個の要素の組合せに分割する手法です．例えば「加藤太郎」という文字列について 2-gram (bigram) にすると「加藤」「藤太」「太郎」という組合せに分割されます．
まず，辞書のキーを bigram に分割し辞書型のインデックスを作成する関数を次のとおり作成します．
def build_bigram_dict_index(members: dict):
dict_index = {} # 2文字→氏名の集合
for name in members.keys():
# 2文字ずつの n-gram を作成（長さ1の名前にも対応）
grams = set()
if len(name) == 1:
grams.add(name)
else:
for i in range(len(name) -1):
grams.add(name[i:i+2])
# インデックスに登録する
for g in grams:
if g not in dict_index:
dict_index[g] = {name}
else:
dict_index[g].add(name)
return dict_index
この関数 build_bigram_dict_index() を呼び出してインデックスを作成します．例えば「加藤」で検索すれば「加藤太郎」が得られ，「太郎」で検索すると「加藤太郎」と「藤田太郎」が得られることを意味しています．
bigram_dict_index = build_bigram_dict_index(members)
bigram_dict_index
{'藤太': {'加藤太郎', '武藤太'},
'加藤': {'加藤太郎'},
'太郎': {'加藤太郎', '藤田太郎'},
'藤次': {'佐藤次郎'},
'次郎': {'佐藤次郎'},
'佐藤': {'佐藤次郎'},
'田太': {'藤田太郎'},
'藤田': {'藤田太郎'},
'武藤': {'武藤太'},
'藤': {'藤'}}
しかしながら上の build_bigram_dict_index() 関数の定義では，16行目で辞書 dict_index のキー g について値 name を追加しています．このときキー g が辞書 dict_index に存在しなければエラーとなることから，13行目でキーの存在をチェックしています．もちろん，この関数でも動作は問題ありませんが，次のように defaultdict を用いると存在チェックが不要になり，処理（コード）が簡単になります．
ここでは defaultdict を使って上のコードを改良します．具体的には，次のとおり1行目で defaultdict をインポートします．4行目のように記述することで，辞書 index にキーが存在しない場合，集合 (set) で初期化されます．したがって，15行目ではキーの存在を確認することなく記述できるため，コードが簡略化されました．
from collections import defaultdict
def build_bigram_index(members):
index = defaultdict(set) # 2文字→氏名の集合
for name in members.keys():
# 2文字ずつの n-gram を作成（長さ1の名前にも対応）
grams = set()
if len(name) == 1:
grams.add(name)
else:
for i in range(len(name) - 1):
grams.add(name[i:i+2])
# インデックスに登録
for g in grams:
index[g].add(name)
return index
いま定義した関数 build_bigram_index() を呼び出してインデックスを作成します．実質的に同じ内容のインデックスが生成できました．
bigram_index = build_bigram_index(members)
bigram_index
defaultdict(set,
{'藤太': {'加藤太郎', '武藤太'},
'加藤': {'加藤太郎'},
'太郎': {'加藤太郎', '藤田太郎'},
'藤次': {'佐藤次郎'},
'次郎': {'佐藤次郎'},
'佐藤': {'佐藤次郎'},
'田太': {'藤田太郎'},
'藤田': {'藤田太郎'},
'武藤': {'武藤太'},
'藤': {'藤'}})
次にインデックスを用いた検索を行うための関数を次のとおり定義します．
def search_with_bigram(members, bigram_index, query):
# クエリ長が1文字なら総当たりで部分一致
if len(query) == 1:
return [name for name in members if query in name]
# 2文字以上：2-gram で候補を集合積で絞り込み
grams = {query[i:i+2] for i in range(len(query) - 1)}
# まず存在するグラムだけを拾う
candidate_sets = [bigram_index[g] for g in grams if g in bigram_index]
if not candidate_sets:
return []
candidates = set.intersection(*candidate_sets) # 積集合演算（＊ はアンパック演算子）
# 最終チェック（完全な部分一致判定）
return [name for name in candidates if query in name]
実際に様々なキーワードで検索を行ってみます．
print(search_with_bigram(members, bigram_index, "太郎"))
['加藤太郎', '藤田太郎']
print(search_with_bigram(members, bigram_index, "太郎"))
['加藤太郎', '藤田太郎']
print(search_with_bigram(members, bigram_index, "次郎"))
['佐藤次郎']
print(search_with_bigram(members, bigram_index, "太"))
['加藤太郎', '藤田太郎', '武藤太']
print(search_with_bigram(members, bigram_index, "藤太郎"))
['加藤太郎']
print(search_with_bigram(members, bigram_index, "藤太"))
['加藤太郎', '武藤太']
print(search_with_bigram(members, bigram_index, "加藤太郎"))
['加藤太郎']
print(search_with_bigram(members, bigram_index, "藤"))
['加藤太郎', '佐藤次郎', '藤田太郎', '武藤太', '藤']
多数の要素から構成されるような辞書の場合，n-gram によるインデックスを用いた検索は総当たりの検索と比較すると優れた検索性能を有しているはずです．それほど大きくはないですが100件のデータを利用して総当たり検索とインデックスを利用した検索の検索性能を比較してみましょう．
まず，GitHub から百人一首のデータをデータフレームに読み込み，これを辞書に変換します．
# モジュールのインポート
import pandas as pd
import numpy as np
from collections import defaultdict
url = "https://github.com/rinsaka/sample-data-sets/blob/master/hyaku-utf-8.csv?raw=true"
df = pd.read_csv(url)
# データフレームをリストに変換し，さらに辞書を構築
uta = df['uta'].tolist()
kajin = df['kajin'].tolist()
hyaku = dict(zip(uta, kajin))
構築した辞書の中身を確認します．
hyaku
{'秋の田の かりほの庵の 苫をあらみ わが衣手は 露にぬれつつ': '天智天皇',
'春すぎて 夏来にけらし 白妙の 衣ほすてふ 天の香具山': '持統天皇',
'あしびきの 山鳥の尾の しだり尾の ながながし夜を ひとりかも寝む': '柿本人麻呂',
'田子の浦に うち出でて見れば 白妙の 富士の高嶺に 雪はふりつつ': '山部赤人',
...（中略）...
'人もをし 人も恨めし あぢきなく 世を思ふゆゑに 物思ふ身は': '後鳥羽院',
'百敷や ふるき軒端の しのぶにも なほあまりある 昔なりけり': '順徳院'}
総当たりの検索関数を定義します．
def search_hyaku(hyaku, query):
return [uta for uta in hyaku.keys() if query in uta]
インデックスを用いた検索のための関数を定義し，実際にインデックスを生成します．
def build_bigram_index(hyaku):
index = defaultdict(set)
for uta in hyaku.keys():
grams = set()
if len(uta) == 1:
grams.add(uta)
else:
for i in range(len(uta) - 1):
grams.add(uta[i:i+2])
for g in grams:
index[g].add(uta)
return index
def search_with_bigram(hyaku, bigram_index, query):
if len(query) == 1:
return [uta for uta in hyaku if query in uta]
grams = {query[i:i+2] for i in range(len(query) - 1)}
candidate_sets = [bigram_index[g] for g in grams if g in bigram_index]
if not candidate_sets:
return []
candidates = set.intersection(*candidate_sets)
return [uta for uta in candidates if query in uta]
bigram_index = build_bigram_index(hyaku)
マジックコマンドを使って総当たり検索の処理時間を計測します．その結果は平均 4.6 マイクロ秒でした．
%%timeit
search_hyaku(hyaku, "富士")
4.6 µs ± 212 ns per loop (mean ± std. dev. of 7 runs, 100,000 loops each)
同様にインデックス検索の処理時間を計測します．その結果は平均 669 ナノ秒（= 0.669マイクロ秒）でした．
%%timeit
search_with_bigram(hyaku, bigram_index, "富士")
669 ns ± 11.3 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)
高々100件という小さなデータであったにもかかわらず，インデックス検索は総当たり検索の6倍程度の検索性能を有していることが分かりました．