数据转换算法(Burrows Wheeler Transform)

  1. pub fn burrows_wheeler_transform(input: String) -> (String, usize) {
  2.     let len = input.len();
  4.     let mut table = Vec::<String>::with_capacity(len);
  5.     for i in 0..len {
  6.         table.push(input[i..].to_owned() + &input[..i]);
  7.     }
  8.     table.sort_by_key(|a| a.to_lowercase());
  10.     let mut encoded = String::new();
  11.     let mut index: usize = 0;
  12.     for (i, item) in table.iter().enumerate().take(len) {
  13.         encoded.push(item.chars().last().unwrap());
  14.         if item.eq(&input) {
  15.             index = i;
  16.         }
  17.     }
  19.     (encoded, index)
  20. }
  22. pub fn inv_burrows_wheeler_transform(input: (String, usize)) -> String {
  23.     let len = input.0.len();
  24.     let mut table = Vec::<(usize, char)>::with_capacity(len);
  25.     for i in 0..len {
  26.         table.push((i, input.0.chars().nth(i).unwrap()));
  27.     }
  29.     table.sort_by(|a, b| a.1.cmp(&b.1));
  31.     let mut decoded = String::new();
  32.     let mut idx = input.1;
  33.     for _ in 0..len {
  34.         decoded.push(table[idx].1);
  35.         idx = table[idx].0;
  36.     }
  38.     decoded
  39. }
  41. #[cfg(test)]
  42. mod tests {
  43.     use super::*;
  45.     #[test]
  46.     fn basic() {
  47.         assert_eq!(
  48.             inv_burrows_wheeler_transform(burrows_wheeler_transform("CARROT".to_string())),
  49.             "CARROT"
  50.         );
  51.         assert_eq!(
  52.             inv_burrows_wheeler_transform(burrows_wheeler_transform("TOMATO".to_string())),
  53.             "TOMATO"
  54.         );
  55.         assert_eq!(
  56.             inv_burrows_wheeler_transform(burrows_wheeler_transform("THISISATEST".to_string())),
  57.             "THISISATEST"
  58.         );
  59.         assert_eq!(
  60.             inv_burrows_wheeler_transform(burrows_wheeler_transform("THEALGORITHMS".to_string())),
  61.             "THEALGORITHMS"
  62.         );
  63.         assert_eq!(
  64.             inv_burrows_wheeler_transform(burrows_wheeler_transform("RUST".to_string())),
  65.             "RUST"
  66.         );
  67.     }
  69.     #[test]
  70.     fn special_characters() {
  71.         assert_eq!(
  72.             inv_burrows_wheeler_transform(burrows_wheeler_transform("!.!.!??.=::".to_string())),
  73.             "!.!.!??.=::"
  74.         );
  75.         assert_eq!(
  76.             inv_burrows_wheeler_transform(burrows_wheeler_transform(
  77.                 "!{}{}(((&&%%!??.=::".to_string()
  78.             )),
  79.             "!{}{}(((&&%%!??.=::"
  80.         );
  81.         assert_eq!(
  82.             inv_burrows_wheeler_transform(burrows_wheeler_transform("//&$[]".to_string())),
  83.             "//&$[]"
  84.         );
  85.     }
  87.     #[test]
  88.     fn empty() {
  89.         assert_eq!(
  90.             inv_burrows_wheeler_transform(burrows_wheeler_transform("".to_string())),
  91.             ""
  92.         );
  93.     }
  94. }