Расстояние Хэмминга

Описание

• Википедия
• GitHub

Расстояние Хэмминга (кодовое расстояние) (Hamming distance) - это число позиций, в которых соответствующие символы двух строк одинаковой длины различны. Другими словами, этот алгоритм измеряет минимальное количество замен символов, которые необходимо произвести для преобразования одной строки в другую. В более общем случае расстояние Хэмминга применяется для строк одинаковой длины и служит метрикой различия (функцией, определяющей расстояние в метрическом пространстве) объектов одинаковой размерности.

Примеры

Расстояние Хэмминга между:

• "karolin" и "kathrin" составляет 3
• "karolin" и "kerstin" составляет 3
• 1011101 и 1001001 составляет 2
• 2173896 и 2233796 составляет 3

Реализация

// algorithms/strings/hamming-distance.js
export default function hammingDistance(x, y) {
  if (x.length !== y.length) {
    throw new Error('Строки должны иметь одинаковую длину')
  }

  let distance = 0

  for (let i = 0; i < x.length; i++) {
    if (x[i] !== y[i]) {
      distance++
    }
  }

  return distance
}

Тестирование

// algorithms/strings/__tests__/hamming-distance.test.js
import hammingDistance from '../hamming-distance'

describe('hammingDistance', () => {
  it('должен выбросить исключение при сравнении строк разной длины', () => {
    const compareStringsOfDifferentLength = () => {
      hammingDistance('a', 'aa')
    }

    expect(compareStringsOfDifferentLength).toThrowError()
  })

  it('должен вычислить расстояния Хэмминга между двумя строками', () => {
    expect(hammingDistance('a', 'a')).toBe(0)
    expect(hammingDistance('a', 'b')).toBe(1)
    expect(hammingDistance('abc', 'add')).toBe(2)
    expect(hammingDistance('karolin', 'kathrin')).toBe(3)
    expect(hammingDistance('karolin', 'kerstin')).toBe(3)
    expect(hammingDistance('1011101', '1001001')).toBe(2)
    expect(hammingDistance('2173896', '2233796')).toBe(3)
  })
})

Запускаем тесты:

npm run test ./algorithms/strings/__tests__/hamming-distance