This is a simple, inefficient implementation of the Burrows-Wheeler transform in C++. I wrote it just to play around with the algorithm, not for any practical application. It takes a single text file as the input, then performs the transform and reverses it:<\/p>\n
\r\n\r\n\r\n#include <iostream>\r\n#include <fstream>\r\n#include <string>\r\n#include <vector>\r\n\r\nusing namespace std;\r\n\r\nvoid bwt(string input,string &bwt_str,int &primaryidx) {\r\n\r\n vector<string> rotations;\r\n\r\n \/\/ 1. generate rotations of input\r\n cout << "rotations:" << endl;\r\n for(int n=0;n<input.size();n++) {\r\n string s;\r\n\r\n s += input[n];\r\n for(int i=n+1;i!=n;i++) {\r\n if(i==input.size()) i=0;\r\n s += input[i];\r\n if(i==input.size()-1) i=-1;\r\n }\r\n rotations.push_back(s);\r\n cout << s << endl;\r\n }\r\n\r\n \/\/ 2. sort\r\n cout << "sorted:" << endl;\r\n sort(rotations.begin(),rotations.end());\r\n for(size_t n=0;n<rotations.size();n++) {\r\n cout << rotations[n] << endl;\r\n }\r\n\r\n bwt_str.clear();\r\n for(size_t n=0;n<rotations.size();n++) {\r\n bwt_str += rotations[n].substr(rotations[n].size()-1,1);\r\n if(rotations[n] == input) {primaryidx = n;}\r\n }\r\n cout << "bwt string: " << bwt_str << endl;\r\n cout << "primaryidx: " << primaryidx << endl;\r\n}\r\n\r\nstring rbwt(string bwt_str,int primaryidx) {\r\n\r\n vector<string> cur_str;\r\n\r\n for(size_t n=0;n<bwt_str.size();n++) {\r\n string s;\r\n s = bwt_str.substr(n,1);\r\n cur_str.push_back(s);\r\n }\r\n\r\n for(;cur_str[0].size() < bwt_str.size();) {\r\n vector<string> new_str = cur_str;\r\n sort(new_str.begin(),new_str.end());\r\n\r\n for(size_t n=0;n<cur_str.size();n++) {\r\n cur_str[n] = cur_str[n] + new_str[n].substr(new_str[n].size()-1,1);\r\n }\r\n }\r\n\r\n cout << "reversed transform:" << endl;\r\n for(size_t n=0;n<cur_str.size();n++) {\r\n cout << cur_str[n] << endl;\r\n }\r\n\r\n sort(cur_str.begin(),cur_str.end());\r\n\r\n cout << "Original String: " << cur_str[primaryidx] << endl;\r\n\r\n return cur_str[primaryidx]; \r\n\r\n}\r\n\r\nint main(int argc,char **argv) {\r\n\r\n string s;\r\n\r\n ifstream infile(argv[1]);\r\n\r\n for(;!infile.eof();) {\r\n char c = (char)infile.get();\r\n\r\n if(!infile.eof()) s += string(1,c);\r\n }\r\n cout << "input: " << s << "END" << endl;\r\n\r\n string bwt_str;\r\n int primaryidx;\r\n\r\n bwt(s,bwt_str,primaryidx);\r\n \r\n rbwt(bwt_str,primaryidx);\r\n}\r\n<\/pre>\n","protected":false},"excerpt":{"rendered":"This is a simple, inefficient implementation of the Burrows-Wheeler transform in C++. I wrote it just to play around with the algorithm, not for any practical application. It takes a single text file as the input, then performs the transform and reverses it: #include <iostream> #include <fstream> #include <string> #include <vector> using namespace std; void […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"jetpack_post_was_ever_published":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_memberships_contains_paid_content":false,"footnotes":"","jetpack_publicize_message":"","jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":false,"jetpack_social_options":{"image_generator_settings":{"template":"highway","default_image_id":0,"font":"","enabled":false},"version":2}},"categories":[1],"tags":[],"class_list":["post-842","post","type-post","status-publish","format-standard","hentry","category-uncategorized"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_shortlink":"https:\/\/wp.me\/p1RRoU-dA","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/41j.com\/blog\/wp-json\/wp\/v2\/posts\/842","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/41j.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/41j.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/41j.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/41j.com\/blog\/wp-json\/wp\/v2\/comments?post=842"}],"version-history":[{"count":1,"href":"https:\/\/41j.com\/blog\/wp-json\/wp\/v2\/posts\/842\/revisions"}],"predecessor-version":[{"id":843,"href":"https:\/\/41j.com\/blog\/wp-json\/wp\/v2\/posts\/842\/revisions\/843"}],"wp:attachment":[{"href":"https:\/\/41j.com\/blog\/wp-json\/wp\/v2\/media?parent=842"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/41j.com\/blog\/wp-json\/wp\/v2\/categories?post=842"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/41j.com\/blog\/wp-json\/wp\/v2\/tags?post=842"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}