Algoritmo para probar la distancia mínima de hamming contra un conjunto?

Tengo una cosa relativamente directa que quiero hacer:

Dado un número de consulta Q, una distancia de consulta d y un conjunto de números S, determine si S contiene o noalguna números con una distancia de Hamming menor o igual que d.

La solución más simple es hacer que S sea una lista e iterar sobre ella, calculando distancias. Si se calcula una distancia menor o igual a d, rescata un retorno VERDADERO.

Pero considerando que todo lo que quiero hacer es verificar una existencia, algo más rápido que una solución de tiempo lineal debería ser posible.

Una cosa que probé es un árbol M. Haciendo referencia a otras preguntas sobre stackoverflow, el artículo de wikipedia (https://en.wikipedia.org/wiki/M-tree) y dos implementaciones preexistentes, ayer pasé varias horas implementando una solución personalizada. Una de las cosas buenas de este problema es que en realidad es más barato calcular popcount sobre el XOR de dos números (usando una instrucción SSE) que almacenar números que permitan evitar calcular la métrica, por lo que hay varios aspectos de la solución que podría simplificarse y optimizarse para la velocidad.

Los resultados fueron muy decepcionantes. Resulta que el radio métrico con el que estoy tratando es pequeño en comparación con la distancia mínima de Hamming. Por ejemplo, en el espacio de números de 12 bits, la distancia máxima de Hamming es 12. Si el mínimo que busco es 4, eso no deja muchas oportunidades para una buena partición no superpuesta. De hecho, intenté justamente eso, creando por fuerza bruta un conjunto de números de 12 bits con una distancia mínima de Hamming de 4 y luego (por fuerza bruta) encontrando una partición óptima del árbol binario para que un algoritmo de búsqueda pudiera visitar un número mínimo de nodos. Si yo quierocontar el número de elementos establecidos dentro de d de la consulta, no puedo reducir el número de visitas a los nodos por debajo de aproximadamente el 30% del total, y parando cuando encuentro que el primero tiene aproximadamente un 4%. Esto significa que más o menos hice una solución de tiempo lineal, donde la sobrecarga del algoritmo de búsqueda de árbol elaborado es casi lo mismo que los ahorros de no tener que verificar tantos miembros del conjunto.

Pero lo que quiero hacer es muy limitado. Ni siquiera quiero contar el número de miembros del conjunto con una distancia de consulta <= d, mucho menos enumerarlos. Solo quiero verificar la existencia. Esto me hace pensar en cosas como filtros de floración y hashes.

También he pensado en tratar de construir una estructura gráfica donde los miembros del conjunto estén conectados por aristas con pesos. Utilizando el hecho de que la distancia de Hamming respeta la desigualdad de triángulos, me parece que debe haber alguna forma de buscar este gráfico de tal manera que los recorridos de borde conduzcan en una dirección de una distancia probablemente menor a la consulta, pero ni siquiera sé por dónde empezar aquí.

¿Alguien tiene alguna otra sugerencia para una solución aquí que pueda superar fácilmente el rendimiento de simplemente iterar una matriz?

EDICIÓN y MOTIVACIÓN:

En última instancia, esto proviene de una pregunta de teoría de codificación. Para un número par dado d y un tamaño de palabra N, ¿cuántos códigos con una distancia mínima de hamming d puedo caber en un número de N bits? Esto permite la creación de un código que puede detectar errores de d / 2 bits y corregir errores de hasta d / 2-1 bits. Sabemos acerca de los códigos de límite de Shannon como LDPC, pero esto es para códigos largos con una distancia nebulosa mínima de Hamming, y tardan una eternidad en decodificar. También hay códigos de error de bits múltiples como OLSC que son rápidos de decodificar, pero están lejos de ser eficientes en espacio. Por otro lado, para d = 4, los códigos extendidos de Hamming (SECDED) son óptimamente compactos. He visto métodos basados en BCH para hacer un código DECTADO, pero no sé si son óptimos. Para explorar las codificaciones óptimas, lo que quería hacer era generar conjuntos alternativos de códigos de N bits con algunos d arbitrarios y generar circuitos para codificarlos y decodificarlos, seleccionando el más compacto. También esperaba encontrar algunos patrones que podríamos explotar para códigos más largos.

Si esto (a) aún no se ha hecho, (b) es factible y (c) alguien quisiera ser coautor de un artículo, hágamelo saber. :)

Respuestas a la pregunta(1)

Su respuesta a la pregunta