problemreductions/models/misc/

minimum_external_macro_data_compression.rs

//! Minimum External Macro Data Compression problem implementation.
//!
//! Given an alphabet Sigma, a string s in Sigma*, and a pointer cost h,
//! find a dictionary string D and compressed string C minimizing the total
//! cost |D| + |C| + (h-1) * (number of pointer occurrences in D and C),
//! such that s can be reconstructed from C by replacing pointers with their
//! referenced substrings of D.
//!
//! The configuration uses 2*|s| slots: |s| slots for D (dictionary) and |s|
//! slots for C (compressed string). D-slots use alphabet symbols or empty.
//! C-slots use alphabet symbols, pointers into D (start, len), or empty.
//! D is restricted to be pointer-free (pure alphabet string).
//!
//! This problem is NP-hard (Storer, 1977; Storer & Szymanski, 1978).
//! Reference: Garey & Johnson A4 SR22.

use crate::registry::{FieldInfo, ProblemSchemaEntry};
use crate::traits::Problem;
use crate::types::Min;
use serde::{Deserialize, Serialize};

inventory::submit! {
    ProblemSchemaEntry {
        name: "MinimumExternalMacroDataCompression",
        display_name: "Minimum External Macro Data Compression",
        aliases: &[],
        dimensions: &[],
        category: crate::registry::ProblemCategory::Misc,
        module_path: module_path!(),
        description: "Find minimum-cost compression using an external dictionary and compressed string with pointers",
        fields: &[
            FieldInfo { name: "alphabet_size", type_name: "usize", description: "Size of the alphabet (symbols indexed 0..alphabet_size)" },
            FieldInfo { name: "string", type_name: "Vec<usize>", description: "Source string as symbol indices" },
            FieldInfo { name: "pointer_cost", type_name: "i64", description: "Pointer cost h (each pointer contributes h to the cost)" },
        ],
    }
}

/// Minimum External Macro Data Compression problem.
///
/// Given an alphabet of size `k`, a string `s` over `{0, ..., k-1}`, and
/// a pointer cost `h`, find dictionary string D and compressed string C
/// that minimize cost = |D| + |C| + (h-1) * (pointer count in C).
///
/// # Representation
///
/// The configuration is a vector of `2 * string_length` entries:
/// - First `string_length` entries are D-slots: each is a symbol index
///   in `{0, ..., alphabet_size-1}` or `alphabet_size` (empty/unused).
/// - Next `string_length` entries are C-slots: each is:
///   - A symbol index in `{0, ..., alphabet_size-1}` (literal)
///   - `alphabet_size` (empty/unused)
///   - A value in `{alphabet_size+1, ..., alphabet_size + |s|*(|s|+1)/2}`
///     encoding a pointer (start, len) into D.
///
/// D is the prefix of non-empty D-slots. C is the prefix of non-empty C-slots.
/// The cost is |D| + |C| + (h-1) * (number of pointer symbols in C).
///
/// # Example
///
/// ```
/// use problemreductions::models::misc::MinimumExternalMacroDataCompression;
/// use problemreductions::{Problem, BruteForce};
///
/// // Alphabet {a, b}, string "abab", pointer cost h=2
/// let problem = MinimumExternalMacroDataCompression::new(2, vec![0, 1, 0, 1], 2);
/// let solver = BruteForce::new();
/// let solution = solver.solve(&problem).unwrap();
/// assert!(solution.is_some());
/// ```
#[derive(Debug, Clone, Serialize, Deserialize)]
#[serde(try_from = "MinimumExternalMacroDataCompressionSerde")]
pub struct MinimumExternalMacroDataCompression {
    alphabet_size: usize,
    string: Vec<usize>,
    pointer_cost: i64,
}

#[derive(Deserialize)]
struct MinimumExternalMacroDataCompressionSerde {
    alphabet_size: usize,
    string: Vec<usize>,
    pointer_cost: i64,
}

impl TryFrom<MinimumExternalMacroDataCompressionSerde> for MinimumExternalMacroDataCompression {
    type Error = crate::registry::ConstructionError;

    fn try_from(value: MinimumExternalMacroDataCompressionSerde) -> Result<Self, Self::Error> {
        if value.alphabet_size == 0 && !value.string.is_empty() {
            return Err("alphabet_size must be > 0 when the string is non-empty"
                .to_string()
                .into());
        }
        if value
            .string
            .iter()
            .any(|&symbol| symbol >= value.alphabet_size)
        {
            return Err("all symbols must be less than alphabet_size"
                .to_string()
                .into());
        }
        if value.pointer_cost <= 0 {
            return Err("pointer_cost must be positive".to_string().into());
        }
        Ok(Self {
            alphabet_size: value.alphabet_size,
            string: value.string,
            pointer_cost: value.pointer_cost,
        })
    }
}

impl MinimumExternalMacroDataCompression {
    /// Create a new MinimumExternalMacroDataCompression instance.
    ///
    /// # Panics
    ///
    /// Panics if `alphabet_size` is 0 and the string is non-empty, or if
    /// any symbol in the string is >= `alphabet_size`, or if `pointer_cost` is 0.
    pub fn new(alphabet_size: usize, string: Vec<usize>, pointer_cost: i64) -> Self {
        assert!(
            alphabet_size > 0 || string.is_empty(),
            "alphabet_size must be > 0 when the string is non-empty"
        );
        assert!(
            string
                .iter()
                .all(|&s| s < alphabet_size || alphabet_size == 0),
            "all symbols must be less than alphabet_size"
        );
        assert!(pointer_cost > 0, "pointer_cost must be positive");
        Self {
            alphabet_size,
            string,
            pointer_cost,
        }
    }

    /// Returns the length of the source string.
    pub fn string_length(&self) -> usize {
        self.string.len()
    }

    /// Returns the alphabet size.
    pub fn alphabet_size(&self) -> usize {
        self.alphabet_size
    }

    /// Returns the pointer cost h.
    pub fn pointer_cost(&self) -> i64 {
        self.pointer_cost
    }

    /// Returns the source string.
    pub fn string(&self) -> &[usize] {
        &self.string
    }

    /// Returns the number of valid pointers into D (|s|*(|s|+1)/2).
    fn num_pointers(&self) -> usize {
        let n = self.string.len();
        n * (n + 1) / 2
    }

    /// Returns the C-slot domain size: alphabet_size + 1 (empty) + num_pointers.
    fn c_domain_size(&self) -> usize {
        self.alphabet_size + 1 + self.num_pointers()
    }

    /// Decode a pointer index (offset from alphabet_size+1) into (start, len)
    /// in the dictionary. Pointers are enumerated as:
    /// index 0 -> (0, 1), 1 -> (0, 2), ..., n-1 -> (0, n),
    /// n -> (1, 1), n+1 -> (1, 2), ..., etc.
    fn decode_pointer(&self, ptr_idx: usize) -> Option<(usize, usize)> {
        let n = self.string.len();
        // Enumerate (start, len) pairs where 0 <= start < n, 1 <= len <= n - start
        let mut idx = 0;
        for start in 0..n {
            let max_len = n - start;
            if ptr_idx < idx + max_len {
                let len = ptr_idx - idx + 1;
                return Some((start, len));
            }
            idx += max_len;
        }
        None
    }
}

impl Problem for MinimumExternalMacroDataCompression {
    const NAME: &'static str = "MinimumExternalMacroDataCompression";
    type Solution = Vec<usize>;
    type Value = Min<i64>;

    crate::problem_parameters![
        ("alphabet_size", alphabet_size),
        ("string_length", string_length),
    ];

    fn variant() -> Vec<(&'static str, &'static str)> {
        crate::variant_params![]
    }

    fn evaluate(
        &self,
        config: &Self::Solution,
    ) -> Result<Min<i64>, crate::traits::EvaluationError> {
        Ok({
            let n = self.string.len();
            if config.len() != 2 * n {
                return Err(crate::traits::EvaluationError::InvalidConfiguration(
                    "macro encoding length does not match the string".into(),
                ));
            }

            // Handle empty string case
            if n == 0 {
                return Ok(Min(Some(0)));
            }

            let empty_d = self.alphabet_size; // empty marker for D-slots
            let empty_c = self.alphabet_size; // empty marker for C-slots

            // Decode D: prefix of non-empty D-slots
            let d_slots = &config[..n];
            let d_len = d_slots.iter().position(|&v| v == empty_d).unwrap_or(n);

            // Verify contiguous: all after first empty must be empty
            for &v in &d_slots[d_len..] {
                if v != empty_d {
                    return Ok(Min(None));
                }
            }

            // Verify D symbols are valid alphabet symbols
            let d_str: Vec<usize> = d_slots[..d_len].to_vec();
            if d_str.iter().any(|&v| v >= self.alphabet_size) {
                return Ok(Min(None));
            }

            // Decode C: prefix of non-empty C-slots
            let c_slots = &config[n..];
            let c_len = c_slots.iter().position(|&v| v == empty_c).unwrap_or(n);

            // Verify contiguous: all after first empty must be empty
            for &v in &c_slots[c_len..] {
                if v != empty_c {
                    return Ok(Min(None));
                }
            }

            // Decode C into a sequence of symbols, counting pointers
            let mut decoded = Vec::new();
            let mut pointer_count: usize = 0;

            for &v in &c_slots[..c_len] {
                if v < self.alphabet_size {
                    // Literal symbol
                    decoded.push(v);
                } else if v > self.alphabet_size {
                    // Pointer into D
                    let ptr_idx = v - (self.alphabet_size + 1);
                    if let Some((start, len)) = self.decode_pointer(ptr_idx) {
                        // Pointer must reference valid portion of D
                        if start + len > d_len {
                            return Ok(Min(None));
                        }
                        decoded.extend_from_slice(&d_str[start..start + len]);
                        pointer_count += 1;
                    } else {
                        return Ok(Min(None));
                    }
                } else {
                    // v == empty_c, but we already filtered those out
                    return Ok(Min(None));
                }
            }

            // Check decoded string matches the source string
            if decoded != self.string {
                return Ok(Min(None));
            }

            // Compute cost: |D| + |C| + (h-1) * pointer_count
            let d_len = i64::try_from(d_len).map_err(|_| {
                crate::traits::EvaluationError::IntegerOverflow(
                    "converting the dictionary length to i64".to_string(),
                )
            })?;
            let c_len = i64::try_from(c_len).map_err(|_| {
                crate::traits::EvaluationError::IntegerOverflow(
                    "converting the compressed-string length to i64".to_string(),
                )
            })?;
            let pointer_count = i64::try_from(pointer_count).map_err(|_| {
                crate::traits::EvaluationError::IntegerOverflow(
                    "converting the pointer count to i64".to_string(),
                )
            })?;
            let pointer_cost = self
                .pointer_cost
                .checked_sub(1)
                .and_then(|cost| cost.checked_mul(pointer_count))
                .ok_or_else(|| {
                    crate::traits::EvaluationError::IntegerOverflow(
                        "computing the external macro pointer cost".to_string(),
                    )
                })?;
            let cost = d_len
                .checked_add(c_len)
                .and_then(|cost| cost.checked_add(pointer_cost))
                .ok_or_else(|| {
                    crate::traits::EvaluationError::IntegerOverflow(
                        "computing the external macro compression cost".to_string(),
                    )
                })?;
            Min(Some(cost))
        })
    }
}

impl crate::solvers::BruteForceProblem for MinimumExternalMacroDataCompression {
    fn dimensions(&self) -> Vec<usize> {
        let n = self.string.len();
        let d_domain = self.alphabet_size + 1; // symbols + empty
        let c_domain = self.c_domain_size(); // symbols + empty + pointers
        let mut dims = vec![d_domain; n]; // D-slots
        dims.extend(vec![c_domain; n]); // C-slots
        dims
    }
}

crate::declare_variants! {
    default MinimumExternalMacroDataCompression => "(alphabet_size + 1) ^ string_length * (alphabet_size + 1 + string_length * (string_length + 1) / 2) ^ string_length",
}

crate::register_brute_force! {
    MinimumExternalMacroDataCompression,
}

#[cfg(feature = "example-db")]
pub(crate) fn canonical_model_example_specs() -> Vec<crate::example_db::specs::ModelExampleSpec> {
    // Issue #441 example: alphabet {a,b,c,d,e,f} (6), s="abcdefabcdefabcdef" (18), h=2.
    // Optimal: D="abcdef"(6), C = ptr(0,6) ptr(0,6) ptr(0,6), cost = 6+3+(2-1)*3 = 12.
    // Solved via ILP reduction (brute force infeasible at this size).
    //
    // Config encoding (2*18 = 36 slots):
    // D-slots: [0,1,2,3,4,5, 6,6,...,6] (6 symbols + 12 empty, empty=alphabet_size=6)
    // C-slots: [ptr(0,6), ptr(0,6), ptr(0,6), 6,6,...,6] (3 pointers + 15 empty)
    // ptr(0,6) index: start=0, len=6 → index 5 → encoded as 6+1+5 = 12
    let s: Vec<usize> = (0..6).cycle().take(18).collect();
    let mut optimal_config = vec![0, 1, 2, 3, 4, 5];
    optimal_config.extend(vec![6; 12]); // empty D-slots
    optimal_config.extend(vec![12, 12, 12]); // 3 pointers to D[0..6]
    optimal_config.extend(vec![6; 15]); // empty C-slots
    vec![crate::example_db::specs::ModelExampleSpec {
        id: "minimum_external_macro_data_compression",
        instance: Box::new(MinimumExternalMacroDataCompression::new(6, s, 2)),
        optimal_config: serde_json::to_value(optimal_config)
            .expect("solution serialization must succeed"),
        optimal_value: serde_json::json!(12),
    }]
}

#[cfg(test)]
#[path = "../../unit_tests/models/misc/minimum_external_macro_data_compression.rs"]
mod tests;