Détecter les changements dans une entrée ordonnée aléatoire (fonction de hachage?)

Question

Je lis des lignes de texte qui peuvent arriver dans n'importe quel ordre. Le problème est que la sortie peut être identique à la sortie précédente. Comment puis-je détecter cela sans trier la sortie au préalable?

Existe-t-il une sorte de fonction de hachage pouvant prendre une entrée identique, mais dans n'importe quel ordre, tout en produisant le même résultat?

Answer 1

Le moyen le plus simple semble être de hacher chaque ligne, de stocker le hachage et les données d'origine, puis de comparer chaque nouveau hachage avec votre collection de hachages existants. Si vous obtenez un résultat positif, vous pouvez comparer les données réelles pour vous assurer que ce n'est pas un faux positif. Bien que cela soit extrêmement rare, vous pouvez utiliser un algorithme de hachage plus rapide, tel que MD5 ou CRC (au lieu de quelque chose comme SHA, qui est plus lent mais moins susceptible d'entrer en collision), juste pour que ce soit rapide, puis comparez les données réelles lorsque vous obtenez un hit.

Answer 2

Vous avez donc une entrée comme

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

et vous devez détecter que les première et troisième lignes sont identiques?

Answer 3

Si vous voulez savoir si deux fichiers contiennent le même ensemble de lignes, mais dans un ordre différent, vous pouvez utiliser une fonction de hachage régulière sur chaque ligne, puis combinez-les avec une fonction où l'ordre n'a pas d'importance. comme addition.

Answer 4

Si les lignes sont assez longues, vous pouvez simplement garder une liste des hachages de chaque ligne - triez-les et comparez-les aux sorties précédentes.

Si vous n'avez pas besoin d'une solution 100% infaillible, vous pouvez stocker le hachage de chaque ligne dans un filtre Bloom (consultez-le sur Wikipedia) et comparer les filtres Bloom à la fin du traitement. Cela peut vous donner de faux positifs (c’est-à-dire que vous pensez avoir la même sortie mais ce n’est pas vraiment la même chose), mais vous pouvez modifier le taux d’erreur en ajustant la taille du filtre de Bloom ...

Answer 5

Si vous additionnez les valeurs ASCII de chaque caractère, vous obtiendrez le même résultat, quel que soit l'ordre.

(C'est peut-être un peu trop simplifié, mais cela vous donnera peut-être une idée. Voir Programmation des perles, section 2.8, pour un historique intéressant.)

Answer 6

Toutes les méthodes basées sur le hachage peuvent produire des résultats erronés, car plusieurs chaînes peuvent produire le même hachage. (Ce n'est pas probable, mais c'est possible.) Cela est particulièrement vrai pour la suggestion d'ajouter des hachages, car vous utiliseriez essentiellement un particulièrement mauvais hachage des valeurs de hachage.

Une méthode de hachage ne doit être utilisée que s'il n'est pas essentiel que vous manquiez un changement ou que vous repériez un changement là où il n'en existait aucun.

La méthode la plus précise consiste à conserver une carte en utilisant les chaînes de lignes comme clé et en enregistrant le nombre de chacune en tant que valeur. (Si chaque chaîne ne peut apparaître qu'une seule fois, vous n'avez pas besoin du nombre.) Calculez ceci pour le jeu de lignes attendu. Dupliquez cette collection pour examiner les lignes entrantes, en réduisant le nombre pour chaque ligne telle que vous la voyez.

• Si vous rencontrez une ligne avec un compte zéro (ou aucune entrée de carte), vous avez vu une ligne inattendue.
• Si vous terminez avec des entrées non nulles dans la carte, vous ne voyez pas ce que vous attendiez.

Answer 7

La spécification du problème est un peu limitée.

Si j'ai bien compris, vous souhaitez voir si plusieurs chaînes contiennent les mêmes éléments, quel que soit leur ordre.

Par exemple:

A B C
C B A

sont les mêmes.

Pour ce faire, créez un ensemble de valeurs, puis comparez-les. Pour créer un ensemble, faites:

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

Il vous suffit ensuite de comparer le contenu des ensembles en les parcourant et en les comparant avec d’autres. Le temps d'exécution sera O (N) au lieu de O (NlogN) pour l'exemple de tri.