4

実装するには次の要件がありますが、これは私に「パズル」をもたらします:
Web サーバーがあり、さまざまなユーザー (認証済みおよびログイン済み) が Web サイトのさまざまな領域にアクセスします (つまり、さまざまなリンクをたどって閲覧します)。これらのアクション (またはブラウジングと呼びます) は、ログ ファイルに記録されています。
したがって、これらのファイルには、ユーザーがサーバーにアクセスした日付と、ユーザーがアクセスしたさまざまなリンク (URL) が記録されます。
レコードの簡略化された形式 (説明目的) は次のようになります
Timestamp User-Name URL-1
。 

Date-1 John    URL-1  
Date-1 Nick    URL-1  
Date-1 John    URL-2  
Date-1 George  URL-1  
Date-1 George  URL-2
Date-1 Eve     URL-2  
Date-1 Nick    URL-2  
Date-1 John    URL-3
Date-1 George  URL-3  
Date-1 John    URL-5  
Date-1 Nick    URL-3  
Date-1 Bill    URL-2  
Date-1 George  URL-5
Date-1 Nick    URL-5      
Date-1 Eve     URL-3                
Date-1 Eve     URL-5

など、数百/数千のエントリが存在する可能性があります。サイトの有効な URL を意味するので
、John と Eve では、両方が同じリンクにアクセスしたことを意味します。この例では、一般的にアクセスされる URL シーケンスの最大数を示しています。 URL-1URL-1URL-2,URL-3,URL-5

問題:この情報を使用することに興味があり、ログ ファイルがカバーする日時範囲全体および/または特定の日時範囲の両方で、すべてのユーザーがアクセスする URL の最も頻繁にアクセスされるシーケンスを見つけます。
これをどのように行うかについて、最初の考えがあります。たとえば、最初に考えたのは、すべてを格納しHashMaps、各外観のカウンターを含め、マップ エントリをループして最大値を見つけることでしたが、スペースとランタイムの両方で大きなオーバーヘッドがあるように思えます。
また、これについて考えれば考えるほど、たとえば文字列パターン マッチングのような「標準的な」ソリューションがあるように思えますKMP algorithm。
次に、接尾辞ツリーなどを使用できるかどうかを考えましたが、トライを実装することしか知らないので、これのスペースの複雑さは次のようになると思いますO(N^2). 圧縮されたバージョンがあることは知っていますが、それらは複雑すぎると思います。この問題に対するより良い/標準的な解決策がある場合に備えて、時間を無駄にしたくありません.

提案/入力は大歓迎です。

4

2 に答える 2

3

さて、あなたは、どんな提案/入力も高く評価されると言いました。. それでは、簡単に次のアルゴリズムをお勧めします。

  1. 必要な日付範囲のログ ファイルをフィルター処理し、各ユーザーの URL シーケンスを並行して収集しますList。

  2. ステップ 1. の後、大きなシーケンスのセットができました。このステップでは、この問題は文字列のリストで最も一般的な部分文字列を見つけるタスクと同等です。これはすでに解決済みの問題です。

UPD:その後、それぞれURLを a のように検討"char"して"string"ください。

于 2013-01-11T18:56:36.993 に答える
0

申し訳ありませんが、ログ ファイルにあるデータでこれを達成することは不可能だと思います。

私が見る問題は、最も使用されているURL のシーケンスを探していることです。あなたの質問では、userId のみがあり、セッション インジケーターはありません。つまり、単一のセッション中に彼らが何をしていたかを確実に見つけることができません。彼らがたどっていた道を見つけようとするとき、あなたは異なるセッションを混ぜているかもしれません。

各セッションのパスを作成し、いくつかの (まだ不明な) プログラムを実行して、最も使用されている「アーク」を見つけることができる sessionId があるとします。

于 2013-01-11T19:17:07.570 に答える