problemreductions/models/misc/

minimum_internal_macro_data_compression.rs

//! Minimum Internal Macro Data Compression problem implementation.
//!
//! Given an alphabet Σ, a string s ∈ Σ*, and a pointer cost h,
//! find a single compressed string C ∈ (Σ ∪ {pointers})* minimizing the cost
//! |C| + (h−1) × (number of pointer occurrences in C),
//! such that s can be obtained from C by resolving all pointer references
//! within C itself (left-to-right, greedy longest match).
//!
//! Unlike external macro compression, there is no separate dictionary — the
//! compressed string C serves as both dictionary and output.
//!
//! This problem is NP-hard (Storer, 1977; Storer & Szymanski, 1978).
//! Reference: Garey & Johnson A4 SR23.

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

inventory::submit! {
    ProblemSchemaEntry {
        name: "MinimumInternalMacroDataCompression",
        display_name: "Minimum Internal Macro Data Compression",
        aliases: &[],
        dimensions: &[],
        category: crate::registry::ProblemCategory::Misc,
        module_path: module_path!(),
        description: "Find minimum-cost self-referencing compression of a string with embedded 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 adds h−1 extra to the cost)" },
        ],
    }
}

/// Minimum Internal Macro Data Compression problem.
///
/// Given an alphabet of size `k`, a string `s` over `{0, ..., k-1}`, and
/// a pointer cost `h`, find a compressed string C that minimizes
/// cost = |C| + (h−1) × (pointer count in C), where C uses itself as both
/// dictionary and compressed output.
///
/// # Representation
///
/// The configuration is a vector of `string_len` entries. Each entry is:
/// - A symbol index in `{0, ..., alphabet_size-1}` (literal)
/// - `alphabet_size` (end-of-string marker; positions after this are padding)
/// - A value in `{alphabet_size+1, ..., alphabet_size + string_len}`,
///   encoding a pointer to C\[v − alphabet_size − 1\] with greedy longest match.
///
/// During decoding, pointers are resolved left-to-right. A pointer at position
/// i referencing position j (where j < i in the decoded output) copies symbols
/// from the already-decoded output starting at j using greedy longest match.
///
/// # Example
///
/// ```
/// use problemreductions::models::misc::MinimumInternalMacroDataCompression;
/// use problemreductions::{Problem, BruteForce};
///
/// // Alphabet {a, b}, string "abab", pointer cost h=2
/// let problem = MinimumInternalMacroDataCompression::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 = "MinimumInternalMacroDataCompressionSerde")]
pub struct MinimumInternalMacroDataCompression {
    alphabet_size: usize,
    string: Vec<usize>,
    pointer_cost: i64,
}

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

impl TryFrom<MinimumInternalMacroDataCompressionSerde> for MinimumInternalMacroDataCompression {
    type Error = crate::registry::ConstructionError;

    fn try_from(value: MinimumInternalMacroDataCompressionSerde) -> 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 MinimumInternalMacroDataCompression {
    /// Create a new MinimumInternalMacroDataCompression 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_len(&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
    }

    /// Decode the compressed string C and return the decoded string,
    /// the active length of C, and the pointer count.
    /// Returns None if decoding fails (invalid pointer, circular reference, etc.).
    fn decode(&self, config: &[usize]) -> Option<(Vec<usize>, usize, usize)> {
        let n = self.string.len();
        let k = self.alphabet_size;
        let eos = k; // end-of-string marker

        // Find active length: prefix before first end-of-string marker
        let active_len = config.iter().position(|&v| v == eos).unwrap_or(n);

        // Verify contiguous: all after first EOS must be EOS or padding
        for &v in &config[active_len..] {
            if v != eos {
                return None;
            }
        }

        // Decode left-to-right. A pointer at compressed position c_idx
        // referencing C[j] copies from the decoded output that existed
        // before this pointer (no overlapping/runaway copy).
        let mut decoded = Vec::new();
        let mut pointer_count: usize = 0;

        for &v in &config[..active_len] {
            if v < k {
                // Literal symbol
                decoded.push(v);
            } else if v > k {
                // Pointer: references C[ref_pos] in the compressed string
                let ref_pos = v - k - 1;
                if ref_pos >= decoded.len() {
                    return None; // pointer references undecoded position
                }
                // Greedy longest match from decoded[ref_pos..copy_start]
                // (only pre-existing decoded content, no overlapping copy)
                let copy_start = decoded.len();
                let mut matched = 0;
                while copy_start + matched < n {
                    let src_idx = ref_pos + matched;
                    if src_idx >= copy_start {
                        break; // cannot read beyond pre-existing content
                    }
                    if decoded[src_idx] != self.string[copy_start + matched] {
                        break;
                    }
                    decoded.push(decoded[src_idx]);
                    matched += 1;
                }
                if matched == 0 {
                    return None; // pointer must copy at least one symbol
                }
                pointer_count += 1;
            } else {
                // v == eos, but we filtered those out above
                return None;
            }
        }

        Some((decoded, active_len, pointer_count))
    }
}

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

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

    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() != n {
                return Err(crate::traits::EvaluationError::InvalidConfiguration(
                    "macro encoding length does not match the string".into(),
                ));
            }

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

            match self.decode(config) {
                Some((decoded, active_len, pointer_count)) => {
                    if decoded != self.string {
                        Min(None)
                    } else {
                        let active_len = i64::try_from(active_len).map_err(|_| {
                            crate::traits::EvaluationError::IntegerOverflow(
                                "converting the active encoding 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 internal macro pointer cost".to_string(),
                                )
                            })?;
                        let cost = active_len.checked_add(pointer_cost).ok_or_else(|| {
                            crate::traits::EvaluationError::IntegerOverflow(
                                "computing the internal macro compression cost".to_string(),
                            )
                        })?;
                        Min(Some(cost))
                    }
                }
                None => Min(None),
            }
        })
    }
}

impl crate::solvers::BruteForceProblem for MinimumInternalMacroDataCompression {
    fn dimensions(&self) -> Vec<usize> {
        let n = self.string.len();
        let domain = self.alphabet_size + n + 1; // literals + EOS + pointers
        vec![domain; n]
    }
}

crate::declare_variants! {
    default MinimumInternalMacroDataCompression => "(alphabet_size + string_len + 1) ^ string_len",
}

crate::register_brute_force! {
    MinimumInternalMacroDataCompression,
}

#[cfg(feature = "example-db")]
pub(crate) fn canonical_model_example_specs() -> Vec<crate::example_db::specs::ModelExampleSpec> {
    // Issue #442 example: alphabet {a,b,c} (3), s="abcabcabc" (9), h=2
    // Optimal: C = [a, b, c, ptr(0), ptr(0), EOS, EOS, EOS, EOS]
    //   active_len = 5, pointers = 2
    //   cost = 5 + (2-1)*2 = 7
    //
    // Config encoding:
    //   alphabet_size = 3, string_len = 9, domain = 3+9+1 = 13
    //   Literals: 0=a, 1=b, 2=c
    //   EOS: 3
    //   Pointers: 4=ptr(C[0]), 5=ptr(C[1]), ...
    let s: Vec<usize> = vec![0, 1, 2, 0, 1, 2, 0, 1, 2];
    let optimal_config = vec![
        0, 1, 2, // literals a, b, c
        4, // ptr(C[0]) -> greedy "abc"
        4, // ptr(C[0]) -> greedy "abc"
        3, 3, 3, 3, // EOS padding
    ];
    vec![crate::example_db::specs::ModelExampleSpec {
        id: "minimum_internal_macro_data_compression",
        instance: Box::new(MinimumInternalMacroDataCompression::new(3, s, 2)),
        optimal_config: serde_json::to_value(optimal_config)
            .expect("solution serialization must succeed"),
        optimal_value: serde_json::json!(7),
    }]
}

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