Upgrade to Pro
— share decks privately, control downloads, hide ads and more …
Speaker Deck
Features
Speaker Deck
PRO
Sign in
Sign up for free
Search
Search
トライとダブル配列の基礎
Search
Shunsuke Kanda
August 03, 2022
Research
1
1.3k
トライとダブル配列の基礎
昔勉強会で使ったもの
Shunsuke Kanda
August 03, 2022
Tweet
Share
More Decks by Shunsuke Kanda
See All by Shunsuke Kanda
Leveraging LLMs for Unsupervised Dense Retriever Ranking (SIGIR 2024)
kampersanda
2
390
Lucene/Elasticsearch の Character Filter でユニコード正規化するとトークンのオフセットがズレるバグへの Workaround - Search Engineering Tech Talk 2024 Spring
kampersanda
0
1.4k
Binary and Scalar Embedding Quantization for Significantly Faster & Cheaper Retrieval
kampersanda
2
420
Binary search with modern processors
kampersanda
33
14k
AIP Open Seminar #6
kampersanda
0
240
ICDM2020
kampersanda
0
210
SIGSPATIAL20
kampersanda
0
200
EliasFano
kampersanda
1
250
Fast Succinct Trie
kampersanda
1
720
Other Decks in Research
See All in Research
CVPR2025論文紹介:Unboxed
murakawatakuya
0
170
GPUを利用したStein Particle Filterによる点群6自由度モンテカルロSLAM
takuminakao
0
350
MIRU2025 チュートリアル講演「ロボット基盤モデルの最前線」
haraduka
15
8.6k
ロボット学習における大規模検索技術の展開と応用
denkiwakame
1
130
世界の人気アプリ100個を分析して見えたペイウォール設計の心得
akihiro_kokubo
PRO
62
30k
SSII2025 [SS1] レンズレスカメラ
ssii
PRO
2
1.1k
2025年度人工知能学会全国大会チュートリアル講演「深層基盤モデルの数理」
taiji_suzuki
25
19k
最適化と機械学習による問題解決
mickey_kubo
0
180
Pythonでジオを使い倒そう! 〜それとFOSS4G Hiroshima 2026のご紹介を少し〜
wata909
0
730
不確実性下における目的と手段の統合的探索に向けた連続腕バンディットの応用 / iot70_gp_rff_mab
monochromegane
2
180
[論文紹介] Intuitive Fine-Tuning
ryou0634
0
120
国際論文を出そう!ICRA / IROS / RA-L への論文投稿の心構えとノウハウ / RSJ2025 Luncheon Seminar
koide3
9
5.3k
Featured
See All Featured
Stop Working from a Prison Cell
hatefulcrawdad
271
21k
Into the Great Unknown - MozCon
thekraken
40
2.1k
Embracing the Ebb and Flow
colly
88
4.8k
Practical Tips for Bootstrapping Information Extraction Pipelines
honnibal
PRO
23
1.5k
Chrome DevTools: State of the Union 2024 - Debugging React & Beyond
addyosmani
7
890
Navigating Team Friction
lara
189
15k
Fight the Zombie Pattern Library - RWD Summit 2016
marcelosomers
234
17k
YesSQL, Process and Tooling at Scale
rocio
173
14k
The Cult of Friendly URLs
andyhume
79
6.6k
How STYLIGHT went responsive
nonsquared
100
5.8k
RailsConf 2023
tenderlove
30
1.2k
Designing Experiences People Love
moore
142
24k
Transcript
トライとダブル配列の基礎 @kampersanda
キー検索と文字列照合 2
キー検索 3 ¨ 文字列のキーを検索して,レコードを取り出す ¤ 人間が辞書から検索するのと同じ ¤ 応用:辞書検索、かな漢字変換、etc… キー(読み) 内容(表記)
レコード1 あっぷる アップル,etc… レコード2 こころ 心,ココロ,此処路,etc… レコード3 かお 顔,買お,^^;,∧( ’Θ’ )∧,etc… レコード4 ぴかちゅう ピカチュウ,光宙,etc…
代表的なキー検索手法 4 ¨ 線形探索(Linear Search) ¤ キー集合を探索 ¨ 二分探索(Binary Search)
¤ 整列済みのキー集合を探索 ¨ 二分探索木(Binary Search Tree) ¤ キーの大小関係に基いて二分木を構築 ¨ ハッシュ表(Hash Table) ¤ ハッシュ関数による分配 ¨ トライ(Trie) ¤ トライ木を用いた探索 O(mn) O(m lg n) O(m lg n) O(m) O(m) n:キー数、m:パターン長
文字列照合とは 5 ¨ テキストに含まれる特定のパターンを見つける ¤ 特定のパターン = キー ¤ 例)力任せのアルゴリズム
O(mn) n m:パターン長、n:テキスト長 n テキスト: “ピーチボーイリバーサイド” n パターン: “リバー” ピ ー チ ボ ー イ リ バ ー サ イ ド リ バ ー ずらして照合していく
代表的な文字列照合手法 6 ¨ 状況による分類 ¤ 長いテキストから少数のキーを検索する場合 n 手法:接尾辞配列,接尾辞木,転置索引,etc… n 応用:全文検索,ウェブ検索,ゲノム解析,etc…
¤ 短いテキストから多数のキーを検索する場合 n 手法:トライ,AC法,etc… n 応用:形態素解析,フィルタリング,ウイルス検知,etc… ¨ 参考書籍 ¤ 情報検索アルゴリズム [北ら 02]
トライ 7
トライ 8 ¨ キー集合を表現するラベル付き木 ¤ キーの構成文字をラベルとする ¤ 例 n “嶺上開花”,“嶺上牌”,“四風連打”,“四槓子”
連 子 牌 開 上 風 槓 花 打 嶺 四
トライにおける検索 9 ¨ 根から葉までの移動 ¤ 入力された文字を辿る n 葉に到達 ➔ Found
n 到達不可 ➔ Not Found 連 子 牌 開 上 風 槓 花 打 嶺 四
トライにおける検索 10 ¨ 根から葉までの移動 ¤ “嶺上開花”を検索 n 葉に到達 ➔ Found
¤ “四槓流れ”を検索 n 到達不可 ➔ Not Found 連 子 牌 開 上 風 槓 花 打 嶺 四
トライにおける終端文字 11 ¨ キーの終端を表す文字‘#’ ¤ 部分キーを判別するために用いることがある ¤ 例 n “嶺上”,“嶺上開花”,“嶺上牌”,“四風連打”,“四槓子”
連 子 牌 開 # 上 風 槓 打 # # 花 # # 嶺 四
トライの特徴 12 ¨ 時間効率 ¤ 理論的にはキー数の影響を受けない ¤ 該当キーの長さのみに影響を受ける ¨ 空間効率
¤ 共通の接頭辞は共有される ¨ 機能 ¤ 入力文字列に含まれるキーの検出(形態素解析) ¤ 照合失敗位置の検出(スペルチェック) ¤ キーの補完(入力補完,文書校正)
トライの実装 13 ¨ 遷移関数 goto を実現する ¤ 節点 cur から節点
next への遷移が文字 label に対し て定義されている場合、goto(cur, label) = next ¤ そうでなければ、goto(cur, label) = –1 next cur label
代表的なトライのデータ構造 14 ¨ 行列 ¤ 時間効率 ➔ 良い O(m) ¤
空間効率 ➔ 悪い O(nσ) ¨ 二分木 ¤ 時間効率 ➔ 悪い O(mσ) ¤ 空間効率 ➔ 良い O(n) ¨ ダブル配列 ¤ 時間効率 ➔ 良い O(m) ¤ 空間効率 ➔ 良い O(n) m:パターン長 n:節点数 σ:アルファベットサイズ
行列によるトライ 15 ¨ 次のノードへの参照を配列に格納 ¤ 遷移時間 O(1) n 高速 ¤
空間効率 O(nσ) n 悪い(疎) ¨ def goto(cur, label) ¤ return M[cur][label] 7:牌 4:開 3:# 2:上 8:# 5:花 6:# 1:嶺 0: # 嶺 上 開 花 牌 0 1 1 2 2 3 4 7 … σ n
二分木によるトライ 16 ¨ 次のノードへの参照を連結リストに格納 ¤ 遷移時間 O(σ) n 低速 ¤
空間効率 O(n) n 良い(密) id label child sib node structure 4 開 5 7 例 7:牌 4:開 3:# 2:上 8:# 5:花 6:# 1:嶺 0:
二分木によるトライの遷移 17 ¨ def goto(cur, label) ¤ next := cur.child
¤ loop n if next = –1 then return –1 n if next.label = label then return next n next := next.sib 3 # 4 4 開 5 7 7 牌 8 7:牌 4:開 3:# 2:上 2 上 3 child sib sib
ダブル配列 18
コンセプト 19 ¨ 疎な行列をうまく畳み込む # 嶺 上 開 花 牌
0 1 1 2 2 3 6 8 3 4 4 5 5 6 7 7 8
# 嶺 上 開 花 牌 0 1 1 2
2 3 6 8 3 4 4 5 5 5 6 7 7 7 8 コンセプト 20 ¨ 疎な行列をうまく畳み込む +3 +5 +7 上下で衝突しないようにスライド
# 嶺 上 開 花 牌 0 1 1 2
2 3 6 8 3 4 4 5 5 5 6 7 7 7 8 コンセプト 21 ¨ 疎な行列をうまく畳み込む +3 +5 +7 上下で衝突しないようにスライド 畳み込むとダブル配列になる
畳み込みのご様子 22 0 1 2 3 4 5 6 7
8 BASE CHECK ?:牌 ?:開 ?:# ?:上 ?:# ?:花 ?:# ?:嶺 0: # 嶺 上 開 花 牌 0 ✔ +0 0 1
畳み込みのご様子 23 0 1 2 3 4 5 6 7
8 BASE 0 CHECK 0 ?:牌 ?:開 ?:# ?:上 ?:# ?:花 ?:# 1:嶺 0: # 嶺 上 開 花 牌 1 ✔ +0 1 2
畳み込みのご様子 24 0 1 2 3 4 5 6 7
8 BASE 0 0 CHECK 0 1 ?:牌 ?:開 ?:# 2:上 ?:# ?:花 ?:# 1:嶺 0: # 嶺 上 開 花 牌 2 ✔ ✔ ✔
畳み込みのご様子 25 0 1 2 3 4 5 6 7
8 BASE 0 0 CHECK 0 1 # 嶺 上 開 花 牌 2 ✔ ✔ ✔ +3 2 2 2 ?:牌 ?:開 ?:# 2:上 ?:# ?:花 ?:# 1:嶺 0: 3 6 8
ダブル配列 26 ¨ BASE, CHECKという2つの配列によるトライ表現 ¤ 遷移時間 O(1) ➔ 高速
¤ 空間効率 O(n) ➔ 良い 0 1 2 3 4 5 6 7 8 BASE 0 0 3 5 0 7 CHECK 0 1 2 6 4 2 8 2 8:牌 6:開 3:# 2:上 7:# 4:花 5:# 1:嶺 0:
ダブル配列における遷移 27 ¨ def goto(cur, label) ¤ next := BASE[cur]
+ label ¤ if CHECK[next] = cur n return next ¤ return -1 # 嶺 上 0 1 2 8:牌 6:開 3:# 2:上 0 1 2 3 4 5 6 7 8 BASE 0 0 3 5 0 7 CHECK 0 1 2 6 4 2 8 2 6 := BASE[2] + 開 = 3 + 3 開 花 牌 3 4 5 CHECK[6] = 2
ダブル配列の構築 28 ¨ 静的 ¤ ソート済みのキー集合から構築 ¤ 他の構築済みのトライから変形 ¨ 動的
¤ ずらして挿入 ¨ 詳細は略 ¤ 効率的なダブル配列の構築はめんどくさい ¤ とりわけ動的は職人芸
トライの比較 29 ¨ 時間効率 ¤ ダブル配列 >= 行列 > 二分木
¨ 空間効率 ¤ ダブル配列 > 二分木 > 行列 ¨ 実装難度 ¤ ダブル配列 > 二分木 > 行列 ¨ 結論 ¤ ダブル配列は優秀 ¤ 多くのケースで十分に小さく、十分に高速
ダブル配列の応用例 30 ¨ 辞書検索 ¤ Darts、Darts-clone ¨ 形態素解析 ¤ ChaSen,MeCab
¨ 係り受け解析 ¤ CaboCha ¨ ウイルス検知 ¤ ClamAV ¨ Nグラム言語モデル ¤ DALM ¨ 全文検索エンジン ¤ groonga ¨ オンラインテキスト処理 ¤ Cedar ¨ 圧縮文字列辞書 ¤ Xcdat
ダブル配列の圧縮 31
ダブル配列の圧縮 32 ¨ ポインタベースなデータ構造なので、簡潔データ 構造と比べるとさすがに大きい ¤ ダブル配列: Ω(n lg n)
ビット ¤ LOUDS: 2n + n lg σ + o(n) ビット ¨ 圧縮方策 ¤ 節点削減:冗長な節点を削減する ¤ 要素圧縮:要素あたりのメモリ消費を抑える
CHECKの圧縮 [Yata+ 07] 33 ¨ CHECKに親番号ではなく遷移文字を記入する ¤ CHECKが log n
から log σ に ¤ BASE[i] ≠ BASE[i’] for any i ≠ i’ 0 1 2 3 4 5 6 7 8 9 BASE 0 2 3 7 1 9 CHECK 嶺 # 上 花 開 # 牌 # 6 := BASE[4] + 開 = 3 + 3 CHECK[6] = 開 # 嶺 上 0 1 2 開 花 牌 3 4 5 6:開 4:上 親の参照はできない!!
BASE、CHECKの圧縮 [Kanda+ 17] 34 ¨ 基本的なアイデア ¤ 遷移条件さえ満たせば節点は自由に配置できる ¤ BASE値とCHECK値が、その要素番号と近くなるように節点
を配置し、その差分を代用する ¤ ランダムアクセス可能な可変長符号で配列を表現 0 50000 100000 150000 200000 250000 0 50000 100000 150000 200000 250000 CHECK[i] XOR i Address: i XOR ほとんどの値が 1バイトで表せる 0 50000 100000 150000 200000 250000 0 50000 100000 150000 200000 250000 CHECK[i] Address: i 親の参照もできます