Purposive without Foresight

/**
 * Created on 5 Jun 2007, 22:51:02 Copyright Ning Zhao. All rights
 * reserved.
 */
package org.ningning.sandbox;
 
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Scanner;
 
/**
 * A very simple implementation of a shortest path based algorithm for
 * approximate string-to-string matching problem. The weight (in this
 * program I call it error score) of the difference between an input
 * string and a reference string is computed concerning the following
 * error cases: character absence (input: chery, reference cherry);
 * character redundance (input: cherrry, reference: cherry); character
 * mismatch (input: cherrz, reference: cherry); character position swap
 * (input: chrery, reference: cherry). More complex error cases can be
 * inserted.
 * <p />
 * The total error score between a reference string and input string is
 * the sum of minimal error scores of each pairs of correspoding
 * characters at the same positions in the strings. Reference strings
 * which have the lowest error scores are most likely to match the input
 * string, thus will be recommended by the program.
 * <p />
 * The attached food.txt has one food item per line. If you want to use
 * your own reference strings, you can either use the same format as
 * food.txt or modify the string scanning code in this program.
 *
 * @author Ellen Ning Zhao
 * @license <a href="http://www.gnu.org/copyleft/gpl.html">GPL V2</a>
 */
public class ApproximateStringMatchingDemo {
 
  private List<String> foods = new ArrayList<String>();
 
  private Map<String, Double> matchingScores = new HashMap<String, Double>();
 
  private Scanner scanner;
 
  /**
   * This table stores scores of combinations of any two ASCII symbols.
   * It is for the typo case errMatching to look up. For example, I
   * meant "cherry" but I typed "cherrz". In my typing there is a
   * matching error at the last position. More frequent typos are given
   * lower scores. For example, the character "v" and "b" are frequently
   * mistyped for each other, so if "v" and "b" appears at the same
   * positions of two words, the error score would be very low. This is
   * a symetric matrix, actually filling half matrix is already correct,
   * but inversing this matrix or write one more auxiliary method for
   * table looking up is slower than filling up the whole table. So I am
   * doing the simpler way.
   */
  private static double[][] mismatchScoreTable;
 
  private String in;
 
  private int inLength;
 
  public ApproximateStringMatchingDemo(String fileName) {
 
    // read the file, fill the food list
    try {
      scanner = new Scanner(new FileReader(fileName));
      while (scanner.hasNext()) {
        this.foods.add(scanner.nextLine());
      }
    } catch (FileNotFoundException e) {
      e.printStackTrace();
      System.exit(1);
    }
 
    if (mismatchScoreTable == null) initMismatchScoreTable();
  }
 
  public List<String> getFoods() {
    return this.foods;
  }
 
  /**
   * Initialize the score table. Finer scoring can be added later. Here
   * these cases are just for example. The many cases here can be
   * externalized into a rule file, and this rule file can be loaded
   * dynamically. We can add more rules like ignore cases, etc.
   */
  private static void initMismatchScoreTable() {
 
    mismatchScoreTable = new double[256][256];
 
    // Score any combination of two characters as 1 by default.
    for (int i = 0; i < 256; i++)
      for (int j = 0; j < 256; j++)
        mismatchScoreTable[i][j] = 1.0d;
 
    // If the input charater and reference character are the same,
    // there is no typo. So the error score is 0.
    for (int i = 0; i < 256; i++)
      mismatchScoreTable[i][i] = 0.0d;
 
    // For people who use both German keyboard and English keyboard,
    // this typo is highly frequent.
    mismatchScoreTable['y']['z'] = 0.1d;
    mismatchScoreTable['z']['y'] = 0.1d;
 
    mismatchScoreTable['v']['b'] = 0.15d;
    mismatchScoreTable['b']['v'] = 0.15d;
 
    mismatchScoreTable['n']['m'] = 0.11d;
    mismatchScoreTable['m']['n'] = 0.11d;
 
    mismatchScoreTable['t']['r'] = 0.15d;
    mismatchScoreTable['r']['t'] = 0.15d;
 
    mismatchScoreTable['g']['h'] = 0.15d;
    mismatchScoreTable['h']['g'] = 0.15d;
 
    mismatchScoreTable['y']['u'] = 0.15d;
    mismatchScoreTable['u']['y'] = 0.15d;
 
    // more typo possibilities can be inserted here....
  }
 
  /**
   * @param in
   *          the input string
   * @return the error score map.
   */
  public Map<String, Double> getScores(String in) {
    this.in = in;
    this.inLength = in.length();
 
    for (String food : this.foods) {
 
      int refLength = food.length();
 
      double[][] errScore = new double[inLength + 1][refLength + 1];
      errScore[0][0] = 0.0d;
 
      for (int inCharAt = 1; inCharAt <= this.inLength; inCharAt++)
        errScore[inCharAt][0] = inCharAt;
 
      for (int refCharAt = 1; refCharAt <= refLength; refCharAt++)
        errScore[0][refCharAt] = refCharAt;
 
      for (int inCharAt = 1; inCharAt <= inLength; inCharAt++)
        for (int refCharAt = 1; refCharAt <= refLength; refCharAt++) {
          // if a character is absent at the given position
          // in the input string, we add score 1.
          double charAbsence = errScore[inCharAt - 1][refCharAt] + 1;
 
          // if a character is redundant at the given position in the
          // input string, we add score 1.
          double charRedundance = errScore[inCharAt][refCharAt - 1] + 1;
 
          // if it is a matching error, we add the score specified in
          // the score table for matching errors.
          double mismatch = errScore[inCharAt - 1][refCharAt - 1]
                  + mismatchScoreTable[this.in.charAt(inCharAt - 1)][food
                          .charAt(refCharAt - 1)];
 
          // initialize the score for swap error to a very big value.
          double charPositionSwap = 999999d;
 
          // score for swap error
          if (inCharAt > 1
                  && refCharAt > 1
                  && this.in.charAt(inCharAt - 1) == food
                          .charAt(refCharAt - 2)
                  && this.in.charAt(inCharAt - 2) == food
                          .charAt(refCharAt - 1)) {
 
            // the score for typing "ie" as "ei" and vice versa
            // is even lower
            if (this.in.charAt(inCharAt - 2) == 'e'
                    && this.in.charAt(inCharAt - 1) == 'i') {
              charPositionSwap = errScore[inCharAt - 2][refCharAt - 2] + 0.25;
            }
 
            // more cases can be inserted here.
 
            else charPositionSwap = errScore[inCharAt - 2][refCharAt - 2] + 0.5;
          }
 
          // more error cases can be inserted here.
 
          double minScore = mismatch;
 
          if (charAbsence < minScore) {
            minScore = charAbsence;
          }
 
          if (charRedundance < minScore) {
            minScore = charRedundance;
          }
 
          if (charPositionSwap < minScore) {
            minScore = charPositionSwap;
          }
 
          errScore[inCharAt][refCharAt] = minScore;
        }
      this.matchingScores.put(food, errScore[this.inLength][refLength]);
    }
    return this.matchingScores;
  }
 
  /**
   * @param args
   */
  public static void main(String[] args) {
    System.out
            .println("Please type the file name. Be sure to check path: ");
    Scanner sc = new Scanner(System.in);
    String filename = sc.next();
    ApproximateStringMatchingDemo demo = new ApproximateStringMatchingDemo(
            filename);
 
    System.out.println("There are " + demo.getFoods().size()
            + " items in the file.");
 
 
    System.out.print("Please type a word. Type q for exit: ");
    sc.nextLine();
    while (sc.hasNext()) {
      String in  = sc.nextLine();
 
      if (in.equals("q")) {
        System.exit(0);
      }
 
      System.out.println("You typed " + in);
 
      System.out.println("--------------------------------------------");
      Map scoreMap = demo.getScores(in);
      for (String food : demo.getFoods()) {
        System.out.println(food + "\t error score: " + scoreMap.get(food));
      }
 
      System.out.println("--------------------------------------------");
 
      double minScore = (Double) Collections.min(scoreMap.values());
 
      if (minScore == 0.0d) {
        System.out.println(in + " is in the list.");
      } else {
        List<String> corrections = new ArrayList<String>();
        StringBuffer sb = new StringBuffer("Do you mean ");
        for (String food : demo.getFoods()) {
          if (scoreMap.get(food).equals(minScore)) {
            corrections.add(food);
            sb.append(food).append(" or ");
          }
        }
        sb.append("?");
        System.out.println(sb.toString());
      }
      System.out.println();
      System.out.println("Please type a word. Type q for exit: ");
    }
  }
}