Вычисление расстояния Хэмминга на C++

Программирование Программирование на С++ Решение задач на С++ Вычисление расстояния Хэмминга на C++

В этой теме 0 ответов, 1 участник, последнее обновление  Васильев Владимир Сергеевич 2 мес., 1 неделя назад.

  • Автор
    Сообщения
  • #5555
    @admin

    Строго по определению расстоянием Хэмминга называют количество позиций, в которых соответствующие символы двух слов одинаковой длины различны. Другими словами — это число, которое служит метрикой различия двух элементов (будь то строки, массивы байт, точки в пространстве и тд).

    Несколько примеров

    1. Битовые расстояния — количество позиций с различными битами

    10101011
    10101000
    Расстояние Хэмминга равно 2
    
    101
    101
    Расстрояние Хэмминга равно 0
    
    11111
    00001
    Расстрояние Хэмминга равно 4

    2. Расстояния в слове — количество позиций в различными символами

    helloworld
    hellowarld
    Расстояние Хэмминга равно 1

    Битовое расстояние Хэмминга — C++

    Задача состоит в том, чтобы посчитать количество позиций, в которых биты различны. В качестве «слов» будем рассматривать вектора байт одинаковой длины.

    int hamingDist(vector<byte> vec1, vector<byte> vec2) {
        if (vec1.size() != vec2.size()) {
            return -1;
        }
        int size = vec1.size();
     
        int hamingCount = 0;
        for (int i = 0; i < size; i++) {
            char mask = 1;
            int maskSlide = 0;
            int slide = 0;
            for (int j = 0; j < 8; j++) {
                char bit1 = (vec1[i] & (mask << maskSlide)) >> slide;
                char bit2 = (vec2[i] & (mask << maskSlide)) >> slide;
     
                if (bit1 != bit2) {
                    hamingCount++;
                }
     
                maskSlide++;
                slide++;
            }
        }
     
        return hamingCount;
    }

    Байтовое расстояние Хэмминга — C++

    Если в случае с битами нам пришлось работать с масками и битовыми смещениями, то количество различных байт можно посчитать в два счета.

    int hamingDistByte(vector<byte> vec1, vector<byte> vec2) {
        if (vec1.size() != vec2.size()) {
            return -1;
        }
     
        int hamingCount = 0;
        for (int i = 0; i < vec1.size(); i++) {
            if (vec1[i] != vec2[i]) {
                hamingCount++;
            }
        }
     
        return hamingCount;
    }

    В качестве заключения можно только сказать, что эта реализация не является эффективной ни в коем случае, наверняка можно хитро воспользоваться свойствами расстояния Хэмминга и ускорить подсчет. Но для моей задачи такой реализации оказалось достаточно.

    Материал взят тут: http://mindhalls.ru/hamming-distance-c-cpp/

Для ответа в этой теме необходимо авторизоваться.