¿Cómo encontrar cadenas comunes entre dos archivos muy grandes?

Question

tengo dos archivos muy grandes (y ninguno de ellos caben en la memoria). Cada archivo tiene una cadena (que no tiene espacios y tiene 99/100/101 caracteres de longitud) en cada línea.

Actualización: Las cadenas no se encuentran ordenadas.
Update2: Estoy trabajando con Java en Windows.

Ahora quiero averiguar la mejor manera para descubrir todas las cadenas que ocurren en ambos archivos.

He estado pensando en usar el tipo de combinación externa para ordenar ambos archivos y luego hacer una comparación, pero no estoy seguro de si esa sería la mejor manera de hacerlo. Como las cuerdas son casi del mismo largo, siempre me pregunté si sería una buena idea calcular algún tipo de hash para cada cuerda, ya que eso debería facilitar las comparaciones entre cadenas, pero eso significaría que tengo que almacenar los hash. calculado para las cadenas que he encontrado desde los archivos hasta el momento para que puedan usarse más adelante al compararlas con otras cadenas. No puedo precisar cuál sería exactamente la mejor manera. Estoy buscando tus sugerencias.

Cuando sugiera una solución, también indique si la solución funcionaría si hubiera más de 2 archivos y cadenas que ocurrieran en todos ellos.

Answer 1

¿Hay algún orden para los datos en los archivos? La razón por la que pregunto es que aunque una comparación línea por línea tomaría una eternidad, pasar por un archivo línea por línea mientras que hacer una búsqueda binaria en el otro sería mucho más rápido. Sin embargo, esto solo puede funcionar si los datos están ordenados de una manera particular.

Answer 2

Cargaría ambos archivos en dos tablas de base de datos para que cada cadena en el archivo se convirtiera en una fila en la tabla y utilizara consultas SQL para encontrar filas duplicadas usando una combinación.

Answer 3

No ha dicho en qué plataforma está trabajando, así que supongo que está trabajando en Windows, pero en el caso improbable de que esté en una plataforma Unix, las herramientas estándar lo harán por usted.

sort file1 | uniq > output 
sort file2 | uniq >> output 
sort file3 | uniq >> output 
... 
sort output | uniq -d 

Answer 4

lo haría de la siguiente manera (para cualquier número de archivos):

• Ordenar sólo 1 archivo (# 1).
• Recorre cada línea del archivo siguiente (n. ° 2) y realiza una búsqueda binaria en el archivo n. ° 1 (según el número de líneas).
• Si encuentra la cadena; escríbalo en otro archivo temporal (# temp1).
• Después de terminar con # 2, ordenar # temp1 ir a # 3 y hacer la misma búsqueda pero esta vez en # temp1, no # 1, que debería tomar mucho menos que el primero ya que esto solo tiene líneas repetidas.
• Repita este proceso con nuevos archivos temporales, eliminando los archivos #temp anteriores. Cada iteración debería tomar menos y menos, a medida que disminuye el número de líneas repetidas.

Answer 5

Yo ordenaría cada archivo, luego usaría un algoritmo de línea balanceada, leyendo una línea a la vez desde un archivo u otro.

Answer 6

Un hash solución basada podría tener este aspecto (en pseudocódigo pitón):

hashes = dict() 
for file in files: 
    for line in lines: 
     h = md5(line) 
     hashes[h] += 1 

Entonces bucle de nuevo, líneas de impresión a juego:

for file in files: 
    for line in lines: 
     h = md5(line) 
     if hashes[h] == nfiles: 
      print line 
      del hashes[h] # since we only want each once. 

Hay dos problemas potenciales.

1. posibles colisiones hash (que puede ser mitigado algunos, pero es un riesgo.)
2. tiene que ser capaz de manejar un diccionario (matriz asociativa) de tamaño: | uniq líneas en todos los archivos |

Esto es O (líneas * costo (md5)).

(si la gente es una implementación más completa de python, es bastante fácil de escribir, ¡aunque no sé java!).

Answer 7

Dependiendo de cuán similares sean las entradas dentro de un archivo, podría ser posible crear un Trie (no árbol). Usando este trie puedes iterar el otro archivo y verificar cada entrada si está dentro del trie.

Cuando tenga más de 2 archivos, itere sobre un archivo y construya un nuevo trie de las coincidencias. De esta forma, el último trie tendrá todas las coincidencias que están contenidas en todos los archivos.

Answer 8

Para hacerlo en Windows, es bastante simple .. Digamos que usted tiene dos archivos A y B. Los archivos 'A' contienen las cadenas que desea buscar en el archivo B. simplemente abra el símbolo del sistema y use la siguiente comando

FINDSTR /G:A B > OUTPUT 

este comando es bastante rápido y puede comparar dos archivos de manera muy eficiente. La salida del archivo contendrá las cadenas comunes en A y B.

si desea llevar a cabo las operaciones (OR cadenas en B diferente de A) a continuación, utilizar

FINDSTR /V /G:A B > OUTPUT