Saltar a contenido

Errores encontrados en el código original

Fecha: 2026-11-16. Desde el 2026-11-17 hay un resumen en la página de los asesores, y los errores se publicarán como sección del artículo.

Resumen

Programa Síntoma Causa Estado
GCreduct (gcReduct.jar) Cuenta menos reductos en algunas matrices Lista de atributos repetidos termina en el primer 0, y 0 es un id válido Corregido y verificado
MinReduct (MinReduct.jar) Nsol de más o de menos cuando hay columnas repetidas El mismo terminador, más una suma duplicada Corregido y verificado
sRGA (sRGA.jar) Cuenta de más cuando el reducto más corto tiene longitud 1 Comparación desplazada en uno Corregido y verificado
fast-BR (fastBR.jar y el código de CTBRES) Cuenta de menos cuando una columna llena está repetida El reducto de una sola columna se cuenta una vez, sin sus copias Corregido y verificado (hallado el 2026-11-16 por la noche)
GCreduct, MinReduct, fast-BR, fast-CT_EXT Excepción o bucle sin fin en matrices degeneradas Los generadores de candidatos vacían la pila Corregido y verificado
CAMARDF (Cpp1.cpp) Agota memoria; falla con muchas columnas Fuga de memoria y atributos guardados como char No corregido; sustituido por java/src/shortest/Camardf.java
Artículo de Susmaga (1998) Figuras 3 y 4 Errata de signo Solo documentado

"Verificado" significa: 442 matrices pequeñas con referencia independiente, sin ningún conteo distinto y sin ninguna corrida sin respuesta (sección "Verificación"). No es una demostración.

Las versiones corregidas están en java/fixed/. Los originales en legacy/ no se tocaron.

1. Terminador de atributos repetidos (GCreduct y MinReduct)

BasicMatrix.reduceColumns() elimina columnas repetidas y guarda en repeatedAtts los ids de las columnas que representan a un grupo. El arreglo se crea lleno de ceros y los bucles que lo recorren paran en el primer cero:

while (BM.repeatedAtts[k] != 0) {

El id 0 es válido. Tras la rotación inicial, el id 0 corresponde a la última columna del archivo. Si esa columna pertenece a un grupo repetido, queda primera en la lista, el bucle para de inmediato y se pierden las multiplicidades de todos los grupos.

Evidencia: en experiments/preliminar/gcreduct-conteo/soy_1.txt y soy_9.txt el par repetido incluye la última columna (columnas 26 y 34, y 4 y 34). El JAR original reporta 535 reductos; fast-BR y fast-CT_EXT reportan 570. En el archivo original de soybean el par repetido es 32 y 33, y el JAR acierta.

Corrección: el arreglo se llena con -1 y los bucles paran en -1.

2. Suma duplicada en MinReduct

Esta parte se leyó del código descompilado de MinReduct.jar, porque el fuente incluido en Shortest_src.zip es anterior al JAR y no tiene la variable extras ni la clase MinCandGen.

Cuando aparece un reducto más corto que los anteriores, el código reinicia el resultado y suma count - 1 a extras. Luego, fuera de ese bloque, vuelve a sumar count - 1 para el mismo reducto. El primer reducto de cada nueva longitud mínima se cuenta con sus copias dos veces.

Evidencia: matriz de 3 filas y 4 columnas con filas 0 0 0 1, 1 0 0 0, 0 1 1 0. Hay 2 reductos más cortos; el JAR reporta 3.

Corrección: se eliminó la suma dentro del bloque de reinicio.

3. Comparación desplazada en sRGA

Leído del código descompilado de sRGA.jar. El bucle descarta un conjunto parcial con:

if (R.tope >= k) continue;

tope es el índice del último elemento, es decir, el tamaño menos uno. La condición deja pasar conjuntos de tamaño k y los extiende a k + 1. Como k empieza en 1, la primera pasada ya admite tamaño 2. Si el reducto más corto tiene longitud 1, el resultado mezcla reductos de longitud 1 y 2.

Evidencia: en 200 matrices aleatorias pequeñas falla en las 8 que tienen longitud mínima 1 y en ninguna otra. En arrhythmia reporta 3236; las demás herramientas reportan 5.

Corrección: if (R.tope + 1 >= k) continue;. También se cambió la condición del bucle exterior de k < numColumnas a k <= numColumnas.

4. CAMARDF

Cpp1.cpp es el fuente de los autores con modificaciones de Vladimir para contar todos los reductos más cortos; los cambios están marcados con comentarios en español. El original devolvía un solo reducto mínimo.

  • DelChar reserva una lista nueva en cada iteración y solo se libera la última. La memoria crece con los candidatos visitados. Es la explicación probable de las corridas sin memoria reportadas en el artículo de MinReduct; no se reprodujo.
  • Los atributos se guardan como char con valor i + 1. Con más de 127 columnas se desborda, y la columna 256 vale '\0', que es el terminador de cadena.
  • La entrada es una tabla de decisión cuya última columna es la clase, no una matriz básica.

java/src/shortest/Camardf.java reproduce el algoritmo sin esos límites. Con la opción -faithful da la misma respuesta y el mismo número de candidatos que el fuente C en 211 de 213 matrices. Las dos diferencias: arrhythmia (279 columnas, 129 contra 130 candidatos, misma respuesta) y led24, cuyo archivo contiene una fila de ceros.

5. Errata en el artículo de Susmaga

En la Figura 1 (MRGA) la unión que define T_i recorre los R con R ∩ C_i = ∅. En las Figuras 3 (k-RGA) y 4 (S-RGA) aparece R ∩ C_i ≠ ∅. Lo correcto es = ∅: solo se extienden los conjuntos que todavía no cubren la cláusula. Ni el código original ni Srga.java arrastran la errata.

6. Reducto de una sola columna en fast-BR

Encontrado al verificar contra la referencia independiente. Hasta entonces fastBR.jar se usaba como referencia.

FastBR.extraerTT() trata aparte el caso en que una columna sola es reducto (columna llena de unos):

if (rasgo_X.cantValoresUnitarios() == numFilas) {
    solucion[0] = 1;
    solucion[1] = primero + 1;
    contadorTestores++;

En el resto del código cada reducto encontrado sobre la matriz sin columnas repetidas se expande con la tabla contraidos. Aquí no: una columna llena con n copias cuenta 1 en vez de n.

Evidencia: matriz de 3 filas y 5 columnas con filas 1 0 0 1 1, 0 1 0 1 1, 0 0 1 1 1. Hay 3 reductos ({3}, {4} y {0, 1, 2}); el JAR reporta 2. El mismo código está en CTBRES/Algorithms/src/edu/tt/alghoritms/br_colums_CH/Fast_BR.java.

Corrección: contadorTestores += contraidos[0][rasgo_X.idTupla];.

Alcance: hace falta una columna llena y repetida. En los paquetes públicos solo ocurre en BMarrhythmia.txt.

7. Matrices degeneradas

Si la fila con menos unos tiene todas las columnas distintas, o todas menos una, los programas no terminan bien:

  • GapCandGen (GCreduct) y MinCandGen (MinReduct): el bucle que elimina brechas vacía la pila y lee la posición -1. ArrayIndexOutOfBoundsException.
  • FastCandGen (fast-CT_EXT): la pila queda con tope negativo y el programa no termina.
  • FastBR: lee pMatriz[primero] antes de comprobar el fin, y saca de una pila vacía en la lista exterior. Además tempMat tiene una fila de menos cuando todas las columnas son iguales.

Ejemplos: matriz identidad de 2 por 2, matriz de una sola fila, y 1 1 0 1 / 1 0 1 1.

Corrección: guardas en los cuatro generadores (marcadas con FIX en java/fixed/). Ninguna matriz de los paquetes públicos cae en este caso, así que no afecta nada publicado.

Alcance sobre resultados publicados

Ver docs/reporte-2026-11-17.md y experiments/audit/results/. La auditoría revisa todas las matrices de los paquetes de GCreduct, MinReduct y CTBRES.

Datos con problemas

  • BMled24.txt del paquete de MinReduct: 2459 filas y una de ellas es todo ceros. No es una matriz básica válida.

Verificación

experiments/shortest/verify_fixed.py compara originales, corregidos e implementaciones nuevas contra una referencia en Python (experiments/lib/bm.py) que no comparte código con ellos. La referencia se comprobó contra fuerza bruta en 300 matrices de hasta 14 columnas.

Grupos: 200 matrices aleatorias, 150 con columnas repetidas (la mitad con una repetida en la última posición), 40 con columnas vacías, 40 con una columna llena, 12 casos límite. Total 442.

Programa Original: conteo distinto Original: sin respuesta Corregido: conteo distinto Corregido: sin respuesta
GCreduct 122 32 0 0
fast-BR 25 19 0 0
fast-CT_EXT 0 7 0 0
MinReduct 176 23 0 0
sRGA 38 0 0 0

Actualización del 2026-11-17: GCreduct, fast-BR, fast-CT_EXT y MinReduct corregidos aceptan -list. Junto con Camardf, Srga, Mmcs, Rs y el SHD de Uno, coinciden por conjunto de reductos con la referencia en las 442 matrices y en 8 de UCI (experiments/shortest/results/verify_sets_uci.txt). La copia corregida de sRGA sigue comparándose solo por conteo.

Todos los fallos de los originales quedan explicados por cinco condiciones que se pueden leer de la matriz (experiments/audit/profile.py): ningún conteo distinto ocurrió fuera de ellas.

Salida completa: experiments/shortest/results/verify_small.txt y verify_uci.txt.

Pruebas de regresión, un comando: scripts/build.sh && python3 tests/run.py. Son 11 matrices pequeñas; los corregidos pasan las 11 y los JAR originales ninguna (python3 tests/run.py --original).