[解決済み] 検索語句の上位10位を見つけるアルゴリズム

質問

今、面接の準備をしているのですが、以前、面接で聞かれたこんな質問を思い出しました。

あなたは、Google の検索語句のトップ 10 を継続的に表示するソフトウェアを設計するよう依頼されました。あなたは、Google で現在検索されている検索語のリアルタイムのストリームを無限に提供するフィードにアクセスすることを許可されています。これを実装するために、どのようなアルゴリズムとデータ構造を使用するかを説明しなさい。あなたは2つのバリエーションを設計することになります。

(i) すべての時間（すなわち、あなたがフィードを読み始めてから）のトップ10の検索語を表示する。

(ii) 1時間ごとに更新される、過去1ヶ月の検索語句の上位10件のみを表示する。

トップ10リストを得るために近似値を使用することができますが、選択を正当化する必要があります."。

私はこの面接で爆死してしまい、未だにこれをどのように実装すればいいのか本当に分からないのです。

最初の部分は、無限リストの連続的に成長するサブシーケンスで最も頻繁に使用される10個の項目を尋ねます。私は選択アルゴリズムを調べましたが、この問題を解決するためのオンライン版を見つけることができませんでした。

2 番目の部分は有限リストを使用しますが、処理されるデータ量が多いため、1 か月分の検索語をすべてメモリに保存し、1 時間ごとにヒストグラムを計算することは実際には不可能です。

この問題は、トップ 10 リストが継続的に更新されているという事実によってさらに難しくなっており、何らかの方法で、スライド ウィンドウ上でトップ 10 を計算する必要があります。

何かアイデアはありますか？

どのように解決するのですか？

さて、非常に多くのデータがあるように見えますが、すべての周波数を保存するには、おそらく法外なコストがかかるでしょう。 データ量が非常に多い場合 の領域に入ります。 データストリームアルゴリズム .

この分野の有用な書籍。 Muthukrishnan - "Data Streams: Algorithms and Applications"

上記の中から選んだ、今回の問題に密接に関連する参考文献です。 Manku, Motwani - "Approximate Frequency Counts over Data Streams" [pdf].

ちなみに、スタンフォードのMotwaniは、(編集)非常に重要な "Randomized Algorithms" の著者です。 の本の著者です。 この本の第11章では、この問題を扱っています。 . 編集する 申し訳ありませんが、悪い参照、その特定の章は、別の問題である。確認した後、私は代わりにお勧めします の 5.1.2 節を参照してください。 Muthukrishnan の 本 を、オンラインで入手することができます。

へー、いいインタビューの質問だね。