Comment comparer des fichiers texte volumineux?

Maintenant que vous avez donné plus de détails, l'approche que je prendrais repose sur pré-partitionnement, et, éventuellement, le tri avant de chercher des allumettes.

Cela devrait éliminer une quantité importante de comparaisons qui n'auraient autrement pas de match de toute façon dans la naïve, la force brute de l'approche. Pour la clarté de l'exposé, permet de peg à la fois des fichiers à 40 millions de lignes chacun.

Partitionnement: de Lire à travers file_1 et envoyer toutes les lignes commençant par mat1 à file_1_mat1, et ainsi de suite. Faire de même pour file_2. C'est trivial, avec un peu de grep, ou si vous désirez le faire par programmation en Java, c'est un débutant de l'exercice.

C'est un passage dans deux fichiers pour un total de 80million lignes lire, produisant deux ensembles de 50 dossiers de 800 000 lignes chacun en moyenne.

Tri: Pour chaque partition, les trier en fonction de la valeur numérique dans la deuxième colonne (la limite inférieure de file_1 et le nombre réel de file_2). Même si de 800 000 lignes ne peut pas tenir en mémoire je suppose que nous pouvons nous adapter 2-voie externe, de fusion de tri et d'effectuer plus rapidement (moins de lectures) qu'une sorte de ensemble l'espace non partitionné.

Comparaison: Maintenant, vous avez juste à itérer une fois par les deux paires de file_1_mat1 et file_2_mat1, sans besoin de garder quelque chose en mémoire, la sortie correspond à votre fichier de sortie. Répétez l'opération pour le reste des partitions à son tour. Pas besoin d'un final "fusionner" l'étape (sauf si vous êtes de traitement des partitions en parallèle).

Même sans l'étape du triage de la naïveté de comparaison vous êtes déjà en train de le doit travailler plus vite dans plus de 50 paires de fichiers et 800 000 lignes chacun, plutôt que d'avoir deux fichiers avec 40 millions de lignes chacun.

OriginalL'auteur Alistair A. Israel

Dans un monde idéal, vous devez être capable de lire à chaque ligne de file_2 en mémoire (probablement à l'aide d'une recherche rapide de l'objet comme un HashSet, selon vos besoins), puis lire chaque ligne de file_1 un à la fois et de le comparer à votre structure de données de la tenue de la lignes de file_2.

Comme vous l'avez dit vous manquez de mémoire cependant, je pense que diviser et conquérir de type stratégie serait la meilleure. Vous pouvez utiliser la même méthode, comme je l'ai mentionné ci-dessus, mais le lire en une de la moitié (ou un tiers, d'un quart... selon la quantité de mémoire que vous pouvez utiliser) des lignes à partir de file_2 et de les stocker, puis de comparer l'ensemble des lignes file_1. Puis lire dans le prochain demi/tiers/quart/whatever dans la mémoire (en remplacement de l'ancien lignes) et de passer par file_1 de nouveau. Cela signifie que vous devez passer par file_1 plus, mais vous devez travailler avec votre mémoire contraintes.

EDIT: En réponse à l'ajout de détails à votre question, je voudrais changer ma réponse dans la partie. Au lieu de lire dans tous file_2 (ou en morceaux) et dans la lecture de file_1 une ligne à la fois, à l'inverse, comme file_1 contient les données à vérifier.

Également, en ce qui concerne la recherche de la correspondance des lignes. Je pense que le meilleur moyen serait de faire un traitement sur file_1. Créer un HashMap<List<Range>> que des cartes d'une Chaîne de caractères ("mat1" - "mat50") à une liste de Ranges (juste un wrapper pour un startOfRange int et un endOfRange int) et de le remplir avec les données de file_1. Ensuite, écrivez une fonction (en ignorant la vérification des erreurs)

boolean isInRange(String material, int value)
{
    List<Range> ranges = hashMapName.get(material);
    for (Range range : ranges)
    {
        if (value >= range.getStart() && value <= range.getEnd())
        {
            return true;
        }
    }
    return false;
}

et de l'appeler pour chaque (analysé) de la ligne de file_2.

OriginalL'auteur epochengine

Pas sûr de savoir comment bien une réponse ce serait, mais jetez un oeil à cette page: http://c2.com/cgi/wiki?DiffAlgorithm - il résume un peu diff algorithmes. Chasse-McIlroy algorithme est probablement la meilleure mise en œuvre. À partir de cette page il y a également un lien vers une implémentation java de la GNU diff. Cependant, je pense qu'une mise en œuvre en C/C++ et compilé en code natif sera beaucoup plus rapide. Si vous êtes coincé avec java, vous pouvez envisager de JNI.

OriginalL'auteur Aleks G

Si vous voulez une approche simple: vous pouvez hachage des fichiers et de comparer le hash. Mais c'est probablement plus rapide (surtout si les fichiers sont différents) pour l'utilisation de votre approche. À propos de la consommation de mémoire: assurez-vous d'utiliser suffisamment de mémoire, sans utiliser de tampon pour ce genre de chose est une mauvaise idée..

Et toutes ces réponses sur les tables de hachage, les sommes de contrôle etc: ce ne sont pas des plus rapides. Vous avez qu'à lire l'ensemble du dossier dans les deux cas. Avec des hachages/sommes de contrôle vous avez même de calculer quelque chose...

OriginalL'auteur duedl0r

Je n'ai jamais travaillé avec de gros fichiers, mais c'est mon idée et devrait fonctionner.

Vous pourrait envisager de hachage. À l'aide de Hachage SHA-1.

Importer les suivants

import java.io.FileInputStream;
import java.security.MessageDigest;

Une fois votre fichier texte, etc a été chargé de l'avoir en boucle sur chaque ligne et à la fin d'imprimer la table de hachage. L'exemple des liens ci-dessous permettra d'aller plus en profondeur.

StringBuffer myBuffer = new StringBuffer("");
//For each line loop through
    for (int i = 0; i < mdbytes.length; i++) {
        myBuffer.append(Integer.toString((mdbytes[i] & 0xff) + 0x100, 16).substring(1));
    }
System.out.println("Computed Hash = " + sb.toString());

SHA exemple de Code en se concentrant sur Fichier Texte

DONC, la Question sur le calcul de SHA en JAVA (Éventuellement utile)

Un autre exemple de code de hachage.

Simple lire chaque fichier seperatley, si la valeur de hachage pour chaque fichier est le même à la fin du processus, alors que les deux fichiers sont identiques. Si non, alors quelque chose est incorrect.

Alors si vous obtenez une valeur différente que vous pouvez faire le super temps, ligne par ligne, vérifier.

Dans l'ensemble, Il semble que la lecture ligne par ligne par ligne par ligne, etc prendrait une éternité. Je voudrais faire cela si vous essayez de trouver les différences individuelles. Mais je pense que le hachage serait plus rapide pour voir si elles sont la même chose.

La somme de contrôle SHA

OriginalL'auteur sealz

Ma solution serait de produire un index d'un fichier, d'abord, puis l'utiliser pour faire la comparaison. C'est à l'instar de certaines autres réponses en ce qu'il utilise le hachage.

Vous mentionner que le nombre de lignes est à environ 45 millions de dollars. Cela signifie que vous pourrait (éventuellement) de stocker un index qui utilise 16 octets par entrée (128 bits) et elle serait d'utiliser environ 45 000 000 d'*16 = ~685MB de RAM, ce qui n'est pas déraisonnable sur un système moderne. Il y a des frais fixes en utilisant la solution que je décris ci-dessous, vous pouvez encore le trouver, vous devez utiliser d'autres techniques telles que les fichiers mappés en mémoire ou sur disque tables pour créer l'index. Voir Hypertable ou HBase pour un exemple de la façon de stocker l'index dans un disque rapide à base de la table de hachage.

Donc, dans son intégralité, l'algorithme serait quelque chose comme:

1. Créer un hachage de la carte les cartes de Long pour une Liste de Longs (HashMap<Long, de la Liste<Long>>)
2. Obtenir le hash de chaque ligne dans le premier fichier (Objet.hashCode devrait être suffisant)
3. Obtenir l'offset dans le fichier de la ligne de sorte que vous pouvez le retrouver plus tard
4. Ajouter le décalage à la liste des lignes avec correspondance hashCodes dans la table de hachage carte
5. Comparer chaque ligne de la deuxième fichier pour l'ensemble de la ligne de décalages dans l'index
6. Garder toutes les lignes qui ont des entrées correspondantes

EDIT:
En réponse à votre édité question, ce ne serait pas vraiment l'aider en lui-même. Vous pouvez simplement de hachage de la première partie de la ligne, mais ce ne serait que la création de 50 entrées différentes. Vous pouvez ensuite créer un autre niveau dans la structure de données, ce qui permettrait de carte le début de chaque plage pour le décalage de la ligne d'où elle vient.

Donc quelque chose comme index.get("mat32") serait de retour un TreeMap des plages. Vous pourriez regarder pour la gamme précédente la valeur que vous êtes à la recherche pour lowerEntry(). Ensemble, ce serait vous donner une assez rapide pour vérifier si une donnée matX/nombre de combinaison a été dans l'une des plages que vous avez verifié.

OriginalL'auteur Mike Houston

Que penser de l'utilisation de la source de contrôle, comme Mercurial? Je ne sais pas, peut-être que ce n'est pas exactement ce que vous voulez, mais c'est un outil qui est conçu pour suivre les changements entre deux révisions. Vous pouvez créer un référentiel, de commettre le premier fichier, puis le remplacer par un autre, un commit la seconde:

hg init some_repo
cd some_repo
cp ~/huge_file1.txt .
hg ci -Am "Committing first huge file."
cp ~/huge_file2.txt huge_file1.txt
hg ci -m "Committing second huge file."

De là, vous pouvez obtenir un diff, vous dire ce que les lignes diffèrent. Si vous pourrait en quelque sorte de l'utiliser diff pour déterminer ce que les lignes étaient les mêmes, vous être tous ensemble.

C'est juste une idée, quelqu'un me corrige si je me trompe.

OriginalL'auteur Igor Zinov'yev