Go to Qiita Advent Calendar 2024 Top
LoginSignup
4
1

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

情報検索・検索技術Advent Calendar 2024

Day 3
@soyamash7

転置インデックスの実装

Last updated at Posted at 2024-12-02

前書き

人生は短く、あなたはこの世に存在するすべての文章を読み通すことはできない。

転置インデックスが解決を試みる問題は、つまるところ、上記のような真実に集約される。

文章を『読まずに知る』ことを志す。それは、換言すれば、人の五感に氾濫するありとあらゆる情報を整理し、自在にコントロールする試みであるーー

さすがにこんな大言壮語は嘘だ。よりフェアな言い方をすれば、極めて局所的かつ部分的解決へのわずかな取っ掛りとなり得る程度の、心許ないほどささやかな試み。

その実装を簡単にまとめる。

実装

データ構造

創世記一章一節には「はじめに神は天と地とを創造された」と書かれている。
転置インデックスに必要なのは『辞書』と『転置リスト』だ。

辞書

ここで求められているのは、語の文字列が入力された場合に、その語に対応するIDを出力する機能である。
つまり連想配列の機能を有する構造であれば何でもよい。実装は好きなものを選べばいいだろう。
たとえばソート配列、あるいはハッシュテーブル、それからトライ木。

ただしその選択には少なからず注意が必要だ。あなたが選ぶ辞書のデータ構造は、あなたが提供したい検索機能と密接に関わっている。
完全一致検索に加えて、前方一致検索を提供したいのならソート配列やトライ木は有力な選択肢となるだろう。

それぞれにメリット・デメリットがあり、すべての機能を高速に提供する完璧なデータ構造というものは存在しない。

今回は完全一致検索のみを提供するために、ハッシュテーブルを使用する。検索速度は最良に近いが、メモリ消費量が比較的大きい。

std::unordered_map<std::string, int> token_dict_;

転置リスト

ここで求められているのは、語のIDが入力された場合に、その語が出現する文書IDのソート済み配列と、それぞれの文書における出現位置のソート済み配列を出力する機能である。
つまり連想配列と二次元配列の組合せで実現できる。

語のIDを連番にすることで、上述の連想配列部分を配列に置き換えることができる。この配列のインデックスは語のIDに対応する。その場合、転置リストの全体は三次元配列となる。この変更のメリットはメモリ消費量が抑えられることだ。デメリットは特にない。

配列を片方向連結リストに置き換えることもできる。この変更のメリットはデータの動的更新が比較的容易に行えることだ。デメリットは検索時に二分探索が行えなくなり、検索速度が低下する点にある。このデメリットを克服するために、スキップリストを使うこともできる。

自由には必ず責任が伴う。今回はハッシュテーブルと二次元配列を使用する。

struct DocPositions {
  int doc_id;
  std::vector<int> positions;
};
using InvertedList = std::unordered_map<int, std::vector<DocPositions> >;
InvertedList corpus_il_;

転置インデックスの構築

文書が与えられたら、まず分かち書きを行うべきだ。何かについて思い悩むのはそのあとでいい。

検索対象とする言語によって様々な形態素解析ツールがあり、文字ngramを使用すれば比較的言語に依存しない処理を実装することができる。もしあなたが望むのなら語幹や原形への変換、正規化を行うこともできる。

分かち書きによって得られた各語を辞書に登録し、語のIDを得る。語のIDに紐付けられた転置リストを参照し、その末尾に文書IDを追加し、出現位置を追加する。

転置リスト内の各配列はすべて昇順にソートされている必要がある。あとから転置リストのソートを行う手間を考慮するなら、ここでの文書は文書ID順に処理するほうが、あなたのプログラムをより単純なものにしてくれる。

すぐ後に後述するが、ここで実装した関数はクエリ処理においても使用される。引数に転置リストとフラグを受け取っているのはそのためだ。

int constructIL(int doc_id, const char *s_raw, InvertedList &il, bool is_search) {
  std::string s_wakati(tagger_->parse(s_raw));
  while (s_wakati[s_wakati.length() - 1] == '\n' ||
         s_wakati[s_wakati.length() - 1] == ' ') {
    s_wakati = s_wakati.substr(0, s_wakati.length() - 1); // 最後尾が改行 or 空白になっている場合は除去する
  }
  const char *s = s_wakati.data();
  std::string token;
  int cur_position = 0;
  while (true) {
    if (*s == ' ' || *s == '\0') { // 単語区切り
      int cur_token_id = -1;
      /* token_idを取得する */
      if (token_dict_.find(token) == token_dict_.end()) {
        if (is_search)
          return 1; // ヒットせず
        /* 初めて見るtoken */
        token_dict_[token] = token_id_;
        cur_token_id = token_id_;
        token_id_++;
      } else {
        /* すでにtoken_idの割り振られたtoken */
        cur_token_id = token_dict_[token];
      }

      /* 転置インデックスに格納する */
      if (il[cur_token_id].size() > 0 &&
          il[cur_token_id].back().doc_id == doc_id) {
        /* 同じドキュメント */
        il[cur_token_id].back().positions.push_back(cur_position);
      } else {
        /* 次のドキュメント */
        il[cur_token_id].resize(il[cur_token_id].size() + 1);
        il[cur_token_id].back().doc_id = doc_id;
        il[cur_token_id].back().positions.push_back(cur_position);
      }
      cur_position += token.length();
      token.clear();
      if (*s == '\0')
        break; // 文末
      s++;
      continue;
    }
    token += *s++;
  }
  return 0;
};

フレーズ検索

上で予告した通り、まずクエリから転置リストを構築する。クエリを一つの文書とみなし、文書IDはまだ使用していないダミーのものを用意する。コーパスを処理したときと同様、まずクエリに対する単語分割が行われ、各語ごとに出現位置が転置リストへと格納される。

そしてあなたの手元には、コーパスから構築された転置リストと、クエリから構築された転置リストが残される。片方はとても重く、もう片方はあまりに軽い。

InvertedList query_il;
std::string q;
std::cout << "q:";
std::cin >> q;
p.constructIL(0, q.c_str(), query_il, true)

複雑な物事は小さく始めるのがコツだ。クエリ中に含まれる単語のうち、最も出現文書数が少ないものをAタームと名付ける。このAタームについては線形探索、つまり先頭から愚直に処理していくと心に決める。

/* クエリのトークン中で最もポスティングリストが短いものをa_termとする */
int a_term_id = -1;
int a_term_docs_len = INT_MAX;
for (auto &oth_term : q_il) {
  int oth_term_id = oth_term.first;
  if (corpus_il_.find(oth_term_id) == corpus_il_.end())
    return 0; // ヒットせず
  if (corpus_il_[oth_term_id].size() < a_term_docs_len) {
    a_term_id = oth_term_id;
    a_term_docs_len = corpus_il_[oth_term_id].size();
  }
}

Aタームの転置リストから文書IDを一つ取り出し、その文書IDがクエリ中の他の単語に対応する転置リストに含まれるか否かを二分探索する。配列内をソートしておいた見返りが、ここでようやく与えられる。

for (DocPositions &a_dp : corpus_il_[a_term_id]) { // a_termは線形探索
  int a_doc_id = a_dp.doc_id;
  /* 同文書出現チェック */
  std::unordered_map<int, std::vector<int> *> pos_dict; // 同文書に対する各タームのPositionsを保持する
  pos_dict[a_term_id] = &a_dp.positions;
  bool same_doc_check = true;
  for (auto &oth_term : q_il) {
    int oth_term_id = oth_term.first;
    if (oth_term_id == a_term_id)
      continue;
    DocPositions *oth_dp = binarySearch(corpus_il_[oth_term_id], a_doc_id);  // 二分探索
    if (oth_dp->doc_id == a_doc_id) {
      pos_dict[oth_term_id] = &(oth_dp->positions);
    } else {
      skip_to_doc_id = oth_dp->doc_id;
      same_doc_check = false; // a_doc_idの存在しないポスティングリストがあった
      break;
    }
  }
  if (same_doc_check == false) {
    continue;
  } 

// 下に続く

クエリ中のすべての語が、ある文書に含まれているとわかったのなら、次はそれぞれの出現位置を確認しなければならない。クエリ中の語の並びが、コーパス上でも再現されていなければならない。

まずはAタームの位置を基準に他の語の相対位置を求めておく。ここで気を付けたいのは、クエリ中におけるAタームの出現が一度きりとは限らない点だ。

/* a_termに対する他タームのクエリ中相対出現位置を保存する */
std::vector<std::pair<int, int> > relative_pos;       // term_id, 相対位置
int a_term_pos_q = q_il[a_term_id].back().positions[0]; // クエリ中にa_termが複数回出現する場合に注意
for (auto &oth_term : q_il) {
  int oth_term_id = oth_term.first;
  std::vector<DocPositions> *oth_term_pl = &oth_term.second;
  for (int oth_term_pos_q : oth_term_pl->back().positions) {
    if (oth_term_pos_q == a_term_pos_q)
      continue;
    relative_pos.emplace_back(std::make_pair(oth_term_id, oth_term_pos_q - a_term_pos_q));
  }
}

次にコーパス中のAタームの出現位置を線形探索し、各語の相対位置を足し合わせ、その位置が各語の出現位置リストに含まれるか否かを二分探索する。

/* 出現位置アライメントチェック */
for (auto &a_term_pos_c : (*pos_dict[a_term_id])) { // a_termは線形探索
  bool aliment_pos_check = true;
  for (auto &term_rel : relative_pos) {
    int term_id = term_rel.first;
    int term_rel_pos = term_rel.second;
    int oth_term_pos_c = binarySearch((*pos_dict[term_id]), term_rel_pos + a_term_pos_c); // 二分探索
    if (oth_term_pos_c != term_rel_pos + a_term_pos_c) {
      aliment_pos_check = false;
      skip_to_pos = oth_term_pos_c - term_rel_pos;
      break; // 相対位置にそのタームが存在しなかった
    }
  }
  if (aliment_pos_check == false) {
    continue;
  } else {
    HitInfo h;
    h.doc_id = a_doc_id;  // 出現doc_id
    h.position = a_term_pos_c - a_term_pos_q; // 出現位置
    result.emplace_back(h);
  }
}

そして無事すべての語が正しく配列されていることがわかったのなら、その文書のその位置に、クエリで指定されたフレーズが誤りなく出現していると判定することができる。一つでも欠けていれば、その場所には何も存在しなかったと判定することができる。

探し物が見つからなかったからといって、それで何かを失ったと考えるのは悲観的に過ぎる。青い鳥は鳥かごの中にいたし、病気の子はどこにもいなかったのだ。

そして何より、失敗から学ぶことは常に有用だ。二分探索において、探している数字が見つからなかった場合、その数字より大きな最小の数字を得ることができる。ここで得られた数字より小さいAターム上の数字は、確実にフレーズの出現しえない箇所であることがわかっているので、比較せずスキップすることができる。

つまるところ、探す必要のない場所は探さないほうがいいし、この記事だって読む必要がないのなら読まないほうがいいのだ。

繰り返しになるが、人生はあまりに短い。コードの全体は以下のようになる。

サンプルコード
postings.cpp
#include <algorithm>
#include <climits>
#include <iostream>
#include <fstream>
#include <mecab.h>
#include <string>
#include <unordered_map>
#include <vector>

struct HitInfo {
  int doc_id;
  int position;
};

struct DocPositions {
  int doc_id;
  std::vector<int> positions;
};

using InvertedList = std::unordered_map<int, std::vector<DocPositions> >;

class Postings {
 public:
  Postings() {
    tagger_ = MeCab::createTagger("-Owakati");
  };
  ~Postings() {
    delete tagger_;
  };

  int addDocument(int doc_id, const char *s) {
    return constructIL(doc_id, s, corpus_il_, false);
  };

  int constructIL(int doc_id, const char *s_raw, InvertedList &il, bool is_search) {
    std::string s_wakati(tagger_->parse(s_raw));
    while (s_wakati[s_wakati.length() - 1] == '\n' ||
           s_wakati[s_wakati.length() - 1] == ' ') {
      s_wakati = s_wakati.substr(0, s_wakati.length() - 1); // 最後尾が改行 or 空白になっている場合は除去する
    }
    const char *s = s_wakati.data();
    std::string token;
    int cur_position = 0;
    while (true) {
      if (*s == ' ' || *s == '\0') { // 単語区切り
        int cur_token_id = -1;
        /* token_idを取得する */
        if (token_dict_.find(token) == token_dict_.end()) {
          if (is_search)
            return 1; // ヒットせず
          /* 初めて見るtoken */
          token_dict_[token] = token_id_;
          cur_token_id = token_id_;
          token_id_++;
        } else {
          /* すでにtoken_idの割り振られたtoken */
          cur_token_id = token_dict_[token];
        }

        /* 転置インデックスに格納する */
        if (il[cur_token_id].size() > 0 &&
            il[cur_token_id].back().doc_id == doc_id) {
          /* 同じドキュメント */
          il[cur_token_id].back().positions.push_back(cur_position);
        } else {
          /* 次のドキュメント */
          il[cur_token_id].resize(il[cur_token_id].size() + 1);
          il[cur_token_id].back().doc_id = doc_id;
          il[cur_token_id].back().positions.push_back(cur_position);
        }
        cur_position += token.length();
        token.clear();
        if (*s == '\0')
          break; // 文末
        s++;
        continue;
      }
      token += *s++;
    }
    return 0;
  };

  int phrase_search(InvertedList &q_il, std::vector<HitInfo> &result) {
    /* クエリのトークン中で最もポスティングリストが短いものをa_termとする */
    int a_term_id = -1;
    int a_term_docs_len = INT_MAX;
    for (auto &oth_term : q_il) {
      int oth_term_id = oth_term.first;
      if (corpus_il_.find(oth_term_id) == corpus_il_.end())
        return 0; // ヒットせず
      if (corpus_il_[oth_term_id].size() < a_term_docs_len) {
        a_term_id = oth_term_id;
        a_term_docs_len = corpus_il_[oth_term_id].size();
      }
    }
    
    int skip_to_doc_id = -1;  // 検索失敗時に得られる数字まで線形探索をスキップできる
    for (DocPositions &a_dp : corpus_il_[a_term_id]) { // a_termは線形探索
      if (a_dp.doc_id < skip_to_doc_id) continue;
      int a_doc_id = a_dp.doc_id;
      /* 同文書出現チェック */
      std::unordered_map<int, std::vector<int> *> pos_dict; // 同文書に対する各タームのPositionsを保持する
      pos_dict[a_term_id] = &a_dp.positions;
      bool same_doc_check = true;
      for (auto &oth_term : q_il) {
        int oth_term_id = oth_term.first;
        if (oth_term_id == a_term_id)
          continue;
        DocPositions *oth_dp = binarySearch(corpus_il_[oth_term_id], a_doc_id);  // 二分探索
        if (oth_dp->doc_id == a_doc_id) {
          pos_dict[oth_term_id] = &(oth_dp->positions);
        } else {
          skip_to_doc_id = oth_dp->doc_id;
          same_doc_check = false; // a_doc_idの存在しないポスティングリストがあった
          break;
        }
      }
      if (same_doc_check == false) {
        continue;
      }
      /* 出現位置アライメントチェック */
      /* a_termに対する他タームのクエリ中相対出現位置を保存する */
      std::vector<std::pair<int, int> > relative_pos;       // term_id, 相対位置
      int a_term_pos_q = q_il[a_term_id].back().positions[0]; // クエリ中にa_termが複数回出現する場合に注意
      for (auto &oth_term : q_il) {
        int oth_term_id = oth_term.first;
        std::vector<DocPositions> *oth_term_pl = &oth_term.second;
        for (int oth_term_pos_q : oth_term_pl->back().positions) {
          if (oth_term_pos_q == a_term_pos_q)
            continue;
          relative_pos.emplace_back(std::make_pair(oth_term_id, oth_term_pos_q - a_term_pos_q));
        }
      }

      int skip_to_pos = -1;  // 検索失敗時に得られる数字まで線形探索をスキップできる
      for (auto &a_term_pos_c : (*pos_dict[a_term_id])) { // a_termは線形探索
        if (a_term_pos_c < skip_to_pos) continue;
        bool aliment_pos_check = true;
        for (auto &term_rel : relative_pos) {
          int term_id = term_rel.first;
          int term_rel_pos = term_rel.second;
          int oth_term_pos_c = binarySearch((*pos_dict[term_id]), term_rel_pos + a_term_pos_c); // 二分探索
          if (oth_term_pos_c != term_rel_pos + a_term_pos_c) {
            aliment_pos_check = false;
            skip_to_pos = oth_term_pos_c - term_rel_pos;
            break; // 相対位置にそのタームが存在しなかった
          }
        }
        if (aliment_pos_check == false) {
          continue;
        } else {
          HitInfo h;
          h.doc_id = a_doc_id;  // 出現doc_id
          h.position = a_term_pos_c - a_term_pos_q; // 出現位置
          result.emplace_back(h);
        }
      }
    }

    return 0;
  };

 private:  
  InvertedList corpus_il_;
  std::unordered_map<std::string, int> token_dict_;
  int token_id_ = 1;
  MeCab::Tagger *tagger_;
  DocPositions* binarySearch(std::vector<DocPositions> &v, int target_doc_id) {
    /* doc_idの二分探索 */
    int left = -1; 
    int right = (int) v.size(); 
    while (right - left > 1) {
      int mid = left + (right - left) / 2;
      if (v[mid].doc_id >= target_doc_id) {
        right = mid;
      } else {
        left = mid;
      }
    }    
    return &(v[right]);
  }
  int binarySearch(std::vector<int> &v, int target_pos) {
    /* positionsの二分探索 */
    return *std::lower_bound(v.begin(), v.end(), target_pos);
  }
};

int main() {
  Postings p;
  std::ifstream ifs("./input_raw.txt"); // 行区切りのコーパス
  std::string line;
  int doc_id = 1; // 1オリジン
  while (getline(ifs, line)) {
    p.addDocument(doc_id++, line.c_str());
  }

  while (true) {
    InvertedList query_il;
    std::string q;
    std::cout << "q:";
    std::cin >> q;

    if (p.constructIL(0, q.c_str(), query_il, true)) { // dummyのdoc_idとして0を渡す
      std::cout << "0 hit" << std::endl;
      continue;
    }
    std::vector<HitInfo> result;
    if (p.phrase_search(query_il, result)) {
      std::cout << "0 hit" << std::endl;
      continue;
    }
    for (auto &r : result) {
      std::cout << "doc_id:" << r.doc_id << ", pos:" << r.position << std::endl;
    }
    std::cout << result.size() << " hit" << std::endl;
  }
  return 0;
}

実装を追った結果わかったこと

  1. クエリ中に含まれる語のうち、一つでも出現頻度の少ない語が含まれれば、フレーズ検索の速度は十分高速である
  2. 逆に、すべての語の出現頻度が多ければ、フレーズ検索にかかる時間が増大する
  3. 検索対象のフレーズの出現数が少ないほど、スキップできる箇所が増えて検索速度は速くなる

遠回りは時として、将来の落とし穴を減らしてくれる。これらの事柄は実装を追わなければわからなかったことだ。

触れなかったこと

  1. 転置リストの圧縮
    • コーパスの増大に伴って、転置リストは巨大になるので圧縮して保持する
    • フレーズ検索部分が十分に高速な場合、圧縮転置リストの展開にかかる時間が支配的になる
  2. 分散処理
    • 転置リストを分割し、別々のプロセスで処理することにより高速化が図れる
    • スループットの向上のみを考慮するなら、単純に複数プロセスでリクエストを受け付ける方向性も考えられる
  3. ストップワードの除外
    • クエリに含まれたストップワードを完全一致の条件から外すことで、高速化・メモリ消費量の低減させることもできる

後書き

上記のプログラムに改良できる点はいくらでもあるし、よりよい解説記事だって星の数ほどあるだろう。
それでもあなたがこの記事を最後まで読んでくれたという事実に、偶然以上の意味を見出すのは私の勝手だ。

あなたの前途を祈って、以下に参考文献を列挙する。

参考文献

  • 山田 浩之, 末永 匡(2014). 検索エンジン自作入門 技術評論社
  • Stefan Büttcher, Charles L. A. Clarke, Gordon V. Cormack(2020). 情報検索 :検索エンジンの実装と評価 森北出版
4
1
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
4
1

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?