Detectar cambios en el azar ordenado de entrada (función de hash?)

Question

Estoy leyendo las líneas de texto que pueden aparecer en cualquier orden.El problema es que la salida puede ser en realidad idéntico a la anterior salida.¿Cómo puedo detectar esto, sin ordenar la salida de la primera?

¿Hay algún tipo de función hash que puede tomar entradas idénticas, pero en cualquier orden, y todavía producen el mismo resultado?

Answer 1

La forma más sencilla parece ser el hash de cada línea en la forma en, guardar el hash y los datos originales y, a continuación, compare cada nuevo hash con su colección existente de hashes.Si obtiene un resultado positivo, se puede comparar los datos reales, para asegurarse de que no es un falso positivo - aunque esto sería extremadamente raro, usted podría ir con el más rápido algoritmo de hash como MD5, CRC (en lugar de algo como el SHA, que es más lento, pero menos propensos a chocar), sólo es rápido, y luego comparar los datos reales cuando usted consigue un éxito.

Answer 2

Así que usted no tiene la entrada como

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

y usted necesita para detectar que la primera y tercera líneas son idénticas?

Answer 3

Si desea averiguar si dos archivos contienen el mismo conjunto de líneas, pero en un orden diferente, puede utilizar una regular la función de hash sobre cada línea por separado, luego combinar con una función en la que el pedido no importa, como adición.

Answer 4

Si las líneas son bastante largos, se podía mantener una lista de los valores hash de cada línea -- ordenar los y comparar con los anteriores salidas.

Si usted no necesita un 100% infalible para la solución, se puede almacenar el hash de cada línea en una Flor de filtro (buscar en Wikipedia) y comparar los filtros de Bloom en el final del proceso.Esto puede dar falsos positivos (es decir,usted cree que tiene la misma salida pero no es realmente el mismo), pero usted puede ajustar la tasa de error en el ajuste del tamaño de la Flor filtro...

Answer 5

Si se suman los valores ASCII de cada carácter, se obtendría el mismo resultado sin importar el orden.

(Esto puede ser un poco demasiado simplificado, pero tal vez se despierta una idea para usted.Consulte Programación de Perlas, la sección 2.8, para una interesante historia de fondo.)

Answer 6

Cualquiera de los hash basado en métodos pueden producir malos resultados porque más de una cadena puede producir el mismo valor hash.(No es probable, pero es posible.) Esto es particularmente cierto de la sugerencia de añadir el hash, ya que sería esencialmente de tomar una particularmente malo hash de los valores de hash.

Un hash método sólo debe intentarse si no es crítico que usted pierda un cambio de punto o de un cambio, donde no existe ninguno.

La forma más exacta sería la de mantener un Mapa utilizando la línea de las cuerdas, como clave y almacenar el recuento de cada uno como el valor.(Si cada cadena sólo puede aparecer una vez, usted no necesita el conde.) Calcular esto para lo que se esperaba de líneas.Duplicar esta colección para examinar las líneas entrantes, reduciendo el número de cada línea, como se puede ver.

• Si se encuentra en una línea con un contador cero (o no entrada de mapa a todos), han visto una línea que usted no esperaba.
• Si al final esta con los no-cero entradas restantes en el Mapa, usted no ve algo que le espera.

Answer 7

Bien, el problema de la especificación es un poco limitado.

Como entiendo que usted desea ver si hay varias cadenas contienen los mismos elementos sin importar el orden.

Por ejemplo:

A B C
C B A

son los mismos.

La manera de hacer esto es crear un conjunto de los valores, a continuación, compare los conjuntos.Para crear un conjunto que hacer:

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

A continuación, basta con comparar el contenido de los conjuntos mediante la ejecución a través de uno de los conjuntos y su comparación con w/otros.El tiempo de ejecución será O(N) en lugar de O(NlogN) para la clasificación de ejemplo.