percentile | Блог очередного разработчика

Problem:

I have many different URLs in database.

From many sites.

I dont know how these sites work and url structure.

So I need to get 500 URLs from each site then compare and group it by common static part.

Which should be automatically merged via replacing with {var} any dynamic URL parts.

And then get ~10 urls as result.

Final result: reduce database size

Solution:

Here is some kind Proof of Concept

Example with splitting URL by «?»

— Parse parameters.

— Calculate frequency for unique parameter values.

— Get Nth percentile.

— Build URLs and replace parameters which frequency is more than Nth percentile

For small data like here in sandbox 50 percentile is enough to group some URL.

For «big real data» 90-95 percentile.
For example: I use 90 percentile for 5000 links -> result ~200 links

<?php 
$stats = [];

$pages = [
    (object)['page' => 'http://example.com/?page=123'],
    (object)['page' => 'http://example.com/?page=123'],
    (object)['page' => 'http://example.com/?page=123'],
    (object)['page' => 'http://example.com/?page=321'],
    (object)['page' => 'http://example.com/?page=321'],
    (object)['page' => 'http://example.com/?page=321'],
    (object)['page' => 'http://example.com/?page=qwas'],
    (object)['page' => 'http://example.com/?page=safa15'],
]; // array of objects with page property = URL

$params_counter = [];
foreach ($pages as $page) {
    $components = explode('?', $page->page);

    if (!empty($components[1])) {
        parse_str($components[1], $params);
        foreach ($params as $key => $val) {
            if (!isset($params_counter[$key][$val])) {
                $params_counter[$key][$val] = 0;
            }
            $params_counter[$key][$val]++;
        }
    }
}

function procentile($percentile, $array)
{
    sort($array);
    $index = ($percentile/100) * count($array);
    if (floor($index) == $index) {
        $result = ($array[$index-1] + $array[$index])/2;
    } else {
        $result = $array[floor($index)];
    }
    return $result;
}


$some_data = [];
foreach ($params_counter as $key => $val) {
    $some_data[$key] = count($val);
}

$procentile = procentile(90, $some_data);

foreach ($pages as $page) {
    $components = explode('?', $page->page);

    if (!empty($components[1])) {
        parse_str($components[1], $params);
        arsort($params);
        foreach ($params as $key => $val) {
            if ($some_data[$key] > $procentile) {
                $params[$key] = '$var';
            }
        }
        arsort($params);

        $pattern = http_build_query($params);

        $new_url = urldecode('?'.$pattern);

        if (!isset($stats[$new_url])) {
            $stats[$new_url] = 0;
        }
        $stats[$new_url]++;
    }
}

arsort($stats);

var_dump($stats);

<?php

$stats = [];

$pages = [

(object)['page' => 'http://example.com/?page=123'],

(object)['page' => 'http://example.com/?page=321'],

(object)['page' => 'http://example.com/?page=qwas'],

(object)['page' => 'http://example.com/?page=safa15'],

]; // array of objects with page property = URL

$params_counter = [];

foreach ($pages as $page) {

$components = explode('?', $page->page);

if (!empty($components[1])) {

parse_str($components[1], $params);

foreach ($params as $key => $val) {

if (!isset($params_counter[$key][$val])) {

$params_counter[$key][$val] = 0;

}

$params_counter[$key][$val]++;

}

function procentile($percentile, $array)

{

sort($array);

$index = ($percentile/100) * count($array);

if (floor($index) == $index) {

$result = ($array[$index-1] + $array[$index])/2;

} else {

$result = $array[floor($index)];

}

return $result;

}

$some_data = [];

foreach ($params_counter as $key => $val) {

$some_data[$key] = count($val);

}

$procentile = procentile(90, $some_data);

foreach ($pages as $page) {

$components = explode('?', $page->page);

if (!empty($components[1])) {

parse_str($components[1], $params);

arsort($params);

foreach ($params as $key => $val) {

if ($some_data[$key] > $procentile) {

$params[$key] = '$var';

}

arsort($params);

$pattern = http_build_query($params);

$new_url = urldecode('?'.$pattern);

if (!isset($stats[$new_url])) {

$stats[$new_url] = 0;

}

$stats[$new_url]++;

}

arsort($stats);

var_dump($stats);