4

1 行に 1 単語の大きなファイルがあります。ファイル全体がソートされたので、圧縮する必要があります。単に GZIP を使用するだけで、かなり良い結果が得られます。ただし、ソートされた単語のリストを扱っていることを知っていると、もっとうまくできるかどうか疑問に思っています。

並べ替えられた単語のリストのスニペットを次に示します。

[...]
ABAISSAT
ABAISSATES
ABAISSE
ABAISSEE
ABAISSEES
ABAISSEMENT
ABAISSEMENTS
ABAISSENT
ABAISSER
ABAISSERA
ABAISSERAI
ABAISSERAIENT
ABAISSERAIS
[...]

プレフィックスを使用してファイルを圧縮すると、GZIP よりも良い結果が得られますか?

[...]
ABAISS AT ATES E EE EES EMENT EMENTS ENT ER ERA ERAI ERAIENT ERAIS
[...]

私が説明している種類の圧縮を使用して、単語のリストを圧縮できるアルゴリズムは何ですか? データを圧縮する方法は他にありますか?

PS私はTrieの使用について考え、それを実装しました。Trie is memory の最終的なサイズは、リスト自体とほぼ同じ大きさであり、リストをロードする時間は非常に長くなりました。これらの理由から、私はその道を歩まないことに決めました。

4

2 に答える 2

6

フロント圧縮のようなものを考えているようです。各エントリは、エントリが前のエントリと共有する左端の文字数のカウントであり、その後に残りの共有されていない文字が続きます。データを使用した例:

0, ABAISSAT
8, ES
6, E
7, E
etc.

結果には gzip (またはその他の圧縮) が必要です。

于 2012-06-27T05:43:58.140 に答える
1

連続する 2 つの単語の差を計算する関数を作成し、それをリスト全体に適用して GZIP 圧縮することもできます (また、最初の単語を開始点として保存する必要があります)。

関数はどのように見えますか？よくわかりませんが、それを試してみる必要があります。

アイデアは、連続した単語間の違いは (情報の点で) 小さいということです。

これは、ビデオ圧縮で使用されるのと同じ概念のアイデアのようなものです (とにかく、テクニックの 1 つです) - 連続するフレームは非常に似ています。

于 2012-06-27T05:28:12.673 に答える