distance.php

<?php

// cet algorithme est d'une telle violence

$dim = 3;
$d = 32; // lol

$v1 = array_randn($dim);32;
$v2 = array_randn($dim);

for ($j=0; $j < $d; $j++)
	$projections[] = array_randn($dim);

$r1 = get_signature($v1, $projections);
$r2 = get_signature($v2, $projections);

$xor = $r1 ^ $r2;

$true_sim = angular_similarity($v1, $v2);
$hash_sim = ($d - number_of_non_zero($xor)) / $d;

$diff = abs($hash_sim - $true_sim) / $true_sim;

printf("true %.4f, hash %.4f, diff %4f\n", $true_sim, $hash_sim, $diff);

function get_signature($vector, $projections)
{
	$res = 0;
	foreach($projections as $projection) {
		$res = $res << 1;
		$val = array_sum(array_map(function($a,$b) { return $a * $b; }, $projection, $vector));
		$val >= 0 && $res |= 1;
	}
	
	return $res;
}

function number_of_non_zero($num)
{
	if ($num == 0)
		return 0;
	
	$res = 0;
	do {
		$num &= $num -1;
		$res += 1;
	} while($num);
	
	return $res;
}

function angular_similarity($a, $b)
{
	$dot_prod = array_sum(array_map(function($a,$b) { return $a * $b; }, $a, $b));
	$sum_a    = sqrt(array_sum(array_map(function($a) { return $a * $a; }, $a)));
	$sum_b    = sqrt(array_sum(array_map(function($b) { return $b * $b; }, $b)));
	$cosine   = $dot_prod / ($sum_a * $sum_b);
	return 1.0 - (acos($cosine) / pi());
}

function array_randn($n)
{
	if ($n == 0)
		return [];
	
	for($i=0; $i<$n; $i++)
		$arr[] = rand(-50,50);
	
	return $arr;
}