У меня есть относительно простая вещь, которую я хочу сделать:

Учитывая номер запроса Q, расстояние запроса d и набор чисел S, определяют, содержит ли Sлюбой числа с расстоянием Хэмминга, меньшим или равным d.

Самое простое решение - просто сделать S списком и перебрать его, вычисляя расстояния. Если вычислено расстояние меньше или равно d, выведите возврат TRUE.

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

Одна вещь, которую я попробовал, это М-дерево. Ссылка на некоторые другие вопросы по stackoverflow, статья в Википедии (https://en.wikipedia.org/wiki/M-tree) и двух уже существующих реализаций, я вчера потратил несколько часов на реализацию индивидуального решения. Одна из приятных сторон этой проблемы заключается в том, что на самом деле дешевле вычислить поп-счет по XOR двух чисел (используя инструкцию SSE), чем хранить числа, которые позволят избежать вычисления метрики, поэтому существует несколько аспектов решения, которые может быть упрощен и оптимизирован для скорости.

Результаты были очень разочаровывающими. Оказывается, что метрический радиус, с которым я имею дело, мал по сравнению с минимальным расстоянием Хэмминга. Например, в пространстве 12-битных чисел максимальное расстояние Хэмминга равно 12. Если я ищу минимум 4, это не оставляет большой возможности для хорошего неперекрывающегося разбиения. Фактически, я попробовал именно это, создавая методом грубой силы набор из 12-битных чисел с минимальным расстоянием Хэмминга, равным 4, а затем (методом грубой силы) находил оптимальное разбиение двоичного дерева, чтобы алгоритм поиска мог посещать минимальное количество узлов. Если я захочуподсчитывать количество элементов набора в d запроса, я не могу уменьшить количество посещений узла ниже примерно 30% от общего числа, и остановка, когда я обнаружил, что первое посещение имеет около 4%. Это означает, что я более или менее сделал решение с линейным временем, где издержки сложного алгоритма поиска по дереву примерно такие же, как и экономия от необходимости проверять столько элементов набора.

Но то, что я хочу сделать, очень ограничено. Я не хочу даже подсчитывать количество членов набора с расстоянием между запросами <= d, а тем более перечислять их. Я просто хочу проверить существование. Это заставляет меня думать о таких вещах, как фильтры Блума и хэши.

Я также думал о попытке построить структуру графа, где элементы набора соединяются ребрами с весами. Используя тот факт, что расстояние Хэмминга учитывает неравенство треугольника, мне кажется, должен быть какой-то способ поиска в этом графике, чтобы обходы краев вели в направлении, вероятно, меньшего расстояния до запроса, но я даже не знаю, с чего начать Вот.

У кого-нибудь есть какие-либо другие предложения для решения, которое могло бы легко превзойти производительность простой итерации массива?

РЕДАКТИРОВАНИЕ И МОТИВАЦИЯ:

В конечном итоге это связано с вопросом теории кодирования. Для данного четного числа d и размера слова N, сколько кодов с минимальным расстоянием Хэмминга d я могу вписать в N-разрядное число? Это позволяет создать код, который может обнаруживать ошибки битов d / 2, исправлять ошибки вплоть до битов d / 2-1. Мы знаем о кодах предела Шеннона, таких как LDPC, но это для длинных кодов с туманным минимальным расстоянием Хэмминга, и их декодирование занимает вечность. Существуют также многобитовые коды ошибок, такие как OLSC, которые можно быстро декодировать, но они далеки от экономии места. С другой стороны, для d = 4 расширенные коды Хэмминга (SECDED) оптимально компактны. Я видел BCH-методы для создания кода DECTED, но я не знаю, являются ли они оптимальными. Чтобы исследовать оптимальные кодировки, я хотел генерировать альтернативные наборы кодов из N битов с некоторыми произвольными d и генерировать схемы для их кодирования и декодирования, выбирая наиболее компактные. Я также надеялся найти некоторые шаблоны, которые мы могли бы использовать для более длинных кодов.

Если это (а) еще не сделано, (б) осуществимо и (в) кто-то хотел бы стать соавтором статьи, пожалуйста, дайте мне знать. :)