Detectar alterações na entrada ordenada aleatoriamente (função hash?)

Question

Estou lendo linhas de texto que podem vir em qualquer ordem.O problema é que a saída pode realmente ser idêntica à saída anterior.Como posso detectar isso, sem primeiro classificar a saída?

Existe algum tipo de função hash que pode receber entradas idênticas, mas em qualquer ordem, e ainda produzir o mesmo resultado?

Answer 1

A maneira mais fácil seria fazer o hash de cada linha no caminho, armazenando o hash e os dados originais e, em seguida, comparar cada novo hash com sua coleção de hashes existentes.Se obtiver um resultado positivo, você pode comparar os dados reais, para ter certeza de que não é um falso positivo - embora isso seja extremamente raro, você pode usar um algoritmo de hash mais rápido, como MD5 ou CRC (em vez de algo como SHA, que é mais lento, mas tem menos probabilidade de colidir), apenas para que seja rápido e compare os dados reais quando você acertar.

Answer 2

Então você tem entradas como

A B C D
D E F G
C B A D

e você precisa detectar que a primeira e a terceira linhas são idênticas?

Answer 3

Se você quiser descobrir se dois arquivos contêm o mesmo conjunto de linhas, mas em uma ordem diferente, você pode usar uma função hash regular em cada linha individualmente e combiná-los com uma função onde a ordem não importa, como adição.

Answer 4

Se as linhas forem bastante longas, você poderá simplesmente manter uma lista dos hashes de cada linha - classificá-los e comparar com os resultados anteriores.

Se você não precisa de uma solução 100% infalível, você pode armazenar o hash de cada linha em um filtro Bloom (procure na Wikipedia) e comparar os filtros Bloom no final do processamento.Isso pode lhe dar falsos positivos (ou seja,você acha que tem a mesma saída, mas não é realmente a mesma), mas pode ajustar a taxa de erro ajustando o tamanho do filtro Bloom...

Answer 5

Se você somar os valores ASCII de cada caractere, obterá o mesmo resultado, independentemente da ordem.

(Isso pode ser um pouco simplificado, mas talvez lhe desperte uma ideia.Consulte Pérolas de Programação, seção 2.8, para uma história interessante.)

Answer 6

Qualquer um dos métodos baseados em hash pode produzir resultados ruins porque mais de uma string pode produzir o mesmo hash.(Não é provável, mas é possível.) Isto é particularmente verdadeiro no que diz respeito à sugestão de adicionar os hashes, já que você estaria essencialmente tomando um particularmente ruim hash dos valores de hash.

Um método hash só deve ser tentado se não for crítico que você perca uma alteração ou detecte uma alteração onde não existe nenhuma.

A maneira mais precisa seria manter um Map usando as strings de linha como chave e armazenando a contagem de cada uma como valor.(Se cada string só puder aparecer uma vez, você não precisará da contagem.) Calcule isso para o conjunto de linhas esperado.Duplique esta coleção para examinar as linhas recebidas, reduzindo a contagem de cada linha conforme você a vê.

• Se você encontrar uma linha com contagem zero (ou nenhuma entrada no mapa), você viu uma linha que não esperava.
• Se você terminar com entradas diferentes de zero restantes no Mapa, você não viu algo que esperava.

Answer 7

Bem, a especificação do problema é um pouco limitada.

Pelo que entendi, você deseja ver se várias strings contêm os mesmos elementos, independentemente da ordem.

Por exemplo:

A B C
C B A

são os mesmos.

A maneira de fazer isso é criar um conjunto de valores e depois comparar os conjuntos.Para criar um conjunto faça:

HashSet set = new HashSet();
foreach (item : string) {
   set.add(item);
}

Em seguida, basta comparar o conteúdo dos conjuntos percorrendo um dos conjuntos e comparando-o com outros.O tempo de execução será O(N) em vez de O(NlogN) para o exemplo de classificação.