Πρόσφατα διάβασα ένα πολύ ενδιαφέρον άρθρο από τον Peter Norvig για το πως μπορούμε να γράψουμε έναν Spelling Corrector!!!

(Ο Peter Norvig είναι Director of Research στην Google και γνωστός LISP hacker, έχοντας γράψει εκπληκτικά βιβλία για AI με την LISP).

Ο Norvig παρουσιάζει τον αλγόριθμο με ένα πολύ μικρό προγραμματάκι (21 lines) σε python. Εντυπωσιασμένος από την ιδέα και τον πολύ όμορφο python κώδικα, αποφάσισα να δοκιμάσω μια υλοποίηση σε C# 3.0... Ο τελικός κώδικας είναι αρκετά μεγαλύτερος από τον αντίστοιχο python... αλλα anyway ... C# είναι ... και πάλι καλά να λέμε...

Happy code hacking

public class ToySpellingCorrector
{

   private readonly Dictionary<string, int> dictionaryOfWords;

   public ToySpellingCorrector(string filename)
   {
      dictionaryOfWords = Train(Words(File.ReadAllText(filename)));
   }

   private Dictionary<string, int> Train(IEnumerable<string> words)
   {
      var query = from word in words
                  group word by word into g
                  select new { Key = g.Key, Value = g.Count() };

      return query.ToDictionary(item => item.Key, item => item.Value);
   }

   private IEnumerable<string> Words(string text)
   {
      return text.ToLower().FindAll("[a-z]+");
   }


   public string Correct(string word)
   {

      var candidateStrings = SelectTheFirstNonEmptyCandidateSet( Known(word.Enumerate()), 
                                                                  Known(EditsDistanceOne(word)),
                                                                  Known(EditsDistanceTwo(word)),
                                                                  word.Enumerate());

      return candidateStrings.Max((first, second) => dictionaryOfWords[first].CompareTo(dictionaryOfWords[second]));

   }

   private IEnumerable<string> Known(IEnumerable<string> words)
   {
      var query = from word in words
                  where dictionaryOfWords.ContainsKey(word)
                  select word;
      return query.Distinct();
   }

   private IEnumerable<string> SelectTheFirstNonEmptyCandidateSet(params IEnumerable<string>[] candidates)
   {
      return ( from candidate in candidates
               where candidate.Any()
               select candidate ).First();
   }

   private IEnumerable<string> EditsRawDistanseOne(string word)
   {
      return word.Deletion()
                  .Concat(word.Transposition())
                  .Concat(word.Alternation())
                  .Concat(word.Insertion());
   }

   private IEnumerable<string> EditsRawDistanceTwo(string word)
   {
      foreach (string edit in EditsRawDistanseOne(word))
         foreach (string innerEdit in EditsRawDistanseOne(edit))
            yield return innerEdit;
   }

   private IEnumerable<string> EditsDistanceOne(string word)
   {
      return EditsRawDistanseOne(word).Distinct();
   }

   private IEnumerable<string> EditsDistanceTwo(string word)
   {
      return EditsRawDistanceTwo(word).Distinct();
   }
}

public static class MyExtensions
{

   public static IEnumerable<string> Deletion(this string word)
   {
      for (int i = 0; i < word.Length; i++)
         yield return word.Substring(0, i) + word.Substring(i + 1);
   }

   public static IEnumerable<string> Transposition(this string word)
   {
      for (int i = 0; i < word.Length - 1; i++)
         yield return word.Substring(0, i) + word.Substring(i + 1, 1) + word.Substring(i, 1) + word.Substring(i + 2);
   }

   public static IEnumerable<string> Alternation(this string word)
   {
      for (int i = 0; i < word.Length; i++)
         for (char c = 'a'; c <= 'z'; c++)
            yield return word.Substring(0, i) + c.ToString() + word.Substring(i + 1);
   }

   public static IEnumerable<string> Insertion(this string word)
   {
      for (int i = 0; i <= word.Length; i++)
         for (char c = 'a'; c <= 'z'; c++)
            yield return word.Substring(0, i) + c.ToString() + word.Substring(i);
   }

   public static IEnumerable<string> FindAll(this string text, string pattern)
   {
      MatchCollection matchCollection = Regex.Matches(text, pattern);
      foreach (Match match in matchCollection)
      {
         yield return match.Value;
      }
   }

   public static IEnumerable<T> Enumerate<T>(this T source)
   {
      yield return source;
   }

   public static T Max<T>(this IEnumerable<T> source, Comparison<T> comparison)
   {
      if (source == null) throw new ArgumentNullException("source");
      T value = default(T);
      bool hasValue = false;
      foreach (T x in source)
      {
         if (hasValue) 
         {
            if (comparison(x, value) > 0) 
               value = x;
         }
         else 
         {
            value = x;
            hasValue = true;
         }
      }
      if (hasValue) return value;
      throw new InvalidOperationException("Sequence contains no elements");
   }

}


class Program
{
   static void Main(string[] args)
   {
      ToySpellingCorrector toySpellingCorrector = new ToySpellingCorrector("big.txt");

      while(true)
      {
         Console.Write(">>>");
         string word = Console.ReadLine();
         if(word == string.Empty) break;
         Console.WriteLine("Correct: {0}", toySpellingCorrector.Correct(word));
      }
   }
}