たとえば、一連の文字列があるとします。
"entrance",
"scent",
"transcend".
初期文字列を構築するために使用できる部分文字列の最適な「レキシコン」を見つけたいと思います。基準は、レキシコンとそのレキシコンを使用する文字列の両方を格納するために必要なメモリの最小量です。
たとえば、指定された文字列のセットの場合、部分文字列の最適なレキシコンは次のようになります。
"scen" = 1,
"tran" = 2,
"en" = 3,
"ce" = 4,
"t" = 5,
"d" = 6
次の方法でエンコードされた文字列の初期セットを使用します (それぞれ\Nがレキシコンからの文字列 N への参照を表します)。
\3\2\4
\1\5
\2\1\6
元の文字列の 22 文字 + 元のアルファベットを構成する 8 文字に対して、文字列を作成するために使用される合計 8 つの参照 + レキシコンを格納するために必要な 14 文字。フットプリントの正確な式が必要な場合は、 と仮定しsizeof( reference ) == sizeof( char )、1 つの文字列 (エンコードされた文字列とレキシコン内の両方) のフットプリントは であり、length of string * sizeof( char or reference )追加のオーバーヘッドはありません。
この問題を解決するための最適なアルゴリズムは何ですか? このアルゴリズムには確立された名前がありますか? NP困難ですか？もしそうなら、最適ではないが多項式の解はありますか?
編集:私が思い付くことができる最善の解決策は次のとおりです:文字列の初期セットで最長の共通部分文字列を見つけます。(substring_length - 1) * total_occurrences_of_it_in_the_set - substring_lengthその置換によって保存された文字/参照の数を考慮して、その部分文字列のスコアを とします。次に、すべての小さな部分文字列 (長さ 2 まで) を見つけて、同じ方法でスコアを計算します。この方法で見つかったすべての部分文字列の中で、最大のスコアを持つ部分文字列が勝ち、レキシコンに入ります。次に、文字列の最初のセットで部分文字列がそれへの参照に置き換えられ、文字列のセットに単一の文字とレキシコン参照のみが含まれるまでプロセスが繰り返されます。その後、残りのすべての単一文字をレキシコンに導入し、それらをセット内の参照に置き換えます。スコアリングの説明は次のとおりです。substring_length代わりに参照を追加し (したがって)、部分文字列を格納するために文字が-1必要です(したがって)。substring_length-substring_length
あなたが考えることができるより良いアプローチはありますか？