Answered! Analysing n-grams in a sample text (NgramAnalyser)…

import java.util.ArrayList;
import java.util.HashMap;
import java.util.Set;
import java.util.Map;
import java.util.LinkedHashMap;
import java.util.HashSet;
import java.util.Arrays;

/**
* Perform n-gram analysis of a string.
*
* Analyses the frequency with which distinct n-grams, of length n,
* appear in an input string. For the purposes of all analyses of the input
* string, the final n-1 n-grams appearing in the string should be
* “filled out” to a length of n characters, by adding
* a sequence of contiguous characters from the start of the string.
* e.g. “abbc” includes “bca” and “cab” in its 3-grams
*/
public class NgramAnalyser {
/** dictionary of all distinct n-grams and their frequencies */
private HashMap<String,Integer> ngram;

/** number of distinct characters in the input */
private int alphabetSize;

/** n-gram size for this object (new field) */
private int ngramSize;

/**
* Analyse the frequency with which distinct n-grams, of length n,
* appear in an input string.
* n-grams at the end of the string wrap to the front
* e.g. “abbbbc” includes “bca” and “cab” in its 3-grams
* ngram Hashmap is sorted alphabetically after being completed
* @param int n size of n-grams to create
* @param String inp input string to be modelled
*/
public NgramAnalyser(int n, String inp) {

this.checkNgramInput(n, inp);

this.ngramSize = n;
this.ngram = new HashMap<String, Integer>(inp.length());

ArrayList<Character> distinctLetters = new ArrayList<Character>();

String ngramTemp;
Character charTemp;
int ngramOccurance;

for (int i = 0; i < inp.length(); i++) {

ngramTemp = this.splice(inp, i, ngramSize);
charTemp = inp.charAt(i);

if (this.ngram.containsKey(ngramTemp)) {
ngramOccurance = this.ngram.get(ngramTemp);
this.ngram.put(ngramTemp, ngramOccurance + 1);
} else {
this.ngram.put(ngramTemp, 1);
}

if (!distinctLetters.contains(charTemp)) {
distinctLetters.add(charTemp);
}
}

this.alphabetSize = distinctLetters.size();

this.ngramSort();

}

/**
* Analyses the input text for n-grams of size 1.
*/
public NgramAnalyser(String inp) {
this(1,inp);
}

/**
* @return int the size of the alphabet of a given input
*/
public int getAlphabetSize() {
return this.alphabetSize;
}

/**
* @return the total number of distinct n-grams appearing
*         in the input text.
*/
public int getDistinctNgramCount() {

Set<String> distinctNgrams = this.getDistinctNgrams();

return distinctNgrams.size();
}

/**
* @return Return a set containing all the distinct n-grams
*         in the input string.
*/
public Set<String> getDistinctNgrams() {

Set<String> distinctNgrams = this.ngram.keySet();
return distinctNgrams;
}

/**
* @return the total number of n-grams appearing
*         in the input text (not requiring them to be distinct)
* should be equal to the length of the input string
*/
public int getNgramCount() {

int ngramcount = 0;

for (Map.Entry<String, Integer> entry : this.ngram.entrySet()) {
ngramcount += entry.getValue();
}

return ngramcount;
}

/**
* Return the frequency with which a particular n-gram appears
* in the text. If it does not appear at all, return 0.
*
* @param ngram The n-gram to get the frequency of
* @return The frequency with which the n-gram appears.
*/
public int getNgramFrequency(String ngram) {
for (Map.Entry<String, Integer> entry : this.ngram.entrySet()) {
if (ngram.equals(entry.getKey())) {
return entry.getValue();
}
}

return 0;
}

/**
* Generate a summary of the ngrams for this object.
* @return a string representation of the n-grams in the input text
* comprising the ngram size and then each ngram and its frequency
* where ngrams are presented in alphabetical order.
*/
public String toString() {

String outputString = Integer.toString(this.ngramSize);
outputString = outputString + “n”;
outputString = outputString + this.printHashMap(this.ngram);

return outputString;
}

/**
* @return a sub-string specified by the starting index (inclusive) and its length
* If startIndex + length > str.length(), the resulting sub-string will wrap around the end
* Hence splice(“hello”, 3, 4) returns “lohe” (“lo” from the end and “he” from the start)
* And splice (“burger”, 2, 3) returns “rge”
* @throws an IndexOutOfBounds exception if startIndex is negative
* or length is greater than str.length()
* @param s – string to splice
* @param startIndex – start of splice (inclusive)
* @param length – length of splice (number of character in sub-string)
* Public for use in ModelMatcher.java to find sequences.
*/

public static String splice(String s, int startIndex, int length) {

if (length > s.length()) {
throw new IndexOutOfBoundsException
(“NgramAnalyser: Length of substring greater than parent string”);
}

int endIndex = (startIndex + length) % s.length();

if (endIndex <= startIndex ) {
return s.substring(startIndex, s.length()) + s.substring(0, endIndex);
} else {
return s.substring(startIndex, endIndex);
}
}

/**
* Sort am ngram Hashmap by it’s keys (alphabetically)
* @return The sorted hashmap
* Requires the hashmap to have strings for keys and
* integers for values, as per the ngram hashmap
* for both the parameter and the returned map.
* @param map – The hashmap to be sorted
* @throws an IllegalArgument exception if map is not initialized/empty
*/

private HashMap<String, Integer> mapSort(HashMap<String, Integer> map) {

if (map == null || map.size() == 0) {
throw new IllegalArgumentException(“mapSort: map must be initialized and non-empty”);
}

Object[] keysObject = map.keySet().toArray();

//Convert keys object array to keys string array
String[] keys = Arrays.copyOf(keysObject, keysObject.length, String[].class);

Arrays.sort(keys);

HashMap<String, Integer> newMap = new LinkedHashMap<String, Integer>();
int newValue;

for (String newKey : keys) {
newValue = map.get(newKey);
newMap.put(newKey, newValue);
}

return newMap;
}

/**
* Sorts the classes ngram hashmap
* @return the sorted hashmap
* Calls mapSort with parameter this.ngram
*/

private void ngramSort() {
this.ngram = this.mapSort(this.ngram);
}

/**
* Helper function that runs the input of an Ngram constructor
* against some basic checks to sanitize inputs.
* @throws an IllegalArgumentException if the input fields are unsuitable:
*         – input string is empty or null
*         – ngram size is smaller than zero or
*           greater than the length of the input string
*/

private void checkNgramInput(int n, String input) {
if (input == null) {
throw new IllegalArgumentException(“NgramAnalyser: Input string cannot be null”);
} else if (input == “”) {
throw new IllegalArgumentException(“NgramAnalyser: Input string cannot be empty”);
}

if (n <= 0 || n > input.length()) {
throw new IllegalArgumentException
(“NgramAnalyser: ngram size is out of string index bounds”);
}
}

/**
* Utility function to print out a Hashmap in a table format as per project specs
* @param – map to be printed
* @return a string of the map table
*         each entry is printed on its own line, with key and value seperated by a space
*         No newline characters precede or follow the table string
* @throws an IllegalArgumentException if the map is null/empty
* Generic types used to handle both doubles and integers
*/

public static <N extends Number> String printHashMap(HashMap<String, N> map) {

String outputString = “”;

for (Map.Entry<String, N> entry : map.entrySet()) {
outputString = outputString + entry.getKey() + ” ” + entry.getValue().toString();
outputString = outputString + “n”;
}

//Remove final n
outputString = NgramAnalyser.splice(outputString, 0, outputString.length() – 1);

return outputString;
}

}
==========================================================================================================
//ProjectTest.java
import static org.junit.Assert.*;
import org.junit.After;
import org.junit.Before;
import org.junit.Test;
import java.util.Set;

/**
* The test class ProjectTest for student test cases.
* Add all new test cases to this task.
*
*/
public class ProjectTest
{
/**
* Default constructor for test class ProjectTest
*/
public ProjectTest() {

}

/**
* Sets up the test fixture.
*
* Called before every test case method.
*/
@Before
public void setUp() {
}

/**
* Tears down the test fixture.
*
* Called after every test case method.
*/
@After
public void tearDown() {

}

//TODO add new test cases from here include brief documentation

/**
* Test if the number of lines in a string output from Ngram.toString()
* is valid (i.e equal to the size of the alphabet of that Ngram)
* Also ensures that the sort, splice and constructor functions work
* as required to produce the required comparison
*/
@Test(timeout=1000)
public void testSensibleToStringSize() {

String[] stringsToTest = {“Hello my friend”,
“be”,
“Have a nice day you filthy animal”,
“asdfghjkl$$sdfghj%%”,
“2”,
“adadadadaaaaa”,
”    “};

Integer[] ngramSizesToTest = {1, 2, 3, 4, 5};

NgramAnalyser analysis;
String analysisString;

for (String s : stringsToTest) {
for (int i : ngramSizesToTest) {

if (i > s.length()) {
try {
analysis = new NgramAnalyser(i, s);
} catch (IllegalArgumentException e) {
assertEquals(0, 0);
}
} else {
analysis = new NgramAnalyser(i, s);
analysisString = analysis.toString();

//Number of lines is equal to the number of n’s plus 1
int numberofLines = analysisString.length() –
analysisString.replace(“n”, “”).length() + 1;

assert(numberofLines >= analysis.getAlphabetSize());

}
}
}
}

/**
* Tests various aspects of the getDistinctNgrams function
* inlcuding set length with comparison to basic boundaries
*/

@Test(timeout=1000)
public void testGetDistinctNgrams() {
String[] stringsToTest = {
“123!@#123!@#”,
“adadadadadadadad”,
“cadadcdaadcdbed”,
“aaaaaa”,
“HOWWEYVUFXBINEF”,
“ba”,
“a e”
};

for (String stringToTest : stringsToTest) {

int ngramSize = 2;
NgramAnalyser analysis = new NgramAnalyser(ngramSize, stringToTest);

Set<String> distinctNgrams = analysis.getDistinctNgrams();
int distinctNgramCount = analysis.getDistinctNgramCount();
int totalNgramCount = analysis.getNgramCount();

//Test that there are fewer or equal distinct Ngrams than total Ngrams
assert(distinctNgramCount <= totalNgramCount);

//Test that there are fewer or equal distinct Ngrams than the size
//of the analysed string
assert(distinctNgramCount <= stringToTest.length());

//Test that the alphabet size is smaller than
//or equal to the number of distinct NGrams
assert(analysis.getAlphabetSize() <= distinctNgramCount);
}

}

/**
* Tests the NgramAnalyser function for more complicated and longer ngrams
* Shore up and finish sooner or later
*/
@Test(timeout=1000)
public void testNgramAnalyser() {

//Realistic testing – e.g on long strings
String[] stringsToTest = {
“modelMatcher.get(this.getAlphabetSize() – 1 the 15##&&&”,

“The quick brown fox jumped over the lazy dog”,

“The probability we obtain from this calculation may be very”+
“small – in fact, potentially so small as to be indistinguishable”+
“from zero when using Java’s built-in floating-point arithmetic.”+
“Therefore, we will calculate and express the likelihood using”,

“In this project, your task will be to write a computer program”+
“that can (usually) predict whether text samples such as these”+
“are more likely to have been written by one author or another, “+
“be from one language or another and so on. There are many”+
“reasonable computational approaches to this problem. Our approach”+
“will not be to try to solve the problem as an intelligent human”+
“would. Instead, in this project, we will consider one of the”+
“computational models: Markov models. We will begin by building”+
“a statistical model of the kind of language used in each category”+
“of texts we consider. For example, we will train a system using text”+
“by different authors. Then, given a new piece of text, we will”+
“determine who wrote it by measuring how well it fits each of the”+
“statistical models, and selecting the one that gives the best fit”
};

int[] ngramSizesToTest = {2, 4, 6, 10};

for (String stringToTest : stringsToTest) {
for (int ngramSize : ngramSizesToTest) {
NgramAnalyser analysis = new NgramAnalyser(ngramSize, stringToTest);

//Test toString method
String toString = analysis.toString();
//System.out.println(toString);

//Test that ngramCount = length of the string
assert(analysis.getNgramCount() == stringToTest.length());
//Test that the alphabet size doesn’t exceed the length of the string
assert(analysis.getAlphabetSize() <= stringToTest.length());
//

//Perform some basic tests done in getDistinctNgram tests.
assert(analysis.getDistinctNgramCount() <= analysis.getNgramCount());
assert(analysis.getDistinctNgramCount() <= stringToTest.length());
assert(analysis.getAlphabetSize() <= analysis.getDistinctNgramCount());

//Ensure each n-gram is of the correct length

for (String ngram : analysis.getDistinctNgrams()) {
assert(ngram.length() == ngramSize);
}
}
}

//Specific cases

//1-grams from a 1 length string
NgramAnalyser analysis = new NgramAnalyser(1, “1”);
assert(analysis.getNgramCount() == 1);
assert(analysis.getAlphabetSize() == 1);
assert(analysis.getDistinctNgrams().size() == 1);

//n-gram from an n-length string (15 in this case)
String s = “djaaaabaaaabcda”;
analysis = new NgramAnalyser(15, s);
assert(analysis.getDistinctNgrams().contains(s));

}