!7

// https://towardsdatascience.com/symspell-vs-bk-tree-100x-faster-fuzzy-string-search-spell-checking-c4f10d80a078

// SymSpell: 1 million times faster through Symmetric Delete spelling correction algorithm

//

// The Symmetric Delete spelling correction algorithm reduces the complexity of edit candidate generation and dictionary lookup 

// for a given Damerau-Levenshtein distance. It is six orders of magnitude faster and language independent.

// Opposite to other algorithms only deletes are required, no transposes + replaces + inserts.

// Transposes + replaces + inserts of the input term are transformed into deletes of the dictionary term.

// Replaces and inserts are expensive and language dependent: e.g. Chinese has 70,000 Unicode Han characters!

//

// Copyright (C) 2015 Wolf Garbe

// Version: 3.0

// Author: Wolf Garbe <wolf.garbe@faroo.com>

// Maintainer: Wolf Garbe <wolf.garbe@faroo.com>

// URL: http://blog.faroo.com/2012/06/07/improved-edit-distance-based-spelling-correction/

// Description: http://blog.faroo.com/2012/06/07/improved-edit-distance-based-spelling-correction/

//

// License:

// This program is free software; you can redistribute it and/or modify

// it under the terms of the GNU Lesser General Public License, 

// version 3.0 (LGPL-3.0) as published by the Free Software Foundation.

// http://www.opensource.org/licenses/LGPL-3.0

//

// Usage: single word + Enter:  Display spelling suggestions

//        Enter without input:  Terminate the program

private static int editDistanceMax=2;

private static int verbose = 0;

//0: top suggestion

//1: all suggestions of smallest edit distance 

//2: all suggestions <= editDistanceMax (slower, no early termination)

private static class dictionaryItem

{

    public List<Integer> suggestions = new ArrayList<Integer>();

    public int count = 0;

}

private static class suggestItem

{

    public String term = "";

    public int distance = 0;

    public int count = 0;

    @Override

    public boolean equals(Object obj)

    {

        return term.equals(((suggestItem)obj).term);

    }

    @Override

    public int hashCode()

    {

        return term.hashCode();

    }       

}

p {

  //Create the dictionary from a sample corpus

  //e.g. http://norvig.com/big.txt , or any other large text corpus

  //The dictionary may contain vocabulary from different languages. 

  //If you use mixed vocabulary use the language parameter in Correct() and CreateDictionary() accordingly.

  //You may use CreateDictionaryEntry() to update a (self learning) dictionary incrementally

  //To extend spelling correction beyond single words to phrases (e.g. correcting "unitedkingom" to "united kingdom") simply add those phrases with CreateDictionaryEntry().

  File corpus = prepareProgramFile("big.txt");

  gunzipFile(loadLibrary(#1012160), corpus);

  CreateDictionary(f2s(corpus), "");

  ReadFromStdIn();

}

//Dictionary that contains both the original words and the deletes derived from them. A term might be both word and delete from another word at the same time.

//For space reduction a item might be either of type dictionaryItem or Int. 

//A dictionaryItem is used for word, word/delete, and delete with multiple suggestions. Int is used for deletes with a single suggestion (the majority of entries).

private static HashMap<String, Object> dictionary = new HashMap<String, Object>(); //initialisierung

//List of unique words. By using the suggestions (Int) as index for this list they are translated into the original String.

private static List<String> wordlist = new ArrayList<String>();

//create a non-unique wordlist from sample text

//language independent (e.g. works with Chinese characters)

private static Iterable<String> parseWords(String text)

{

    // \w Alphanumeric characters (including non-latin characters, umlaut characters and digits) plus "_" 

    // \d Digits

    // Provides identical results to Norvigs regex "[a-z]+" for latin characters, while additionally providing compatibility with non-latin characters

	List<String> allMatches = new ArrayList<String>();

	Matcher m = Pattern.compile("[\\w-[\\d_]]+").matcher(text.toLowerCase());

	while (m.find()) {

		allMatches.add(m.group());

	}

	return allMatches;

}

public static int maxlength = 0;//maximum dictionary term length

//for every word there all deletes with an edit distance of 1..editDistanceMax created and added to the dictionary

//every delete entry has a suggestions list, which points to the original term(s) it was created from

//The dictionary may be dynamically updated (word frequency and new words) at any time by calling createDictionaryEntry

private static boolean CreateDictionaryEntry(String key, String language)

{

	boolean result = false;

    dictionaryItem value=null;

    Object valueo;

    valueo = dictionary.get(language+key);

    if (valueo!=null)

    {

        //int or dictionaryItem? delete existed before word!

        if (valueo instanceof Integer) { 

        	int tmp = (int)valueo; 

        	value = new dictionaryItem(); 

        	value.suggestions.add(tmp); 

        	dictionary.put(language + key,value); 

    	}

        //already exists:

        //1. word appears several times

        //2. word1==deletes(word2) 

        else

        {

            value = (dictionaryItem)valueo;

        }

        //prevent overflow

        if (value.count < Integer.MAX_VALUE) value.count++;

    }

    else if (wordlist.size() < Integer.MAX_VALUE)

    {

        value = new dictionaryItem();

        value.count++;

        dictionary.put(language + key, value);

        if (key.length() > maxlength) maxlength = key.length();

    }

    //edits/suggestions are created only once, no matter how often word occurs

    //edits/suggestions are created only as soon as the word occurs in the corpus, 

    //even if the same term existed before in the dictionary as an edit from another word

    //a treshold might be specifid, when a term occurs so frequently in the corpus that it is considered a valid word for spelling correction

    if(value.count == 1)

    {

        //word2index

        wordlist.add(key);

        int keyint = (int)(wordlist.size() - 1);

        result = true;

        //create deletes

        for (String delete : Edits(key, 0, new HashSet<String>()))

        {

            Object value2;

            value2 = dictionary.get(language+delete);

            if (value2!=null)

            {

                //already exists:

                //1. word1==deletes(word2) 

                //2. deletes(word1)==deletes(word2) 

                //int or dictionaryItem? single delete existed before!

                if (value2 instanceof Integer) 

                {

                    //transformes int to dictionaryItem

                    int tmp = (int)value2; 

                    dictionaryItem di = new dictionaryItem(); 

                    di.suggestions.add(tmp); 

                    dictionary.put(language + delete,di);

                    if (!di.suggestions.contains(keyint)) AddLowestDistance(di, key, keyint, delete);

                }

                else if (!((dictionaryItem)value2).suggestions.contains(keyint)) AddLowestDistance((dictionaryItem) value2, key, keyint, delete);

            }

            else

            {

                dictionary.put(language + delete, keyint);         

            }

        }

    }

    return result;

}

//create a frequency dictionary from a corpus

private static void CreateDictionary(String corpus, String language)

{

	File f = new File(corpus);

    if(!(f.exists() && !f.isDirectory()))

    {

        System.out.println("File not found: " + corpus);

        return;

    }

    System.out.println("Creating dictionary ...");

    long startTime = System.currentTimeMillis();

    long wordCount = 0;

    BufferedReader br = null;

    try {

	br = new BufferedReader(new FileReader(corpus));

      String line;

      while ((line = br.readLine()) != null) 

      {

          for (String key : parseWords(line))

          {

             if (CreateDictionaryEntry(key, language)) wordCount++;

          }

      }

    }

    catch (Exception e) {

	// TODO Auto-generated catch block

	e.printStackTrace();

}

    //wordlist.TrimExcess();

    long endTime = System.currentTimeMillis();

    System.out.println("\rDictionary: " + wordCount + " words, " + dictionary.size() + " entries, edit distance=" + editDistanceMax + " in " + (endTime-startTime)+"ms ");

}

//save some time and space

private static void AddLowestDistance(dictionaryItem item, String suggestion, int suggestionint, String delete)

{

    //remove all existing suggestions of higher distance, if verbose<2

    //index2word

	//TODO check

    if ((verbose < 2) && (item.suggestions.size() > 0) && (wordlist.get(item.suggestions.get(0)).length()-delete.length() > suggestion.length() - delete.length())) item.suggestions.clear();

    //do not add suggestion of higher distance than existing, if verbose<2

    if ((verbose == 2) || (item.suggestions.size() == 0) || (wordlist.get(item.suggestions.get(0)).length()-delete.length() >= suggestion.length() - delete.length())) item.suggestions.add(suggestionint); 

}

//inexpensive and language independent: only deletes, no transposes + replaces + inserts

//replaces and inserts are expensive and language dependent (Chinese has 70,000 Unicode Han characters)

private static HashSet<String> Edits(String word, int editDistance, HashSet<String> deletes)

{

    editDistance++;

    if (word.length() > 1)

    {

        for (int i = 0; i < word.length(); i++)

        {

        	//delete ith character

            String delete =  word.substring(0,i)+word.substring(i+1);

            if (deletes.add(delete))

            {

                //recursion, if maximum edit distance not yet reached

                if (editDistance < editDistanceMax) Edits(delete, editDistance, deletes);

            }

        }

    }

    return deletes;

}

private static List<suggestItem> Lookup(String input, String language, int editDistanceMax)

{

    //save some time

    if (input.length() - editDistanceMax > maxlength) 

    	return new ArrayList<suggestItem>();

    List<String> candidates = new ArrayList<String>();

    HashSet<String> hashset1 = new HashSet<String>();

    List<suggestItem> suggestions = new ArrayList<suggestItem>();

    HashSet<String> hashset2 = new HashSet<String>();

    Object valueo;

    //add original term

    candidates.add(input);

    while (candidates.size()>0)

    {

        String candidate = candidates.get(0);

        candidates.remove(0);

        //save some time

        //early termination

        //suggestion distance=candidate.distance... candidate.distance+editDistanceMax                

        //if canddate distance is already higher than suggestion distance, than there are no better suggestions to be expected

        //label for c# goto replacement

        nosort:{

        	if ((verbose < 2) && (suggestions.size() > 0) && (input.length()-candidate.length() > suggestions.get(0).distance)) 

        		break nosort;

          //read candidate entry from dictionary

        	valueo = dictionary.get(language + candidate);

          if (valueo != null)

          {

              dictionaryItem value= new dictionaryItem();

              if (valueo instanceof Integer) 

              	value.suggestions.add((int)valueo);

              else value = (dictionaryItem)valueo;

              //if count>0 then candidate entry is correct dictionary term, not only delete item

              if ((value.count > 0) && hashset2.add(candidate))

              {

                  //add correct dictionary term term to suggestion list

                  suggestItem si = new suggestItem();

                  si.term = candidate;

                  si.count = value.count;

                  si.distance = input.length() - candidate.length();

                  suggestions.add(si);

                  //early termination

                  if ((verbose < 2) && (input.length() - candidate.length() == 0)) 

                  	break nosort;

              }

              //iterate through suggestions (to other correct dictionary items) of delete item and add them to suggestion list

              Object value2;

              for (int suggestionint : value.suggestions)

              {

                  //save some time 

                  //skipping double items early: different deletes of the input term can lead to the same suggestion

                  //index2word

              	//TODO

              	String suggestion = wordlist.get(suggestionint);

                  if (hashset2.add(suggestion))

                  {

                      //True Damerau-Levenshtein Edit Distance: adjust distance, if both distances>0

                      //We allow simultaneous edits (deletes) of editDistanceMax on on both the dictionary and the input term. 

                      //For replaces and adjacent transposes the resulting edit distance stays <= editDistanceMax.

                      //For inserts and deletes the resulting edit distance might exceed editDistanceMax.

                      //To prevent suggestions of a higher edit distance, we need to calculate the resulting edit distance, if there are simultaneous edits on both sides.

                      //Example: (bank==bnak and bank==bink, but bank!=kanb and bank!=xban and bank!=baxn for editDistanceMaxe=1)

                      //Two deletes on each side of a pair makes them all equal, but the first two pairs have edit distance=1, the others edit distance=2.

                      int distance = 0;

                      if (suggestion != input)

                      {

                          if (suggestion.length() == candidate.length()) distance = input.length() - candidate.length();

                          else if (input.length() == candidate.length()) distance = suggestion.length() - candidate.length();

                          else

                          {

                              //common prefixes and suffixes are ignored, because this speeds up the Damerau-levenshtein-Distance calculation without changing it.

                              int ii = 0;

                              int jj = 0;

                              while ((ii < suggestion.length()) && (ii < input.length()) && (suggestion.charAt(ii) == input.charAt(ii))) ii++;

                              while ((jj < suggestion.length() - ii) && (jj < input.length() - ii) && (suggestion.charAt(suggestion.length() - jj - 1) == input.charAt(input.length() - jj - 1))) jj++;

                              if ((ii > 0) || (jj > 0)) { 

                              	distance = DamerauLevenshteinDistance(suggestion.substring(ii, suggestion.length() - jj), input.substring(ii, input.length() - jj)); 

                              } 

                              else distance = DamerauLevenshteinDistance(suggestion, input);

                          }

                      }

                      //save some time.

                      //remove all existing suggestions of higher distance, if verbose<2

                      if ((verbose < 2) && (suggestions.size() > 0) && (suggestions.get(0).distance > distance)) suggestions.clear();

                      //do not process higher distances than those already found, if verbose<2

                      if ((verbose < 2) && (suggestions.size() > 0) && (distance > suggestions.get(0).distance)) continue;

                      if (distance <= editDistanceMax)

                      {

                      	value2 = dictionary.get(language + suggestion);

                      	if (value2!=null)

                          {

                              suggestItem si = new suggestItem();

                              si.term = suggestion;

                              si.count = ((dictionaryItem)value2).count;

                              si.distance = distance;

                              suggestions.add(si);

                          }

                      }

                  }

              }//end foreach

          }//end if         

          //add edits 

          //derive edits (deletes) from candidate (input) and add them to candidates list

          //this is a recursive process until the maximum edit distance has been reached

          if (input.length() - candidate.length() < editDistanceMax)

          {

              //save some time

              //do not create edits with edit distance smaller than suggestions already found

              if ((verbose < 2) && (suggestions.size() > 0) && (input.length() - candidate.length() >= suggestions.get(0).distance)) continue;

              for (int i = 0; i < candidate.length(); i++)

              {

                  String delete = candidate.substring(0, i)+candidate.substring(i+1);

                  if (hashset1.add(delete)) candidates.add(delete);

              }

          }

        } //end lable nosort

    } //end while

    //sort by ascending edit distance, then by descending word frequency

    if (verbose < 2) 

    	//suggestions.Sort((x, y) => -x.count.CompareTo(y.count));

    	Collections.sort(suggestions, new Comparator<suggestItem>()

                {

            public int compare(suggestItem f1, suggestItem f2)

            {

                return -(f1.count-f2.count);

            }        

        });

    else 

    	//suggestions.Sort((x, y) => 2*x.distance.CompareTo(y.distance) - x.count.CompareTo(y.count));

    	Collections.sort(suggestions, new Comparator<suggestItem>()

                {

            public int compare(suggestItem x, suggestItem y)

            {

                return ((2*x.distance-y.distance)>0?1:0) - ((x.count - y.count)>0?1:0);

            }        

        });

    if ((verbose == 0)&&(suggestions.size()>1)) 

    	return suggestions.subList(0, 1); 

    else return suggestions;

}

private static void Correct(String input, String language)

{

    List<suggestItem> suggestions = null;

    /*

    //Benchmark: 1000 x Lookup

    Stopwatch stopWatch = new Stopwatch();

    stopWatch.Start();

    for (int i = 0; i < 1000; i++)

    {

        suggestions = Lookup(input,language,editDistanceMax);

    }

    stopWatch.Stop();

    Console.WriteLine(stopWatch.ElapsedMilliseconds.ToString());

    */

    //check in dictionary for existence and frequency; sort by ascending edit distance, then by descending word frequency

    suggestions = Lookup(input, language, editDistanceMax);

    //display term and frequency

    for (suggestItem suggestion: suggestions)

    {

        System.out.println( suggestion.term + " " + suggestion.distance + " " + suggestion.count);

    }

    if (verbose !=0) System.out.println(suggestions.size() + " suggestions");

    System.out.println("done");

}

private static void ReadFromStdIn()

{

    String word;

    BufferedReader br =  new BufferedReader(new InputStreamReader(System.in));

    try {

	while ((word = br.readLine())!=null)

	{

	    Correct(word,"");

	}

} catch (IOException e) {

	// TODO Auto-generated catch block

	e.printStackTrace();

}

}

// Damerau–Levenshtein distance algorithm and code 

// from http://en.wikipedia.org/wiki/Damerau%E2%80%93Levenshtein_distance (as retrieved in June 2012)

public static int DamerauLevenshteinDistance(String a, String b) {

	  final int inf = a.length() + b.length() + 1;

  int[][] H = new int[a.length() + 2][b.length() + 2];

  for (int i = 0; i <= a.length(); i++) {

   H[i + 1][1] = i;

   H[i + 1][0] = inf;

  }

  for (int j = 0; j <= b.length(); j++) {

   H[1][j + 1] = j;

   H[0][j + 1] = inf;

  }

  HashMap<Character, Integer> DA = new HashMap<Character, Integer>();

  for (int d = 0; d < a.length(); d++) 

   if (!DA.containsKey(a.charAt(d)))

    DA.put(a.charAt(d), 0);

  for (int d = 0; d < b.length(); d++) 

   if (!DA.containsKey(b.charAt(d)))

    DA.put(b.charAt(d), 0);

  for (int i = 1; i <= a.length(); i++) {

   int DB = 0;

   for (int j = 1; j <= b.length(); j++) {

    final int i1 = DA.get(b.charAt(j - 1));

    final int j1 = DB;

    int d = 1;

    if (a.charAt(i - 1) == b.charAt(j - 1)) {

     d = 0;

     DB = j;

    }

    H[i + 1][j + 1] = min(

      H[i][j] + d, 

      H[i + 1][j] + 1,

      H[i][j + 1] + 1, 

      H[i1][j1] + ((i - i1 - 1)) 

      + 1 + ((j - j1 - 1)));

   }

   DA.put(a.charAt(i - 1), i);

  }

  return H[a.length() + 1][b.length() + 1];

 }

static int min(int a, int b, int c, int d) {

  return Math.min(a, Math.min(b, Math.min(c, d)));

}

static int min(int a, int b) { ret Math.min(a, b); }

static long min(long a, long b) { ret Math.min(a, b); }

static float min(float a, float b) { ret Math.min(a, b); }