読者です 読者をやめる 読者になる 読者になる

文法圧縮(5)

NLP

文法圧縮(Re-Pair)の構築部分については、線形時間で構築できるようになったが、文法圧縮部分の辞書をどう簡潔に保持するか?という問題が残っている。

例えば、

abcabcabb

という文字列に対して、Re-Pairを適用して、以下のような辞書(R)と圧縮文字列(C)が得られたとする。

辞書(R):
s ---> ab
t ---> sc
u ---> ts

圧縮文字列(C):
tub

このとき、辞書(R)を単純にハッシュで保持することもできるが、簡潔に保持することもできる。図に示す。

f:id:ryokkie:20140101174858p:plain

詳しい作り方は、後で述べるので、まずは、簡単に説明する。辞書(R)を2分木を使って表現し、その構造をRbというビットベクトルで表現する。ビットベクトルの1は、ノードであり、0が葉である。木を行きがけ順(pre-order)で探索して、Rbを表現する。また、葉の文字を行きがけ順に並べたのがRsである。このとき、uの中にsが出てくるが、すでに部分木として表現されているので、Rbでの部分木の位置をRsに表現する。なので、実際には、木というよりもDAGと表現した方が良い気がする。

例として、このデータ構造を使って、「t」を展開してみる。「t」が表現されているのは、Rbで1の位置である(位置は0からとする)。このとき、

rank_0(Rb, 1) = 0

なので、Rsの開始位置を0に設定する。つまり、Rbの開始位置を1とし、Rsの開始位置を0とする。ここからは、Rbを順番に探索して、0の数が1の数より大きくなった時点で探索を終了する。また、Rbが0の時は、Rsから文字を一つ取り出す。実際に探索してみる。Rbの1の位置と2の位置には、1があるので、1の数を2とする。Rbが3の位置から0が連続しているので、1の数が2だったので、0が2を超えるまで、Rsから順に文字を取り出すと、「abc」を取り出すことができる。これは、「t」を展開したことと等しい。

次にこのような簡潔表現を構築する方法について説明する。まず、辞書の各定義が別の定義から使われている数を数える。例の場合、以下のような回数となる。

s : 2
t : 1
u : 0

つまり、uはどの定義からも参照されていないことがわかる。このとき、どの定義からも参照されていないuを頂点として、再帰的に展開していく。Rbの0の位置に1を設定し、「u ---> ts」であるため、「t」を展開する。「t」は、展開可能であるため、Rbの1の位置に1を設定し、「t ---> sc」であるため、「s」を展開する。「s」は展開可能であるため、Rbの2の位置に1を設定する。「s ---> ab」の「a」と「b」はこれ以上展開できないため、Rbの3と4の位置に0を設定し、Rsの0と1の位置に「a」と「b」を設定する。次に、「t ---> sc」の「c」もこれ以上展開できないので、Rbの5の位置に0を設定し、Rsの2の位置に「c」を設定する。最後に、「u ---> ts」の「s」は、展開可能であるが、すでに表現されているので、Rbの6の位置に0を設定し、Rsには、その部分木の開始位置として、Rbの位置である2を設定する。圧縮文字列であるCについては、Rbの位置を使って表現する。

このように表現することで、辞書(R)の構造をRbを利用して、簡潔に表現できる。また、辞書(R)の「s t u」の展開後の文字列である「ab sc ts」の6文字は、冗長性を排除することで、Rsにおいて、4文字で表現することができる。Cは変わらない。また、Rbを完備辞書で表現すれば、ランダムアクセスも可能である。

ただし、辞書の簡潔表現は、一旦、Re-Pairの圧縮を行ってから辞書を圧縮する必要があると思うので、中間メモリは、簡潔にはならない。

次は、今回紹介した辞書の簡潔表現を使って、Re-Pairを利用した完備辞書についてまとめてみる。

広告を非表示にする