Eu tenho alguns milhões de valores de 32 bits. Para cada valor, quero encontrar todos os outros valores a uma distância de 5. De maneira ingênua, isso requer comparações de , o que quero evitar.
Percebi que se apenas tratasse esses valores de 32 bits como números inteiros e classificasse a lista uma vez, então os valores que diferiam apenas nos bits menos significativos acabariam muito próximos. Isso me permite ter uma "janela" ou faixa de números mais curta dentro da qual eu possa realizar comparações reais em pares para a distância exata de hamming. No entanto, quando 2 valores variam apenas nos bits de ordem superior, eles acabam fora dessa "janela" e aparecem nas extremidades opostas da lista classificada. Por exemplo
11010010101001110001111001010110
01010010101001110001111001010110
estaria muito distante, mesmo que a distância de hamming seja 1. Como a distância de hamming entre 2 valores é preservada quando os dois são rotacionados, imaginei que, fazendo 32 rotações à esquerda e depois ordenando a lista todas as vezes, é provável que 2 valores terminará perto o suficiente na lista classificada em pelo menos um deles.
Embora essa abordagem esteja me dando bons resultados, estou lutando para estabelecer formalmente a correção dessa abordagem.
Dado que estou procurando valores correspondentes com distância de impedimento ou menos, eu realmente preciso fazer todas as rotações de 32 bits? Por exemplo, se e o tamanho da minha janela for 1000, preciso fazer rotações máximas de 24 bits, porque mesmo que o bit disperso apareça em qualquer um dos 8 bits de ordem inferior, os números resultantes não serão diferentes em mais de 1000.
A[i].close
Respostas:
Como afirmado, sua abordagem é problemática, porque se 2 bitmaps tiverem diferenças espaçadas uniformemente, em qualquer rotação, haverá diferenças em alguns bits de ordem superior.
Informação adicional:
fonte
a resposta de minar é excelente e provavelmente é a abordagem correta para esse problema em particular. No entanto, mencionarei mais uma abordagem possível:
Você pode usar uma função hash sensível à localidade (LSH). Uma função de hash sensível à localidade é projetada de modo que, se estão próximos na distância de Hamming, . Se você tiver um hash , poderá armazenar todos os seus valores em uma tabela de hash (usando a função hash e abrir hash) e poderá rapidamente encontrar todos os pares de valores próximos da distância de Hamming . Existem várias técnicas para construir um LSH; você pode consultar as referências sobre este tópico para encontrar vários candidatos.x , y H ( x ) = H ( y ) H HH x,y H(x)=H(y) H H
Dito isto, para o seu problema específico (com os parâmetros específicos que você mencionou), espero que os dois algoritmos de minar provem ser melhores na prática do que qualquer esquema baseado em LSH. Menciono isso apenas no caso de outros leitores chegarem a essa pergunta com um problema semelhante, mas com parâmetros diferentes em que o LSH pode fazer mais sentido.
fonte