4

私は、既存の用語と重複しないことを期待して、自分自身を転がす用語ループを思いついた。基本的に、私は印刷されたテキストのループを見つけるためのアルゴリズムを考え出そうとしています。

単純なものから複雑なものまでのいくつかの例

例1

与えられた：

a a a a a b c d

私は言いたい：

5x(a) b c d

またはアルゴリズム的に：

for 1 .. 5
    print a
end
print b
print c
print d

例2

与えられた：

a b a b a b a b c d

私は言いたい：

4x(a b) c d

またはアルゴリズム的に：

for 1 .. 4
    print a
    print b
end
print c
print d

例3

与えられた：

a b c d b c d b c d b c e

私は言いたい：

a 3x(b c d) b c e

またはアルゴリズム的に：

print a
for 1 .. 3
    print b
    print c
    print d
end
print b
print c
print d

それは私が知っているアルゴリズムを思い出させませんでした。問題のいくつかはあいまいになる可能性があるように感じますが、今のところ、解決策の1つを見つけるだけで十分です。効率はいつでも歓迎ですが、必須ではありません。これどうやってするの？

編集

まず第一に、すべての議論に感謝します。ロゼッタのLZWアルゴリズムを採用し、入力で実行しました。

abcdbcdbcdbcdef

それは私に与えました：

a
b
c
d
8  => bc
10 => db
9  => cd
11 => bcd
e
f

私が持っている辞書：

a a
c c
b b
e e
d d
f f
8 bc
9 cd
10 db
11 bcd
12 dbc
13 cdb
14 bcde
15 ef
7 ab

圧縮には適しているように見えますが、私が望んでいたものではありません。私が必要としているのは、私の例からのアルゴリズム表現の圧縮のようなものです。

  • 後続のシーケンス（シーケンスが繰り返されている場合、間に他のシーケンスはありません）
  • 辞書はなく、ループのみ
  • 還元不可能
  • 最大シーケンスサイズ（アルゴリズム表現を最小化する）
  • ネストされたループが許可されているとしましょう（コメントで前に言ったこととは反対に）
4

1 に答える 1

2

私は、最大シーケンスサイズを与えるアルゴリズムから始めます。アルゴリズム表現を常に最小化するとは限りませんが、近似アルゴリズムとして使用できます。または、最適なアルゴリズムに拡張することもできます。

  1. LCP配列とともに、テキストの接尾辞配列を作成することから始めます。
  2. LCP配列のインデックスの配列を並べ替えます。LCP配列のより大きな要素のインデックスが最初に来ます。これにより、同じ長さの繰り返しシーケンスがグループ化され、最大シーケンスサイズから始めて貪欲な方法でシーケンスを処理できます。
  3. LCP値でグループ化された接尾辞配列エントリを抽出し（グループによって、選択されたLCP値を持つすべてのエントリと、より大きなLCP値を持つすべてのエントリを意味します）、テキスト内の位置で並べ替えます。
  4. 位置の差がLCPと等しくないエントリを除外します。残りのエントリについては、LCPに等しい長さのプレフィックスを取得します。これにより、テキスト内のすべての可能なシーケンスが得られます。
  5. 順序付けられたコレクション（たとえば、バイナリ検索ツリー）に、開始位置でソートされたシーケンスを追加します。シーケンスは、ソートされたLCPに表示される順序で追加されるため、長いシーケンスが最初に追加されます。シーケンスは、それらが独立している場合、または一方が他方の中に完全にネストされている場合にのみ追加されます。交差する間隔は無視されます。たとえば、caba caba bab順番abにと交差するcabaため、無視されます。ただし、のcababa cababa babab1つのインスタンスabが削除されると、2つのインスタンスは完全に大きなシーケンスの内側にあり、2つのインスタンスは完全にその外側にあります。
  6. 最後に、この順序付けられたコレクションには、アルゴリズム表現を生成するために必要なすべての情報が含まれています。

例：

Text          ababcabab

Suffix array  ab abab ababcabab abcabab b bab babcabab bcabab cabab
LCP array       2    4         2       0 1   3        1      0

Sorted LCP            4 3 2 2 1 1 0 0
Positional difference 5 5 2 2 2 2 - -
Filtered LCP          - - 2 2 - - - -
Filtered prefixes   (ab ab) (ab ab)

アルゴリズムのスケッチ。最小限のアルゴリズム表現を生成します。

前のアルゴリズムの最初の4つのステップから始めます。5番目のステップを変更する必要があります。現在、交差する間隔を無視することはできないため、すべてのシーケンスがコレクションに追加されます。コレクションには交差する間隔が含まれるようになったため、間隔ツリーなどの高度なデータ構造として実装することをお勧めします。

次に、ネストされたシーケンスを含むすべてのシーケンスのアルゴリズム表現の長さを、最小のものから再帰的に決定します。すべてのシーケンスが評価されるとき、テキスト全体の最適なアルゴリズム表現を計算します。シーケンスまたはテキスト全体を処理するためのアルゴリズムは、動的計画法を使用します。テキスト/シーケンスの長さに等しい列数とアルゴリズム表現の長さに等しい行数のマトリックスを割り当てます。区間木の順序通りのトラバーサルを実行し、各テキスト位置で可能なすべてのシーケンスでこの行列を更新します。一部のセルに複数の値が可能な場合は、それらのいずれかを選択するか、より長いまたはより短いサブシーケンスを優先します。

于 2012-11-04T17:41:13.923 に答える