接尾辞木に基づく大規模文字列索引の効率よい構築アルゴリズム

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

本年度は、前年度提案より進めているデータ圧縮に関する研究を発展させ、テキストの走査により圧縮に用いる辞書の評価と再構築を繰り返すことによって圧縮率を高めた手法を提案した。VF符号はデータ圧縮手法の一つであり、分節木と呼ばれる、文字列の集合を表す辞書を用いて、テキストを辞書の要素の列に変換することで圧縮を実現する。このため、いかに圧縮に有用な文字列を辞書に含めるかが、高い圧縮率の実現に重要である。しかし、最適な辞書を構築することは困難であることが知られている。近年ではKidaやKleinによって接尾辞木を用いた分節木構築法が提案されているが、VF符号はLZ法などの手法に対し圧縮率で劣っていた。これに対し提案手法では、分節木を用いてテキストを圧縮する際、分節木のどの文字列がよく用いられるか解析し、その結果を用いて分節木を再構築、つまり訓練することで圧縮率を高める。計算機実験では、訓練を繰り返すことでgzipと同程度の圧縮率を達成している。この圧縮法はVF符号の一種であり、特殊なアルゴリズムを用いて圧縮したテキストデータに対し復号を伴わずに高速に文字列検索を行う、圧縮照合と呼ばれる手法に適しており、大規模テキストデータベースからの高速な検索の実現への適用が期待される。また、本年度は語頭符号に対する接尾辞木の構築アルゴリズムを示した。この結果はAnderssonやInenagaらによって研究されている単語接尾辞木を発展させたものであり、来年度6月にCPM2011で発表予定である。