ストリーミングデータを格納

Question

ストリーミングデータ（10分ごとに10ミリ秒のストリング）を仮定すると、2つのストリングが全く同じ文字であるが異なるオーダーであれば、一度。

2つの文字列がO（n）時間で動作するこの基準を満たし、各文字列の文字の頻度ヒストグラムを作成し、それらのヒストグラムが同じかどうかを確認するソリューションがあります。しかし、新しい文字列を（< = 10 M）の文字列と比較しなければならないので、これはうまくいきません。私は、各文字列をヒストグラムとして保存し、それらのサイズに基づいて異なるブロックでそれらを区切ると、それはより効率的なものにすることができますが、それでもなお巨大な時間の複雑さを持つことができます。ヒストグラム入力（文字列： "cacao" - >ヒストグラム： "a2：c2：o1"）で動作する完璧なハッシュ関数を持つことが理想的です。

Answer 1

文字列が十分に短い場合は、ソートされた文字列を比較することは、ヒストグラムを比較するよりも速いかもしれません（チェックする価値があります）。ソートは一度だけ実行されることに注意してください。ただ、マップのいくつかの種類に分類した文字列を配置します。

Answer 2

私はtrieのわずか仕立てバージョンは実際にあなたが興味を持っているものであろうと想像ハッシュマップ、ツリーマップなど

利点：

• それはそれはあなたがしたい場合は、文字列
• を挿入するためにOの最悪の場合パフォーマンス（k）を持っている
• あなたのトライで文字列の出現を検索するための時間O（m）をとります特定の部分の出現数を追跡するために、端末文字列に達すると各ノードを増加させることができます（端末 "thou"、 "考え"などの出現を追跡できるように）

欠点（S）：

• これはメモリ集約することができます。あなたは各単語の各文字を格納する必要がありますリンクは、異なるフレーズと各単語に描か