Trie

プログラミング

はじめに

Trieとその周辺を調べたのでまとめた。

Trie(トライ木)とは

  • 文字列探索のための順序付木構造
    • Prefix Treeとも呼ばれる
    • 由来は「reTRIEval」らしい
  • 共通のPrefixをまとめたデータ構造で、文字列が辞書(Trie)に登録されているかを高速に検索することができるもの
    • 各ノードに文字を割り当てておき、ルートからたどることで文字列が登録されているかを保持する
  • 検索速度は、長さmの文字列ならば最悪でO(m)
    • 二分探索の場合O(log n)だが、nは登録されている文字列の数
  • 状況によっては、サイズが巨大になってしまう(少数の長い文字列があるなど)


Trieの実装

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

struct Trie {
  bool leaf;
  Trie* node[256];
  Trie(){
    leaf = false;
    for(int i=0; i<256; i++){
      node[i] = (Trie*)0;
    }
  }
  void insert(const string &str){
    Trie *r = this;
    for(int i=0; i<str.length(); i++){
      char c = str[i];
      if(!r->node[c]) r->node[c] = new Trie;
      r = r->node[c];
    }
    r->leaf = true;
  }
  bool find(const string &str) const {
    const Trie *r = this;
    for(int i=0; i<str.length(); i++){
      char c = str[i];
      if(!r->node[c]) return false;
      r = r->node[c];
    }
    return r->leaf;
  }    
};

void check(const Trie &t, const string &str){
  cout << str << ": ";
  if(t.find(str)) cout << "find" << endl;
  else cout << "not find" << endl;
}

int main(){
  Trie trie;
  trie.insert("an");
  trie.insert("ant");
  trie.insert("all");
  trie.insert("allot");
  trie.insert("alloy");
  trie.insert("aloe");
  trie.insert("are");
  trie.insert("ate");
  trie.insert("be");

  check(trie, "an");
  check(trie, "all");
  check(trie, "allow");
  check(trie, "aiueo");
  check(trie, "are");
  check(trie, "bc");
  
  return 0;
}

Double-Array(ダブル配列)とは

  • Trieデータ構造の一種で、配列を使ってトライを表現する
    • 2つの配列BASEとCHECKがTrieの各ノードに対応していて、文字は辺に割り当てられておりそれを表現する配列CODEとBASEを参照することで対応する次のノード番号を計算する
    • 各配列は以下を満たすようにしてある
      • 「ノード番号xから文字cに対応するノード番号y」をBASE[x]+c=yで計算できる
      • 「ノードyの元ノードx」がCHECK[y]=xで計算できる
  • 文字列の検索
    • ルートノードから一文字ずつ頂点が存在するかどうかを確認する
    • 現在のノードxに対応するBASE[x]と文字cに対応するCODE[c]の値の和が次のノードyに対応する
      • CHECK[y]は元のノード番号xを保持するので確認できる
    • BASE[x]が負の数値の場合、葉に対応するようにすることで葉かどうかの判定ができるようにする

DoubleArrayの実装

要調査リスト

参考文献