Как правильно сравнить массивы и оценить их схожесть?

Итак, допустим у нас есть числа, расположенные по кругу:
08da16694f0b4fa0841218dd8ca2061b.png
Если перевести это в массив, получится
$numbers = [1,2,3,4,5,7,2,8];

Но если начать счет с другого элемента
6c2e7d4bff1c41ea8f936f4ff82b67bf.png
То получится такой массив
$numbers = [2,3,4,5,7,2,8,1];

По сути, круги одинаковые, но полученные массивы разные.
Вопрос 1: Как их правильно сравнивать?

Допустим, эти круги немного отличаются, на пару значений
a13bbf0ccb6f401fb1233e2d3165dea1.png
В данном случае круги с числами похожи на 6/8 = 75%
Вопрос 2: Как определить процент их схожести?

К сожалению, своих мозгов не совсем хватает. Прошу не готовый код, а хотя бы алгоритмы
  • Вопрос задан
  • 8158 просмотров
Решения вопроса 1
nowm
@nowm
Если два массива имеют одинаковую длину, можно просто двигать по кругу первый массив и сравнивать его элементы с элементами второго. Потом можно просто выбрать максимальное совпадение и перегнать в проценты. Примерно так:

$arr1 = [1,2,3,4,5,7,2,8];
$arr2 = [2,9,5,5,7,2,8,1];

$len = count($arr1);
$conformity = [];

for($i = 0; $i < $len; $i++) {
	/**
	 * $temp содержит нули в позициях, где числа в двух массивах 
	 * по одному и тому же индексу не равны. Единицы — там, где равны.
	 */
	$temp = array_map(function($x,$y){return intval($x==$y);}, $arr1, $arr2);
	
	// Элементы полученного массива суммируются и добавляются в отчётный массив
	$conformity[] = array_sum($temp);
	
	// Массив прокручивается на одну позицию
	$arr1[] = array_shift($arr1);
}

//С помощью max($conformity) выбирается максимальное совпадение элементов
echo sprintf("Max conformity is %s%%\n", number_format(100*(max($conformity)/$len), 2));


Это конкретно для ситуации, когда длина «колец» одинаковая.

Update: ещё один вариант:

$arr1 = [1,2,3,4,5,7,2,8];
$arr2 = [2,9,5,5,7,2,8,1];

function conformity($arr1, $arr2) {
	$len = count($arr1);
	$max = $curr = 0;
	
	for($i = 0; $i < $len; $i++) {
		array_map(function($x,$y)use(&$curr){$curr += intval($x==$y);}, $arr1, $arr2);
		
		if($curr == $len) {
			return 100;
		}

		$max = $max > $curr ? $max : $curr;
		$curr = 0;
		
		$arr1[] = array_shift($arr1);
	}
	
	return 100*($max/$len);
};

echo sprintf("Max conformity is %s%%\n", number_format(conformity($arr1, $arr2), 2));
Ответ написан
Пригласить эксперта
Ответы на вопрос 7
ErmIg
@ErmIg
Программист
По сути, кольца чисел - это периодические фунции. Лучше сравнивать не сами значения, их фурье спектры. Если отбросить фазу комплексного фурье спектра, то спектры таких колец будут схожими, даже если их отсчитывать с разных позиций.
Ответ написан
gbg
@gbg
Баянист. Тамада. Услуги.
Способов сравнения массивов можно придумать неограниченное количество.

Как правило, перед сравнением выдвигают сначала определенные требования (критерии эквивалентности), а потом уже на этих критериях изобретают сравнение.
Ответ написан
Нужно сформулировать что такое схожесть и сразу станет ясно как сравнивать ;)
Ответ написан
На самом деле, я тут подумал, и придумал получше Фурье.
Например, если вы говорите, что массивы одинаковы с точностью до поворота, то можно и надо сравнивать их на эквивалентность (я не говорю про процентную схожесть, тут сложнее), то можно интерпретировать их как строчки, и составить такую, например:
S + "$" + T + T,
где S -- один массив, а после разделителя два раза подряд записанный правый массив. Тогда тут достаточно запустить посчиать префикс-функцию с помощью алгоритма Кнута-Морриса-Пратта за линейное время. Если же интересуют схожие куски, то надо копать в сторону суффиксных массивов и деревьев, если хочется линейное время
Ответ написан
@Sumor
Правильного способа сравнить два массива с двумя и более элементами не существует в принципе.
Допустимые способы сравнения зависят от вашей предметной области, от того откуда берутся эти самые круги с числами. Какая мощность массивов? Одинаковая ли она? Это набор чисел (множество) или их порядок на круге имеет значение? Числа представлены количественной шкалой (можно проводить математические расчёты) или это качественные значения (математические расчёты невозможны или не имеют логического смысла)?
В качестве меры схожести можно выбрать, например:
1. Количество разных элементов: [1,2,3,4,5,7,2,8] [2,9,5,5,7,2,8,1] - мера равна 2
2. Сумма модулей разности элементов: [1,2,3,4,5,7,2,8] [1,2,3,4,6,7,4,8] - мера равна 3
3. Аналог расстояния Левенштейна: [1,2,3,4,5,7,2,8] [2,3,4,5,7,2,8,1] - мера равна 2
Ответ написан
@FanatPHP
Чебуратор тега PHP
я думаю, алгорим diff должен подойти
Ответ написан
Mrrl
@Mrrl
Заводчик кардиганов
Существует решение, работающее в худшем случае за O(N*sqrt(N*log(N))), а в типичном - за O(N*log(N)).
Пусть наши массивы - A и B.
Создадим массив Q из 2*N троек, содержащих (элемент массива, индекс в массиве, какой это массив - A или B).
Сортируем по полю "элемент массива".
Заводим массив C длины N, в котором будем считать C[k]=число совпадений при сдвиге на k позиций.
Просматриваем отсортированный массив Q. Для каждого значения X в нём сразу видно, сколько раз и на каких местах X встретился в массивах A и B. Пусть он p раз встретился в A (в позициях a1,a2,...,ap) и q раз - в B (в позициях b1,b2,...,bq). Если p*q < N*log(N), то за p*q операций модифицируем C, увеличивая на 1 все C[(bj-ai) mod N].
В противном случае строим массивы из 0 и 1, содержащие маски вхождения X в A и B, и считаем с помощью быстрого преобразования Фурье их свёртку. Прибавляем её к C.
Наихудший для этого алгоритма случай - когда в массивах примерно sqrt(N/log(N)) различных значений, которые встречаются примерно одинаковое количество раз.
Ответ написан
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы