文字列の圧縮列挙索引技術とパターン照合技術

伝住　周平; 有村　博紀; 定兼　邦彦

あらまし

伝住　周平有村　博紀定兼　邦彦

Vol.97 No.12pp.1080-1085

発行日:2014/12/01

Online ISSN:2188-2355

Print ISSN:0913-5693

種別:小特集　「フカシギの数え方」から広がるアルゴリズムの理工学――二分決定グラフによる離散構造処理と広がる応用分野――

専門分野:

キーワード:
系列BDD, 索引, 文字列, データ圧縮, 簡潔データ構造,

本文:PDF(523.8KB)>>

あらまし:
大規模な文字列データの操作は，文字列処理の分野で最も重要な課題の一つである．本稿では，文字列集合をコンパクトに圧縮し様々な操作を可能とする系列二分決定グラフ（系列BDD，SeqBDD）を紹介し，関連するパターン照合技術について紹介する．この系列BDDは，文字列データに拡張したZDDの一種であるが，同時に，従来から自然言語処理や文字列処理分野で研究されてきたトライや，有限オートマトン，接尾辞グラフなどのテキスト索引のためのデータ構造とも密接な関連を持つ．これら既存のデータ構造との関係や，近年発展が著しい簡潔データ構造と関連した話題についても述べる．

あらまし

ログイン

メニュー