algorithm - reales - ¿Representación de gráfico comprimido?
representacion grafica de fracciones mixtas (6)
¿Qué tal si solo escribe sus nodos, enlaces y asociaciones a un sistema de base de datos escalable existente (MySQL, SQL Server, Oracle, etc.)? Puede crear índices y procedimientos almacenados para un procesamiento más rápido del nivel de base de datos, si es necesario.
Si no puede ir a esta ruta por algún motivo, deberá ingresar y sacar datos de la página (¡tal como lo hacen los sistemas DB!). La compresión de los datos es una ayuda de banda a corto plazo en muchos casos. Si no puede elevar el techo de la RAM por alguna razón, solo se está comprando a sí mismo por un tiempo limitado, por lo que recomiendo no comprimirlo.
Estoy trabajando en un proyecto paralelo que implica la codificación de todos los enlaces entre páginas de Wikipedia. He raspado esta información a disco, pero el uso de memoria requerido para codificar la estructura de este gráfico es bastante ridículo: hay millones de nodos y decenas de millones de enlaces. Si bien esta estructura cabe en la memoria, no estoy seguro de lo que haría si hubiera, digamos, mil millones de enlaces o mil millones de páginas.
Mi pregunta es: ¿existe una forma de comprimir sin pérdidas un gráfico demasiado grande para que quepa en la memoria y que no se ajuste a la memoria? Si no es así, ¿existe un buen algoritmo con pérdida que para alguna definición de "estructura" no pierda demasiada estructura del gráfico original?
En general, si tiene N nodos y un promedio de X enlaces salientes por nodo, X mucho más pequeño que N, necesitará XN Ln N bits de información para representarlo, a menos que pueda encontrar patrones en la estructura del enlace. (que luego puedes explotar para bajar la entropía). XN Ln N está dentro de un orden de magnitud desde la complejidad de su lista de adyacencia de 32 bits.
Hay algunos trucos que puedes hacer para reducir el tamaño un poco más:
- Use códigos huffman para codificar destinos de enlaces. Asigne códigos más cortos a páginas de referencia frecuente y códigos más largos a páginas infrecuentes.
- Encuentra una manera de dividir el conjunto de páginas en clases. Almacene cada enlace entre las páginas dentro de la misma clase que "0" + "# dentro de la clase"; enlaces entre páginas en diferentes categorías como "1" + "clase de destino" + "# dentro de clase".
Vale la pena revisar los enlaces de Giuseppe, pero solo el experimento le dirá qué tan bien esos algoritmos son aplicables a Wikipedia.
Hace un tiempo formé parte de un artículo sobre la compresión de gráficos web para que quepan en la memoria. Lo conseguimos a unos 6 bits por enlace.
Los gráficos como los enlaces y los gráficos sociales están muy bien estudiados y, por lo general, tienen propiedades estadísticas que permiten representaciones comprimidas eficientes.
Una de estas propiedades, por ejemplo, es que para los bordes salientes, la codificación diferencial de la lista de adyacencia tiene una distribución de baja potencia, es decir, hay muchos valores muy pequeños y muy pocos valores grandes, por lo que la mayoría de los códigos universales funcionan bastante bien. En particular, la clase de códigos zeta es demostrablemente óptima en esta configuración, y en el documento, los autores comprimieron el gráfico de enlaces de un pequeño rastreo web con aproximadamente 3 bits por enlace.
Su código (para Java, Python y C ++) está disponible en su página web como un marco de compresión de gráficos, por lo que debería poder experimentar con él sin mucha codificación.
Este algoritmo es un poco antiguo (2005) y ha habido desarrollos en el campo, pero no tengo los indicadores a los documentos en este momento, las mejoras de todas formas no son significativas y no creo que haya ningún código disponible y probado Eso los implementa.
Si no necesita la mutabilidad, observe cómo BGL representa un gráfico en un formato de filas dispersas comprimidas . Según los documentos, "minimiza el uso de memoria a O (n + m) donde n y m son el número de vértices y bordes, respectivamente". Boost Graph Library incluso tiene un ejemplo que refleja su caso de uso.
Antes de llegar muy lejos con esto, deberías descubrir cómo pretendes interrogar tu gráfica. ¿Necesita enlaces que apunten a la página así como enlaces fuera de una página? ¿Necesita poder encontrar de manera eficiente la cantidad de enlaces en una página determinada? Para una lista bastante bien pensada de operaciones gráficas básicas, eche un vistazo a los conceptos de la Biblioteca de Gráficos de Boost (BGL) . A continuación, puede asignar esto a los requisitos de diferentes algoritmos. La ruta más corta de Dijkstra , por ejemplo, requiere un gráfico que modele "Vertex List Graph" y "Incidence Graph".
en su caso, está intentando comprimir un solo gráfico en una memoria en lugar de una gran familia de gráficos en general. Cuando solo tiene un único gráfico para comprimir, puede encontrar cualquier presentación algorítmica arbitraria para él y esto se convierte en un problema de complejidad de Kolmogorov . En general, no se pueden comprimir los gráficos aleatorios de manera eficiente porque son aleatorios y, por lo tanto, no se pueden predecir y, cuando no se pueden predecir, no se pueden comprimir. Esto viene de la teoría de la información básica; Es lo mismo que no puedes comprimir imágenes con ruido aleatorio.
Supongamos que tiene 2 30 (billones) de páginas y todos tienen exactamente 2 4 enlaces salientes y que los enlaces se distribuyen de forma aleatoria. Los enlaces en cada página representan casi 16 * 30 bits de información (no del todo porque los 16 enlaces son distintos y esto agrega una cantidad minúscula de redundancia). Entonces tiene 2 30 * 16 * 30 = 2 32 * 120 = 15 GB de información allí, y la teoría de la información dice que no puede encontrar una representación GENERAL más pequeña. Debe utilizar la estructura particular del gráfico de Wikipedia para situarse por debajo de ese límite inferior de la información teórica.