アーカイブ方法
- 前述のように、 テキストは単語で構成されています。 実験的なアーカイバでは、文字はビットシーケンスに常に置き換えられます。これは、文字がほとんどなく、コードが使用するメモリスペースが少ないためです。
A = 00、B = 01、C = 10、G = 110
各文字が何百万回も発生する巨大な本を圧縮する必要がある場合、保存されているメモリも巨大です。 ただし、この方法は文字だけで機能するわけではありません。 単語もテキストの繰り返し単位であり、見かけほど多くはありません。 Dahlの辞書には約200,000の単語が含まれており、平均的な匿名の人は日常会話で3〜4000語しか使用していません。 もちろん、ロシア語では単語を曲げたり、活用したりできますが、 tribayana.ru /？p = 4143によると、Leo Tolstoyの「戦争と平和」には38,873個の元のトークンしかありません。 1つのレジスタ（方法2を参照）と固定コード長により、各ワードは2バイトでエンコードされます。 ソースファイルがUTF-8で記述されていると便利です。UTF-8では、2バイトはキリル文字の書記素です。 ロシア語の平均単語長は7.2文字です。 つまり、ゲインは7.2倍です。 この記事では、ファイル内で見つかった単語のリストを「辞書」と呼びます。
「パパ」= 0、「スープ」= 10、「ハーブ」= 11
- アーカイバを作成する場合は、エンコードを制限します。 通常、ファイルをエンコードするためにすべてのUnicode文字は必要ありません。 ほとんどの場合、ASCIIページとロシア語のアルファベットのみが役立ちます。 256文字-それほど多くはありませんが、 TrllServはサンドボックスを無駄に見ませんでした。 文字は大文字と小文字です。 象形文字については今のところ忘れてください。 小文字がテキストの基礎である場合、大文字はほとんどの場合文ごとに1つかかります。 さらに、通常のルールに従ってコードテーブルを作成する場合、かなり長いビットシーケンス（プレフィックスエンコーディングを使用）を選択する必要があり、さらに悪いことに、「辞書」には大文字と小文字が異なるだけの同じ単語が入力されます。 多くのメモリが無駄になります。 私たちにとって、「」と「」はまったく同じ文字であり、マシンにとっては-コード表とはまったく異なる2つの値です。 不要な単語を生成しないように、すべての文字はすでにアーカイバー自体にペアで保存されています。 彼はすべて大文字を小文字に落とします。 これに加えて、大文字が立っていたテキストの単語がマークされ、その番号が各単語に保存されます。 ここで大文字は常に単語の先頭に表示され、「Camel Style」は「Camel」と「Style」の別々のトークンに分割されます。 そのため、大文字の数を含むテキスト内の単語番号は一意にデコードされます。
「始まり」-1
CAPS-4
「ZEAD」-3
「OPTOVIC」：「OP」-1、「TOv」-2、「Ik」-1
- 各非文字（算術または句読点）は（1文字から）個別のトークンによってエンコードされます。 スペースのみが特別にエンコードされます。 ほとんどの場合、単語はスペースで区切られ、それぞれを手動で挿入しても意味がありません。 標準を確立するだけで十分です。特に指定のない限り、2ワード間でデコードするときは1つのスペースを意味します。 それ以外の場合は、アーカイブ内のスペースで示されます。 そのような例外がいくつかあります。
- アーカイブ内の一連のスペース（1つ以上）は、テキスト内の同じ一連のスペースを意味します。 厳密なインデントでpythonスクリプトを圧縮するときに便利です。
「Word1 ____ word2」->「word1」+「____」+「word」
*下線-スペース
- アーカイブ内の2つの単語間のスペースは、テキスト内の2つの単語の間にスペースがないことを意味します。 はい、そうです。 松葉杖からラクダスタイル。
"ZABBOCHERG"-> "for" + "" + "bbo" + "" + "che" + "" + "rg"
* 4つの単語すべてにマークが付けられ、それぞれの大文字の数が保存されます
- デフォルトでは、文字以外の文字は左側の単語の右側に「アタッチ」され、右側の単語（または文字）とスペースで区切られます。 アーカイブ内のスペースはルールを変更します。
「硝酸塩-、_砂糖」->「硝酸塩」+「、」+「砂糖」
「コンマ_、_サー」->「コンマ」+「」+「、」+「サー」
「ちょっと-田舎者！」->「ちょっと」+「、」+「」+「田舎者」+「！」
「Zrolilit _、-the boyboy」->「zatrolil」+ "" + "、" + "" + "schoolboy"
*ここで、「_」はスペース、「-」は不在です。 Habrの機能により、自動修正。
- アーカイブの先頭にある1つのスペース（最初の文字）は、テキストの先頭にある1つのスペースを意味します。
[テキストの始まり] "first"-> [アーカイブの始まり] "" + "first"
一連のスペースは、単一の自動スペースを置き換えます。
- アーカイブ内の一連のスペース（1つ以上）は、テキスト内の同じ一連のスペースを意味します。 厳密なインデントでpythonスクリプトを圧縮するときに便利です。
- 数字は文字としてエンコードされ、数字は単語としてエンコードされます。 数字の付いた文字は連結されます。 数字の大文字小文字は使用できません。
「265」->「265」
228条-> 228条
Adyn1111マルハナバチ-> Adyn1111マルハナバチ
これらの4つの方法は、損失や歪みなしにソースファイルの「折りたたみ」を提供します。
一般的なアルゴリズム
それで何が起こっているのでしょうか？
- テキストはソースファイルから読み取られ、パーサーによって並行してカットされ、「辞書」がコンパイルされ、「辞書」インデックスがテキスト自体の単語に置き換えられます。 同時に、各「語彙」単語の出現頻度が計算され、大文字が収集されます。
- 「辞書」は、発生頻度でソートされます。 プログラムの実装では、インデックスリストが加速のためにソートされます。
- 「アルファベット」が形成されます-テキストに存在するすべての文字のリストは、「辞書」内の文字の出現頻度でソートされます。 「辞書」の文字の代わりに、「アルファベット」のインデックスが置換されます。 実装では、ワイルドカードリストもソートされます。
- 「アルファベット」と「辞書」は、たとえばハフマンによると、何らかの方法でエンコードされます。
- 記録用のアーカイブファイルが開きます。 順序付けられた「アルファベット」のコード表が導入されました。 終端は垂直タブで区切られています。
- 「アルファベット」コード表を使用して、「辞書」コード表がビット単位で入力されます。 終端は垂直タブで区切られています。
- 大文字のインデックスとその数は、複数の単語がある場合に導入されます。 終端は垂直タブで区切られています。
- コードブック「辞書」を使用して、ビットごとにテキストが入力されます。
実装
図は悲しいです。 コードを書いている間、混乱しました。 この記事では、アルゴリズムは単純に見えますが、機械には理解できるようになっており、人間には理解できません。 実際、すべての順列とインデックスは、ポインターのひどいピラミッドです。 彼はできる限りのことをしましたが、ほとんど何でもできました。 このプログラムは機能し、ほとんど準備ができています。「辞書」と「アルファベット」のプレフィックスエンコーディングのアルゴリズムだけを実装しているわけではありません-最も難しいのではなく、最も重要な部分です。 これがないと、アプリケーションは機能し、残りの機能を正しく実行しますが、アーカイブのサイズはわずかに減少します。 ナイアシルを選ぶ理由 はい、恥ずかしいです。 ポインターの配列で迷子になったため、エンコードしませんでした。 あなたの創造物を解き、リファクタリングするには時間がかかります。そして私の専門の人々は今それを非常に欠いています。 Minobraコース：知識が少なく、準備のための型テストが増えます。 同僚と一緒にプロジェクトを終了し、彼らに助けを求めることは可能ですが、結局のところ、それらのほとんどのアーカイバアルゴリズムは致命的です。 しかし、私は何であるかを示します。 「はじめの部分」なしでは「戦争と平和」は見つからなかったので、「マスターズとマルガリータ」のアーカイブを作成しました。 より少ないページがより理にかなっています。
元のサイズ：1.4 MB。
アーカイブサイズ：1.6 MB。
ユーレカ！ アーカイバはファイルサイズを増やしました。 コーディングがなければ、意味がありません。 具体的な例を考えてみましょう。
上記の例外を含む2行：
JLK ijo、ewrt lhuiOij jfds + huk uih EGE！*
897 y98 uih-124 jfds JLK
これになった：
もちろん、適切なコーディングがなければ圧縮の問題はありませんが、アーカイブ構造（本質）は明確に示されています。
一般に、試験の進行中に、タンバリンで踊るのが好きで、松葉杖用の松葉杖を書く準備ができている良い匿名の人がいる場合、Cのソースは次のとおりです。
PS実装の準備ができました。
愛をこめて。