Rilevare i cambiamenti casuali ordinato ingresso (funzione di hash?)

Question

Sto leggendo le righe di testo che può venire in qualsiasi ordine.Il problema è che l'uscita può effettivamente essere indentical alla precedente uscita.Come posso rilevare questo, senza ordinare l'output prima?

C'è un qualche tipo di funzione hash che può prendere identici ingresso, ma in qualsiasi ordine, e continuano a produrre lo stesso risultato?

Answer 1

Il modo più semplice potrebbe sembrare l'hash di ogni riga sul modo in, la memorizzazione di hash e i dati originali, e quindi confrontare ogni nuovo hash con la vostra collezione esistente di hash.Se si ottiene un positivo, è possibile confrontare i dati, per verificare che non sia un falso positivo - anche se questo sarebbe estremamente raro, si potrebbe andare con un veloce algoritmo di hash come MD5 o CRC (invece di qualcosa come SHA, che è più lento ma meno probabile che si scontrano), solo così è più veloce, e poi confrontare i dati reali quando si ottiene un colpo.

Answer 2

Così si ha l'ingresso

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

ed è necessario rilevare che la prima e la terza riga sono identici?

Answer 3

Se volete scoprire se due file contengono le stesse linee, ma in un ordine diverso, è possibile utilizzare una normale funzione di hash su ogni singola riga, per poi unirli con una funzione a cui ordine non importa, come aggiunta.

Answer 4

Se le linee sono piuttosto lunghi, si può solo tenere un elenco di hash di ogni riga ... specie quelli e confrontare con le precedenti uscite.

Se non avete bisogno di un 100% a prova di stupido soluzione, è possibile memorizzare l'hash di ogni riga di un Bloom filter (cercare su Wikipedia) e confrontare i filtri di Bloom alla fine del trattamento.Questo può dare falsi positivi (cioèpensi di avere lo stesso risultato, ma non è proprio la stessa), ma è possibile modificare il tasso di errore di regolazione della dimensione del filtro di Bloom...

Answer 5

Se si sommano i valori ASCII di ogni carattere, si otterrebbe lo stesso risultato indipendentemente dall'ordine.

(Questo può essere un po ' troppo semplificato, ma forse scintille un'idea per voi.Vedere la Programmazione di Perle, sezione 2.8, per un'interessante storia.)

Answer 6

Qualsiasi hash-based metodi possono produrre risultati non validi perché più di una stringa in grado di produrre lo stesso hash.(Non è probabile, ma è possibile.) Questo è particolarmente vero per il suggerimento di aggiungere gli hash, dal momento che si sarebbe essenzialmente di prendere un particolarmente brutto hash dei valori di hash.

Un metodo di hash deve essere eseguita solo se non è fondamentale che si dimentica di cambiare spot o di un cambiamento che in realtà non esiste.

Il modo più preciso sarebbe quello di mantenere una Mappa utilizzando la linea di corde chiave e memorizzare il numero di ogni come valore.(Se ogni stringa può apparire solo una volta, non hai bisogno di il conte.) Il calcolo di questo previsto per il set di righe.Duplica questa collezione per esaminare le linee in entrata, riducendo il conteggio per ogni linea, come potete vedere.

• Se si verifica una linea con un numero zero (o nessuna voce di mappa a tutto), ho visto una linea che non si aspettava.
• Se alla fine di questo con il non-zero rimanenti voci nella Mappa, non vedi qualcosa che ti aspetta.

Answer 7

Beh, il problema specifica è un po ' limitato.

Da quanto ho capito vuoi vedere se più stringhe contengono gli stessi elementi indipendentemente dall'ordine.

Per esempio:

A B C
C B A

sono le stesse.

Il modo per farlo è quello di creare un insieme di valori, quindi, di confrontare il set.Per creare un set di fare:

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

Poi basta confrontare il contenuto del set in esecuzione attraverso uno dei set e comparazione w/gli altri.Il tempo di esecuzione sarà O(N) invece di O(NlogN) per lo smistamento esempio.