From 1fda5521c53e7db8c5ef3111fca9b92c05e6ad4f Mon Sep 17 00:00:00 2001
From: Peter Wu <peter@lekensteyn.nl>
Date: Thu, 2 Apr 2015 11:57:49 +0200
Subject: quick nongreedy

---
 spellchecker/src/SpellCorrector.java | 69 ++++++++++++++++++++++++++++++++----
 1 file changed, 62 insertions(+), 7 deletions(-)

diff --git a/spellchecker/src/SpellCorrector.java b/spellchecker/src/SpellCorrector.java
index dd6e73a..8cbc8ca 100644
--- a/spellchecker/src/SpellCorrector.java
+++ b/spellchecker/src/SpellCorrector.java
@@ -26,13 +26,12 @@ public class SpellCorrector {
         this.cmr = cmr;
     }
 
-    public String correctPhrase(String phrase) {
-        if (phrase == null || phrase.length() == 0) {
-            throw new IllegalArgumentException("phrase must be non-empty.");
-        }
-
-        String[] words = phrase.split(" ");
-
+    /**
+     * Broken greedy approach, not used.
+     *
+     * @param words
+     */
+    private void greedyApproach(String[] words) {
         SentenceRater rater = new SentenceRater(words);
 
         // Try to change 1 word and see whether the suggestions are OK.
@@ -56,6 +55,62 @@ public class SpellCorrector {
                 break;
             }
         }
+    }
+
+    /**
+     *
+     * @param level The number of words that have been modified so far.
+     */
+    private SentenceRater nonGreedyApproach(String[] words, int level) {
+        SentenceRater rater = new SentenceRater(words);
+
+        // find best word
+        for (int i = 0; i < words.length; i++) {
+            final int word_index = i;
+            String old_word = words[word_index];
+            // try to find a better suggestion for this word.
+            Map<String, Double> candidates = getCandidateWords(old_word);
+            candidates.forEach((word, channel_probability) -> {
+                rater.tryWord(word_index, word, channel_probability);
+            });
+        };
+
+        // if a better word was found, use the change
+        if (rater.hasBetterSuggestion()) {
+            rater.saveSuggestion();
+            // if there are less than 3 typos, hunt for more typos
+            if (level < 3) {
+                SentenceRater subResult;
+                subResult = nonGreedyApproach(rater.words.clone(), level + 1);
+                // check if other typos found
+                if (subResult != null) {
+                    if (subResult.evaluateWord(-1) > rater.evaluateWord(-1)) {
+                        System.err.println("Subresult is better!");
+                        return subResult;
+                    }
+                    System.err.println("Subresult is not better!");
+                } else {
+                    System.err.println("no subresult found");
+                }
+            }
+            return rater;
+        } else {
+            System.err.println("No suggestion found.");
+            return null;
+        }
+    }
+
+    public String correctPhrase(String phrase) {
+        if (phrase == null || phrase.length() == 0) {
+            throw new IllegalArgumentException("phrase must be non-empty.");
+        }
+
+        String[] words = phrase.split(" ");
+
+        SentenceRater rater = nonGreedyApproach(words, 0);
+        if (rater != null) {
+            words = rater.getBestSentence();
+        }
 
         return String.join(" ", words);
     }
-- 
cgit v1.2.1