大規模データにおける高速検索可能な動的圧縮文字列辞書の研究

点击翻译按钮获取中文摘要

今年度は，研究計画に沿ってさまざまな圧縮文字列辞書を提案し，その成果を論文やソフトウェアを通して発表した．その研究成果は主に３つである．１つ目は，既存の静的圧縮文字列辞書の構築に必要となる膨大なコストを解消した手法である．既存の静的圧縮文字列辞書では，Re-Pairと呼ばれる強力な文字列圧縮技法を適用することで，高いメモリ効率を達成している一方で，その構築時間や領域は膨大であり，大規模なデータに対して適用する場合は実用的な時間で辞書を構築することができない．そこで本研究では，文字列辞書の圧縮に文字列辞書を再帰的に適用することで，この問題を解決した．2つ目は，ダブル配列を用いた辞書構造が動的応用において抱える問題を解決する手法である．ダブル配列は，現実的な作業領域で高速な検索を提供するデータ構造であり，形態素解析器や全文検索エンジンで現在も広く用いられている．一方で，更新が繰り返されるとダブル配列は性能が低下することが知られており，必要に応じて再構成を施す必要がある．本研究では，既存の手法を用いた場合，その再構成時間が問題になることを示し，それを解決するための手法をいくつか提案した．3つ目は，メモリ効率に優れた動的文字列辞書の提案である．ここ10年，静的な圧縮文字列辞書に関する研究は実用的にも大きく進展した一方で，動的な圧縮文字列辞書に関する研究は理論に留まっている．現実的な既存の動的辞書の実装は，静的な辞書と比べて遥かに多くのメモリを使用する．そこで，本研究では，Path DecompositionとCompact Hashingと呼ばれる技法を応用することで，メモリ効率の良い動的文字列辞書を提案した．どの手法においても，実データを用いた実験により厳密に評価を与え，有効性を示した．