Repository navigation
Expand file tree
/
Copy pathSimilarity.php
More file actions
92 lines (73 loc) · 2.48 KB
/
Copy pathSimilarity.php
File metadata and controls
92 lines (73 loc) · 2.48 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
<?php
declare(strict_types=1);
namespace Pharaonic\Diff\Text;
use Pharaonic\Diff\Algorithm\Myers;
/**
* How alike two lines are, from 0 to 1: twice the number of words and punctuation characters
* they share in order, divided by how many both lines have together
*
* Lines longer than the inline limit are scored by their common prefix and suffix instead, which
* stays fast on huge lines. Lines without any words are compared character by character.
*
* When the words two lines share regardless of order already score below $floor, that upper
* bound is returned without aligning the words, since only scores at or above it matter.
*
* @internal
*/
final class Similarity
{
public static function ratio(string $a, string $b, int $maxLength, float $floor = 0.0): float
{
if ($a === $b) {
return 1.0;
}
if ($a === '' || $b === '') {
return 0.0;
}
if (strlen($a) > $maxLength || strlen($b) > $maxLength) {
return self::edges($a, $b);
}
$aTokens = Tokens::words($a);
$bTokens = Tokens::words($b);
if ($aTokens === [] || $bTokens === []) {
$aTokens = str_split($a);
$bTokens = str_split($b);
}
$total = count($aTokens) + count($bTokens);
$bound = 2 * self::shared($aTokens, $bTokens) / $total;
if ($bound < $floor) {
return $bound;
}
$common = 0;
foreach (Myers::diff($aTokens, $bTokens) as [$operation]) {
$common += $operation === Myers::EQUAL ? 1 : 0;
}
return 2 * $common / $total;
}
/**
* How many tokens both lists contain, counting repeats, regardless of order
*
* @param list<string> $a
* @param list<string> $b
*/
private static function shared(array $a, array $b): int
{
$counts = array_count_values($b);
$shared = 0;
foreach (array_count_values($a) as $token => $count) {
$shared += min($count, $counts[$token] ?? 0);
}
return $shared;
}
private static function edges(string $a, string $b): float
{
$max = min(strlen($a), strlen($b));
$prefix = strspn($a ^ $b, "\0");
$prefix = min($prefix, $max);
$suffix = 0;
while ($suffix < $max - $prefix && $a[strlen($a) - 1 - $suffix] === $b[strlen($b) - 1 - $suffix]) {
$suffix++;
}
return 2 * ($prefix + $suffix) / (strlen($a) + strlen($b));
}
}