Eu tenho uma coisa relativamente direta que quero fazer:

Dado um número de consulta Q, uma distância de consulta d e um conjunto de números S, determine se S contém ou nãoqualquer números com distância de Hamming menor ou igual a d.

A solução mais simples é fazer de S uma lista e iterar sobre ela, calculando as distâncias. Se uma distância menor ou igual a d for calculada, resgate um retorno TRUE.

Mas, considerando que tudo o que quero fazer é verificar a existência, algo mais rápido que uma solução de tempo linear deve ser possível.

Uma coisa que tentei é uma M-tree. Fazendo referência a outras perguntas sobre o stackoverflow, o artigo da wikipedia (https://en.wikipedia.org/wiki/M-tree) e duas implementações preexistentes, passei várias horas ontem implementando uma solução personalizada. Uma das coisas boas sobre esse problema é que, na verdade, é mais barato computar popcount sobre o XOR de dois números (usando uma instrução SSE) do que armazenar números que permitiriam evitar o cálculo da métrica; portanto, existem vários aspectos da solução que poderia ser simplificado e otimizado para velocidade.

Os resultados foram muito decepcionantes. Acontece que o raio métrico com o qual estou lidando é pequeno comparado à distância mínima de Hamming. Por exemplo, no espaço de números de 12 bits, a distância máxima de Hamming é 12. Se o mínimo que estou procurando é 4, isso não deixa muitas oportunidades para um bom particionamento sem sobreposição. De fato, tentei exatamente isso, criando por força bruta um conjunto de números de 12 bits com distância mínima de Hamming de 4 e, em seguida (por força bruta), encontrando o particionamento ideal de árvore binária para que um algoritmo de pesquisa pudesse visitar um número mínimo de nós. Se eu querocontagem o número de elementos definidos em d da consulta, não posso reduzir o número de visitas de nós abaixo de cerca de 30% do total e parando quando encontrar a primeira visita em cerca de 4%. Isso significa que eu fiz mais ou menos uma solução de tempo linear, em que a sobrecarga do algoritmo elaborado de pesquisa em árvore é quase a mesma das economias de não ter que verificar quantos membros do conjunto.

Mas o que eu quero fazer é muito limitado. Não quero nem contar o número de membros do conjunto com distância da consulta <= d, muito menos enumerá-los. Eu só quero verificar a existência. Isso me faz pensar em coisas como filtros de flores e hashes.

Também pensei em tentar criar uma estrutura de gráfico em que membros do conjunto sejam conectados por arestas com pesos. Usando o fato de que a distância de Hamming respeita a desigualdade de triângulo, parece-me que deve haver alguma maneira de pesquisar esse gráfico, de modo que as passagens de arestas conduzam em uma direção da distância provavelmente menor à consulta, mas eu nem sei por onde começar aqui.

Alguém tem alguma outra sugestão para uma solução aqui que possa facilmente superar o desempenho de simplesmente iterar uma matriz?

EDIÇÃO e MOTIVAÇÃO:

Em última análise, isso vem de uma questão da teoria da codificação. Para um determinado número par de tamanho de palavra N, quantos códigos com distância mínima de hamming d posso caber em um número de N bits? Isso permite a criação de um código que pode detectar erros de d / 2 bits, corrigir erros de até d / 2-1 bits. Sabemos sobre códigos de limite de Shannon como LDPC, mas isso é para códigos longos com distância nebulosa mínima de Hamming, e eles levam uma eternidade para decodificar. Também existem códigos de erro de vários bits, como o OLSC, que são rápidos para decodificar, mas estão longe de economizar espaço. Por outro lado, para d = 4, os códigos Hamming estendidos (SECDED) são idealmente compactos. Eu já vi métodos baseados em BCH para criar um código DECTED, mas não sei se eles são ótimos. Para explorar codificações ideais, o que eu queria fazer era gerar conjuntos alternativos de códigos de N bits com alguns d arbitrários e gerar circuitos para codificá-los e decodificá-los, selecionando o mais compacto. Eu também esperava encontrar alguns padrões que poderíamos explorar por códigos mais longos.

Se isso ainda não foi feito, (b) é viável e (c) alguém gostaria de ser co-autor de um artigo, informe-me. :)