最近、（おそらく）不定詞からすべての可能な単語形式を生成できる形態学的辞書を洗練するために、ロシア語のかなり膨大な頻度の辞書が必要でした。 頻度辞書は非常に単純なものであり、その中の単語は、分析されたテキストで出現する頻度によって順序付けられています。
タスク、それは非常に単純に思え、おそらく最前線でプログラミングを勉強するときに解決されるでしょう。 しかし、このようなかさばるライブラリの分析、および私が使用するライブラリは157ヘクタール以上に及ぶため、平均的な家庭用コンピューターのリソースは十分にtight迫しています。 より正確には、ライブラリは0.5〜2 GBの50個のzipアーカイブに保存され、各アーカイブにはfb2形式の20〜3万点の作品が含まれています。 圧縮された形式では、重量は60 GBです。
この問題はc＃で解決されました。 夕方にパフォーマンスを開始して朝に結果を得ることができるように、結果は適切な時間で取得する必要があります。
ソリューションを検索する
配列
「額」と呼ばれるものを解決する最も明白な方法は、最初の2つの配列-言葉、2番目の数-です。 新しい単語に出会った場合、最初の配列にない場合は最初の配列に追加し、最初の単語が見つかった場合は2番目の配列のインデックスに追加します。 このオプションを試した後、私はすぐに失望しました。数時間後、プログラムは最初のアーカイブの前半にきしみました。 プロのプログラマーは、おそらくこのアプローチをすでに笑っているでしょう。 しかし、私は告白します-私はキャッチが私を待っているとさえ想像しませんでした。
それから私は検索し始めました-プログラムが呼吸するのを妨げる非常にボトルネックはどこにありますか。 ボトルネックは、新しい単語を追加したときでした。 配列を整然とした状態に保つには、単語を真ん中のどこかに挿入する必要があり、場合によっては最初に挿入する必要があります。 これを行うには、配列の各要素を選択した位置の右側に右にシフトする必要があります。 数百万の単語になると、このアクティビティは処理者にとって非常に骨の折れる作業となり、復venが必要になり、プログラムの完了を今後数週間延期します。
順序付きリスト
各要素を単純にその構造の最後に追加するが、同時にそれらを順序付けることができるようなデータ構造を探す必要がありました。 次に、順序付きリストに出会いました。 順序付きリストのセルには、データ自体と別のセルへのポインターが格納されます。 すべてが素晴らしく、新しい単語を追加して2つのインデックスを変更するだけです。前の単語のインデックスはこれを示し、この単語のインデックスは以下を示します。 しかし、これは不運です。そのようなリストでの検索は、非常に計算が必要です。 順序付けられた配列で、途中から検索を開始し、1回の反復で半分に分割できる場合、順序付けられたリストでは、ボール全体で適切な場所が見つかるまで、スレッドのようにポインターからポインターに沿って登る必要があります。 私はこのオプションを試しませんでした。前回の失敗で教えられたので、すぐに待ち伏せを嗅ぎました。
バイナリ検索ツリー
数時間後に次のデータ構造が見つかりました。 バイナリ検索ツリーに出会いました。 さまざまなオプションについて少し読んだ後、私はソビエトの科学者アデルソン・ウェルスキー・ゲオルギー・マクシモヴィッチとランディス・エフゲニー・ミハイロヴィチによって作成された自己バランスAVLツリーに落ち着き、姓から名前を継承しました。
バイナリツリーの構造は順序付きリストに似ていますが、いくつかのリーフ（いわゆるリーフ）を除く各要素は2つの要素を参照します。 ルート要素は、順序付けられた配列の中央にある要素です。 さらに、小さい要素（左）と大きい要素（右）を参照します。左ブランチのすべての要素がこれよりも小さく、右ブランチのすべての要素がより多くなることが保証されています。 ここまで来た左または右の要素を調べたところ、同じ階層が表示され、2つの要素も参照します。左のブランチも小さく、右のブランチは大きくなっています。 そのようなツリーのバランスをとる方法を理解するには、対応する記事を読むことをお勧めします 。例： AVL-trees バイナリ検索ツリーが私の要件を完全に満たしていることに注意することが重要です。 新しいアイテムのクイック検索とクイック追加。
結果
その結果、最適化にさらに数時間を費やした後、アーカイブをRAMに解凍し、さまざまな単語の頻度をカウントし、AVLツリーを使用してデータを処理するマルチスレッドアプリケーションを得ました。
ここに、プログラムの結果に関する数行、左側の単語、右側の頻度があります。 これらは、さまざまな長さの最も一般的な単語です。
- i 34361402
- 36192092
- 52479822から
- 126422246で
- および158458227
...
- によって23978868
- 彼は32602346です
- 次に42163693
- 83001625で
- いいえ97183097
...
- すべて19576264
- これは21318968です
- その27719894
- 30228770など
- その63106338
...
- でも6789652
- 6832494でした
- 7750404の場合
- 私12381969
- 15450767でした
...
- 5455561があります
- とても5,477,013
- 時間6317279
- とき9788599
- 9987225へ
...
- 嫌い296
- 高品質の350
- エクセレンス384
- 優秀489
- 卓越した3739
...
- 嫌い46
- 嫌い52
- 民間企業60
- 卓越91
- 国民社会主義96
合計で、950万語が受信され、分析は8482秒続き、アンパックされたテキストの平均処理速度は18.57 mb / sでした。
これで、データを使用して形態の語彙を絞り込むことができます。語彙を取得したら、「周波数アナライザ」を改善することができます。 同様のルートワードをグループ化できます。 さらに、この作業には、さまざまなエンコーディングなどを備えた「周波数アナライザ」が必要です。 次は文の解析です。 最後に、何らかの適切なセマンティックネットワークを取得したいと思います。
私の「レポート」はプログラミングと言語学の両方のトピックをカバーしているという事実にもかかわらず-筆記の不正確さ（特に句読点）や問題の最もスムーズな解決策を非難しないようお願いしますが、これらのエラーを指摘するか、よりエレガントな解決策を提案するようお願いします、嬉しいです。
どうもありがとう。