Informative

Sunday, 16 November 2014

Find Google Page Rank in PHP

<?php

/*
*
* @Author: Zuhair Mirza
* @Implementation Of Google Page Rank in PHP
* @Date : 17-November-2014
*
* Google PageRank (Google PR) is one of the methods Google uses to determine a page's relevance
* or importance. Important pages receive a higher PageRank and are more likely to appear at the top
* of the search results. Google PageRank (PR) is a measure from 0 - 10. Google Pagerank is based
* on backlinks.
*
*/

$url = 'http://en.wikipedia.org/';

$pr = new GooglePageRank();
echo "$url has Google PageRank: " . $pr->get_google_pagerank($url);

class GooglePageRank {

public function get_google_pagerank($url) {

$query = "http://toolbarqueries.google.com/tbr?client=navclient-auto&ch=" . $this->CheckHash($this->HashURL($url)) . "&features=Rank&q=info:" . $url . "&num=100&filter=0";

$data = file_get_contents($query);

$pos = strpos($data, "Rank_");
if ($pos === false) {

} else {
$pagerank = substr($data, $pos + 9);
return $pagerank;
}
}

public function StrToNum($Str, $Check, $Magic) {
$Int32Unit = 4294967296; // 2^32
$length = strlen($Str);
for ($i = 0; $i < $length; $i++) {
$Check *= $Magic;
if ($Check >= $Int32Unit) {
$Check = ($Check - $Int32Unit * (int) ($Check / $Int32Unit));
$Check = ($Check < -2147483648) ? ($Check + $Int32Unit) : $Check;
}
$Check += ord($Str{$i});
}
return $Check;
}

public function HashURL($String) {
$Check1 = $this->StrToNum($String, 0x1505, 0x21);
$Check2 = $this->StrToNum($String, 0, 0x1003F);
$Check1 >>= 2;
$Check1 = (($Check1 >> 4) & 0x3FFFFC0 ) | ($Check1 & 0x3F);
$Check1 = (($Check1 >> 4) & 0x3FFC00 ) | ($Check1 & 0x3FF);
$Check1 = (($Check1 >> 4) & 0x3C000 ) | ($Check1 & 0x3FFF);
$T1 = (((($Check1 & 0x3C0) << 4) | ($Check1 & 0x3C)) << 2 ) | ($Check2 & 0xF0F );
$T2 = (((($Check1 & 0xFFFFC000) << 4) | ($Check1 & 0x3C00)) << 0xA) | ($Check2 & 0xF0F0000 );
return ($T1 | $T2);
}

public function CheckHash($Hashnum) {
$CheckByte = 0;
$Flag = 0;
$HashStr = sprintf('%u', $Hashnum);
$length = strlen($HashStr);
for ($i = $length - 1; $i >= 0; $i --) {
$Re = $HashStr{$i};
if (1 === ($Flag % 2)) {
$Re += $Re;
$Re = (int) ($Re / 10) + ($Re % 10);
}
$CheckByte += $Re;
$Flag ++;
}
$CheckByte %= 10;
if (0 !== $CheckByte) {
$CheckByte = 10 - $CheckByte;
if (1 === ($Flag % 2)) {
if (1 === ($CheckByte % 2)) {
$CheckByte += 9;
}
$CheckByte >>= 1;
}
}
return '7' . $CheckByte . $HashStr;
}

}

Saturday, 31 May 2014

Implementation Of Bellman Ford Algorithm in PHP

<?php

/*
*
* @Author: Zuhair Mirza
* @Implementation Of Bellman Ford Algorithm in PHP
* @Date : 01-June-2014
*
* The Bellman–Ford algorithm is an algorithm that computes shortest
* paths from a single source vertex to all of the other vertices in a weighted digraph
*
*/

define('INFINITY', 10000000);

$matrix = array(
0 => array(0, 3, 4),
1 => array(0, 0, 2),
2 => array(0, -2, 0),
);

$len = count($matrix);

$dist = array();

BellmanFord($matrix, $dist, 0);

// [0, 2, 4]
var_dump($dist);

function BellmanFord(&$matrix, &$dist, $start) {
global $len;

foreach (array_keys($matrix) as $vertex) {
$dist[$vertex] = INFINITY;
if ($vertex == $start) {
$dist[$vertex] = 0;
}
}

for ($k = 0; $k < $len - 1; $k++) {
for ($i = 0; $i < $len; $i++) {
for ($j = 0; $j < $len; $j++) {

echo $i . "--" . $dist[$i] . "<br/>";
echo $j . "--" . $dist[$j] . "<br/>";
echo $matrix[$j][$i] . "<br/>";
echo "-------------<br/>";

if ($dist[$i] > $dist[$j] + $matrix[$j][$i]) {
$dist[$i] = $dist[$j] + $matrix[$j][$i];
echo "------Done-------<br/>";
}
}
}

for ($i = 0; $i < $len; $i++) {
for ($j = 0; $j < $len; $j++) {
if ($dist[$i] > $dist[$j] + $matrix[$j][$i]) {
echo 'The graph contains a negative cycle!';
}
}
}
}
}

?>

Saturday, 3 May 2014

Implementation Of Levenshtein Distance Algorithm in PHP

<?php

/*
*
* @Author: Zuhair Mirza
* @Implementation Of Levenshtein Distance Algorithm (Edit Distance) in PHP
* @Date : 04-May-2013
*
*/

$s1 = "POLYNOMIAL";
$s2 = "EXPONENTIAL";

LevenshteinDistance($s1, $s2);

function LevenshteinDistance($s, $t) {
$m = strlen($s);
$n = strlen($t);

for ($i = 0; $i <= $m; $i++)
$d[$i][0] = $i;
for ($j = 0; $j <= $n; $j++)
$d[0][$j] = $j;

for ($i = 1; $i <= $m; $i++) {
for ($j = 1; $j <= $n; $j++) {

$c = ($s[$i - 1] == $t[$j - 1]) ? 0 : 1;
$d[$i][$j] = min($d[$i - 1][$j] + 1, $d[$i][$j - 1] + 1, $d[$i - 1][$j - 1] + $c);
}
}

printMatrix($d, $s, $t);

return $d[$m][$n];
}

function flip_row_col_array($array) {
$out = array();
foreach ($array as $rowkey => $row) {
foreach ($row as $colkey => $col) {
$out[$colkey][$rowkey] = $col;
}
}
return $out;
}

function printMatrix($d, $str1, $str2) {

$array = flip_row_col_array($d);
echo "<table border = '1'>";
echo "<tr>";
echo "<td>";
echo "</td>";
echo "<td colspan=11>";
echo $str1;
echo "</td>";
echo "</tr>";

$str2 = str_split($str2);

$count = 0;

foreach ($array as $j => $value) {

echo "<tr>";

foreach ($value as $i => $node) {

if ($i == 0):

if ($count == 0):
echo "<td>";
echo "</td>";
else:
echo "<td>";
echo $str2[$j - 1];
echo "</td>";

endif;
$count++;
endif;

echo "<td>";
echo $node;
echo "</td>";
}
echo "</tr>";
}
echo "</table>";
}

?>

Implementation Of Breadth First Search in PHP

<?php

/*
*
* @Author: Zuhair Mirza
* @Implementation Of Breadth First Search in PHP
* @Date : 04-May-2013
*
*/

$g = array(
0 => array(0, 1, 1, 0, 0, 0),
1 => array(1, 0, 0, 1, 0, 0),
2 => array(1, 0, 0, 1, 0, 0),
3 => array(0, 1, 1, 0, 1, 0),
4 => array(0, 0, 0, 1, 0, 1),
5 => array(0, 0, 0, 0, 1, 0),
);

function init(&$visited, &$graph) {
foreach ($graph as $key => $vertex) {
$visited[$key] = 0;
}
}

function breadth_first(&$graph, $start, $visited) {
// create an empty queue
$q = array();

// initially enqueue only the starting vertex
array_push($q, $start);
$visited[$start] = 1;
echo $start . "\n";

while (count($q)) {
$t = array_shift($q);

foreach ($graph[$t] as $key => $vertex) {
if (!$visited[$key] && $vertex == 1) {
$visited[$key] = 1;
array_push($q, $key);
echo $key . "\t";
}
}
echo "\n";
}
}

$visited = array();
init($visited, $g);

breadth_first($g, 2, $visited);
?>

Implementation Of Depth First Search in PHP

<?php

/*
*
* @Author: Zuhair Mirza
* @Implementation Of Depth First Search in PHP
* @Date : 04-May-2013
*
*/

class Graph {

protected $_len = 0;
protected $_g = array();
protected $_visited = array();

public function __construct() {
$this->_g = array(
array(0, 1, 1, 0, 0, 0),
array(1, 0, 0, 1, 0, 0),
array(1, 0, 0, 1, 1, 1),
array(0, 1, 1, 0, 1, 0),
array(0, 0, 1, 1, 0, 1),
array(0, 0, 1, 0, 1, 0),
);

$this->_len = count($this->_g);

$this->_initVisited();
}

protected function _initVisited() {
for ($i = 0; $i < $this->_len; $i++) {
$this->_visited[$i] = 0;
}
}

public function depthFirst($vertex) {
$this->_visited[$vertex] = 1;

echo $vertex . "\n";

for ($i = 0; $i < $this->_len; $i++) {

//d(0,$vertex,$this->_g[$vertex][$i],$i);
if ($this->_g[$vertex][$i] == 1 && !$this->_visited[$i]) {
$this->depthFirst($i);
}
}
}

}

$g = new Graph();
// 2 0 1 3 4 5
//$g->depthFirst(2);
//$g->depthFirst(0);
$g->depthFirst(2);
?>

Monkey Minimum Number of Jumps Algorithm

<?php

/*
*
* Subject : Design & Analysis of Algorithms
*
* Question :
*
Billo is a monkey trained by our beloved Raju. Billo can perform jumping very eccentrically.
Given an array of positive integers in which each element represents number of possible hop
choices that he can jump. Starting with array index=0, design an algorithm that finds the
minimum number of jumps to reach the end of the array.
Example:
Input: A[] = {1, 3, 5, 8, 4, 2, 6, 7, 6, 8, 9}
Output: 3
Initially Billo is sitting at index 0. As A[0]=1, he can jump at most 1 hop, i.e., to index 1. At
index 1, A[1]=3, so he can jump at most 3 hops (to index 2, 3 or 4). Optimally, he can reach
last position of A in 3 jumps (0 -> 1 -> 3-> 10).
*
* @Author: Zuhair Mirza
* @Date : 4-May-2014
*
*/

$array = array(1, 3, 5, 8, 4, 2, 6, 7, 6, 8, 9);
//$array = array(1, 4, 3, 8, 5, 6, 2, 9, 7, 8);
//$array = array(1, 4, 3, 2, 5, 6, 2, 9, 7, 8, 9, 8);

$nodeIndex = 0;
$nodeValue = $array[$nodeIndex] + $nodeIndex;

echo $nodeIndex . "->";
$maxKey = runAlgo($array, $nodeIndex, $nodeValue);

function runAlgo($array, $start, $node) {

for ($j = $start; $j <= $node; $j++) {
if (isset($array[$j])):
$newArray[$j] = $array[$j];
endif;
}

if (end($newArray) >= end($array)):

$maxsIndex = count($array) - 1;
echo $maxsIndex;
exit();

else:

$maxsIndex = array_keys($newArray, max($newArray));
echo $maxsIndex[0] . "->";
$nodeIndex = $maxsIndex[0];
$nodeValue = $array[$nodeIndex] + $maxsIndex[0];
$maxKey3 = runAlgo($array, $nodeIndex, $nodeValue);

endif;

?>

Sunday, 30 March 2014

How to detect face in PHP

Download full code of FACE DETECTION ( including .json and .dat ) file link : https://github.com/mauricesvay/php-facedetection

Here is index.php file code :

<?php

include "FaceDetector.php";

$detector = new svay\FaceDetector();
$detector->faceDetect('lena512color.jpg');
$detector->toJpeg();

Here is FaceDetector.php Library File Code

<?php
//
// This program is free software; you can redistribute it and/or
// modify it under the terms of the GNU General Public License
// as published by the Free Software Foundation; either version 2
// of the License, or (at your option) any later version.
//
// This program is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
// GNU General Public License for more details.
//
// You should have received a copy of the GNU General Public License
// along with this program; if not, write to the Free Software
// Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
//
// @Author Karthik Tharavaad
// karthik_tharavaad@yahoo.com
// @Contributor Maurice Svay
// maurice@svay.Com

namespace svay;

class FaceDetector
{

protected $detection_data;
protected $canvas;
protected $face;
private $reduced_canvas;

public function __construct($detection_file = 'detection.dat')
{
if (is_file($detection_file)) {
$this->detection_data = unserialize(file_get_contents($detection_file));
} else {
throw new Exception("Couldn't load detection data");
}
}

public function faceDetect($file)
{
if (is_resource($file)) {

$this->canvas = $file;

} elseif (is_file($file)) {

$this->canvas = imagecreatefromjpeg($file);

} else {

throw new Exception("Can not load $file");
}

$im_width = imagesx($this->canvas);
$im_height = imagesy($this->canvas);

//Resample before detection?
$ratio = 0;
$diff_width = 320 - $im_width;
$diff_height = 240 - $im_height;
if ($diff_width > $diff_height) {
$ratio = $im_width / 320;
} else {
$ratio = $im_height / 240;
}

if ($ratio != 0) {
$this->reduced_canvas = imagecreatetruecolor($im_width / $ratio, $im_height / $ratio);

imagecopyresampled(
$this->reduced_canvas,
$this->canvas,
0,
0,
0,
0,
$im_width / $ratio,
$im_height / $ratio,
$im_width,
$im_height
);

$stats = $this->getImgStats($this->reduced_canvas);

$this->face = $this->doDetectGreedyBigToSmall(
$stats['ii'],
$stats['ii2'],
$stats['width'],
$stats['height']
);

if ($this->face['w'] > 0) {
$this->face['x'] *= $ratio;
$this->face['y'] *= $ratio;
$this->face['w'] *= $ratio;
}
} else {
$stats = $this->getImgStats($this->canvas);

$this->face = $this->doDetectGreedyBigToSmall(
$stats['ii'],
$stats['ii2'],
$stats['width'],
$stats['height']
);
}
return ($this->face['w'] > 0);
}

public function toJpeg()
{
$color = imagecolorallocate($this->canvas, 255, 0, 0); //red

imagerectangle(
$this->canvas,
$this->face['x'],
$this->face['y'],
$this->face['x']+$this->face['w'],
$this->face['y']+ $this->face['w'],
$color
);

header('Content-type: image/jpeg');
imagejpeg($this->canvas);
}

public function toJson()
{
return json_encode($this->face);
}

public function getFace()
{
return $this->face;
}

protected function getImgStats($canvas)
{
$image_width = imagesx($canvas);
$image_height = imagesy($canvas);
$iis = $this->computeII($canvas, $image_width, $image_height);
return array(
'width' => $image_width,
'height' => $image_height,
'ii' => $iis['ii'],
'ii2' => $iis['ii2']
);
}

protected function computeII($canvas, $image_width, $image_height)
{
$ii_w = $image_width+1;
$ii_h = $image_height+1;
$ii = array();
$ii2 = array();

for ($i=0; $i<$ii_w; $i++) {
$ii[$i] = 0;
$ii2[$i] = 0;
}

for ($i=1; $i<$ii_h-1; $i++) {
$ii[$i*$ii_w] = 0;
$ii2[$i*$ii_w] = 0;
$rowsum = 0;
$rowsum2 = 0;
for ($j=1; $j<$ii_w-1; $j++) {
$rgb = ImageColorAt($canvas, $j, $i);
$red = ($rgb >> 16) & 0xFF;
$green = ($rgb >> 8) & 0xFF;
$blue = $rgb & 0xFF;
$grey = (0.2989*$red + 0.587*$green + 0.114*$blue)>>0; // this is what matlab uses
$rowsum += $grey;
$rowsum2 += $grey*$grey;

$ii_above = ($i-1)*$ii_w + $j;
$ii_this = $i*$ii_w + $j;

$ii[$ii_this] = $ii[$ii_above] + $rowsum;
$ii2[$ii_this] = $ii2[$ii_above] + $rowsum2;
}
}
return array('ii'=>$ii, 'ii2' => $ii2);
}

protected function doDetectGreedyBigToSmall($ii, $ii2, $width, $height)
{
$s_w = $width/20.0;
$s_h = $height/20.0;
$start_scale = $s_h < $s_w ? $s_h : $s_w;
$scale_update = 1 / 1.2;
for ($scale = $start_scale; $scale > 1; $scale *= $scale_update) {
$w = (20*$scale) >> 0;
$endx = $width - $w - 1;
$endy = $height - $w - 1;
$step = max($scale, 2) >> 0;
$inv_area = 1 / ($w*$w);
for ($y = 0; $y < $endy; $y += $step) {
for ($x = 0; $x < $endx; $x += $step) {
$passed = $this->detectOnSubImage($x, $y, $scale, $ii, $ii2, $w, $width+1, $inv_area);
if ($passed) {
return array('x'=>$x, 'y'=>$y, 'w'=>$w);
}
} // end x
} // end y
} // end scale
return null;
}

protected function detectOnSubImage($x, $y, $scale, $ii, $ii2, $w, $iiw, $inv_area)
{
$mean = ($ii[($y+$w)*$iiw + $x + $w] + $ii[$y*$iiw+$x] - $ii[($y+$w)*$iiw+$x] - $ii[$y*$iiw+$x+$w])*$inv_area;

$vnorm = ($ii2[($y+$w)*$iiw + $x + $w]
+ $ii2[$y*$iiw+$x]
- $ii2[($y+$w)*$iiw+$x]
- $ii2[$y*$iiw+$x+$w])*$inv_area - ($mean*$mean);

$vnorm = $vnorm > 1 ? sqrt($vnorm) : 1;

$passed = true;
for ($i_stage = 0; $i_stage < count($this->detection_data); $i_stage++) {
$stage = $this->detection_data[$i_stage];
$trees = $stage[0];

$stage_thresh = $stage[1];
$stage_sum = 0;

for ($i_tree = 0; $i_tree < count($trees); $i_tree++) {
$tree = $trees[$i_tree];
$current_node = $tree[0];
$tree_sum = 0;
while ($current_node != null) {
$vals = $current_node[0];
$node_thresh = $vals[0];
$leftval = $vals[1];
$rightval = $vals[2];
$leftidx = $vals[3];
$rightidx = $vals[4];
$rects = $current_node[1];

$rect_sum = 0;
for ($i_rect = 0; $i_rect < count($rects); $i_rect++) {
$s = $scale;
$rect = $rects[$i_rect];
$rx = ($rect[0]*$s+$x)>>0;
$ry = ($rect[1]*$s+$y)>>0;
$rw = ($rect[2]*$s)>>0;
$rh = ($rect[3]*$s)>>0;
$wt = $rect[4];

$r_sum = ($ii[($ry+$rh)*$iiw + $rx + $rw]
+ $ii[$ry*$iiw+$rx]
- $ii[($ry+$rh)*$iiw+$rx]
- $ii[$ry*$iiw+$rx+$rw])*$wt;

$rect_sum += $r_sum;
}

$rect_sum *= $inv_area;

$current_node = null;

if ($rect_sum >= $node_thresh*$vnorm) {

if ($rightidx == -1) {

$tree_sum = $rightval;

} else {

$current_node = $tree[$rightidx];

}

} else {

if ($leftidx == -1) {

$tree_sum = $leftval;

} else {

$current_node = $tree[$leftidx];
}
}
}

$stage_sum += $tree_sum;
}
if ($stage_sum < $stage_thresh) {
return false;
}
}
return true;
}
}