¿Cómo lidiar con un archivo de texto muy grande?

Actualmente estoy escribiendo algo que necesita manejar archivos de texto muy grandes (algunos GiB por lo menos). Lo que se necesita aquí (y esto es fijo) es:¿Cómo lidiar con un archivo de texto muy grande?

basadas en CSV, siguiendo el RFC 4180, con la excepción de la línea incrustado rompe
acceso de lectura al azar a las líneas, aunque la mayoría línea por línea y cerca del final
líneas al final
(líneas cambiantes). Obviamente que las llamadas para el resto del archivo que ser reescrito, también es raro, por lo que no es particularmente importante en este momento

El tamaño del archivo prohíbe mantener por completo en la memoria (que tampoco es deseable, ya que cuando los cambios deben agregarse tan pronto como sea posible).

He pensado en utilizar una región mapeada en memoria como una ventana en el archivo que se mueve si se solicita una línea fuera de su rango. Por supuesto, en esa etapa todavía no tengo abstracción por encima del nivel de bytes. Para trabajar con los contenidos tengo un CharsetDecoder que me da un CharBuffer. Ahora el problema es que puedo tratar con líneas de texto probablemente bien en el CharBuffer, pero también necesito saber el desplazamiento de bytes de esa línea dentro del archivo (para mantener un caché de índices y compensaciones de línea, así no tengo para escanear el archivo desde el principio nuevamente para encontrar una línea específica).

¿Hay alguna manera de asignar las compensaciones en un CharBuffer para compensar en la coincidencia ByteBuffer en absoluto? Obviamente, es trivial con ASCII o ISO-8859- *, menos con UTF-8 y con ISO 2022 o BOCU-1 las cosas se pondrían realmente feas (no es que realmente esperara las dos últimas, pero UTF-8 debería ser el predeterminado aquí - y aún plantea problemas).

Creo que podría simplemente convertir una porción de CharBuffer en bytes de nuevo y usar la longitud. O funciona o tengo problemas con signos diacríticos, en cuyo caso probablemente podría ordenar el uso de NFC o NFD para asegurar que el texto siempre esté codificado de manera no ambigua.

Aún así, me pregunto si ese es incluso el camino a seguir aquí. ¿Hay mejores opciones?

ETA: algunas respuestas a preguntas comunes y sugerencias aquí:

Se trata de un almacenamiento de datos para corridas de simulación, la intención de ser una alternativa local pequeño-montarse a una base de datos en toda regla. También tenemos backends de bases de datos y se usan, pero para los casos en los que no están disponibles o no se aplican, queremos esto.

También apoyo solo un subconjunto de CSV (sin saltos de línea incrustados), pero está bien por ahora. Los puntos problemáticos aquí son más o menos que no puedo predecir cuánto durarán las líneas y, por lo tanto, necesito crear un mapa aproximado del archivo.

En cuanto a lo que describí anteriormente: El problema que estaba ponderando era que puedo determinar fácilmente el final de una línea en el nivel del personaje (U + 000D + U + 000A), pero no quería suponer que esto se ve como 0A 0D en el nivel de bytes (que ya falla para UTF-16, por ejemplo, donde es 0D 00 0A 00 o 00 0D 00 0A). Pensaba que podía hacer que la codificación de caracteres cambiara al no codificar los detalles de la codificación que uso actualmente. Pero creo que podría apegarme a UTF-8 e ingorar en todo lo demás. Sin embargo, se siente mal, de alguna manera.

Fuente

2011-01-18 Joey

parece reinvención de las páginas de memoria del búfer del servidor sql. ¿Es el escenario de trabajo o cualquier otra cosa lo que le impide usar una base de datos integrada? – Osw

Cualquiera que sea la solución real, deberá crear al menos un índice de línea parcial o, si tiene el control completo del archivo y su contenido, puede considerar el uso de longitudes de línea fija. – biziclop

Es muy difícil mantener un mapeado 1: 1 entre una secuencia de Caracteres Java (que son efectivamente UTF-16) y bytes que podrían ser cualquier cosa dependiendo de la codificación de su archivo.Incluso con UTF-8, el mapeo "obvio" de 1 byte a 1 char solo funciona para ASCII. Ni UTF-16 ni UTF-8 garantizan que un carácter Unicode pueda almacenarse en una sola máquina char o byte.

Me gustaría mantener mi ventana en el archivo como un búfer de bytes, no un búfer de caracteres. Luego, para encontrar finales de línea en el búfer de bytes, codificaría la cadena Java "\r\n" (o posiblemente solo "\n") como una secuencia de bytes usando la misma codificación que el archivo. Luego utilizaría esa secuencia de bytes para buscar la línea terminaciones en el buffer byte. La posición de una línea que termina en el búfer + el desplazamiento del búfer desde el inicio del archivo se correlaciona exactamente con la posición de bytes en el archivo del final de línea.

Agregar líneas es solo una cuestión de buscar hasta el final del archivo y agregar sus nuevas líneas. Cambiar líneas es más complicado. Creo que mantendría una lista o un mapa de las posiciones de byte de las líneas modificadas y cuál es el cambio. Cuando esté listo para escribir los cambios:

ordenar la lista de cambios de posición de byte
leer el archivo original hasta el próximo cambio y escribirlo en un archivo temporal.
escribe la línea modificada en el archivo temporal.
omita la línea modificada en el archivo original.
regrese al paso 2 a menos que haya llegado al final del archivo original
mueva el archivo temp sobre el archivo original.

Fuente

2011-01-18 11:26:05 JeremyP

Hm, de hecho, no pensé en buscar el salto de línea codificado. De alguna manera, las soluciones obvias me eluden a veces. En cuanto al desplazamiento al mapeo de índices de fila: eso está planeado y es necesario, de hecho. Un cambio en una sola fila invalida cada uno posterior, por supuesto, pero de una manera predecible. Pero como esta es una operación muy rara, puedo ignorarla (por ahora). – Joey

Nota al margen: la asignación de memoria del archivo ya me proporciona un búfer de bytes. Pero no puedo tratar esos bytes como texto a menos que los decodifique en un búfer de caracteres. Pero sí tengo ambos en realidad. Gracias por la sugerencia de encontrar el salto de línea codificado; Voy por esa ruta ahora. – Joey

@Joey: Sí, debería haber enfatizado que la parte importante del truco es codificar el salto de línea utilizando la codificación del archivo en lugar de decodificar el archivo (o parte de él). Cómo se obtiene la secuencia de bytes de la ventana de archivos no es tan importante, excepto, por supuesto, que la asignación de memoria debe ser más rápida. – JeremyP

¿Sería posible dividir el archivo en "subarchivos" (por supuesto, no debe dividirlo en un solo carácter Utf-8)? Luego necesita metadatos para cada uno de los subarchivos (número total de caracteres y número total de líneas).

Si tiene esto y los "subarchivos" son relativamente pequeños, de modo que siempre puede cargar uno por completo, entonces la manipulación es más fácil.

Incluso la edición se vuelve fácil, ya que solo necesita actualizar el "subarchivo" y sus metadatos.

Si lo pone al límite: entonces puede usar una base de datos y almacenar una línea por fila de base de datos. - Si esta es una buena idea, depende en gran medida de su caso de uso.

Fuente

2011-01-18 10:18:11 Ralph

Para datos basados en líneas, no querrá dividir una línea entre archivos. También podría dividir un archivo de forma virtual, registrando la misma información con un desplazamiento en el archivo. El extremo es recordar dónde está cada línea en el archivo. –

@ Peter Lawrey: por supuesto si es posible dividir solo en los saltos de línea – Ralph

Lo que estoy haciendo aquí es un archivo simple basado en CSV pensado como una pequeña alternativa local a una base de datos en toda regla. Es un sumidero de datos para ejecuciones de simulación y también tenemos backends de bases de datos. Pero no siempre son aplicables o apropiados. – Joey

CharBuffer asume todos los personajes son UTF-16 o UCS-2 (tal vez alguien sabe la diferencia)

El problema utilizando un formato de texto adecuado es que se necesita leer todos los bytes saber dónde está el personaje enésimo es o donde está la n'th línea. Utilizo archivos de texto de varios GB pero asumo datos ASCII-7, y solo leo/escribo secuencialmente.

Si desea un acceso aleatorio en un archivo de texto no indexado, no puede esperar que sea eficaz.

Si está dispuesto a comprar un nuevo servidor, puede obtener uno con 24 GB por alrededor de £ 1,800 y 64 GB por alrededor de £ 4,200. Esto le permitiría cargar incluso archivos de varios GB en la memoria.

Fuente

2011-01-18 10:18:59

UTF-16. UCS-2 no está en uso desde hace bastante tiempo (excepto en aplicaciones que [erróneamente] asumen que un carácter Unicode tiene dos bytes de longitud). Y es por eso que tengo un CharsetDecoder para obtener caracteres Unicode de lo que sea que esté en el archivo. Pero obviamente eso oscurece un poco el mapeo de caracteres a bytes. Y no, no lo hago sin indizar. Recordaré las compensaciones de las líneas seleccionadas para tener una idea aproximada de dónde está cada línea en el archivo (como se señala en la pregunta también). En cuanto a la memoria, debería funcionar en sistemas de 32 bits también. – Joey

Si sabe dónde está el inicio y el final de cada línea. (puede calcular el final desde donde comienza la siguiente línea), debería poder leer readedly la línea (o líneas si necesita más de una) Sin embargo, si tiene memoria/hardware limitado, debe esperar que cada acceso aleatorio tome aproximadamente 9 ms (la latencia de un disco típico). En cuyo caso, la forma en que lo hace en el software no importa demasiado y simplemente debe hacerlo simple y confiable. –

Bueno, el problema que tuve al pensar fue que puedo determinar fácilmente el final de una línea en el nivel del personaje (U + 000D + U + 000A), pero no quiero suponer que esto se parece a '0A 0D' en el nivel de byte (falla para UTF-16, por ejemplo, donde es '0D 00 0A 00' o' 00 0D 00 0A'). Mi idea era que podía hacer que la codificación de caracteres cambiara al no codificar los detalles de la codificación que uso actualmente. Pero creo que podría apegarme a UTF-8 e ingorar en todo lo demás. Sin embargo, se siente mal, de alguna manera. – Joey

Si ha fijado las líneas de ancho, entonces con RandomAccessFile podría resolver muchos de sus problemas. Me doy cuenta de que sus líneas probablemente sean no de ancho fijo, pero podría imponer esto de forma artificial agregando un indicador de final de línea y líneas de relleno (por ejemplo, con espacios).

Esto obviamente funciona mejor si su archivo tiene actualmente una distribución bastante uniforme de las longitudes de línea y no tiene algunas líneas que son muy, muy largas. La desventaja es que esto aumentará artificialmente el tamaño de su archivo.

Fuente

2011-01-18 10:47:06 Qwerky

El formato es CSV. Los espacios son parte de los campos, así que no puedo simplemente rellenarlos. Además, el almacenamiento de cadenas de longitud desconocida es problemático: si aparece una cadena más larga, ¿debo rellenar todas las líneas que también escribí anteriormente? – Joey

@Joey El método se basa en una longitud de línea fija, por lo que tendrá que haber una longitud máxima impuesta. – Qwerky

Encontrar el inicio de la línea:

del palillo con el UTF-8 y \ n que indica el final de la línea no debería ser un problema. Alternativamente, puede permitir UTF-16 y reconocer los datos: tiene que ser citado (por ejemplo), tiene N comandos (punto y coma) y otro final de línea. Puede leer el encabezado para saber cuántas columnas tiene la estructura.

insertar en el medio del archivo

se puede lograr mediante la reserva de un espacio al final/comienzo de cada línea.

líneas adjuntas al final

Eso es trivial, siempre que el archivo está bloqueado (como cualquier otra modificación)

Fuente

2011-01-18 11:11:07 bestsss

En el caso del conteo de columnas fijas, dividía el archivo lógica y/o físicamente en columnas e implementaba algunos envoltorios/adaptadores para tareas IO y administraba el archivo como un todo.

Fuente

2011-01-18 11:26:49 Osw

¿Qué tal una tabla de compensaciones en intervalos algo regulares en el archivo, por lo que puede reiniciar el análisis en algún lugar cerca del lugar que está buscando?

La idea sería que estos serían desviaciones de bytes donde la codificación estaría en su estado inicial (es decir, si los datos estaban codificados en ISO-2022, entonces este punto estaría en el modo compatible con ASCII). Cualquier índice en los datos consistiría entonces en un puntero a esta tabla más lo que sea necesario para encontrar la fila real. Si coloca los puntos de reinicio de modo que cada uno se encuentre entre dos puntos, se ajuste a la ventana de mmap, entonces puede omitir el código de verificación/reasignación/reinicio de la capa de análisis, y usar un analizador que asume que los datos se mapean secuencialmente.

Fuente

2011-01-18 12:40:16

Como se señaló en la pregunta, esto está planeado y no es exactamente mi problema en este momento. – Joey

¿Cómo lidiar con un archivo de texto muy grande?

Respuesta

Cuestiones relacionadas