Trieで共有接頭辞を索引化する

概要

Trieによる共有接頭辞の索引

文字列集合の各文字遷移を木として共有し、prefix通過数・prefix DP・辞書順探索をnode上で処理する。

考え方

共通prefixを一度だけ保存する根付き木がTrieである。根からの経路が文字列を表し、節点にはそのprefixを持つ文字列の個数や終端数を置く。比較を文字単位の枝選択へ移すことで、文字列全体の繰り返し比較を避ける。

rootの通過数と終端数を0で初期化する。文字列を挿入するときrootの通過数を一増やし、一文字ずつ子がなければ作って進み、各nodeの通過数も増やす。末尾nodeの終端数を増やす。prefix Pをたどったnodeの通過数がPで始まる登録文字列数、終端数がPそのものの個数である。辺がなければ0。空文字列の挿入はrootの両数へ寄与する。

辞書順列挙ではnodeの終端を先に出し、子を文字昇順にDFSする。prefix自身がその延長より先に来るためこの順になる。子の通過数を使えばk番目も、終端の重複分を引き、子の個数を小さい文字から差し引いて降りることで得られる。登録文字列の削除は存在する終端数を確認し、同じpathの通過数を減らす。

成立条件と計算量

総入力長Lなら節点数は高々L+1。固定文字種の配列遷移で挿入・検索は文字列長に比例するが、空間はO(Lσ)。疎な連想配列では探索費用も含める。重複文字列と「prefix自身が終端」の扱いを分ける。

問題一覧

各問題の解説は問題ごとの本文として執筆します。各項目には主題・追加で学ぶ技能・既習技能の役割を示します。

関連問題

前提・学習成果・出典

習得対象の目安: 水色(1200–1599)。共有prefixを木にし、通過数・辞書順・文字遷移をnode上で管理する。

対象色の読み方は本書の読み方を参照してください。

概念上の親: 文字列アルゴリズム。問題へ進む前に、下記の直接前提のうち未習得の単元を確認する。

Canonical taxonomy: FinalTaxonomyBuild final-taxonomy-build-initial digest f1ae39bc7201c3374c108e800284e1e0068ce6f7a57f15b2a9e5219616e3c4fe / LearningUnit unit-trie-prefix

習得する技能

  • 文字列集合をTrieへ挿入し、nodeの通過数・子遷移・辞書順を使って共有接頭辞の問いを処理できる。

前提と範囲

共通前提: prereq-abc-advanced-v1 (1.0.0)。

直接の前提単元: なし。

このUnitを直接前提とする単元: Aho–Corasick。

文字ごとの遷移を配列やmapで持ち、複数文字列の共有接頭辞を木として索引化する。

このUnitでは扱わないもの

  • failure linkやZ値で接頭辞と接尾辞の一致状態を更新する文字列照合。

根拠