Code/Projects/PacketLevelSignatureExtractor/src/test/java/edu/uci/iotproject/test/SequenceAlignmentTest.java

   1 package edu.uci.iotproject.test;
   2
   3 import edu.uci.iotproject.comparison.seqalignment.AlignmentPricer;
   4 import edu.uci.iotproject.comparison.seqalignment.SequenceAlignment;
   5 import org.junit.Before;
   6 import org.junit.Test;
   7
   8 import java.util.function.ToIntBiFunction;
   9 import java.util.function.ToIntFunction;
  10
  11 import static org.junit.Assert.assertTrue;
  12 import static org.junit.Assert.fail;
  13
  14 /**
  15  * Tests the implementation of {@link SequenceAlignment}.
  16  *
  17  * @author Janus Varmarken {@literal <jvarmark@uci.edu>}
  18  * @author Rahmadi Trimananda {@literal <rtrimana@uci.edu>}
  19  */
  20 public class SequenceAlignmentTest {
  21
  22     private char[] lowercaseVowels;
  23     private char[] lowercaseConsonants;
  24
  25     private Character[] meanChars;
  26     private Character[] nameChars;
  27
  28     /**
  29      * Cost function for the alignment of letters in the example execution of the sequence alignment algorithm in
  30      * Kleinberg's and Tardos' "Algorithm Design", where 'mean' and 'name' are aligned.
  31      */
  32     private ToIntBiFunction<Character, Character> kleinbergExampleAlignmentCostFunc;
  33
  34     /**
  35      * Cost function for the alignment of letters with gaps in the example execution of the sequence alignment algorithm
  36      * in Kleinberg's and Tardos' "Algorithm Design", where 'mean' and 'name' are aligned. Gap cost is set to 2,
  37      * regardless of input character.
  38      */
  39     private ToIntFunction<Character> kleinbergExampleGapCostFunc;
  40
  41     /**
  42      * Calculates the cost of aligning a letter with another letter or a letter with a gap according to the cost recipe
  43      * used in the example in Kleinberg & Tardos.
  44      */
  45     private AlignmentPricer<Character> kleinbergAlignmentPricer;
  46
  47     /**
  48      * Executes the sequence alignment algorithm using the cost function defined in the example in Kleinberg & Tardos,
  49      * i.e., {@link #kleinbergAlignmentPricer}.
  50      */
  51     private SequenceAlignment<Character> kleinbergSequenceAligner;
  52
  53     @Before
  54     public void initialize() {
  55         // We consider 'y' a vowel for the sake of simplicity.
  56         // Note: we assume an all lowercase string!
  57         lowercaseVowels = new char[] { 'a', 'e', 'i',  'o', 'u', 'y' };
  58         lowercaseConsonants = new char[] { 'b', 'c', 'd', 'f', 'g', 'h', 'j', 'k', 'l', 'm', 'n', 'p', 'q', 'r', 's',
  59                 't', 'v', 'w', 'x', 'z' };
  60         kleinbergExampleAlignmentCostFunc = (c1, c2) -> {
  61             // Unbox to primitive type for the sake of brevity in the statements to follow.
  62             final char char1 = c1.charValue();
  63             final char char2 = c2.charValue();
  64
  65             // If char1 and char2 are the same characters, the cost of aligning them is 0.
  66             if (char1 == char2) return 0;
  67
  68             final boolean char1IsVowel = isVowel(char1);
  69             final boolean char1IsConsonant = isConsonant(char1);
  70             final boolean char2IsVowel = isVowel(char2);
  71             final boolean char2IsConsonant = isConsonant(char2);
  72
  73             // Alignment cost is undefined for non alphabet characters.
  74             if (!char1IsVowel && !char1IsConsonant) fail("not an alphabet letter: " + char1);
  75             if (!char2IsVowel && !char2IsConsonant) fail("not an alphabet letter: " + char2);
  76
  77             // If char1 and char2 are both vowels or both consonants, the cost is 1.
  78             if (char1IsVowel && char2IsVowel || char1IsConsonant && char2IsConsonant) return 1;
  79
  80             // If one of char1 and char2 is a consonant, while the other is a vowel, the cost is 3.
  81             return 3;
  82         };
  83         // The cost of a gap is 2, regardless of what letter is aligned with the gap.
  84         kleinbergExampleGapCostFunc = c -> 2;
  85
  86         // char[] -> Character[] conversion courtesy of https://stackoverflow.com/a/27690990/1214974
  87         meanChars = "mean".chars().mapToObj(c -> (char)c).toArray(Character[]::new);
  88         nameChars = "name".chars().mapToObj(c -> (char)c).toArray(Character[]::new);
  89
  90         kleinbergAlignmentPricer = new AlignmentPricer<>(kleinbergExampleAlignmentCostFunc,
  91                 kleinbergExampleGapCostFunc);
  92
  93         kleinbergSequenceAligner = new SequenceAlignment<>(kleinbergAlignmentPricer);
  94     }
  95
  96     @Test
  97     public void kleinbergExampleOptAlignmentCostShouldBe6() {
  98         // Cost of the optimal alignment of the two words
  99         final int optAlignmentCost = kleinbergSequenceAligner.calculateAlignment(meanChars, nameChars);
 100         final int expectedAlignmentCost = 6;
 101         String msg = String.format("Kleinberg example: computed opt != expected opt (computed=%d expected=%d)",
 102                 optAlignmentCost, expectedAlignmentCost);
 103         assertTrue(msg, optAlignmentCost == expectedAlignmentCost);
 104     }
 105
 106
 107     @Test
 108     public void meanAlignedWithEmptyStringShouldBe8() {
 109         final int optAlignmentCost = kleinbergSequenceAligner.calculateAlignment(meanChars, new Character[0]);
 110         // 'mean' aligned with the empty string equals paying four gap costs, so total cost is: 4 * 2 = 8.
 111         final int expectedAlignmentCost = 8;
 112         String msg = String.format("'mean' aligned with empty string: computed opt != expected opt (computed=%d expected=%d)",
 113                 optAlignmentCost, expectedAlignmentCost);
 114         assertTrue(msg, optAlignmentCost == expectedAlignmentCost);
 115     }
 116
 117     @Test
 118     public void mAlignedWithNameShouldBe6() {
 119         /*
 120          * Note: this also uses the cost function specified in Kleinberg & Tardos.
 121          * Best alignment should be:
 122          * n a m e
 123          * _ _ m _
 124          * This should have a cost of 3 * gapCost = 6
 125          */
 126         final int optAlignmentCost = kleinbergSequenceAligner.calculateAlignment(new Character[] { 'm' }, nameChars);
 127         final int expectedAlignmentCost = 6;
 128         String msg = String.format("'m' aligned with 'name': computed opt != expected opt (computed=%d expected=%d)",
 129                 optAlignmentCost, expectedAlignmentCost);
 130         assertTrue(msg, optAlignmentCost == expectedAlignmentCost);
 131     }
 132
 133     @Test
 134     public void meAlignedWithNameShouldBe4() {
 135         /*
 136          * Note: this also uses the cost function specified in Kleinberg & Tardos.
 137          * Best alignment should be:
 138          * n a m e
 139          * _ _ m e
 140          * This should have a cost of 2 * gapCost = 4
 141          */
 142         final int optAlignmentCost = kleinbergSequenceAligner.calculateAlignment(new Character[] { 'm', 'e' }, nameChars);
 143         final int expectedAlignmentCost = 4;
 144         String msg = String.format("'me' aligned with 'name': computed opt != expected opt (computed=%d expected=%d)",
 145                 optAlignmentCost, expectedAlignmentCost);
 146         assertTrue(msg, optAlignmentCost == expectedAlignmentCost);
 147         // Check that order of arguments doesn't matter
 148         final int optAlignmentCostReversed = kleinbergSequenceAligner.calculateAlignment(nameChars, new Character[] { 'm', 'e' });
 149         msg = "'me' aligned with 'name': different order of arguments unexpectedly produced different result";
 150         assertTrue(msg, optAlignmentCostReversed == optAlignmentCost && optAlignmentCostReversed == expectedAlignmentCost);
 151     }
 152
 153     @Test
 154     public void ameAlignedWithNameShouldBe2() {
 155         /*
 156          * Note: this also uses the cost function specified in Kleinberg & Tardos.
 157          * Best alignment should be:
 158          * n a m e
 159          * _ a m e
 160          * This should have a cost of 1 * gapCost = 2
 161          */
 162         final int optAlignmentCost = kleinbergSequenceAligner.calculateAlignment(new Character[] { 'a', 'm', 'e' }, nameChars);
 163         final int expectedAlignmentCost = 2;
 164         String msg = String.format("'ame' aligned with 'name': computed opt != expected opt (computed=%d expected=%d)",
 165                 optAlignmentCost, expectedAlignmentCost);
 166         assertTrue(msg, optAlignmentCost == expectedAlignmentCost);
 167     }
 168
 169     @Test
 170     public void fameAlignedWithNameShouldBe1() {
 171         /*
 172          * Note: this also uses the cost function specified in Kleinberg & Tardos.
 173          * Best alignment should be:
 174          * n a m e
 175          * f a m e
 176          * This should have a cost of 1 * consonantMatchedWithConsonantCost = 1
 177          */
 178         final int optAlignmentCost = kleinbergSequenceAligner.calculateAlignment(new Character[] { 'f', 'a', 'm', 'e' },
 179                 nameChars);
 180         final int expectedAlignmentCost = 1;
 181         String msg = String.format("'fame' aligned with 'name': computed opt != expected opt (computed=%d expected=%d)",
 182                 optAlignmentCost, expectedAlignmentCost);
 183         assertTrue(msg, optAlignmentCost == expectedAlignmentCost);
 184     }
 185
 186     @Test
 187     public void nameAlignedWithNameShouldBe0() {
 188         /*
 189          * Note: this also uses the cost function specified in Kleinberg & Tardos.
 190          * Best alignment should be:
 191          * n a m e
 192          * n a m e
 193          * This should have a cost of 0.
 194          */
 195         final int optAlignmentCost = kleinbergSequenceAligner.calculateAlignment(new Character[] { 'n', 'a', 'm', 'e' },
 196                 nameChars);
 197         final int expectedAlignmentCost = 0;
 198         String msg = String.format("'name' aligned with 'name': computed opt != expected opt (computed=%d expected=%d)",
 199                 optAlignmentCost, expectedAlignmentCost);
 200         assertTrue(msg, optAlignmentCost == expectedAlignmentCost);
 201     }
 202
 203     @Test
 204     public void emanAlignedWithNameShouldBe6() {
 205         /*
 206          * Note: this also uses the cost function specified in Kleinberg & Tardos.
 207          * Best alignment should be:
 208          *
 209          * _ n a m e
 210          * e m a n _
 211          *
 212          *    or
 213          *
 214          * n a m e _
 215          * _ e m a n
 216          *
 217          * This should have a cost of 2 * gapCost + 2 * consonantMatchedWithConsonantCost = 2 * 2 + 2 * 1 = 6.
 218          */
 219         final int optAlignmentCost = kleinbergSequenceAligner.calculateAlignment(new Character[] { 'e', 'm', 'a', 'n' },
 220                 nameChars);
 221         final int expectedAlignmentCost = 6;
 222         String msg = String.format("'eman' aligned with 'name': computed opt != expected opt (computed=%d expected=%d)",
 223                 optAlignmentCost, expectedAlignmentCost);
 224         assertTrue(msg, optAlignmentCost == expectedAlignmentCost);
 225     }
 226
 227     @Test
 228     public void naemAlignedWithNameShouldBe4() {
 229         /*
 230          * Note: this also uses the cost function specified in Kleinberg & Tardos.
 231          * Best alignment should be:
 232          *
 233          * n a _ m e
 234          * n a e m _
 235          *
 236          *    or
 237          *
 238          * n a m e _
 239          * n a _ e m
 240          *
 241          * This should have a cost of 2 * gapCost = 4.
 242          */
 243         final int optAlignmentCost = kleinbergSequenceAligner.calculateAlignment(new Character[] { 'n', 'a', 'e', 'm' },
 244                 nameChars);
 245         final int expectedAlignmentCost = 4;
 246         String msg = String.format("'naem' aligned with 'name': computed opt != expected opt (computed=%d expected=%d)",
 247                 optAlignmentCost, expectedAlignmentCost);
 248         assertTrue(msg, optAlignmentCost == expectedAlignmentCost);
 249     }
 250
 251
 252     /**
 253      * Checks if {@code letter} is a lowercase vowel. Note: for simplicity, 'y' is considered a <em>vowel</em>.
 254      * @param letter A {@code char} expected to be a vowel.
 255      * @return {@code true} if {@code letter} is a vowel, {@code false} otherwise.
 256      */
 257     private boolean isVowel(char letter) {
 258         for (char vowel : lowercaseVowels) {
 259             if (letter == vowel) {
 260                 return true;
 261             }
 262         }
 263         return false;
 264     }
 265
 266     /**
 267      * Checks if {@code letter} is a lowercase consonant. Note: for simplicity, 'y' is considered a <em>vowel</em>.
 268      * @param letter A {@code char} expected to be a consonant.
 269      * @return {@code true} if {@code letter} is a consonant, {@code false} otherwise.
 270      */
 271     private boolean isConsonant(char letter) {
 272         for (char consonant : lowercaseConsonants) {
 273             if (letter == consonant) {
 274                 return true;
 275             }
 276         }
 277         return false;
 278     }
 279 }