[2E1-OS-13a] AIと制約プログラミング(1/3)

[2E1-OS-13a-05] 大規模文字列集合データを表現するSequence BDDの高速な構築手法とその評価

〇杉野 創¹、川原 純¹、湊 真一¹ (1. 京都大学)

キーワード：系列二分決定グラフ、SeqBDD、データ圧縮、文字列処理

大規模文字列集合データをコンピュータ上に効率的に表現し処理することは、文字列集合の索引化やデータマイニングなど幅広い応用において重要である。Loekitoらが提案した系列二分決定グラフ（Sequence BDD、SeqBDD）は文字列集合を効率的に表現するデータ構造であり、文字列集合データを圧縮したまま豊富な演算を適用できる特徴をもつ。本研究では、大規模文字列集合データを保持するテキストデータを入力とし、その文字列集合を表現するSeqBDDをボトムアップに高速に構築する手法を提案する。文字列を逐次的に和集合演算により追加する既存手法と比べ、提案手法は多くの場合に高速に動作し、特に共通する接頭辞をもつ文字列が集合内に多く出現するような入力に対してより効果的である。本発表では、提案アルゴリズムについて述べ、様々なデータセットを用いてその有効性を評価した結果を示す。