BurrowsWheelerTransform.cs

using System;
using System.Linq;

namespace Algorithms.DataCompression;

/// <summary>
///     The Burrows–Wheeler transform (BWT) rearranges a character string into runs of similar characters.
///     This is useful for compression, since it tends to be easy to compress a string that has runs of repeated
///     characters.
///     See <a href="https://en.wikipedia.org/wiki/Burrows%E2%80%93Wheeler_transform">here</a> for more info.
/// </summary>
public class BurrowsWheelerTransform
{
    /// <summary>
    ///     Encodes the input string using BWT and returns encoded string and the index of original string in the sorted
    ///     rotation matrix.
    /// </summary>
    /// <param name="s">Input string.</param>
    public (string encoded, int index) Encode(string s)
    {
        if (s.Length == 0)
        {
            return (string.Empty, 0);
        }

        var rotations = GetRotations(s);
        Array.Sort(rotations, StringComparer.Ordinal);
        var lastColumn = rotations
            .Select(x => x[^1])
            .ToArray();
        var encoded = new string(lastColumn);
        return (encoded, Array.IndexOf(rotations, s));
    }

    /// <summary>
    ///     Decodes the input string and returns original string.
    /// </summary>
    /// <param name="s">Encoded string.</param>
    /// <param name="index">Index  of original string in the sorted rotation matrix.</param>
    public string Decode(string s, int index)
    {
        if (s.Length == 0)
        {
            return string.Empty;
        }

        var rotations = new string[s.Length];

        for (var i = 0; i < s.Length; i++)
        {
            for (var j = 0; j < s.Length; j++)
            {
                rotations[j] = s[j] + rotations[j];
            }

            Array.Sort(rotations, StringComparer.Ordinal);
        }

        return rotations[index];
    }

    private string[] GetRotations(string s)
    {
        var result = new string[s.Length];

        for (var i = 0; i < s.Length; i++)
        {
            result[i] = s.Substring(i) + s.Substring(0, i);
        }

        return result;
    }
}