Interface IBuilder

Builds Burrows-Wheeler objects, such as BWMatrix and BWTransform of the provided TextWithTerminator.

Namespace: MoreStructures.BurrowsWheelerTransform.Builders
Assembly: MoreStructures.dll
Syntax
public interface IBuilder

Methods

| Improve this Doc View Source

BuildMatrix(BWTransform)

Rebuilds the original BWMatrix from a BWTransform representing the last column of the Burrows-Wheeler Matrix (which is also the Burrows-Wheeler Transform).

Declaration
BWMatrix BuildMatrix(BWTransform lastBWMColumn)
Parameters
Type Name Description
BWTransform lastBWMColumn

The last column of the Burrows-Wheeler Matrix.
Returns
Type Description
BWMatrix

The matrix, wrapped into a BWMatrix object.
Remarks

Because the entire Burrows-Wheeler Matrix is built from the text with an invertible function, and the same happens for the Burrows-Wheeler Transform of the text, it's possible to get back the entire matrix from its last column.

| Improve this Doc View Source

BuildMatrix(TextWithTerminator)

Build a BWMatrix of the provided text, which is a n-ary search tree in which edges coming out of a node are substrings of text which identify edges shared by all paths to leaves, starting from the node.

Declaration
BWMatrix BuildMatrix(TextWithTerminator text)
Parameters
Type Name Description
TextWithTerminator text

The text to build the BWM, with its terminator (required).
Returns
Type Description
BWMatrix

The matrix, wrapped into a BWMatrix object.
Remarks

Examples

Code:

var builder = ...
builder.BuildMatrix(new("mississippi")).Content

Result:

{
    "$mississippi",
    "i$mississipp",
    "ippi$mississ",
    "issippi$miss",
    "ississippi$m",
    "mississippi$",
    "pi$mississip",
    "ppi$mississi",
    "sippi$missis",
    "sissippi$mis",
    "ssippi$missi",
    "ssissippi$mi",
}
| Improve this Doc View Source

BuildTransform(BWMatrix)

Builds the Burrows-Wheeler Transform from the provided BWMatrix.

Declaration
BWTransform BuildTransform(BWMatrix matrix)
Parameters
Type Name Description
BWMatrix matrix

The matrix, whose BWT has to be calculated.
Returns
Type Description
BWTransform

The transform, wrapped into a BWTransform object.
Remarks

| Improve this Doc View Source

BuildTransform(TextWithTerminator)

Builds the Burrows-Wheeler Transform from the provided TextWithTerminator.

Declaration
BWTransform BuildTransform(TextWithTerminator text)
Parameters
Type Name Description
TextWithTerminator text

The text, whose BWT has to be calculated.
Returns
Type Description
BWTransform

The transform, wrapped into a BWTransform object.
Remarks

| Improve this Doc View Source

InvertMatrix(BWMatrix)

Rebuilds the original TextWithTerminator from the BWMatrix.

Declaration
TextWithTerminator InvertMatrix(BWMatrix matrix)
Parameters
Type Name Description
BWMatrix matrix

The matrix, whose original text has to be calculated.
Returns
Type Description
TextWithTerminator

The text which corresponds to the provided matrix.
| Improve this Doc View Source

InvertTransform(RotatedTextWithTerminator)

Rebuilds the original TextWithTerminator from a RotatedTextWithTerminator representing the last column of the Burrows-Wheeler Matrix (which is also the Burrows-Wheeler Transform).

Declaration
TextWithTerminator InvertTransform(RotatedTextWithTerminator lastBWMColumn)
Parameters
Type Name Description
RotatedTextWithTerminator lastBWMColumn

The last column of the Burrows-Wheeler Matrix.
Returns
Type Description
TextWithTerminator

The text which corresponds to the provided text which produced a BWM whose last column is the one provided.
Remarks

REQUIREMENT
lastBWMColumn requires a terminator to be specified in order to correctly compare strings, since the terminator should always be considered smaller than any other char.

ALGORITHM
Multiple strategies for inversion are possible: via n-mers construction, via last-first property, ...

Extension Methods