// copies of the Software, and to permit persons to whom the Software is
// furnished to do so, subject to the following conditions:
//
// The above copyright notice and this permission notice shall be included in all
// copies or substantial portions of the Software.
//
// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
// FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
// AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
// LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
// OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
// SOFTWARE.
importjava.io.BufferedReader;
importjava.io.File;
importjava.io.IOException;
importjava.io.InputStream;
importjava.io.InputStreamReader;
importjava.nio.charset.Charset;
importjava.nio.charset.StandardCharsets;
importjava.nio.file.Files;
importjava.nio.file.Paths;
importjava.util.*;
importjava.util.regex.Matcher;
importjava.util.regex.Pattern;
publicclassSymSpell {
publicenumVerbosity {
Top,
Closest,
All
}
privatestaticintdefaultMaxEditDistance = 2;
privatestaticintdefaultPrefixLength = 7;
privatestaticintdefaultCountThreshold = 1;
privatestaticintdefaultInitialCapacity = 16;
privatestaticintdefaultCompactLevel = 5;
privateintinitialCapacity;
privateintmaxDictionaryEditDistance;
privateintprefixLength; //prefix length 5..7
privatelongcountThreshold; //a treshold might be specifid, when a term occurs so frequently in the corpus that it is considered a valid word for spelling correction
//verbosity=Top: the suggestion with the highest term frequency of the suggestions of smallest edit distance found
//verbosity=Closest: all suggestions of smallest edit distance found, the suggestions are ordered by term frequency
//verbosity=All: all suggestions <= maxEditDistance, the suggestions are ordered by edit distance, then by term frequency (slower, no early termination)
// maxEditDistance used in lookup can't be bigger than the maxDictionaryEditDistance
// used to construct the underlying dictionary structure.
if (maxEditDistance > maxDictionaryEditDistance)
thrownewIllegalArgumentException("Dist to big: " + maxEditDistance);
List<SuggestItem> suggestions = newArrayList<>();
intinputLen = input.length();
// early exit - word is too big to possibly match any words
if (inputLen - maxEditDistance > maxLength) returnsuggestions;
//iterate through suggestions (to other correct dictionary items) of delete item and add them to suggestion list
for (Stringsuggestion : dictSuggestions) {
if (suggestion.equals(input)) continue;
intsuggestionLen = suggestion.length();
if ((Math.abs(suggestionLen - inputLen) > maxEditDistance2) // input/suggestion diff > allowed/current best distance
|| (suggestionLen < candidateLen) // sugg must be for a different delete String, in same bin only because of hash collision
|| (suggestionLen == candidateLen && !suggestion.equals(candidate))) // if sugg len = delete len, then it either equals delete or is in same bin only because of hash collision
//do not process higher distances than those already found, if verbosity<All (note: maxEditDistance2 will always equal maxEditDistance when Verbosity.All)
//outer loop (column): all possible part start positions
for (intj = 0; j < input.length(); j++) {
//inner loop (row): all possible part lengths (from start position): part can't be bigger than longest word in dictionary (other than long unknown word)
//we assume the word probabilities of two words to be independent
//therefore the resulting probability of the word combination is the product of the two word probabilities
//instead of computing the product of probabilities we are computing the sum of the logarithm of probabilities
//because the probabilities of words are about 10^-10, the product of many such small numbers could exceed (underflow) the floating number range and become zero