Conceptos Fundamentales de Discretización

La discretización consiste en transformar datos con valores en un rango amplio a un rango más pequeño y manejable, priorizando la identidad o el orden relativo sobre el valor numérico exacto. En el desarrollo de software, esta técnica es útil para optimizar operaciones de búsqueda y almacenamiento. Se distinguen dos enfoques principales: discretización no ordenada y ordenada.

Discretización No Ordenada

Este método se emplea cuando solo se requiere distinguir entre valores únicos, sin considerar su secuencia original. Se implementa comúnmente mediante mapas o tablas hash que asignan un índice incremental a cada dato único. A continuación, se presenta un ejemplo con estructuras modificadas:

#include <iostream>
#include <unordered_map>
using namespace std;

const int LIMIT = 100010;
unordered_map<int, int> hashIndex;
int rawData[LIMIT];
int mappedIndices[LIMIT];

int main() {
    int numElements;
    cin >> numElements;
    for (int idx = 1; idx <= numElements; idx++) {
        cin >> rawData[idx];
        hashIndex[rawData[idx]] = idx; // Asignación de índice único
    }
    // Los valores discretizados se almacenan en hashIndex
    return 0;
}

Este enfoque permite una asignación rápida, pero no preserva el orden inherente de los datos.

Discretización Ordenada

La discretización ordenada es esencial cuando se necesita mantener la secuencia relativa de los elementos, como en aplicaciones de procesamiento de coordenadas o secuencias temporales. El procedimiento implica cuatro etapas clave: duplicación de datos, ordenación, eliminación de duplicados y búsqueda binaria para obtener índices comprimidos.

Implementación con Vector de C++

Utilizando un vector, se simplifica la manipulación dinámica. Aquí se muestra una versión con lógica y variables renombradas:

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

vector<int> sortedUnique;
int sourceData[100010];

int obtainIndex(int value) {
    int lower = 0, upper = sortedUnique.size() - 1;
    while (lower < upper) {
        int midpoint = lower + (upper - lower) / 2;
        if (value <= sortedUnique[midpoint]) {
            upper = midpoint;
        } else {
            lower = midpoint + 1;
        }
    }
    return lower + 1; // Índices basados en 1
}

int main() {
    int count;
    cin >> count;
    for (int i = 1; i <= count; i++) {
        cin >> sourceData[i];
        sortedUnique.push_back(sourceData[i]);
    }
    sort(sortedUnique.begin(), sortedUnique.end());
    sortedUnique.erase(unique(sortedUnique.begin(), sortedUnique.end()), sortedUnique.end());
    // Para mapear un valor a su índice discretizado, invocar obtainIndex()
    return 0;
}

Implementación con Arreglo Estático

Aletrnativamente, se puede usar un arreglo fijo, ajustando la estructura y los nombres de variables para mayor claridad:

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;

const int MAX = 10010;
int initialArray[MAX];
int processedArray[MAX];
int totalUnique;

int locateIndex(int target) {
    int start = 1, end = totalUnique;
    while (start < end) {
        int middle = start + (end - start) / 2;
        if (target <= processedArray[middle]) {
            end = middle;
        } else {
            start = middle + 1;
        }
    }
    return start;
}

int main() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> initialArray[i];
    }
    memcpy(processedArray, initialArray, sizeof(initialArray));
    sort(processedArray + 1, processedArray + 1 + n);
    totalUnique = unique(processedArray + 1, processedArray + 1 + n) - (processedArray + 1);
    // Para obtener el índice comprimido, usar locateIndex()
    return 0;
}