Class NaiveSingleCharPcsClassifier

A ISingleCharPcsClassifier implementation which calculate equivalence classes using the definition.

Inheritance
System.Object
NaiveSingleCharPcsClassifier
Implements
Inherited Members
System.Object.Equals(System.Object)
System.Object.Equals(System.Object, System.Object)
System.Object.GetHashCode()
System.Object.GetType()
System.Object.MemberwiseClone()
System.Object.ReferenceEquals(System.Object, System.Object)
System.Object.ToString()
Namespace: MoreStructures.SuffixArrays.CyclicShifts
Assembly: MoreStructures.dll
Syntax
public class NaiveSingleCharPcsClassifier : ISingleCharPcsClassifier
Remarks

ADVANTAGES AND DISADVANTAGES
- Compared to more advanced implementations, such as OrderBasedSingleCharPcsClassifier, it only requires the Input, to calculate equivalence classes.
- However, its runtime is worse, both in Time and Space Complexity, than a solution based on position list, where the effort of sorting the chars has been already done previously.

ALGORITHM
- Go though each char of the Input.
- For each char, count the distinct chars of Input which are strictly smaller.
- Build an output list of the result.

COMPLEXITY
- For each of the n chars of the Input, a pass of all n chars of Input is done, to count to keep the ones which are strictly smaller.
- Count the distinct occurrences is a O(n) operation in time and space, done via the LINQ method , which uses an internal lightweight implementation of a set.
- The output is a list of n items.
- Therefore, Time Complexity is O(n^2) and Space Complexity is O(n).

Constructors

| Improve this Doc View Source

NaiveSingleCharPcsClassifier(String, Boolean)

Declaration
public NaiveSingleCharPcsClassifier(string input, bool inputWithTerminator)
Parameters
Type Name Description
System.String input

System.Boolean inputWithTerminator

Whether input is terminated by a terminator char. If so, the last char of input will be treated as a terminator char when comparing chars of the input. Otherwise, for System.Char will be used.

Properties

| Improve this Doc View Source

Input

The input text, whose 1-char PCS have to be classified.

Declaration
public string Input { get; }
Property Value
Type Description
System.String

Methods

| Improve this Doc View Source

Classify()

Runs the algorithm, calculating the equivalence classes of each 1-char PCS of the Input.

Declaration
public IList<int> Classify()
Returns
Type Description
IList<System.Int32>

A list of equivalence classes, with as many items as chars in the Input.

Implements

Extension Methods