数据转换算法(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. }