problemreductions/models/misc/
closest_substring.rs

1//! Closest Substring problem implementation.
2//!
3//! Given a finite alphabet `{0, ..., alphabet_size - 1}`, a list of input
4//! strings (not necessarily of equal length), and a substring length `ell`,
5//! find a center string `c` of length `ell` and one length-`ell` window per
6//! input string that together minimize the maximum Hamming distance from `c`
7//! to any selected window.
8
9use crate::registry::{FieldInfo, ProblemSchemaEntry};
10use crate::traits::Problem;
11use crate::types::Min;
12use serde::{Deserialize, Serialize};
13
14inventory::submit! {
15    ProblemSchemaEntry {
16        name: "ClosestSubstring",
17        display_name: "Closest Substring",
18        aliases: &[],
19        dimensions: &[],
20        category: crate::registry::ProblemCategory::Misc,
21        module_path: module_path!(),
22        description: "Find a center string of fixed length and one length-ell window per input string that minimize the maximum Hamming distance between the center and any selected window",
23        fields: &[
24            FieldInfo {
25                name: "alphabet_size",
26                type_name: "usize",
27                description: "Size q of the finite alphabet {0, ..., q-1}",
28            },
29            FieldInfo {
30                name: "strings",
31                type_name: "Vec<Vec<usize>>",
32                description: "Input strings s_1, ..., s_n over the alphabet (possibly of different lengths)",
33            },
34            FieldInfo {
35                name: "substring_length",
36                type_name: "usize",
37                description: "Common window length ell; every input string must have length at least substring_length",
38            },
39        ],
40    }
41}
42
43/// The Closest Substring problem.
44///
45/// Given a finite alphabet `Sigma = {0, ..., q - 1}`, `n` input strings
46/// `s_1, ..., s_n` over `Sigma` (not necessarily of equal length), and a
47/// window length `ell` with `ell <= |s_i|` for every `i`, find a center
48/// `c in Sigma^ell` and per-string window start positions `p_i in {0, ..., W_i - 1}`
49/// (where `W_i = |s_i| - ell + 1`) minimizing
50///
51/// `max_{1 <= i <= n} d_H(c, s_i[p_i .. p_i + ell))`,
52///
53/// where `d_H` is the Hamming distance. Every choice in the discrete cube is
54/// syntactically feasible.
55#[derive(Debug, Clone, Serialize)]
56pub struct ClosestSubstring {
57    alphabet_size: usize,
58    strings: Vec<Vec<usize>>,
59    substring_length: usize,
60}
61
62#[derive(Deserialize)]
63struct ClosestSubstringData {
64    alphabet_size: usize,
65    strings: Vec<Vec<usize>>,
66    substring_length: usize,
67}
68
69impl<'de> Deserialize<'de> for ClosestSubstring {
70    fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
71    where
72        D: serde::Deserializer<'de>,
73    {
74        let data = ClosestSubstringData::deserialize(deserializer)?;
75        Self::new(data.alphabet_size, data.strings, data.substring_length)
76            .map_err(serde::de::Error::custom)
77    }
78}
79
80impl ClosestSubstring {
81    /// Create a new `ClosestSubstring` instance.
82    ///
83    pub fn new(
84        alphabet_size: usize,
85        strings: Vec<Vec<usize>>,
86        substring_length: usize,
87    ) -> Result<Self, crate::registry::ConstructionError> {
88        if strings.is_empty() {
89            return Err("ClosestSubstring requires at least one input string".into());
90        }
91        if strings.iter().any(|s| s.len() < substring_length) {
92            return Err("substring_length must be <= |s_i| for every input string".into());
93        }
94        if alphabet_size == 0 && substring_length > 0 {
95            return Err("alphabet_size must be > 0 when substring_length > 0".into());
96        }
97        if strings
98            .iter()
99            .flat_map(|s| s.iter())
100            .any(|&symbol| symbol >= alphabet_size)
101        {
102            return Err("input symbols must be less than alphabet_size".into());
103        }
104        substring_length
105            .checked_add(strings.len())
106            .ok_or("configuration length exceeds usize")?;
107        strings
108            .iter()
109            .try_fold(0_usize, |total, string| total.checked_add(string.len()))
110            .ok_or("total input length exceeds usize")?;
111        strings
112            .iter()
113            .map(|string| string.len() - substring_length + 1)
114            .try_fold(0_usize, usize::checked_add)
115            .ok_or("total number of windows exceeds usize")?;
116        Ok(Self {
117            alphabet_size,
118            strings,
119            substring_length,
120        })
121    }
122
123    /// Returns the alphabet size `q`.
124    pub fn alphabet_size(&self) -> usize {
125        self.alphabet_size
126    }
127
128    /// Returns the input strings.
129    pub fn strings(&self) -> &[Vec<usize>] {
130        &self.strings
131    }
132
133    /// Returns the number of input strings `n`.
134    pub fn num_strings(&self) -> usize {
135        self.strings.len()
136    }
137
138    /// Returns the common window length `ell`.
139    pub fn substring_length(&self) -> usize {
140        self.substring_length
141    }
142
143    /// Returns the sum of input string lengths.
144    pub fn total_length(&self) -> usize {
145        self.strings.iter().map(|s| s.len()).sum()
146    }
147
148    /// Returns `sum_i W_i`, where `W_i = |s_i| - substring_length + 1`.
149    pub fn total_num_windows(&self) -> usize {
150        self.strings
151            .iter()
152            .map(|s| s.len() - self.substring_length + 1)
153            .sum()
154    }
155}
156
157impl Problem for ClosestSubstring {
158    const NAME: &'static str = "ClosestSubstring";
159    type Solution = Vec<usize>;
160    type Value = Min<i64>;
161
162    crate::problem_parameters![
163        ("alphabet_size", alphabet_size),
164        ("num_strings", num_strings),
165        ("substring_length", substring_length),
166        ("total_length", total_length),
167        ("total_num_windows", total_num_windows),
168    ];
169
170    fn variant() -> Vec<(&'static str, &'static str)> {
171        crate::variant_params![]
172    }
173
174    fn evaluate(
175        &self,
176        config: &Self::Solution,
177    ) -> Result<Min<i64>, crate::traits::EvaluationError> {
178        Ok({
179            let ell = self.substring_length;
180            let n = self.num_strings();
181            if config.len() != ell + n {
182                return Err(crate::traits::EvaluationError::InvalidConfiguration(
183                    "substring witness length does not match the instance".into(),
184                ));
185            }
186            let (center, window_starts) = config.split_at(ell);
187            if center.iter().any(|&symbol| symbol >= self.alphabet_size) {
188                return Ok(Min(None));
189            }
190            for (i, &start) in window_starts.iter().enumerate() {
191                let w_i = self.strings[i].len() - ell + 1;
192                if start >= w_i {
193                    return Err(crate::traits::EvaluationError::InvalidConfiguration(
194                        "substring witness contains an out-of-range window start".into(),
195                    ));
196                }
197            }
198            // Maximum Hamming distance from the center to the chosen window of each string.
199            let mut max_distance = 0_i64;
200            for (i, &start) in window_starts.iter().enumerate() {
201                let window = &self.strings[i][start..start + ell];
202                let distance = i64::try_from(
203                    center
204                        .iter()
205                        .zip(window.iter())
206                        .filter(|(center_symbol, target_symbol)| center_symbol != target_symbol)
207                        .count(),
208                )
209                .map_err(|_| {
210                    crate::traits::EvaluationError::IntegerOverflow(
211                        "converting substring Hamming distance to i64".into(),
212                    )
213                })?;
214                max_distance = max_distance.max(distance);
215            }
216            Min(Some(max_distance))
217        })
218    }
219}
220
221impl crate::solvers::BruteForceProblem for ClosestSubstring {
222    fn dimensions(&self) -> Vec<usize> {
223        let ell = self.substring_length;
224        let mut dims = vec![self.alphabet_size; ell];
225        dims.extend(self.strings.iter().map(|s| s.len() - ell + 1));
226        dims
227    }
228}
229
230crate::declare_variants! {
231    // AM-GM bounds the window-count product; this is an upper bound, not the exact count.
232    default ClosestSubstring => "alphabet_size ^ substring_length * (total_num_windows / num_strings)^num_strings",
233}
234
235crate::register_brute_force! {
236    ClosestSubstring,
237}
238
239#[cfg(feature = "example-db")]
240pub(crate) fn canonical_model_example_specs() -> Vec<crate::example_db::specs::ModelExampleSpec> {
241    vec![crate::example_db::specs::ModelExampleSpec {
242        id: "closest_substring",
243        instance: Box::new(
244            ClosestSubstring::new(
245                2,
246                vec![
247                    vec![0, 0, 0, 1, 1],
248                    vec![1, 0, 1, 0, 0],
249                    vec![1, 1, 0, 0, 1],
250                ],
251                3,
252            )
253            .unwrap(),
254        ),
255        // Center c = [0, 1, 0]; windows (0, 1, 0) selecting s_1[0..3] = 000,
256        // s_2[1..4] = 010, s_3[0..3] = 110 with distances 1, 0, 1 and radius 1.
257        optimal_config: serde_json::json!(vec![0, 1, 0, 0, 1, 0]),
258        optimal_value: serde_json::json!(1),
259    }]
260}
261
262#[cfg(test)]
263#[path = "../../unit_tests/models/misc/closest_substring.rs"]
264mod tests;
problemreductions/models/misc/closest_substring.rs

problemreductions/models/misc/
closest_substring.rs
