ViterbiAlgorithm { public List<SequenceState<S, O, D>> computeMostLikelySequence() { if (message == null) { return new ArrayList<>(); } else { return retrieveMostLikelySequence(); } } ViterbiAlgorithm();  ViterbiAlgorithm(boolean keepMessageHistory); void startWithInitialStateProbabilities(Collection<S> initialStates,
            Map<S, Double> initialLogProbabilities); void startWithInitialObservation(O observation, Collection<S> candidates,
            Map<S, Double> emissionLogProbabilities); void nextStep(O observation, Collection<S> candidates,
            Map<S, Double> emissionLogProbabilities,
            Map<Transition<S>, Double> transitionLogProbabilities,
            Map<Transition<S>, D> transitionDescriptors); void nextStep(O observation, Collection<S> candidates,
            Map<S, Double> emissionLogProbabilities,
            Map<Transition<S>, Double> transitionLogProbabilities); List<SequenceState<S, O, D>> computeMostLikelySequence(); boolean isBroken(); List<Map<S, Double>> messageHistory(); String messageHistoryString();  }
@Test public void testComputeMostLikelySequence() { final List<Rain> candidates = new ArrayList<>(); candidates.add(Rain.T); candidates.add(Rain.F); final Map<Rain, Double> emissionLogProbabilitiesForUmbrella = new LinkedHashMap<>(); emissionLogProbabilitiesForUmbrella.put(Rain.T, log(0.9)); emissionLogProbabilitiesForUmbrella.put(Rain.F, log(0.2)); final Map<Rain, Double> emissionLogProbabilitiesForNoUmbrella = new LinkedHashMap<>(); emissionLogProbabilitiesForNoUmbrella.put(Rain.T, log(0.1)); emissionLogProbabilitiesForNoUmbrella.put(Rain.F, log(0.8)); final Map<Transition<Rain>, Double> transitionLogProbabilities = new LinkedHashMap<>(); transitionLogProbabilities.put(new Transition<Rain>(Rain.T, Rain.T), log(0.7)); transitionLogProbabilities.put(new Transition<Rain>(Rain.T, Rain.F), log(0.3)); transitionLogProbabilities.put(new Transition<Rain>(Rain.F, Rain.T), log(0.3)); transitionLogProbabilities.put(new Transition<Rain>(Rain.F, Rain.F), log(0.7)); final Map<Transition<Rain>, Descriptor> transitionDescriptors = new LinkedHashMap<>(); transitionDescriptors.put(new Transition<Rain>(Rain.T, Rain.T), Descriptor.R2R); transitionDescriptors.put(new Transition<Rain>(Rain.T, Rain.F), Descriptor.R2S); transitionDescriptors.put(new Transition<Rain>(Rain.F, Rain.T), Descriptor.S2R); transitionDescriptors.put(new Transition<Rain>(Rain.F, Rain.F), Descriptor.S2S); final ViterbiAlgorithm<Rain, Umbrella, Descriptor> viterbi = new ViterbiAlgorithm<>(true); viterbi.startWithInitialObservation(Umbrella.T, candidates, emissionLogProbabilitiesForUmbrella); viterbi.nextStep(Umbrella.T, candidates, emissionLogProbabilitiesForUmbrella, transitionLogProbabilities, transitionDescriptors); viterbi.nextStep(Umbrella.F, candidates, emissionLogProbabilitiesForNoUmbrella, transitionLogProbabilities, transitionDescriptors); viterbi.nextStep(Umbrella.T, candidates, emissionLogProbabilitiesForUmbrella, transitionLogProbabilities, transitionDescriptors); final List<SequenceState<Rain, Umbrella, Descriptor>> result = viterbi.computeMostLikelySequence(); assertEquals(4, result.size()); assertEquals(Rain.T, result.get(0).state); assertEquals(Rain.T, result.get(1).state); assertEquals(Rain.F, result.get(2).state); assertEquals(Rain.T, result.get(3).state); assertEquals(Umbrella.T, result.get(0).observation); assertEquals(Umbrella.T, result.get(1).observation); assertEquals(Umbrella.F, result.get(2).observation); assertEquals(Umbrella.T, result.get(3).observation); assertEquals(null, result.get(0).transitionDescriptor); assertEquals(Descriptor.R2R, result.get(1).transitionDescriptor); assertEquals(Descriptor.R2S, result.get(2).transitionDescriptor); assertEquals(Descriptor.S2R, result.get(3).transitionDescriptor); assertFalse(viterbi.isBroken()); List<Map<Rain, Double>> expectedMessageHistory = new ArrayList<>(); Map<Rain, Double> message = new LinkedHashMap<>(); message.put(Rain.T, 0.9); message.put(Rain.F, 0.2); expectedMessageHistory.add(message); message = new LinkedHashMap<>(); message.put(Rain.T, 0.567); message.put(Rain.F, 0.054); expectedMessageHistory.add(message); message = new LinkedHashMap<>(); message.put(Rain.T, 0.03969); message.put(Rain.F, 0.13608); expectedMessageHistory.add(message); message = new LinkedHashMap<>(); message.put(Rain.T, 0.0367416); message.put(Rain.F, 0.0190512); expectedMessageHistory.add(message); List<Map<Rain, Double>> actualMessageHistory = viterbi.messageHistory(); checkMessageHistory(expectedMessageHistory, actualMessageHistory); }