Effectuer beaucoup de remplacements dans un fichier texte à l'aide d'une liste énorme de paires de remplacement

Question

Étant donné:

fichier
• a.txt contenant plusieurs millions de lignes (disons, une phrase par ligne) (2,6 Go
fichier
• ! b.txt contenant 830K lignes avec des paires [word1] [word2]

question:

Comment effectuer le remplacement le plus efficace de chaque mot1 par mot2 pour chacun des 830k tuples (w1, w2) dans le fichier texte énorme?

Des méthodes naïves comme sed, perl, python, etc. nécessiteraient des semaines pour le faire. Y a-t-il des moyens (éventuellement basés sur la parallélisation) d'effectuer cette charge de remplacements?

Answer 1

Je le ferais en SQL.

créer une table avec deux colonnes (Dataline, séquence), et mettre en a.txt il (une ligne par ligne de la table)

puis créer une seconde table, à nouveau avec deux colonnes (mot1 ET mot2) et lire b.txt en elle (encore une fois, une ligne par ligne du tableau)

générer une mise à jour de la déclaration de mise à jour table1 basée sur table2

exécuter l'instruction SQL

quand il est terminé, lire la première table arrière sur dans un fichier

Answer 2

Fractionnez le fichier en plus petits morceaux. Vous êtes probablement en train de manger beaucoup d'espace mémoire en ne faisant rien d'autre que déplacer des bits en mémoire ou sur disque.

Ceci est similaire à la façon dont il est beaucoup plus rapide de concaténer/remplacer sur un tableau de chaînes plutôt que sur une seule chaîne.

La seule astuce consiste à s'assurer que l'endroit où vous placez la pause dans le fichier n'est pas une bonne correspondance, ce qui est relativement trivial. En fait, si vous pouvez le faire par lignes, c'est encore mieux, pas besoin de vérifier les résultats. Je trouve également étrange qu'il faudrait des semaines PERL. Il existe certaines preuves anecdotiques suggèrent qu'il peut gérer cela en moins d'une heure:

• http://www.wellho.net/forum/Perl-Programming/replace-text-in-a-large-text-file.html
• http://muharem.wordpress.com/2008/04/30/text-filtering-with-erlang/

En fait, ils parlent de fichiers 1gb prenant 2 minutes dans le second lien .

Et je ne soupçonnerais pas qu'une opération de remplacement devrait prendre beaucoup plus de temps qu'une opération de copie pour un fichier, après tout, il suffit de ramasser des morceaux du fichier et de remplacer certains bits lorsque vous les déplacez.Il devrait être en mesure de les remplacer à la volée près de la vitesse de les copier (car ils sont déjà en mémoire)

Answer 3

Trier votre liste de recherche/remplacement paires par le mot pour trouver [mot1]

Puis lire à travers le fichier, en divisant chaque ligne en mots, et cherchez chaque mot dans votre liste de mots à remplacer (en utilisant quelque chose d'efficace comme une recherche binaire).

Cela devrait être réalisable.

Answer 4

Je le ferais en python, mais n'importe quelle autre langue ferait l'affaire si vous obtenez l'algorithme correct. L'astuce consiste à garder les paires de mots (fichier b.txt) en mémoire et à parcourir le fichier volumineux en une seule fois. Depuis E/S est une opération beaucoup plus lente que la lecture de la RAM la performance de cette approche serait O (fichier1) + O (fichier2)

En pseudocode:

myMap = {} 
for line in fileB: 
    myMap[1st word of line] = 2nd word of line 

for line in fileA 
    for word in line 
    if myMap contains word 
     replace word with myMap[word] 

J'imagine que c'est le plus rapide, vous pouvez obtenir.

Answer 5

Je suis d'accord avec idrosid réponse de simplement charger les paires en mémoire, puis en streaming sur le fichier. Si vous avez vraiment beaucoup de données (beaucoup de Go) et que vous n'avez pas les ressources de la machine pour le faire aussi vite que vous le souhaitez, le nouveau service Elastic Hadoop d'Amazon serait une bonne solution. Une fois que vous avez un simple exécutable fonctionnant pour de petits fichiers, il serait assez simple de mettre à l'échelle jusqu'à des tonnes de données en utilisant le framework Map Reduce de Hadoop.