kona/src/org/feistymeow/textual/WordBreakFinder.java

   1 package org.feistymeow.textual;
   2
   3 import java.util.HashSet;
   4 import java.util.Set;
   5
   6 public class WordBreakFinder
   7 {
   8   public WordBreakFinder(SimpleDictionary lookups) {
   9     _lookups = lookups;
  10   }
  11
  12   public Set<String> findStringsWithGoodSpacing(String orig) {
  13     HashSet<String> toReturn = new HashSet<String>();
  14     int startingChunk = Math.min(orig.length(), _lookups.longestWord());
  15     for (int i = startingChunk; i >= 1; i--) {
  16       String first = orig.substring(0, i);
  17       if (!_lookups.lookup(first)) {
  18         // fail fast.  this length chunk of the word doesn't match.
  19         continue;
  20       }
  21       String second = orig.substring(i, orig.length());
  22       // first part of string is listed in dictionary.  we can trivially add it if the other part is empty.
  23       if (second.length() == 0) {
  24           toReturn.add(first);
  25           continue;
  26       }
  27       Set<String> matches = findStringsWithGoodSpacing(second);
  28       if (matches != null) {
  29         for (String matched : matches) {
  30            toReturn.add(first + " " + matched);
  31         }
  32       }
  33     }
  34     if (toReturn.isEmpty()) return null;
  35     return toReturn;
  36   }
  37
  38   SimpleDictionary _lookups;
  39
  40   public static void main(String argv[]) {
  41     String smallWordList[] = {
  42        "hops", "barley", "malt", "beer", "turnip"
  43     };
  44     SimpleDictionary lookups = new SimpleDictionary(smallWordList);
  45     WordBreakFinder finder = new WordBreakFinder(lookups);
  46
  47     String toBreak = "maltbeerbeerturniphops";
  48     Set<String> matches =  finder.findStringsWithGoodSpacing(toBreak);
  49     if (matches != null) {
  50       System.out.println("matches found:");
  51       for (String match : matches) {
  52          System.out.println(match);
  53       }
  54     } else {
  55       System.out.println("ERROR: failed to find matches!");
  56     }
  57
  58     toBreak = "maltbeerbeturniphops";
  59     matches =  finder.findStringsWithGoodSpacing(toBreak);
  60     if (matches != null) {
  61       System.out.println("ERROR: matches found:");
  62       for (String match : matches) {
  63          System.out.println(match);
  64       }
  65     } else {
  66       System.out.println("found no matches, which is correct.");
  67     }
  68   }
  69
  70 }
  71
  72
  73