Эффективный алгоритм сравнения сходства между наборами чисел?
У меня есть большое количество наборов чисел. Каждый набор содержит 10 номеров, и мне нужно удалить все наборы, которые имеют 5 или более номеров (неупорядоченных) совпадений с любым другим набором.
Например:
set 1: {12,14,222,998,1,89,43,22,7654,23}
set 2: {44,23,64,76,987,3,2345,443,431,88}
set 3: {998,22,7654,345,112,32,89,9842,31,23}
Учитывая, что 3 набора из 10 чисел выше наборов 1 и наборов 3, будут считаться дубликатами, поскольку они имеют 5 совпадающих номеров. Итак, в этом случае я бы удалил набор 3 (потому что он считается похожим на набор 1).
У меня есть более 10000 наборов для сравнения, и я хочу сделать это очень эффективно. Я переворачиваю это, и я просто не могу придумать эффективный способ выполнить это сравнение (было бы здорово сделать это за один проход).
есть идеи? Спасибо!
Майк
12 ответов
You should rethink your requirements because as it is, the operation does not even have a well-defined result. For example, take these sets:
set 1: {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}
set 2: {6, 7, 8, 9, 10, 11, 12, 13, 14, 15}
set 3: {11, 12, 13, 14, 15, 16, 17, 18, 19, 20}
Если вы сначала считаете 1 и 2 "дубликатами" и исключаете набор 1, то 2 и 3 также являются "дубликатами", и у вас остается только один оставшийся набор. Но если вместо этого сначала удалить набор 2, то у 1 и 3 не будет совпадений, и у вас останется два набора.
Вы можете легко расширить это до ваших полных 10000 наборов, так что было бы возможно, чтобы в зависимости от того, какие наборы вы сравниваете и удаляете первыми, у вас может остаться только один набор или 5000 наборов. Я не думаю, что это то, что вы хотите.
Говоря математически, ваша проблема в том, что вы пытаетесь найти классы эквивалентности, но отношение "сходство", которое вы используете для их определения, не является отношением эквивалентности. В частности, это не транзитивно. С точки зрения непрофессионала, если набор A "похож" на набор B, а набор B "похож" на набор C, то ваше определение не гарантирует, что A также "похоже" на C, и, следовательно, вы не можете сознательно устранить подобные наборы.
Вам нужно сначала уточнить свои требования для решения этой проблемы, прежде чем беспокоиться об эффективной реализации. Либо найдите способ определения транзитивного сходства, либо оставьте все наборы и работайте только со сравнениями (или со списком похожих наборов для каждого отдельного набора).
Еще одна идеальная работа для дерева подписей. Еще раз я в ужасе, что нет библиотеки, которая бы их реализовывала. Дайте мне знать, если вы напишите один.
Из аннотации первой статьи в результатах поиска выше:
Мы предлагаем метод, который представляет заданные данные в виде растровых изображений (подписей) и организует их в иерархический индекс, подходящий для поиска сходства и других связанных типов запросов. В отличие от предыдущего метода, дерево подписи является динамическим и не зависит от аппаратно зашитых констант. Эксперименты с синтетическими и реальными наборами данных показывают, что он устойчив к различным характеристикам данных, масштабируется до размера базы данных и эффективен для различных запросов.
Вы не много говорите о том, каков диапазон чисел, которые могут появиться, но у меня есть две идеи:
перевернутый список, который отображает число, которое появляется в списках, в списки, которые его содержат, а затем пересекает эти списки, чтобы найти те, которые имеют более одного общего числа.
разделите числа или сгруппируйте их по диапазонам "близких" чисел, затем уточните (сузьте) списки, в которых есть номера, в этих диапазонах. Вы уменьшаете диапазоны для сопоставления списков, у вас есть управляемое количество списков, и вы можете точно сравнивать списки. Это был бы подход "близости", я думаю.
Есть способ сделать это с высокой эффективностью по времени, но с чрезвычайно низкой эффективностью пространства.
Если моя математика верна, каждая комбинация из 5 чисел из набора из 10 приводит к 10!(10-5)!5! = 252 комбинации, умноженные на 10000 комплектов = 2,52 миллиона комбинаций. Набор из 5 целых чисел будет занимать 20 байтов, так что вы можете поместить каждую комбинацию для каждого набора в HashSet, и использовать только 5 мегабайт (плюс накладные расходы, которые выдувают его как минимум в 2-3 раза).
Теперь это может показаться дорогим, но если альтернатива, когда вы проверяете новый набор 10 против существующего 10000 индивидуально, состоит в том, что вы вычисляете 252 набора из 5 и смотрите, есть ли какие-то из них в наборе, тогда это должно быть лучше.
В принципе:
public class SetOf5 {
private final static HashSet<Integer> numbers;
private final int hashCode;
public SetOf5(int... numbers) {
if (numbers.length != 5) {
throw new IllegalArgumentException();
}
Set<Integer> set = new HashSet<Integer>();
hashCode = 19;
for (int i : numbers) {
set.add(i);
hashCode = 31 * i + hashCode;
}
this.numbers = Collections.unmodifiableSet(set);
}
// other constructors for passing in, say, an array of 5 or a Collectio of 5
// this is precalculated because it will be called a lot
public int hashCode() {
return numbers.hashCode();
}
public boolean equals(Object ob) {
if (!(ob instanceof SetOf5)) return false;
SetOf5 setOf5 = (SetOf5)ob;
return numbers.containsAll(setOf5.numbers);
}
}
Тогда вам просто нужно сделать две вещи:
- Создать
HashSet<SetOf5>для всех ваших существующих кортежей 5; а также - Создать алгоритм для создания всех возможных наборов из 5.
Ваш алгоритм становится следующим: для каждого набора из 10 чисел создайте все возможные наборы из 5, проверьте каждый из них, чтобы увидеть, есть ли он в наборе. Если это так, отклоните набор 10. Если это не так, добавьте набор 5 к "набору наборов". В противном случае продолжайте.
Я думаю, вы обнаружите, что это будет намного дешевле - по крайней мере, в случае 5 чисел из 10 - чем любое грубое сравнение 10000 наборов друг с другом.
Я не думаю, что есть хороший и красивый способ сделать это. В большинстве других ответов вы сравниваете большинство пар. x,y который был бы O(N^2), Вы можете сделать это быстрее.
Алгоритм: сохранить массив всех 5-ти кортежей. Для каждого нового разбиения его на все 5 возможных кортежей добавьте в этот массив. В конце сортируйте и проверяйте наличие дубликатов.
Есть C(10, 5) = 10*9*8*7*6/120 = 9*4*7примерно 250 подмножеств длины 5 из набора длины 10. Таким образом, вы держите таблицу, которая 10^3 раз больше, чем ваши данные, но выполнять просто O(250*N) операции. Это должно сработать практически, и я подозреваю, что теоретически это тоже самое лучшее.
Это простая проблема, потому что ваши сеты ограничены размером десять. Для каждого набора из десяти чисел у вас есть менее 1000 подмножеств набора, которые содержат как минимум пять чисел. Выберите хеш-функцию, которая хэширует целочисленные последовательности, скажем, в 32-битные числа. Для каждого набора из десяти целых чисел вычислите значение этой хеш-функции для каждого подмножества целых чисел с пятью или более элементами. Это дает менее 1000 значений хеш-функции на один набор из десяти чисел. Добавьте указатель на набор из десяти целых чисел в хеш-таблицу под всеми этими 1000 ключами. Как только вы это сделаете, в вашей хэш-таблице будет 1000 * 10 000 = 10 миллионов записей, что вполне выполнимо; и этот первый проход является линейным (O(n)), потому что размер отдельного набора ограничен 10.
На следующем этапе выполните итерацию всех значений хеша в любом порядке. Всякий раз, когда существует более одного набора, связанного с одним и тем же хеш-значением, это означает, что, скорее всего, они содержат общее подмножество из по меньшей мере пяти целых чисел. Проверьте это, а затем удалите один из наборов и соответствующие записи в хэш-таблице. Продолжить через хэш-таблицу. Это также шаг O (n).
Наконец, предположим, что вы делаете это в C. Вот процедура, которая вычисляет значения хеш-функции для одного набора из десяти целых чисел. Предполагается, что целые числа расположены в порядке возрастания:
static int hash_index;
void calculate_hash(int *myset, unsigned int *hash_values)
{
hash_index = 0;
hrec(myset, hash_values, 0, 0, 0);
}
void hrec(int *myset, unsigned int *hash_values,
unsigned int h, int idx, int card)
{
if (idx == 10) {
if (card >= 5) {
hash_values[hash_index++] = h;
}
return;
}
unsigned int hp = h;
hp += (myset[idx]) + 0xf0f0f0f0;
hp += (hp << 13) | (hp >> 19);
hp *= 0x7777;
hp += (hp << 13) | (hp >> 19);
hrec(myset, hash_values, hp, idx + 1, card + 1);
hrec(myset, hash_values, h, idx + 1, card);
}
Это повторяет все 1024 подмножества и сохраняет значения хеш-значений для подмножеств с количеством элементов 5 или более в hash_values массив. В конце hash_index подсчитывает количество допустимых записей. Это, конечно, константа, но я не рассчитал это здесь численно.
Вы должны найти коэффициент Пирсона между двумя наборами данных. Этот метод сделает вашу программу легко масштабируемой для огромных массивов данных.
Поскольку вам нужно сравнить все пары наборов, алгоритм примерно равен O(N^2), где N - размер набора.
Для каждого сравнения вы можете сделать около O(X+Y), где X и Y - размер двух наборов, в вашем случае 10 каждый, так что он постоянен. Но это требует, чтобы вы предварительно отсортировали все наборы, что добавляет к O(N*xlgx), опять же, xlgx является константой в вашем случае.
Алгоритм линейного сравнения для двух наборов довольно прост, поскольку наборы теперь отсортированы, вы можете выполнять итерации обоих наборов одновременно. Смотрите C++ std::set_intersection для подробностей.
Тогда весь алгоритм равен O(N^2), что было бы довольно медленно для 10000 наборов.
Может быть, вам нужен такой алгоритм (как я понимаю ваша проблема)?
import java.util.Arrays;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Set;
/**
* @author karnokd, 2009.06.28.
* @version $Revision 1.0$
*/
public class NoOverlappingSets {
// because of the shortcomings of java type inference, O(N)
public static Set<Integer> setOf(Integer... values) {
return new HashSet<Integer>(Arrays.asList(values));
}
// the test function, O(N)
public static boolean isNumberOfDuplicatesAboveLimit(
Set<Integer> first, Set<Integer> second, int limit) {
int result = 0;
for (Integer i : first) {
if (second.contains(i)) {
result++;
if (result >= limit) {
return true;
}
}
}
return false;
}
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
List<Set<Integer>> sets = new LinkedList<Set<Integer>>() {{
add(setOf(12,14,222,998,1,89,43,22,7654,23));
add(setOf(44,23,64,76,987,3,2345,443,431,88));
add(setOf(998,22,7654,345,112,32,89,9842,31,23));
}};
List<Set<Integer>> resultset = new LinkedList<Set<Integer>>();
loop:
for (Set<Integer> curr : sets) {
for (Set<Integer> existing : resultset) {
if (isNumberOfDuplicatesAboveLimit(curr, existing, 5)) {
continue loop;
}
}
// no overlapping with the previous instances
resultset.add(curr);
}
System.out.println(resultset);
}
}
Я не являюсь экспертом в обозначениях Big O, но я думаю, что этот алгоритм - O(N*M^2), где N - количество элементов в наборе, а M - общее количество наборов (на основе количества циклов, которые я используется в алгоритме). Я позволил себе определить, что я считаю перекрывающимися множествами.
Я думаю, что ваша проблема полиномиальная. Насколько я помню свои лекции, версия, основанная на принятии решения, будет NP-трудной, но поправьте меня, если я ошибаюсь
Предположим, у вас есть класс NumberSet который реализует ваш неупорядоченный набор (и может перечислять intс, чтобы получить номера). Затем вам понадобятся следующие структуры данных и алгоритм:
Map<int, Set<NumberSet>> numberSetsMap<Pair<NumberSet, NumberSet>, int> matchCountPair<X,Y>является ключевым объектом, который возвращает один и тот же хэш-код и равенство для каждого экземпляра с одинаковыми значениями X и Y (независимо от того, поменялись ли они местами)
Теперь для каждого добавляемого / сравниваемого набора сделайте следующее (псевдокод!!!):
for (int number: setToAdd) {
Set<NumberSet> numbers = numberSets.get(number);
if (numbers == null) {
numbers = new HashSet<NumberSet>();
numberSets.put(number, numbers);
} else {
for (NumberSet numberSet: numbers) {
Pair<NumberSet, NumberSet> pairKey = new Pair<NumberSet, NumberSet>(numberSet, setToAdd);
matchCount.put(pairKey, matchCount.get(pairKey)+1); // make sure to handle null as 0 here in real code ;)
}
}
numbers.add(number);
}
В любое время вы можете пройти через пары, и каждая из которых имеет количество 5 или более, показывает дубликат.
Примечание: удаление наборов может быть плохой идеей, потому что, если A считается дубликатом B, а B дубликатом C, то C не обязательно должен быть дубликатом A. Поэтому, если вы удалите B, вы бы не удаляйте C, и порядок, в котором вы добавляете свои наборы, станет важным.
Мы возьмем набор данных, украсим каждый элемент подписью и отсортируем его. Подпись имеет свойство, заключающееся в том, что сортировка сгруппирует те элементы, которые могут иметь дубликаты. При сравнении data_set[j] с элементами в data_set[j+1 ...], когда первая подпись в [j + 1...] повторной проверке не удалась, мы продвигаемся на i. Этот "критерий смежности" гарантирует, что нам не нужно смотреть дальше; никакой элемент за этим не может быть дубликатом.
Это значительно уменьшает сравнение O(N^2). Сколько я позволю аналитику алгоритма решать, но код ниже делает ~400 тыс. Сравнений вместо 100 м наивного O(N^2).
Подпись начинается с группирования элементов. Мы делим диапазон чисел на N сегментов одинакового размера: 1..k, k+1..2k, 2k+1..3k, ... При выполнении итерации по элементам мы увеличиваем счет, если число попадает в конкретное ведро. Это дает начальную подпись формы (0,0,0,1,3,0,0,...4,2).
Подпись имеет свойство, что если
sum(min(sig_a[i], sig_b[i]) for i in range(10)) >= 5
тогда возможно, что элементы, связанные с подписями, имеют как минимум 5 дубликатов. Но более того, если вышеупомянутое не выполняется, то элементы не могут иметь 5 дубликатов. Давайте назовем это "критерием соответствия подписи".
Но сортировка по вышеуказанной подписи не имеет свойства смежности, упомянутого выше. Однако, если мы изменим подпись, чтобы она была двухэлементной формы:
(sum(sig[:-1]), sig[-1])
тогда "критерий соответствия подписи" выполняется. Но имеет ли место критерий смежности? Да. Сумма этой подписи равна 10. Если мы перечисляем, у нас есть следующие возможные подписи:
(0,10) (1, 9) (2, 8) (3, 7) (4, 6) (5, 5) (6, 4) (7, 3) (8, 2) (9, 1) (10,0)
Если мы сравним (0,10) с (1,9) .. (10,0), мы заметим, что, если проверка подписи не пройдена, она никогда не станет истинной. Критерий смежности верен. Кроме того, этот критерий смежности справедлив для всех положительных значений, а не только для "5".
Хорошо, это хорошо, но разбиение подписи на два больших сегмента не обязательно сократит поиск O(N^2); подпись носит слишком общий характер. Мы решаем эту проблему, создавая подпись для sig[:-1], производя
(sum(sig[:-1]), sig[-1]), (sum(sig[:-2]), sig[-2]), ...
и так далее. Я считаю, что эта подпись все еще удовлетворяет смежность, но я могу ошибаться.
Есть некоторые оптимизации, которые я не делал: подписи нужно только последнее значение каждого кортежа, а не первое, но шаг сортировки должен быть пересмотрен. Кроме того, сравнение сигнатур может быть оптимизировано при раннем сбое, когда становится ясно, что дальнейшее сканирование не может быть успешным.
# python 3.0
import random
# M number of elements, N size of each element
M = 10000
N = 10
# Bounds on the size of an element of each set
Vmin,Vmax = 0, (1 << 12)
# DupCount is number of identical numbers required for a duplicate
DupCount = 5
# R random number generator, same sequence each time through
R = random.Random()
R.seed(42)
# Create a data set of roughly the correct size
data_set = [list(s) for s in (set(R.randint(Vmin, Vmax) for n in range(N)) for m in range(M)) if len(s) == N]
# Adorn the data_set signatures and sort
def signature(element, width, n):
"Return a signature for the element"
def pearl(l, s):
def accrete(l, s, last, out):
if last == 0:
return out
r = l[last]
return accrete(l, s-r, last-1, out+[(s-r,r)])
return accrete(l, s, len(l)-1, [])
l = (n+1) * [0]
for i in element:
l[i // width] += 1
return pearl(l, len(element))
# O(n lg(n)) - with only 10k elements, lg(n) is a little over 13
adorned_data_set = sorted([signature(element, (Vmax-Vmin+1)//12, 12), element] for element in data_set)
# Count the number of possible intersections
def compare_signatures(sig_a, sig_b, n=DupCount):
"Return true if the signatures are compatible"
for ((head_a, tail_a), (head_b, tail_b)) in zip(sig_a, sig_b):
n -= min(tail_a, tail_b)
if n <= 0:
return True
return False
k = n = 0
for i, (sig_a, element_a) in enumerate(adorned_data_set):
if not element_a:
continue
for j in range(i+1, len(adorned_data_set)):
sig_b, element_b = adorned_data_set[j]
if not element_b:
continue
k += 1
if compare_signatures(sig_a, sig_b):
# here element_a and element_b would be compared for equality
# and the duplicate removed by adorned_data_set[j][1] = []
n += 1
else:
break
print("maximum of %d out of %d comparisons required" % (n,k))
Похоже, вы хотите использовать класс HashSet. Это должно дать вам O(1) время поиска, которое должно дать очень эффективное сравнение, если вы правильно сделали свои циклы. (Я не обсуждаю алгоритм здесь, а просто предлагаю структуру данных на случай, если это поможет.)