BurrowsWheelerTransform.cs

usingSystem;
usingSystem.Linq;

namespaceAlgorithms.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>
publicclassBurrowsWheelerTransform
{
/// <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(stringEncoded,intIndex)Encode(strings)
{
if(s.Length==0)
{
return(string.Empty,0);
}

varrotations=GetRotations(s);
Array.Sort(rotations,StringComparer.Ordinal);
varlastColumn=rotations
.Select(x =>x[^1])
.ToArray();
varencoded=newstring(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>
publicstringDecode(strings,intindex)
{
if(s.Length==0)
{
returnstring.Empty;
}

varrotations=newstring[s.Length];

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

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

returnrotations[index];
}

privatestring[]GetRotations(strings)
{
varresult=newstring[s.Length];

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

returnresult;
}
}