3

Web サーバーのログ (apache、nginx など) があるとします。そこから URL の大きなリストを抽出します。

/article/1/view
/article/2/view
/article/1/view
/article/1323/view
/article/1/edit
/help
/article/1/view
/contact
/contact/thank-you
/article/8/edit
...

また

/blog/2012/06/01/how-i-will-spend-my-summer-vacation
/blog/2012/08/30/how-i-wasted-my-summer-vacation
...

['article', '1323', 'view'] または ['blog', '2012', '08', '30', 'how-i-wasted-my -夏休み']。

これらの URL を分析および比較して、URL パス内の「変数」を検出して呼び出すにはどうすればよいでしょうか。つまり、 、 などを認識/article/XXX/viewし/article/XXX/editて/blog/XXX/XXX/XXX/XXX、それらの行に関する情報をログに要約できるようにする必要があります。

変更可能な部分と、似ているが異なるテンプレートを構成する違いの数には、統計的なしきい値が必要になると思います。また、どのデータ構造がこの分析を迅速かつ簡単にするかについても確信が持てません。

スクリプトの出力で、サーバー上に存在するすべての URL テンプレートであると考えられるものを、適切な場合はある程度の信頼値とともに出力したいと考えています。

4

2 に答える 2

2

簡単な解決策は、パスの出現回数を数え、どの値がテンプレートに対応するかを学習することです。ファイルinputに最初のスニペットの URL が含まれているとします。次に、パスごとの訪問を計算します。

awk -F '/' '{ for (i=2; i<=NF; ++i) { for (j=2; j<=i; ++j) printf "/%s", $j; printf "\n" }}' input \
    | sort \
    | uniq -c \
    | sort -rn

これにより、次の結果が得られます。

7 /article
4 /article/1
3 /article/1/view
2 /contact
1 /help
1 /contact/thank-you
1 /article/8/edit
1 /article/8
1 /article/2/view
1 /article/2
1 /article/1323/view
1 /article/1323
1 /article/1/edit

これで、スコア関数f(x, y)に入力できる各パスの重みが得られました。ここで、xはパスのカウントを表し、yはパスの深さを表します。たとえば、最初の行は呼び出しf(7,2)になり、 [0,1]の値、たとえば 0.8 を返し、指定されたパラメーター化が 80% のテンプレートに対応することを示します。もちろん、すべての魔法はfで発生し、アクセスされているパスに基づいて適切な値を考え出す必要があります。適切なfを開発するには、いくつかの小さなデータ セットに対してロジスティック回帰を使用し、それがテンプレートであるというバイナリ機能を適切に予測するかどうかを確認できます。

平凡なルートを取ることもできます: 末尾を削除するだけです。たとえば、すべての値 <= 1 です。

于 2012-08-31T04:58:56.480 に答える
1

DAWGを使用してみませんか？ノードが文字ではなくURIの断片を保存することを除いて。このような：

ここに画像の説明を入力

これは非常に優れたデータ構造です。必要なメモリ量が非常に少なく、トラバースが簡単で、DAG であるため、十分に研究された簡単なアルゴリズムがたくさんあります。また、サンプル内のすべての URL を受け入れ、それ以外はすべて拒否するステート マシンについても説明しています (したがって、実際にそれから正規表現を作成することもできます。これは非常に優れていますが、どうすればよいかを知るほど賢くはありません)。そこから）。

とにかく、このような構造では、問題は「ボトルネック」を見つけることに変わります。そのための適切なアルゴリズムがあると思いますが、変数が大きく変化する十分な大きさのサンプルでは、​​基本的には次のようになります。特定の深さでノードが多いほど、可変部分である可能性が高くなります。

それを行うためのおそらく単純なアプローチは次のようになります。開始部分ごとに個別の DAWG を保持すると、DAWG の平均幅 (深さに基づいて重み付けされる可能性があります) を見つけることができます。レベルの幅がその平均を上回っている場合、平均からの距離に応じた確率を持つ変数と見なします。この時点で、統計の力を十分に発揮できるでしょう。幅の分布をモデリングします。

このアプローチは、「shop/?/?」のように、同じ部分で始まる独立したパターンではうまくいきません。および「ショップ/管理者/?/編集」。これは、ある種のスライディング ウィンドウを使用して、DAWG の一部のみを一度に常に調べるなど、より動的な方法で DAWG-s を調べることで軽減できる可能性がありますが、その方法はわかりません。ああ、最初の部分が変数の場合、全体がひどく失敗しますが、ありがたいことにまれです。

また、同じレベルのすべてのノードが数値を持つ (変数である可能性が高い) など、特定のささいなことに注意することもできます。DAWG を構築する前に、サンプル内の一般的な日付パターンを確実にチェックし、それらを因数分解します。ブログのようなパターンを扱いやすくします。

（ああ、「アルゴリズム」タグを追加すると、おそらく質問にもっと注意が向けられるでしょう。）

于 2012-09-02T01:08:55.527 に答える