Элемент большинства изображений JPEG с использованием Divide и conquer [duplicate]

Существует и не требует, чтобы элементы имели порядок.

Чтобы быть формальным, мы имеем дело с мультимножествами (также называемыми мешками .) В следующем случае для мультимножества S :

• v ( e , S ) - кратность элемента e в S , т. е. количество раз, когда оно происходит (кратность равна нулю, если e вообще не является членом S .)
• #S - мощность S , т. е. количество элементов в S , считающих кратность.
• ⊕ - мультимножественная сумма: если S = L ⊕ R , тогда S содержит все элементы из L и R , подсчитывающие кратность, т.е. v ( e ; S ) = v ( e ; L ) + v ( e ; R ) для любого элемента e . (Это также показывает, что кратность может быть вычислена «делением и покорением».)
• [ x ] - наибольшее целое число, меньшее или равное x .

Элемент m большинства S , если он существует, является тем элементом, что 2 v ( m ; S )> #S .

Назовем L и R a расщепление S , если L ​​ ⊕ R = S и четное расщепление , если | #L - #R | ≤ 1. То есть, если n = #S четно, L и R имеют ровно половину элементов из S , и если n нечетно, чем один имеет мощность [ n / 2], а другой имеет мощность [ n /2]+1.

Для произвольного раскола S на L и R два наблюдения :

1. Если ни L , ни R не имеют элемента большинства, то S не может: для любого элемента e , 2 v ( e ; S ) = 2 v ( e ; L ) + 2 v ( e ; R ) ≤ #L + #R = #S .
2. Если один из L и R имеет мажоритарный элемент m с кратностью k , то он является мажоритарным элементом S , только если он имеет кратность r в другой половине, с 2 ( k + r )> #S .

Алгоритм majo rity ( S ) ниже возвращает либо пару ( m , k ), указывая, что m является элементом большинства с k вхождения или none :

1. Если S пуст, верните none ; если S имеет только один элемент m , затем верните ( m , 1). В противном случае:
2. Сделайте ровное расщепление S на две половины L и R .
3. Пусть ( m , k ) = большинство ( L ), если не none : a. Пусть k ' = k + v ( m ; R ). б. Возврат ( m , k '), если 2 k' > n .
4. В противном случае let ( m , k ) = большинство ( R ), если не none : a. Пусть k ' = k + v ( m ; L ). б. Возврат ( m , k '), если 2 k' > n .
5. В противном случае return none .

Обратите внимание, что алгоритм по-прежнему корректен, даже если split не является четным. Разделение равномерно, хотя, скорее всего, будет лучше работать на практике.

Добавление

Сделал вывод в терминале явным в описании алгоритма выше. Пример кода C ++:

struct majority_t {
    int m; // majority element
    size_t k; // multiplicity of m; zero => no majority element

    constexpr majority_t(): m(0), k(0) {}
    constexpr majority_t(int m_,size_t k_): m(m_), k(k_) {}

    explicit operator bool() const { return k>0; }
};

static constexpr majority_t no_majority;

size_t multiplicity(int x,const int *arr,size_t n) {
    if (n==0) return 0;
    else if (n==1) return arr[0]==x?1:0;

    size_t r=n/2;
    return multiplicity(x,arr,r)+multiplicity(x,arr+r,n-r);
}

majority_t majority(const int *arr,size_t n) {
    if (n==0) return no_majority;
    else if (n==1) return majority_t(arr[0],1);

    size_t r=n/2;
    majority_t left=majority(arr,r);
    if (left) {
        left.k+=multiplicity(left.m,arr+r,n-r);
        if (left.k>r) return left;
    }

    majority_t right=majority(arr+r,n-r);
    if (right) {
        right.k+=multiplicity(right.m,arr,r);
        if (right.k>r) return right;
    }

    return no_majority;
}

Я вижу, по крайней мере, один метод деления и покорения.

Начните с поиска медианы, например, с помощью алгоритма выбора Хора. Если одно значение составляет большинство элементов, медиана должна иметь это значение, поэтому мы только что нашли нужное значение.

Оттуда найдите (например) 25-й и 75-й процентильные предметы. Опять же, если есть элемент большинства, по крайней мере один из них должен иметь то же значение, что и медиана.

Предполагая, что вы еще не исключили, что есть элемент большинства, вы можете продолжить поиск , Например, предположим, что 75-й процентиль был равен медианной, но 25-й процентиль не был.

Когда затем продолжить поиск предмета на полпути между 25-м процентилем и медианом, а также на полпути между 75-м процентилем и концом.

Продолжайте находить медиану каждого раздела, которая должна содержать конец элементов с тем же значением, что и медиана, до тех пор, пока вы не подтвердите или не отрицаете существование

В стороне: я не совсем понимаю, как Бойер-Мур будет использоваться для этой задачи. Boyer-Moore - это способ найти подстроку в строке.

Давайте предположим, что массив равен 1, 2, 1, 1, 3, 1, 4, 1, 6, 1.

Если массив содержит более половины элементов, то тогда должно быть где два последовательных элемента одинаковы.

В приведенном выше примере наблюдатель 1 повторяется более половины раз. И индексы (индекс начинаются с 0), индекс 2 и индекс 3 имеют одинаковый элемент.

Более простой алгоритм деления и покоя работает для случая, когда существует более 1/2 элементов, которые являются одинаковыми, и для некоторого целого k существует n = 2 ^ k элементов.

FindMost(A, startIndex, endIndex)
{  // input array A

if (startIndex == endIndex)  // base case
        return A[startIndex]; 
x = FindMost(A, startIndex, (startIndex + endIndex - 1)/2);
y = FindMost(A, (startIndex + endIndex - 1)/2 + 1, endIndex);

if (x == null && y == null) 
    return null;
else if (x == null && y != null) 
    return y;
else if (x != null && y == null) 
    return x;
else if (x != y) 
    return null;
else return x

}

Этот алгоритм может быть изменен так, что он работает для n, который не является показателем 2, но граничные случаи должны быть тщательно обработаны.