Burrows-Wheeler-Transformation

Short implementation of the Burrows-Wheeler-Transformation in Visual C#.


Libraries
using System;
using System.Text;
using System.Collections.Generic;
using System.Linq;

Code Snippet
public static class BWT {
            public static string encode(string input, out int num)
            {
                string res = string.Empty;
                string data = input.ToLower();
                List<string> rotations = new List<string>();
                foreach (char c in data)
                {
                    string temp = data.Substring(1, data.Length - 1);
                    data = temp + c;
                    rotations.Add(data);
                }

                // Sort
                rotations = rotations.OrderBy(s => s).ToList();

                num = 0;
                foreach (string st in rotations)
                {
                    res += st.Substring(st.Length - 1);
                    if (st == data) num = rotations.IndexOf(st);
                }
                return res;
            }

            public static string decode(string encoded, int num)
            {
                string data = encoded.ToLower();
                List<KeyValuePair<int, string>> rotations = new List<KeyValuePair<int, string>>();
                for (int i = 0; i < data.Length; ++i)
                {
                    string temp = data[i].ToString();
                    KeyValuePair<int, string> current = new KeyValuePair<int, string>(i, temp);
                    rotations.Add(current);
                }

                rotations = rotations.OrderBy(s => s.Value).ToList();

                int index = num;
                string res = string.Empty;
                for (int i = 0; i < rotations.Count; ++i)
                {
                    res += rotations[index].Value;
                    index = rotations[index].Key;
                }

                return res;
            }
}


Implementation

<code>int n; string encoded = BWT.transform("your String", out n); string decoded = BWT.decode(encoded, n);</code> n contains the index for decoding.





Comments
  • mode_editWrite a comment



  • forumComments




Embed Code

We provide special containers which include the full snippet and a link to this site. So for example when you make a tutorial and you are using code from this site, you can use one of the following snippet embeddings:

Load Preview Get Code Close Preview







    Share
    Rating
    thumb_up 1 thumb_down
    Author
    Thorolus

    I'm the head developer and co-founder of GlovilGames Studios (glovilgames.com) and other platforms GlovilGames created, like vsnippets.com, worth-calculator.net, python-obfuscator.com and some mobile apps and games.

    Tags
    BWT
    Compression
    Math



    Informations

    posted on 2016-11-17 12:37:36

    viewed 147 times

    snippet's UUID is 582d967f8524f

    Similar Snippets