はじめに
この記事では string attractors という概念を紹介します。
そして string attractors の具体例として、 LZ77 という圧縮データ構造から string attractors を生成してみます。
この記事で使ったコードは github に置いてあります。
string attractors
string attractors は At the Roots of Dictionary Compression: String Attractors という論文で提案された概念です。
string attractors を使うことで、効率的に部分文字列をとり出せる圧縮データ構造や、 self-index を作ることができます（string attractors から self-index を作る方法は Universal Compressed Text Indexing で提案されています）。
それだけだと普通（？）なのですが、 string attractors には様々な圧縮データ構造との相互変換が可能であるという特徴があります（論文では、それらの圧縮データ構造は実は同じ問題を別の方法で解いている、と述べています）。
例えば LZ77 という圧縮データ構造は、そのままだと部分文字列を取り出すことはできないのですが、 string attractors に変換することで効率的なデータ構造を作ることができます（LZ77 については LZ圧縮：LZ77とLZ78、そしてLZD の説明がわかりやすいです）。
後ほど、この LZ77 から実際に string attractors を作ってみます。
string attractors の定義
string attractors は長さ $n$ の文字列 $T$ に対して、ある条件を満たす位置の部分集合 $\Gamma\subseteq[1,n]$ です。
任意の部分文字列 $T[i..j]$ に対応して、ある $j_k\in\Gamma$ が存在する、というのが string attractors の条件です。
どのような $j_k$ かというと $T[i'..j']=T[i..j]$ となるような $i',j'$ について $j_k\in[i',j']$ となっているようなものです。
別の言い方をすると、文字列 $T$ を任意の部分文字列で検索したときに、マッチした部分文字列の少なくとも1つには string attractors の元が含まれていてね、というのが条件です。
string attractors は同じ文字列に対して複数ありえます。
string attractors の具体例
- 文字列 $T$ のすべての位置の集合 $\{1,2,...,n\}$ は $T$ の最大の string attractors です。
- CDABCCDABCCA という文字列の string attractors の一つは $\Gamma=\{3,6,10,11\}$ です（先頭の位置を0としています）。例えば、 CDA という部分文字列は $T[0..2]$ と $T[5..7]$ の2箇所にありますが、 $6\in[5,7]$ なので string attractors の元を含んでいます。
与えられた位置の集合が string attractors かどうかを確認するコード
実際に、文字列 $T$ と位置集合 $\Gamma$ を与えて、 $\Gamma$ が本当に $T$ の string attractors になっているかを検証するコードを書いてみます。
以下の is_string_attractors() は文字列 text のすべての部分文字列 text[begin:end] を生成して matches_any_string_attractors() で対応する位置が index_list に含まれているかを検証します。
すべての部分文字列に対応する位置があれば index_list は晴れて string attractors を名乗れるというわけです。
def is_string_attractors(
text: str, index_list: Sequence[int]
) -> bool:
'''
index_list が指すインデックス集合が
text の string attractors になっているかどうかを判定します
'''
return all([
matches_any_string_attractors(text, index_list, text[begin:end])
for begin in range(len(text))
for end in range(begin + 1, len(text) + 1)
])
matches_any_string_attractors() は text から subtext にマッチする位置を全部見つけて、そのどれかに index_list の要素が入っているかをチェックしています。
def matches_any_string_attractors(
text: str, index_list: Sequence[int], subtext: str,
) -> bool:
'''
subtext にマッチする text の部分文字列のうちのいずれかに
index_list が指すインデックスのいずれかが
含まれているかどうかを判定します
'''
begin = 0
while True:
index = text[begin:].find(subtext)
if index == -1:
return False
begin = begin + index
end = begin + len(subtext)
if any([index in range(begin, end) for index in index_list]):
return True
begin += 1
ついでに文字列中の string attractors の位置を表示するメソッドも用意しておきます。
def print_string_attractors(
text: str, index_list: Sequence[int]
) -> None:
'''
string attractor の位置の文字を [] で囲んで text を表示します
'''
print(''.join([
f'[{ch}]' if index in index_list else ch
for index, ch in enumerate(text)
]))
これらのメソッドを使って、先ほど紹介した string attractors の例が本当に正しかったかを確認してみます。
text = 'CDABCCDABCCA'
sa_list = [3, 6, 10, 11]
print_string_attractors(text, sa_list)
print('is_valid: {}'.format(is_string_attractors(text, sa_list)))
実行結果は以下の通り。確かに string attractors であったことがわかります。
% pipenv run python -m string_attractors.sample
CDA[B]CC[D]ABC[C][A]
is_valid: True
LZ77 と string attractors
LZ77 の簡単な紹介
LZ77 は文字列を先頭から順番に見ていき factor という単位に分割します。
新規の文字が出てきたら、その1文字が factor となります。
そうでない場合は、すでに通過した部分で一致する最大の部分文字列長ぶんを切り出して factor とします。
すでに何度か出てきている CDABCCDABCCA という文字列の場合、以下のような factor に分割されます。
'C', 'D', 'A', 'B', 'C', 'CDABC', 'C', 'A'
最初の4文字は新規なのでそのまま factor になります。
5文字目の C は1文字目の C に一致しますが、6文字目まで見ると CC に一致する部分文字列は通過していないので結局1文字の factor になります。
6文字目から10文字目の CDABC は 1文字目から5文字目の CDABC に一致しますが、11文字目まで見ると CDABCC に一致する部分文字列は存在するものの、6文字目の C にかぶってしまっているので、 factor は5文字ぶんになります。
11文字目の C 、12文字目の A も一致するのは1文字だけなので1文字の factor になります。
LZ77 の詳細については LZ圧縮：LZ77とLZ78、そしてLZD を参照してください。
FZ77 から string attractors を生成する方法
実は LZ77 の各 factor の最後の位置がそのまま string attractors となっています（！）。
つまり、ある文字列が LZ77 で $\gamma$ 個の factor に分割できるなら、その文字列からは少なくともサイズが $\gamma$ の string attractors を作ることができるわけです。
本当かどうか確認するために、先ほどのコードで検証してみましょう。
text = 'CDABCCDABCCA'
sa_list = [0, 1, 2, 3, 4, 9, 10, 11]
print_string_attractors(text, sa_list)
print('is_valid: {}'.format(is_string_attractors(text, sa_list)))
実行結果は以下の通り。確かに string attractors であったことがわかります。
% pipenv run python -m string_attractors.sample
[C][D][A][B][C]CDAB[C][C][A]
is_valid: True
FZ77 から string attractors を生成するコード
実際に様々な文字列を LZ77 で factor に分割し、そこから string attractors を生成する、というのをやってみます。
LZ77 の各 factor を (参照先の先頭位置, 参照先の末尾位置+1, factor の文字（factor が新規の文字だった場合）) という3つ組で表現しています。この3つ組を directive とよんでいます。
それぞれの対応付けは以下のようになります。
factor_list: ['C', 'D', 'A', 'B', 'C', 'CDABC', 'C', 'A']
directive_list: [(0, 1, 'C'), (1, 2, 'D'), (2, 3, 'A'), (3, 4, 'B'), (0, 1, None), (0, 5, None), (0, 1, None), (2, 3, None)]
string_attractor_list: [0, 1, 2, 3, 4, 9, 10, 11]
文字列から、 directive のリスト（及び string attractors ）を作るために、以下のような LZ77 クラスを書いてみました。
class LZ77:
__slots__ = ['directive_list']
def __init__(self, text: str) -> None:
self.directive_list = self._make_directive_list(text)
@property
def string_attractor_list(self) -> List[int]:
'''
string attractor のリストを取得します
'''
index = -1
string_attractor_list = []
for begin, end, ch in self.directive_list:
index += end - begin
string_attractor_list.append(index)
return string_attractor_list
def _make_directive_list(self, text: str) -> List[Tuple[int, int, Optional[str]]]:
directive_list: List[Tuple[int, int, Optional[str]]] = []
begin = 0
while begin < len(text):
index = begin
subtext = text[begin]
ch: Optional[str] = text[begin]
for end in range(begin + 1, len(text) + 1):
new_subtext = text[begin:end]
new_index = text.find(new_subtext)
if new_index == -1 or new_index + len(new_subtext) > begin:
break
index = new_index
subtext = new_subtext
ch = None
directive_list.append((index, index + len(subtext), ch))
begin += len(subtext)
return directive_list
LZ77 を扱うクラスができたので、様々な文字列を渡して実験をしてみます。
text_list = [
'CDABCCDABCCA',
'abracadabra',
'みるみるミルキィ',
'ケアルケアルラケアルダケアルガケアルジャ',
'働きたくない私は働きたくない私の働きたくない気持ちを大切にして働きたくない',
]
for text in text_list:
sa_list = LZ77(text).string_attractor_list
print_string_attractors(text, sa_list)
print('is_valid: {}'.format(is_string_attractors(text, sa_list)))
実行結果は以下の通り。確かに string attractors であったことがわかります。
% pipenv run python -m string_attractors.sample
[C][D][A][B][C]CDAB[C][C][A]
is_valid: True
[a][b][r][a][c][a][d]abr[a]
is_valid: True
[み][る]み[る][ミ][ル][キ][ィ]
is_valid: True
[ケ][ア][ル]ケア[ル][ラ]ケア[ル][ダ]ケア[ル][ガ]ケア[ル][ジ][ャ]
is_valid: True
[働][き][た][く][な][い][私][は]働きたくない[私][の]働きたくな[い][気][持][ち][を][大][切][に][し][て]働きたくな[い]
is_valid: True
こうして様々な文字列から string attractors を生成してみると、重複した部分文字列（の一部）はいい具合に string attractors から外れていることがわかります。
おわりに
この記事では string attractors の紹介と、その具体例として LZ77 からの生成をやってみました。
string attractors は定義だけ見るとイメージがつきにくいので、具体例を目で見て確認したかったのです。
今回の記事は具体例を示すことに絞っていて、なぜ LZ77 の各 factor の末尾の位置が string attractors になっているのかについては書きませんでした。
論文には今回紹介した内容以外にも様々なことが書かれているので、興味があればぜひ読んでみてください。