転置インデックスを構築しましょう！

こんにちは。コグラフソフトウェアサービス事業部のルイスです。
プログラマーとして面接に行ったとき、ある単語を含むすべての文書を検索するコードを作るよう求められたとしたら、どんな風にコードを書くのでしょうか？
本日は便利なツールを紹介したいと思っています。

転置インデックス引とは？

転置インデックスとは、全文検索を行う対象となる文書群から単語の位置情報を格納するための索引構造をいう。転置索引、転置ファイル、逆引き索引などとも呼ばれています。

weblio.jp

シナリオ

多くの文書を含むリストがあり、特定の用語に基づく文書が返されるとします。例えば、"Python "という単語を検索する場合、コードはその単語を含むすべてのドキュメントを含むリストを返す必要があります。
次のようなリストです。

documents = [
"hello, this is your first Python trial",
"with programming, you can do whatever you want",
"Python allows you to access all services in the web",
"SQL is not an easy programming language, but with practice you can do everything",
"プログラミング言語はすごく好きです"
]

最も簡単な方法は、各文書間で反復処理を行い、"Python "という単語を検索し、その文書を結果リストに保存することです。

results = []
for doc in documents:
  if "Python" in doc:
    results.append(doc)
print(results)

しかし、検索しなければならない文書が100万件あるとしましょう。このやり方は最適ではありません。というのも、Pythonという単語を含む文書を検索するために、アルゴリズムが行うのは、Pythonという単語に一致する文書を見つけるまで、各文書を単語ごとに繰り返し検索することだからです。
このアプローチでは直線的なアプローチになり、多くの単語を含む100万件の文書がある場合、このアプローチの複雑さが増します。

Wikipedia

解決方法：転置インデックス

大量のサンプルデータを検索する場合、最適な方法は転置インデックスを使用することです。この方法は、GoogleやYahoo、いくつかのデータベースなどのプラットフォームで使用されています。
そのため、Dictionaryとしてインデックスを作成することになり、各文書を繰り返し、各文書で単語ごとに検証し、インデックスを作成します。
例えば、Pythonという単語に対して、インデックスはそれが属するドキュメントのインデックスを持つリストという値を持ちます。この例では、最初の文書は0、3番目の文書は2です。

index = {
    'Python' : [0,2],
    ...
}

したがって、アルゴリズム・コードは次のようになります。

index = {}
for i, doc in enumerate(documents):
  for word in doc.split():
    if word not in index:
      index[word] = [i]
    else:
      index[word].append(i)

results = index["Python"]
for i in results:
  print(documents[i])

Dictionaryのキー"Python"でインデックスを参照すると、ドキュメントが存在する値のリストが返されます。このアプローチはO(1)の複雑さを与え、線形複雑さと比較して高速です。これは、Dictionary内の単語の検索が複雑度O(1)に属するためである。

終わり

もし面接で、文書リストから特定の単語を検索するよう求められたら、単純な反復を使う代わりに、より速く正確な転置インデックスを使いましょう！

未経験エンジニアとして働きたい方へ

コグラフ株式会社ソフトウェアサービス事業部ではPythonやSQLの研修を行った後、実務に着手します。研修内容の充実はもちろん、経験者に相談できる環境が備わっています。
このようにコグラフの研修には、実務を想定し着実にスキルアップを目指す環境があります。興味がある方は、下記リンクよりお問い合わせください。