diff options
Diffstat (limited to 'extensions/spellcheck/hunspell/src/suggestmgr.cxx')
| -rw-r--r-- | extensions/spellcheck/hunspell/src/suggestmgr.cxx | 2263 |
1 files changed, 2263 insertions, 0 deletions
diff --git a/extensions/spellcheck/hunspell/src/suggestmgr.cxx b/extensions/spellcheck/hunspell/src/suggestmgr.cxx new file mode 100644 index 0000000000..6b363debd5 --- /dev/null +++ b/extensions/spellcheck/hunspell/src/suggestmgr.cxx @@ -0,0 +1,2263 @@ +/* ***** BEGIN LICENSE BLOCK ***** + * Version: MPL 1.1/GPL 2.0/LGPL 2.1 + * + * Copyright (C) 2002-2022 Németh László + * + * The contents of this file are subject to the Mozilla Public License Version + * 1.1 (the "License"); you may not use this file except in compliance with + * the License. You may obtain a copy of the License at + * http://www.mozilla.org/MPL/ + * + * Software distributed under the License is distributed on an "AS IS" basis, + * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License + * for the specific language governing rights and limitations under the + * License. + * + * Hunspell is based on MySpell which is Copyright (C) 2002 Kevin Hendricks. + * + * Contributor(s): David Einstein, Davide Prina, Giuseppe Modugno, + * Gianluca Turconi, Simon Brouwer, Noll János, Bíró Árpád, + * Goldman Eleonóra, Sarlós Tamás, Bencsáth Boldizsár, Halácsy Péter, + * Dvornik László, Gefferth András, Nagy Viktor, Varga Dániel, Chris Halls, + * Rene Engelhard, Bram Moolenaar, Dafydd Jones, Harri Pitkänen + * + * Alternatively, the contents of this file may be used under the terms of + * either the GNU General Public License Version 2 or later (the "GPL"), or + * the GNU Lesser General Public License Version 2.1 or later (the "LGPL"), + * in which case the provisions of the GPL or the LGPL are applicable instead + * of those above. If you wish to allow use of your version of this file only + * under the terms of either the GPL or the LGPL, and not to allow others to + * use your version of this file under the terms of the MPL, indicate your + * decision by deleting the provisions above and replace them with the notice + * and other provisions required by the GPL or the LGPL. If you do not delete + * the provisions above, a recipient may use your version of this file under + * the terms of any one of the MPL, the GPL or the LGPL. + * + * ***** END LICENSE BLOCK ***** */ +/* + * Copyright 2002 Kevin B. Hendricks, Stratford, Ontario, Canada + * And Contributors. All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * + * 1. Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * + * 2. Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * + * 3. All modifications to the source code must be clearly marked as + * such. Binary redistributions based on modified source code + * must be clearly marked as modified versions in the documentation + * and/or other materials provided with the distribution. + * + * THIS SOFTWARE IS PROVIDED BY KEVIN B. HENDRICKS AND CONTRIBUTORS + * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT + * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS + * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL + * KEVIN B. HENDRICKS OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, + * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, + * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; + * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) + * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT + * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY + * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF + * SUCH DAMAGE. + */ + +#include <stdlib.h> +#include <string.h> +#include <stdio.h> +#include <ctype.h> +#include <time.h> + +#include "suggestmgr.hxx" +#include "htypes.hxx" +#include "csutil.hxx" + +const w_char W_VLINE = {'\0', '|'}; + +#define MAX_CHAR_DISTANCE 4 + +SuggestMgr::SuggestMgr(const char* tryme, unsigned int maxn, AffixMgr* aptr) { + // register affix manager and check in string of chars to + // try when building candidate suggestions + pAMgr = aptr; + + csconv = NULL; + + ckeyl = 0; + ckey = NULL; + + ctryl = 0; + ctry = NULL; + + utf8 = 0; + langnum = 0; + complexprefixes = 0; + + maxSug = maxn; + nosplitsugs = 0; + maxngramsugs = MAXNGRAMSUGS; + maxcpdsugs = MAXCOMPOUNDSUGS; + + if (pAMgr) { + langnum = pAMgr->get_langnum(); + ckey = pAMgr->get_key_string(); + nosplitsugs = pAMgr->get_nosplitsugs(); + if (pAMgr->get_maxngramsugs() >= 0) + maxngramsugs = pAMgr->get_maxngramsugs(); + utf8 = pAMgr->get_utf8(); + if (pAMgr->get_maxcpdsugs() >= 0) + maxcpdsugs = pAMgr->get_maxcpdsugs(); + if (!utf8) { + csconv = get_current_cs(pAMgr->get_encoding()); + } + complexprefixes = pAMgr->get_complexprefixes(); + } + + if (ckey) { + if (utf8) { + ckeyl = u8_u16(ckey_utf, ckey); + } else { + ckeyl = strlen(ckey); + } + } + + if (tryme) { + ctry = mystrdup(tryme); + if (ctry) + ctryl = strlen(ctry); + if (ctry && utf8) { + ctryl = u8_u16(ctry_utf, tryme); + } + } + + // language with possible dash usage + // (latin letters or dash in TRY characters) + lang_with_dash_usage = (ctry && + ((strchr(ctry, '-') != NULL) || (strchr(ctry, 'a') != NULL))); +} + +SuggestMgr::~SuggestMgr() { + pAMgr = NULL; + if (ckey) + free(ckey); + ckey = NULL; + ckeyl = 0; + if (ctry) + free(ctry); + ctry = NULL; + ctryl = 0; + maxSug = 0; +#ifdef MOZILLA_CLIENT + delete[] csconv; +#endif +} + +void SuggestMgr::testsug(std::vector<std::string>& wlst, + const std::string& candidate, + int cpdsuggest, + int* timer, + clock_t* timelimit) { + int cwrd = 1; + if (wlst.size() == maxSug) + return; + for (size_t k = 0; k < wlst.size(); ++k) { + if (wlst[k] == candidate) { + cwrd = 0; + break; + } + } + if ((cwrd) && checkword(candidate, cpdsuggest, timer, timelimit)) { + wlst.push_back(candidate); + } +} + +/* generate suggestions for a misspelled word + * pass in address of array of char * pointers + * onlycompoundsug: probably bad suggestions (need for ngram sugs, too) + * return value: true, if there is a good suggestion + * (REP, ph: or a dictionary word pair) + */ +bool SuggestMgr::suggest(std::vector<std::string>& slst, + const char* w, + int* onlycompoundsug) { + int nocompoundtwowords = 0; + std::vector<w_char> word_utf; + int wl = 0; + size_t nsugorig = slst.size(); + std::string w2; + const char* word = w; + size_t oldSug = 0; + bool good_suggestion = false; + + // word reversing wrapper for complex prefixes + if (complexprefixes) { + w2.assign(w); + if (utf8) + reverseword_utf(w2); + else + reverseword(w2); + word = w2.c_str(); + } + + if (utf8) { + wl = u8_u16(word_utf, word); + if (wl == -1) { + return false; + } + } + + for (int cpdsuggest = 0; (cpdsuggest < 2) && (nocompoundtwowords == 0) && !good_suggestion; + cpdsuggest++) { + + clock_t timelimit; + // initialize both in non-compound and compound cycles + timelimit = clock(); + + // limit compound suggestion + if (cpdsuggest > 0) + oldSug = slst.size(); + + // suggestions for an uppercase word (html -> HTML) + if (slst.size() < maxSug) { + size_t i = slst.size(); + if (utf8) + capchars_utf(slst, word_utf.data(), wl, cpdsuggest); + else + capchars(slst, word, cpdsuggest); + if (slst.size() > i) + good_suggestion = true; + } + + // perhaps we made a typical fault of spelling + if ((slst.size() < maxSug) && (!cpdsuggest || (slst.size() < oldSug + maxcpdsugs))) { + size_t i = slst.size(); + replchars(slst, word, cpdsuggest); + if (slst.size() > i) + good_suggestion = true; + } + if (clock() > timelimit + TIMELIMIT_SUGGESTION) + return good_suggestion; + + // perhaps we made chose the wrong char from a related set + if ((slst.size() < maxSug) && + (!cpdsuggest || (slst.size() < oldSug + maxcpdsugs))) { + mapchars(slst, word, cpdsuggest); + } + if (clock() > timelimit + TIMELIMIT_SUGGESTION) + return good_suggestion; + + // only suggest compound words when no other suggestion + if ((cpdsuggest == 0) && (slst.size() > nsugorig)) + nocompoundtwowords = 1; + + // did we swap the order of chars by mistake + if ((slst.size() < maxSug) && (!cpdsuggest || (slst.size() < oldSug + maxcpdsugs))) { + if (utf8) + swapchar_utf(slst, word_utf.data(), wl, cpdsuggest); + else + swapchar(slst, word, cpdsuggest); + } + if (clock() > timelimit + TIMELIMIT_SUGGESTION) + return good_suggestion; + + // did we swap the order of non adjacent chars by mistake + if ((slst.size() < maxSug) && (!cpdsuggest || (slst.size() < oldSug + maxcpdsugs))) { + if (utf8) + longswapchar_utf(slst, word_utf.data(), wl, cpdsuggest); + else + longswapchar(slst, word, cpdsuggest); + } + if (clock() > timelimit + TIMELIMIT_SUGGESTION) + return good_suggestion; + + // did we just hit the wrong key in place of a good char (case and keyboard) + if ((slst.size() < maxSug) && (!cpdsuggest || (slst.size() < oldSug + maxcpdsugs))) { + if (utf8) + badcharkey_utf(slst, word_utf.data(), wl, cpdsuggest); + else + badcharkey(slst, word, cpdsuggest); + } + if (clock() > timelimit + TIMELIMIT_SUGGESTION) + return good_suggestion; + + // did we add a char that should not be there + if ((slst.size() < maxSug) && (!cpdsuggest || (slst.size() < oldSug + maxcpdsugs))) { + if (utf8) + extrachar_utf(slst, word_utf.data(), wl, cpdsuggest); + else + extrachar(slst, word, cpdsuggest); + } + if (clock() > timelimit + TIMELIMIT_SUGGESTION) + return good_suggestion; + + // did we forgot a char + if ((slst.size() < maxSug) && (!cpdsuggest || (slst.size() < oldSug + maxcpdsugs))) { + if (utf8) + forgotchar_utf(slst, word_utf.data(), wl, cpdsuggest); + else + forgotchar(slst, word, cpdsuggest); + } + if (clock() > timelimit + TIMELIMIT_SUGGESTION) + return good_suggestion; + + // did we move a char + if ((slst.size() < maxSug) && (!cpdsuggest || (slst.size() < oldSug + maxcpdsugs))) { + if (utf8) + movechar_utf(slst, word_utf.data(), wl, cpdsuggest); + else + movechar(slst, word, cpdsuggest); + } + if (clock() > timelimit + TIMELIMIT_SUGGESTION) + return good_suggestion; + + // did we just hit the wrong key in place of a good char + if ((slst.size() < maxSug) && (!cpdsuggest || (slst.size() < oldSug + maxcpdsugs))) { + if (utf8) + badchar_utf(slst, word_utf.data(), wl, cpdsuggest); + else + badchar(slst, word, cpdsuggest); + } + if (clock() > timelimit + TIMELIMIT_SUGGESTION) + return good_suggestion; + + // did we double two characters + if ((slst.size() < maxSug) && (!cpdsuggest || (slst.size() < oldSug + maxcpdsugs))) { + if (utf8) + doubletwochars_utf(slst, word_utf.data(), wl, cpdsuggest); + else + doubletwochars(slst, word, cpdsuggest); + } + if (clock() > timelimit + TIMELIMIT_SUGGESTION) + return good_suggestion; + + // perhaps we forgot to hit space and two words ran together + // (dictionary word pairs have top priority here, so + // we always suggest them, in despite of nosplitsugs, and + // drop compound word and other suggestions) + if (!cpdsuggest || (!nosplitsugs && slst.size() < oldSug + maxcpdsugs)) { + good_suggestion = twowords(slst, word, cpdsuggest, good_suggestion); + } + if (clock() > timelimit + TIMELIMIT_SUGGESTION) + return good_suggestion; + + } // repeating ``for'' statement compounding support + + if (!nocompoundtwowords && (!slst.empty()) && onlycompoundsug) + *onlycompoundsug = 1; + + return good_suggestion; +} + +// suggestions for an uppercase word (html -> HTML) +void SuggestMgr::capchars_utf(std::vector<std::string>& wlst, + const w_char* word, + int wl, + int cpdsuggest) { + std::vector<w_char> candidate_utf(word, word + wl); + mkallcap_utf(candidate_utf, langnum); + std::string candidate; + u16_u8(candidate, candidate_utf); + testsug(wlst, candidate, cpdsuggest, NULL, NULL); +} + +// suggestions for an uppercase word (html -> HTML) +void SuggestMgr::capchars(std::vector<std::string>& wlst, + const char* word, + int cpdsuggest) { + std::string candidate(word); + mkallcap(candidate, csconv); + testsug(wlst, candidate, cpdsuggest, NULL, NULL); +} + +// suggestions for when chose the wrong char out of a related set +int SuggestMgr::mapchars(std::vector<std::string>& wlst, + const char* word, + int cpdsuggest) { + std::string candidate; + clock_t timelimit; + int timer; + + int wl = strlen(word); + if (wl < 2 || !pAMgr) + return wlst.size(); + + const std::vector<mapentry>& maptable = pAMgr->get_maptable(); + if (maptable.empty()) + return wlst.size(); + + timelimit = clock(); + timer = MINTIMER; + return map_related(word, candidate, 0, wlst, cpdsuggest, + maptable, &timer, &timelimit); +} + +int SuggestMgr::map_related(const char* word, + std::string& candidate, + int wn, + std::vector<std::string>& wlst, + int cpdsuggest, + const std::vector<mapentry>& maptable, + int* timer, + clock_t* timelimit) { + if (*(word + wn) == '\0') { + int cwrd = 1; + for (size_t m = 0; m < wlst.size(); ++m) { + if (wlst[m] == candidate) { + cwrd = 0; + break; + } + } + if ((cwrd) && checkword(candidate, cpdsuggest, timer, timelimit)) { + if (wlst.size() < maxSug) { + wlst.push_back(candidate); + } + } + return wlst.size(); + } + int in_map = 0; + for (size_t j = 0; j < maptable.size(); ++j) { + for (size_t k = 0; k < maptable[j].size(); ++k) { + size_t len = maptable[j][k].size(); + if (strncmp(maptable[j][k].c_str(), word + wn, len) == 0) { + in_map = 1; + size_t cn = candidate.size(); + for (size_t l = 0; l < maptable[j].size(); ++l) { + candidate.resize(cn); + candidate.append(maptable[j][l]); + map_related(word, candidate, wn + len, wlst, + cpdsuggest, maptable, timer, timelimit); + if (!(*timer)) + return wlst.size(); + } + } + } + } + if (!in_map) { + candidate.push_back(*(word + wn)); + map_related(word, candidate, wn + 1, wlst, cpdsuggest, + maptable, timer, timelimit); + } + return wlst.size(); +} + +// suggestions for a typical fault of spelling, that +// differs with more, than 1 letter from the right form. +int SuggestMgr::replchars(std::vector<std::string>& wlst, + const char* word, + int cpdsuggest) { + std::string candidate; + int wl = strlen(word); + if (wl < 2 || !pAMgr) + return wlst.size(); + const std::vector<replentry>& reptable = pAMgr->get_reptable(); + for (size_t i = 0; i < reptable.size(); ++i) { + const char* r = word; + // search every occurence of the pattern in the word + while ((r = strstr(r, reptable[i].pattern.c_str())) != NULL) { + int type = (r == word) ? 1 : 0; + if (r - word + reptable[i].pattern.size() == strlen(word)) + type += 2; + while (type && reptable[i].outstrings[type].empty()) + type = (type == 2 && r != word) ? 0 : type - 1; + const std::string&out = reptable[i].outstrings[type]; + if (out.empty()) { + ++r; + continue; + } + candidate.assign(word); + candidate.resize(r - word); + candidate.append(reptable[i].outstrings[type]); + candidate.append(r + reptable[i].pattern.size()); + testsug(wlst, candidate, cpdsuggest, NULL, NULL); + // check REP suggestions with space + size_t sp = candidate.find(' '); + if (sp != std::string::npos) { + size_t prev = 0; + while (sp != std::string::npos) { + std::string prev_chunk = candidate.substr(prev, sp - prev); + if (checkword(prev_chunk, 0, NULL, NULL)) { + size_t oldns = wlst.size(); + std::string post_chunk = candidate.substr(sp + 1); + testsug(wlst, post_chunk, cpdsuggest, NULL, NULL); + if (oldns < wlst.size()) { + wlst[wlst.size() - 1] = candidate; + } + } + prev = sp + 1; + sp = candidate.find(' ', prev); + } + } + r++; // search for the next letter + } + } + return wlst.size(); +} + +// perhaps we doubled two characters +// (for example vacation -> vacacation) +// The recognized pattern with regex back-references: +// "(.)(.)\1\2\1" or "..(.)(.)\1\2" + +int SuggestMgr::doubletwochars(std::vector<std::string>& wlst, + const char* word, + int cpdsuggest) { + int state = 0; + int wl = strlen(word); + if (wl < 5 || !pAMgr) + return wlst.size(); + for (int i = 2; i < wl; i++) { + if (word[i] == word[i - 2]) { + state++; + if (state == 3 || (state == 2 && i >= 4)) { + std::string candidate(word, word + i - 1); + candidate.insert(candidate.end(), word + i + 1, word + wl); + testsug(wlst, candidate, cpdsuggest, NULL, NULL); + state = 0; + } + } else { + state = 0; + } + } + return wlst.size(); +} + +// perhaps we doubled two characters +// (for example vacation -> vacacation) +// The recognized pattern with regex back-references: +// "(.)(.)\1\2\1" or "..(.)(.)\1\2" + +int SuggestMgr::doubletwochars_utf(std::vector<std::string>& wlst, + const w_char* word, + int wl, + int cpdsuggest) { + int state = 0; + if (wl < 5 || !pAMgr) + return wlst.size(); + for (int i = 2; i < wl; i++) { + if (word[i] == word[i - 2]) { + state++; + if (state == 3 || (state == 2 && i >= 4)) { + std::vector<w_char> candidate_utf(word, word + i - 1); + candidate_utf.insert(candidate_utf.end(), word + i + 1, word + wl); + std::string candidate; + u16_u8(candidate, candidate_utf); + testsug(wlst, candidate, cpdsuggest, NULL, NULL); + state = 0; + } + } else { + state = 0; + } + } + return wlst.size(); +} + +// error is wrong char in place of correct one (case and keyboard related +// version) +int SuggestMgr::badcharkey(std::vector<std::string>& wlst, + const char* word, + int cpdsuggest) { + std::string candidate(word); + + // swap out each char one by one and try uppercase and neighbor + // keyboard chars in its place to see if that makes a good word + for (size_t i = 0; i < candidate.size(); ++i) { + char tmpc = candidate[i]; + // check with uppercase letters + candidate[i] = csconv[((unsigned char)tmpc)].cupper; + if (tmpc != candidate[i]) { + testsug(wlst, candidate, cpdsuggest, NULL, NULL); + candidate[i] = tmpc; + } + // check neighbor characters in keyboard string + if (!ckey) + continue; + char* loc = strchr(ckey, tmpc); + while (loc) { + if ((loc > ckey) && (*(loc - 1) != '|')) { + candidate[i] = *(loc - 1); + testsug(wlst, candidate, cpdsuggest, NULL, NULL); + } + if ((*(loc + 1) != '|') && (*(loc + 1) != '\0')) { + candidate[i] = *(loc + 1); + testsug(wlst, candidate, cpdsuggest, NULL, NULL); + } + loc = strchr(loc + 1, tmpc); + } + candidate[i] = tmpc; + } + return wlst.size(); +} + +// error is wrong char in place of correct one (case and keyboard related +// version) +int SuggestMgr::badcharkey_utf(std::vector<std::string>& wlst, + const w_char* word, + int wl, + int cpdsuggest) { + std::string candidate; + std::vector<w_char> candidate_utf(word, word + wl); + // swap out each char one by one and try all the tryme + // chars in its place to see if that makes a good word + for (int i = 0; i < wl; i++) { + w_char tmpc = candidate_utf[i]; + // check with uppercase letters + candidate_utf[i] = upper_utf(candidate_utf[i], 1); + if (tmpc != candidate_utf[i]) { + u16_u8(candidate, candidate_utf); + testsug(wlst, candidate, cpdsuggest, NULL, NULL); + candidate_utf[i] = tmpc; + } + // check neighbor characters in keyboard string + if (!ckey) + continue; + size_t loc = 0; + while ((loc < ckeyl) && ckey_utf[loc] != tmpc) + ++loc; + while (loc < ckeyl) { + if ((loc > 0) && ckey_utf[loc - 1] != W_VLINE) { + candidate_utf[i] = ckey_utf[loc - 1]; + u16_u8(candidate, candidate_utf); + testsug(wlst, candidate, cpdsuggest, NULL, NULL); + } + if (((loc + 1) < ckeyl) && (ckey_utf[loc + 1] != W_VLINE)) { + candidate_utf[i] = ckey_utf[loc + 1]; + u16_u8(candidate, candidate_utf); + testsug(wlst, candidate, cpdsuggest, NULL, NULL); + } + do { + loc++; + } while ((loc < ckeyl) && ckey_utf[loc] != tmpc); + } + candidate_utf[i] = tmpc; + } + return wlst.size(); +} + +// error is wrong char in place of correct one +int SuggestMgr::badchar(std::vector<std::string>& wlst, const char* word, int cpdsuggest) { + std::string candidate(word); + clock_t timelimit = clock(); + int timer = MINTIMER; + // swap out each char one by one and try all the tryme + // chars in its place to see if that makes a good word + for (size_t j = 0; j < ctryl; ++j) { + for (std::string::reverse_iterator aI = candidate.rbegin(), aEnd = candidate.rend(); aI != aEnd; ++aI) { + char tmpc = *aI; + if (ctry[j] == tmpc) + continue; + *aI = ctry[j]; + testsug(wlst, candidate, cpdsuggest, &timer, &timelimit); + if (!timer) + return wlst.size(); + *aI = tmpc; + } + } + return wlst.size(); +} + +// error is wrong char in place of correct one +int SuggestMgr::badchar_utf(std::vector<std::string>& wlst, + const w_char* word, + int wl, + int cpdsuggest) { + std::vector<w_char> candidate_utf(word, word + wl); + std::string candidate; + clock_t timelimit = clock(); + int timer = MINTIMER; + // swap out each char one by one and try all the tryme + // chars in its place to see if that makes a good word + for (size_t j = 0; j < ctryl; ++j) { + for (int i = wl - 1; i >= 0; i--) { + w_char tmpc = candidate_utf[i]; + if (tmpc == ctry_utf[j]) + continue; + candidate_utf[i] = ctry_utf[j]; + u16_u8(candidate, candidate_utf); + testsug(wlst, candidate, cpdsuggest, &timer, &timelimit); + if (!timer) + return wlst.size(); + candidate_utf[i] = tmpc; + } + } + return wlst.size(); +} + +// error is word has an extra letter it does not need +int SuggestMgr::extrachar_utf(std::vector<std::string>& wlst, + const w_char* word, + int wl, + int cpdsuggest) { + std::vector<w_char> candidate_utf(word, word + wl); + if (candidate_utf.size() < 2) + return wlst.size(); + // try omitting one char of word at a time + for (size_t i = 0; i < candidate_utf.size(); ++i) { + size_t index = candidate_utf.size() - 1 - i; + w_char tmpc = candidate_utf[index]; + candidate_utf.erase(candidate_utf.begin() + index); + std::string candidate; + u16_u8(candidate, candidate_utf); + testsug(wlst, candidate, cpdsuggest, NULL, NULL); + candidate_utf.insert(candidate_utf.begin() + index, tmpc); + } + return wlst.size(); +} + +// error is word has an extra letter it does not need +int SuggestMgr::extrachar(std::vector<std::string>& wlst, + const char* word, + int cpdsuggest) { + std::string candidate(word); + if (candidate.size() < 2) + return wlst.size(); + // try omitting one char of word at a time + for (size_t i = 0; i < candidate.size(); ++i) { + size_t index = candidate.size() - 1 - i; + char tmpc = candidate[index]; + candidate.erase(candidate.begin() + index); + testsug(wlst, candidate, cpdsuggest, NULL, NULL); + candidate.insert(candidate.begin() + index, tmpc); + } + return wlst.size(); +} + +// error is missing a letter it needs +int SuggestMgr::forgotchar(std::vector<std::string>& wlst, + const char* word, + int cpdsuggest) { + std::string candidate(word); + clock_t timelimit = clock(); + int timer = MINTIMER; + + // try inserting a tryme character before every letter (and the null + // terminator) + for (size_t k = 0; k < ctryl; ++k) { + for (size_t i = 0; i <= candidate.size(); ++i) { + size_t index = candidate.size() - i; + candidate.insert(candidate.begin() + index, ctry[k]); + testsug(wlst, candidate, cpdsuggest, &timer, &timelimit); + if (!timer) + return wlst.size(); + candidate.erase(candidate.begin() + index); + } + } + return wlst.size(); +} + +// error is missing a letter it needs +int SuggestMgr::forgotchar_utf(std::vector<std::string>& wlst, + const w_char* word, + int wl, + int cpdsuggest) { + std::vector<w_char> candidate_utf(word, word + wl); + clock_t timelimit = clock(); + int timer = MINTIMER; + + // try inserting a tryme character at the end of the word and before every + // letter + for (size_t k = 0; k < ctryl; ++k) { + for (size_t i = 0; i <= candidate_utf.size(); ++i) { + size_t index = candidate_utf.size() - i; + candidate_utf.insert(candidate_utf.begin() + index, ctry_utf[k]); + std::string candidate; + u16_u8(candidate, candidate_utf); + testsug(wlst, candidate, cpdsuggest, &timer, &timelimit); + if (!timer) + return wlst.size(); + candidate_utf.erase(candidate_utf.begin() + index); + } + } + return wlst.size(); +} + +/* error is should have been two words + * return value is true, if there is a dictionary word pair, + * or there was already a good suggestion before calling + * this function. + */ +bool SuggestMgr::twowords(std::vector<std::string>& wlst, + const char* word, + int cpdsuggest, + bool good) { + int c2; + int forbidden = 0; + int cwrd; + + int wl = strlen(word); + if (wl < 3) + return false; + + if (langnum == LANG_hu) + forbidden = check_forbidden(word, wl); + + char* candidate = (char*)malloc(wl + 2); + strcpy(candidate + 1, word); + + // split the string into two pieces after every char + // if both pieces are good words make them a suggestion + for (char* p = candidate + 1; p[1] != '\0'; p++) { + p[-1] = *p; + // go to end of the UTF-8 character + while (utf8 && ((p[1] & 0xc0) == 0x80)) { + *p = p[1]; + p++; + } + if (utf8 && p[1] == '\0') + break; // last UTF-8 character + + // Suggest only word pairs, if they are listed in the dictionary. + // For example, adding "a lot" to the English dic file will + // result only "alot" -> "a lot" suggestion instead of + // "alto, slot, alt, lot, allot, aloft, aloe, clot, plot, blot, a lot". + // Note: using "ph:alot" keeps the other suggestions: + // a lot ph:alot + // alot -> a lot, alto, slot... + *p = ' '; + if (!cpdsuggest && checkword(candidate, cpdsuggest, NULL, NULL)) { + // remove not word pair suggestions + if (!good) { + good = true; + wlst.clear(); + } + wlst.insert(wlst.begin(), candidate); + } + + // word pairs with dash? + if (lang_with_dash_usage) { + *p = '-'; + + if (!cpdsuggest && checkword(candidate, cpdsuggest, NULL, NULL)) { + // remove not word pair suggestions + if (!good) { + good = true; + wlst.clear(); + } + wlst.insert(wlst.begin(), candidate); + } + } + + if (wlst.size() < maxSug && !nosplitsugs && !good) { + *p = '\0'; + int c1 = checkword(candidate, cpdsuggest, NULL, NULL); + if (c1) { + c2 = checkword((p + 1), cpdsuggest, NULL, NULL); + if (c2) { + // spec. Hungarian code (TODO need a better compound word support) + if ((langnum == LANG_hu) && !forbidden && + // if 3 repeating letter, use - instead of space + (((p[-1] == p[1]) && + (((p > candidate + 1) && (p[-1] == p[-2])) || (p[-1] == p[2]))) || + // or multiple compounding, with more, than 6 syllables + ((c1 == 3) && (c2 >= 2)))) + *p = '-'; + else + *p = ' '; + + cwrd = 1; + for (size_t k = 0; k < wlst.size(); ++k) { + if (wlst[k] == candidate) { + cwrd = 0; + break; + } + } + + if (cwrd && (wlst.size() < maxSug)) + wlst.push_back(candidate); + + // add two word suggestion with dash, depending on the language + // Note that cwrd doesn't modified for REP twoword sugg. + if ( !nosplitsugs && lang_with_dash_usage && + mystrlen(p + 1) > 1 && mystrlen(candidate) - mystrlen(p) > 1) { + *p = '-'; + for (size_t k = 0; k < wlst.size(); ++k) { + if (wlst[k] == candidate) { + cwrd = 0; + break; + } + } + + if ((wlst.size() < maxSug) && cwrd) + wlst.push_back(candidate); + } + } + } + } + } + free(candidate); + return good; +} + +// error is adjacent letter were swapped +int SuggestMgr::swapchar(std::vector<std::string>& wlst, + const char* word, + int cpdsuggest) { + std::string candidate(word); + if (candidate.size() < 2) + return wlst.size(); + + // try swapping adjacent chars one by one + for (size_t i = 0; i < candidate.size() - 1; ++i) { + std::swap(candidate[i], candidate[i+1]); + testsug(wlst, candidate, cpdsuggest, NULL, NULL); + std::swap(candidate[i], candidate[i+1]); + } + + // try double swaps for short words + // ahev -> have, owudl -> would + if (candidate.size() == 4 || candidate.size() == 5) { + candidate[0] = word[1]; + candidate[1] = word[0]; + candidate[2] = word[2]; + candidate[candidate.size() - 2] = word[candidate.size() - 1]; + candidate[candidate.size() - 1] = word[candidate.size() - 2]; + testsug(wlst, candidate, cpdsuggest, NULL, NULL); + if (candidate.size() == 5) { + candidate[0] = word[0]; + candidate[1] = word[2]; + candidate[2] = word[1]; + testsug(wlst, candidate, cpdsuggest, NULL, NULL); + } + } + + return wlst.size(); +} + +// error is adjacent letter were swapped +int SuggestMgr::swapchar_utf(std::vector<std::string>& wlst, + const w_char* word, + int wl, + int cpdsuggest) { + std::vector<w_char> candidate_utf(word, word + wl); + if (candidate_utf.size() < 2) + return wlst.size(); + + std::string candidate; + // try swapping adjacent chars one by one + for (size_t i = 0; i < candidate_utf.size() - 1; ++i) { + std::swap(candidate_utf[i], candidate_utf[i+1]); + u16_u8(candidate, candidate_utf); + testsug(wlst, candidate, cpdsuggest, NULL, NULL); + std::swap(candidate_utf[i], candidate_utf[i+1]); + } + + // try double swaps for short words + // ahev -> have, owudl -> would, suodn -> sound + if (candidate_utf.size() == 4 || candidate_utf.size() == 5) { + candidate_utf[0] = word[1]; + candidate_utf[1] = word[0]; + candidate_utf[2] = word[2]; + candidate_utf[candidate_utf.size() - 2] = word[candidate_utf.size() - 1]; + candidate_utf[candidate_utf.size() - 1] = word[candidate_utf.size() - 2]; + u16_u8(candidate, candidate_utf); + testsug(wlst, candidate, cpdsuggest, NULL, NULL); + if (candidate_utf.size() == 5) { + candidate_utf[0] = word[0]; + candidate_utf[1] = word[2]; + candidate_utf[2] = word[1]; + u16_u8(candidate, candidate_utf); + testsug(wlst, candidate, cpdsuggest, NULL, NULL); + } + } + return wlst.size(); +} + +// error is not adjacent letter were swapped +int SuggestMgr::longswapchar(std::vector<std::string>& wlst, + const char* word, + int cpdsuggest) { + std::string candidate(word); + // try swapping not adjacent chars one by one + for (std::string::iterator p = candidate.begin(); p < candidate.end(); ++p) { + for (std::string::iterator q = candidate.begin(); q < candidate.end(); ++q) { + size_t distance = std::abs(std::distance(q, p)); + if (distance > 1 && distance <= MAX_CHAR_DISTANCE) { + std::swap(*p, *q); + testsug(wlst, candidate, cpdsuggest, NULL, NULL); + std::swap(*p, *q); + } + } + } + return wlst.size(); +} + +// error is adjacent letter were swapped +int SuggestMgr::longswapchar_utf(std::vector<std::string>& wlst, + const w_char* word, + int wl, + int cpdsuggest) { + std::vector<w_char> candidate_utf(word, word + wl); + // try swapping not adjacent chars + for (std::vector<w_char>::iterator p = candidate_utf.begin(); p < candidate_utf.end(); ++p) { + for (std::vector<w_char>::iterator q = candidate_utf.begin(); q < candidate_utf.end(); ++q) { + size_t distance = std::abs(std::distance(q, p)); + if (distance > 1 && distance <= MAX_CHAR_DISTANCE) { + std::swap(*p, *q); + std::string candidate; + u16_u8(candidate, candidate_utf); + testsug(wlst, candidate, cpdsuggest, NULL, NULL); + std::swap(*p, *q); + } + } + } + return wlst.size(); +} + +// error is a letter was moved +int SuggestMgr::movechar(std::vector<std::string>& wlst, + const char* word, + int cpdsuggest) { + std::string candidate(word); + if (candidate.size() < 2) + return wlst.size(); + + // try moving a char + for (std::string::iterator p = candidate.begin(); p < candidate.end(); ++p) { + for (std::string::iterator q = p + 1; q < candidate.end() && std::distance(p, q) <= MAX_CHAR_DISTANCE; ++q) { + std::swap(*q, *(q - 1)); + if (std::distance(p, q) < 2) + continue; // omit swap char + testsug(wlst, candidate, cpdsuggest, NULL, NULL); + } + std::copy(word, word + candidate.size(), candidate.begin()); + } + + for (std::string::reverse_iterator p = candidate.rbegin(), pEnd = candidate.rend() - 1; p != pEnd; ++p) { + for (std::string::reverse_iterator q = p + 1, qEnd = candidate.rend(); q != qEnd && std::distance(p, q) <= MAX_CHAR_DISTANCE; ++q) { + std::swap(*q, *(q - 1)); + if (std::distance(p, q) < 2) + continue; // omit swap char + testsug(wlst, candidate, cpdsuggest, NULL, NULL); + } + std::copy(word, word + candidate.size(), candidate.begin()); + } + + return wlst.size(); +} + +// error is a letter was moved +int SuggestMgr::movechar_utf(std::vector<std::string>& wlst, + const w_char* word, + int wl, + int cpdsuggest) { + std::vector<w_char> candidate_utf(word, word + wl); + if (candidate_utf.size() < 2) + return wlst.size(); + + // try moving a char + for (std::vector<w_char>::iterator p = candidate_utf.begin(); p < candidate_utf.end(); ++p) { + for (std::vector<w_char>::iterator q = p + 1; q < candidate_utf.end() && std::distance(p, q) <= MAX_CHAR_DISTANCE; ++q) { + std::swap(*q, *(q - 1)); + if (std::distance(p, q) < 2) + continue; // omit swap char + std::string candidate; + u16_u8(candidate, candidate_utf); + testsug(wlst, candidate, cpdsuggest, NULL, NULL); + } + std::copy(word, word + candidate_utf.size(), candidate_utf.begin()); + } + + for (std::vector<w_char>::reverse_iterator p = candidate_utf.rbegin(); p < candidate_utf.rend(); ++p) { + for (std::vector<w_char>::reverse_iterator q = p + 1; q < candidate_utf.rend() && std::distance(p, q) <= MAX_CHAR_DISTANCE; ++q) { + std::swap(*q, *(q - 1)); + if (std::distance(p, q) < 2) + continue; // omit swap char + std::string candidate; + u16_u8(candidate, candidate_utf); + testsug(wlst, candidate, cpdsuggest, NULL, NULL); + } + std::copy(word, word + candidate_utf.size(), candidate_utf.begin()); + } + + return wlst.size(); +} + +// generate a set of suggestions for very poorly spelled words +void SuggestMgr::ngsuggest(std::vector<std::string>& wlst, + const char* w, + const std::vector<HashMgr*>& rHMgr, + int captype) { + int lval; + int sc; + int lp, lpphon; + int nonbmp = 0; + + // exhaustively search through all root words + // keeping track of the MAX_ROOTS most similar root words + struct hentry* roots[MAX_ROOTS]; + char* rootsphon[MAX_ROOTS]; + int scores[MAX_ROOTS]; + int scoresphon[MAX_ROOTS]; + for (int i = 0; i < MAX_ROOTS; i++) { + roots[i] = NULL; + scores[i] = -100 * i; + rootsphon[i] = NULL; + scoresphon[i] = -100 * i; + } + lp = MAX_ROOTS - 1; + lpphon = MAX_ROOTS - 1; + int low = NGRAM_LOWERING; + + std::string w2; + const char* word = w; + + // word reversing wrapper for complex prefixes + if (complexprefixes) { + w2.assign(w); + if (utf8) + reverseword_utf(w2); + else + reverseword(w2); + word = w2.c_str(); + } + + std::vector<w_char> u8; + int nc = strlen(word); + int n = (utf8) ? u8_u16(u8, word) : nc; + + // set character based ngram suggestion for words with non-BMP Unicode + // characters + if (n == -1) { + utf8 = 0; // XXX not state-free + n = nc; + nonbmp = 1; + low = 0; + } + + struct hentry* hp = NULL; + int col = -1; + phonetable* ph = (pAMgr) ? pAMgr->get_phonetable() : NULL; + std::string target; + std::string candidate; + std::vector<w_char> w_candidate; + if (ph) { + if (utf8) { + u8_u16(w_candidate, word); + mkallcap_utf(w_candidate, langnum); + u16_u8(candidate, w_candidate); + } else { + candidate.assign(word); + if (!nonbmp) + mkallcap(candidate, csconv); + } + target = phonet(candidate, *ph); // XXX phonet() is 8-bit (nc, not n) + } + + FLAG forbiddenword = pAMgr ? pAMgr->get_forbiddenword() : FLAG_NULL; + FLAG nosuggest = pAMgr ? pAMgr->get_nosuggest() : FLAG_NULL; + FLAG nongramsuggest = pAMgr ? pAMgr->get_nongramsuggest() : FLAG_NULL; + FLAG onlyincompound = pAMgr ? pAMgr->get_onlyincompound() : FLAG_NULL; + + std::vector<w_char> w_word, w_target; + if (utf8) { + u8_u16(w_word, word); + u8_u16(w_target, target); + } + + std::string f; + std::vector<w_char> w_f; + + for (size_t i = 0; i < rHMgr.size(); ++i) { + while (0 != (hp = rHMgr[i]->walk_hashtable(col, hp))) { + // skip exceptions + if ( + // skip it, if the word length different by 5 or + // more characters (to avoid strange suggestions) + // (except Unicode characters over BMP) + (((abs(n - hp->clen) > 4) && !nonbmp)) || + // don't suggest capitalized dictionary words for + // lower case misspellings in ngram suggestions, except + // - PHONE usage, or + // - in the case of German, where not only proper + // nouns are capitalized, or + // - the capitalized word has special pronunciation + ((captype == NOCAP) && (hp->var & H_OPT_INITCAP) && + !ph && (langnum != LANG_de) && !(hp->var & H_OPT_PHON)) || + // or it has one of the following special flags + ((hp->astr) && (pAMgr) && + (TESTAFF(hp->astr, forbiddenword, hp->alen) || + TESTAFF(hp->astr, ONLYUPCASEFLAG, hp->alen) || + TESTAFF(hp->astr, nosuggest, hp->alen) || + TESTAFF(hp->astr, nongramsuggest, hp->alen) || + TESTAFF(hp->astr, onlyincompound, hp->alen))) + ) + continue; + + if (utf8) { + u8_u16(w_f, HENTRY_WORD(hp)); + + int leftcommon = leftcommonsubstring(w_word, w_f); + if (low) { + // lowering dictionary word + mkallsmall_utf(w_f, langnum); + } + sc = ngram(3, w_word, w_f, NGRAM_LONGER_WORSE) + leftcommon; + } else { + f.assign(HENTRY_WORD(hp)); + + int leftcommon = leftcommonsubstring(word, f.c_str()); + if (low) { + // lowering dictionary word + mkallsmall(f, csconv); + } + sc = ngram(3, word, f, NGRAM_LONGER_WORSE) + leftcommon; + } + + // check special pronunciation + f.clear(); + if ((hp->var & H_OPT_PHON) && + copy_field(f, HENTRY_DATA(hp), MORPH_PHON)) { + int sc2; + if (utf8) { + u8_u16(w_f, f); + + int leftcommon = leftcommonsubstring(w_word, w_f); + if (low) { + // lowering dictionary word + mkallsmall_utf(w_f, langnum); + } + sc2 = ngram(3, w_word, w_f, NGRAM_LONGER_WORSE) + leftcommon; + } else { + int leftcommon = leftcommonsubstring(word, f.c_str()); + if (low) { + // lowering dictionary word + mkallsmall(f, csconv); + } + sc2 = ngram(3, word, f, NGRAM_LONGER_WORSE) + leftcommon; + } + if (sc2 > sc) + sc = sc2; + } + + int scphon = -20000; + if (ph && (sc > 2) && (abs(n - (int)hp->clen) <= 3)) { + if (utf8) { + u8_u16(w_candidate, HENTRY_WORD(hp)); + mkallcap_utf(w_candidate, langnum); + u16_u8(candidate, w_candidate); + } else { + candidate = HENTRY_WORD(hp); + mkallcap(candidate, csconv); + } + f = phonet(candidate, *ph); + if (utf8) { + u8_u16(w_f, f); + scphon = 2 * ngram(3, w_target, w_f, + NGRAM_LONGER_WORSE); + } else { + scphon = 2 * ngram(3, target, f, + NGRAM_LONGER_WORSE); + } + } + + if (sc > scores[lp]) { + scores[lp] = sc; + roots[lp] = hp; + lval = sc; + for (int j = 0; j < MAX_ROOTS; j++) + if (scores[j] < lval) { + lp = j; + lval = scores[j]; + } + } + + if (scphon > scoresphon[lpphon]) { + scoresphon[lpphon] = scphon; + rootsphon[lpphon] = HENTRY_WORD(hp); + lval = scphon; + for (int j = 0; j < MAX_ROOTS; j++) + if (scoresphon[j] < lval) { + lpphon = j; + lval = scoresphon[j]; + } + } + } + } + + // find minimum threshold for a passable suggestion + // mangle original word three differnt ways + // and score them to generate a minimum acceptable score + std::vector<w_char> w_mw; + int thresh = 0; + for (int sp = 1; sp < 4; sp++) { + if (utf8) { + w_mw = w_word; + for (int k = sp; k < n; k += 4) { + w_mw[k].l = '*'; + w_mw[k].h = 0; + } + + if (low) { + // lowering dictionary word + mkallsmall_utf(w_mw, langnum); + } + + thresh += ngram(n, w_word, w_mw, NGRAM_ANY_MISMATCH); + } else { + std::string mw = word; + for (int k = sp; k < n; k += 4) + mw[k] = '*'; + + if (low) { + // lowering dictionary word + mkallsmall(mw, csconv); + } + + thresh += ngram(n, word, mw, NGRAM_ANY_MISMATCH); + } + } + thresh = thresh / 3; + thresh--; + + // now expand affixes on each of these root words and + // and use length adjusted ngram scores to select + // possible suggestions + char* guess[MAX_GUESS]; + char* guessorig[MAX_GUESS]; + int gscore[MAX_GUESS]; + for (int i = 0; i < MAX_GUESS; i++) { + guess[i] = NULL; + guessorig[i] = NULL; + gscore[i] = -100 * i; + } + + lp = MAX_GUESS - 1; + + struct guessword* glst; + glst = (struct guessword*)calloc(MAX_WORDS, sizeof(struct guessword)); + if (!glst) { + if (nonbmp) + utf8 = 1; + return; + } + + for (int i = 0; i < MAX_ROOTS; i++) { + if (roots[i]) { + struct hentry* rp = roots[i]; + + f.clear(); + const char *field = NULL; + if ((rp->var & H_OPT_PHON) && copy_field(f, HENTRY_DATA(rp), MORPH_PHON)) + field = f.c_str(); + int nw = pAMgr->expand_rootword( + glst, MAX_WORDS, HENTRY_WORD(rp), rp->blen, rp->astr, rp->alen, word, + nc, field); + + for (int k = 0; k < nw; k++) { + if (utf8) { + u8_u16(w_f, glst[k].word); + + int leftcommon = leftcommonsubstring(w_word, w_f); + if (low) { + // lowering dictionary word + mkallsmall_utf(w_f, langnum); + } + + sc = ngram(n, w_word, w_f, NGRAM_ANY_MISMATCH) + leftcommon; + } else { + f = glst[k].word; + + int leftcommon = leftcommonsubstring(word, f.c_str()); + if (low) { + // lowering dictionary word + mkallsmall(f, csconv); + } + + sc = ngram(n, word, f, NGRAM_ANY_MISMATCH) + leftcommon; + } + + if (sc > thresh) { + if (sc > gscore[lp]) { + if (guess[lp]) { + free(guess[lp]); + if (guessorig[lp]) { + free(guessorig[lp]); + guessorig[lp] = NULL; + } + } + gscore[lp] = sc; + guess[lp] = glst[k].word; + guessorig[lp] = glst[k].orig; + lval = sc; + for (int j = 0; j < MAX_GUESS; j++) + if (gscore[j] < lval) { + lp = j; + lval = gscore[j]; + } + } else { + free(glst[k].word); + if (glst[k].orig) + free(glst[k].orig); + } + } else { + free(glst[k].word); + if (glst[k].orig) + free(glst[k].orig); + } + } + } + } + free(glst); + + // now we are done generating guesses + // sort in order of decreasing score + + bubblesort(&guess[0], &guessorig[0], &gscore[0], MAX_GUESS); + if (ph) + bubblesort(&rootsphon[0], NULL, &scoresphon[0], MAX_ROOTS); + + // weight suggestions with a similarity index, based on + // the longest common subsequent algorithm and resort + + int is_swap = 0; + int re = 0; + double fact = 1.0; + if (pAMgr) { + int maxd = pAMgr->get_maxdiff(); + if (maxd >= 0) + fact = (10.0 - maxd) / 5.0; + } + + std::vector<w_char> w_gl; + for (int i = 0; i < MAX_GUESS; i++) { + if (guess[i]) { + // lowering guess[i] + std::string gl; + int len; + if (utf8) { + len = u8_u16(w_gl, guess[i]); + mkallsmall_utf(w_gl, langnum); + u16_u8(gl, w_gl); + } else { + gl.assign(guess[i]); + if (!nonbmp) + mkallsmall(gl, csconv); + len = strlen(guess[i]); + } + + int _lcs = lcslen(word, gl.c_str()); + + // same characters with different casing + if ((n == len) && (n == _lcs)) { + gscore[i] += 2000; + break; + } + // using 2-gram instead of 3, and other weightening + + if (utf8) { + u8_u16(w_gl, gl); + //w_gl is lowercase already at this point + re = ngram(2, w_word, w_gl, NGRAM_ANY_MISMATCH + NGRAM_WEIGHTED); + if (low) { + w_f = w_word; + // lowering dictionary word + mkallsmall_utf(w_f, langnum); + re += ngram(2, w_gl, w_f, NGRAM_ANY_MISMATCH + NGRAM_WEIGHTED); + } else { + re += ngram(2, w_gl, w_word, NGRAM_ANY_MISMATCH + NGRAM_WEIGHTED); + } + } else { + //gl is lowercase already at this point + re = ngram(2, word, gl, NGRAM_ANY_MISMATCH + NGRAM_WEIGHTED); + if (low) { + f = word; + // lowering dictionary word + mkallsmall(f, csconv); + re += ngram(2, gl, f, NGRAM_ANY_MISMATCH + NGRAM_WEIGHTED); + } else { + re += ngram(2, gl, word, NGRAM_ANY_MISMATCH + NGRAM_WEIGHTED); + } + } + + int ngram_score, leftcommon_score; + if (utf8) { + //w_gl is lowercase already at this point + ngram_score = ngram(4, w_word, w_gl, NGRAM_ANY_MISMATCH); + leftcommon_score = leftcommonsubstring(w_word, w_gl); + } else { + //gl is lowercase already at this point + ngram_score = ngram(4, word, gl, NGRAM_ANY_MISMATCH); + leftcommon_score = leftcommonsubstring(word, gl.c_str()); + } + gscore[i] = + // length of longest common subsequent minus length difference + 2 * _lcs - abs((int)(n - len)) + + // weight length of the left common substring + leftcommon_score + + // weight equal character positions + (!nonbmp && commoncharacterpositions(word, gl.c_str(), &is_swap) + ? 1 + : 0) + + // swap character (not neighboring) + ((is_swap) ? 10 : 0) + + // ngram + ngram_score + + // weighted ngrams + re + + // different limit for dictionaries with PHONE rules + (ph ? (re < len * fact ? -1000 : 0) + : (re < (n + len) * fact ? -1000 : 0)); + } + } + + bubblesort(&guess[0], &guessorig[0], &gscore[0], MAX_GUESS); + + // phonetic version + if (ph) + for (int i = 0; i < MAX_ROOTS; i++) { + if (rootsphon[i]) { + // lowering rootphon[i] + std::string gl; + int len; + if (utf8) { + len = u8_u16(w_gl, rootsphon[i]); + mkallsmall_utf(w_gl, langnum); + u16_u8(gl, w_gl); + } else { + gl.assign(rootsphon[i]); + if (!nonbmp) + mkallsmall(gl, csconv); + len = strlen(rootsphon[i]); + } + + // weight length of the left common substring + int leftcommon_score; + if (utf8) + leftcommon_score = leftcommonsubstring(w_word, w_gl); + else + leftcommon_score = leftcommonsubstring(word, gl.c_str()); + // heuristic weigthing of ngram scores + scoresphon[i] += 2 * lcslen(word, gl) - abs((int)(n - len)) + + leftcommon_score; + } + } + + if (ph) + bubblesort(&rootsphon[0], NULL, &scoresphon[0], MAX_ROOTS); + + // copy over + size_t oldns = wlst.size(); + + int same = 0; + for (int i = 0; i < MAX_GUESS; i++) { + if (guess[i]) { + if ((wlst.size() < oldns + maxngramsugs) && (wlst.size() < maxSug) && + (!same || (gscore[i] > 1000))) { + int unique = 1; + // leave only excellent suggestions, if exists + if (gscore[i] > 1000) + same = 1; + else if (gscore[i] < -100) { + same = 1; + // keep the best ngram suggestions, unless in ONLYMAXDIFF mode + if (wlst.size() > oldns || (pAMgr && pAMgr->get_onlymaxdiff())) { + free(guess[i]); + if (guessorig[i]) + free(guessorig[i]); + continue; + } + } + for (size_t j = 0; j < wlst.size(); ++j) { + // don't suggest previous suggestions or a previous suggestion with + // prefixes or affixes + if ((!guessorig[i] && strstr(guess[i], wlst[j].c_str())) || + (guessorig[i] && strstr(guessorig[i], wlst[j].c_str())) || + // check forbidden words + !checkword(guess[i], 0, NULL, NULL)) { + unique = 0; + break; + } + } + if (unique) { + if (guessorig[i]) { + wlst.push_back(guessorig[i]); + } else { + wlst.push_back(guess[i]); + } + } + free(guess[i]); + if (guessorig[i]) + free(guessorig[i]); + } else { + free(guess[i]); + if (guessorig[i]) + free(guessorig[i]); + } + } + } + + oldns = wlst.size(); + if (ph) + for (int i = 0; i < MAX_ROOTS; i++) { + if (rootsphon[i]) { + if ((wlst.size() < oldns + MAXPHONSUGS) && (wlst.size() < maxSug)) { + int unique = 1; + for (size_t j = 0; j < wlst.size(); ++j) { + // don't suggest previous suggestions or a previous suggestion with + // prefixes or affixes + if (strstr(rootsphon[i], wlst[j].c_str()) || + // check forbidden words + !checkword(rootsphon[i], 0, NULL, NULL)) { + unique = 0; + break; + } + } + if (unique) { + wlst.push_back(rootsphon[i]); + } + } + } + } + + if (nonbmp) + utf8 = 1; +} + +// see if a candidate suggestion is spelled correctly +// needs to check both root words and words with affixes + +// obsolote MySpell-HU modifications: +// return value 2 and 3 marks compounding with hyphen (-) +// `3' marks roots without suffix +int SuggestMgr::checkword(const std::string& word, + int cpdsuggest, + int* timer, + clock_t* timelimit) { + // check time limit + if (timer) { + (*timer)--; + if (!(*timer) && timelimit) { + if ((clock() - *timelimit) > TIMELIMIT) + return 0; + *timer = MAXPLUSTIMER; + } + } + + if (pAMgr) { + struct hentry* rv = NULL; + int nosuffix = 0; + + if (cpdsuggest == 1) { + if (pAMgr->get_compound()) { + struct hentry* rv2 = NULL; + struct hentry* rwords[100]; // buffer for COMPOUND pattern checking + rv = pAMgr->compound_check(word, 0, 0, 100, 0, NULL, (hentry**)&rwords, 0, 1, 0); // EXT + if (rv && + (!(rv2 = pAMgr->lookup(word.c_str())) || !rv2->astr || + !(TESTAFF(rv2->astr, pAMgr->get_forbiddenword(), rv2->alen) || + TESTAFF(rv2->astr, pAMgr->get_nosuggest(), rv2->alen)))) + return 3; // XXX obsolote categorisation + only ICONV needs affix + // flag check? + } + return 0; + } + + rv = pAMgr->lookup(word.c_str()); + + if (rv) { + if ((rv->astr) && + (TESTAFF(rv->astr, pAMgr->get_forbiddenword(), rv->alen) || + TESTAFF(rv->astr, pAMgr->get_nosuggest(), rv->alen) || + TESTAFF(rv->astr, pAMgr->get_substandard(), rv->alen))) + return 0; + while (rv) { + if (rv->astr && + (TESTAFF(rv->astr, pAMgr->get_needaffix(), rv->alen) || + TESTAFF(rv->astr, ONLYUPCASEFLAG, rv->alen) || + TESTAFF(rv->astr, pAMgr->get_onlyincompound(), rv->alen))) { + rv = rv->next_homonym; + } else + break; + } + } else + rv = pAMgr->prefix_check(word.c_str(), word.size(), + 0); // only prefix, and prefix + suffix XXX + + if (rv) { + nosuffix = 1; + } else { + rv = pAMgr->suffix_check(word.c_str(), word.size(), 0, NULL, + FLAG_NULL, FLAG_NULL, IN_CPD_NOT); // only suffix + } + + if (!rv && pAMgr->have_contclass()) { + rv = pAMgr->suffix_check_twosfx(word.c_str(), word.size(), 0, NULL, FLAG_NULL); + if (!rv) + rv = pAMgr->prefix_check_twosfx(word.c_str(), word.size(), 0, FLAG_NULL); + } + + // check forbidden words + if ((rv) && (rv->astr) && + (TESTAFF(rv->astr, pAMgr->get_forbiddenword(), rv->alen) || + TESTAFF(rv->astr, ONLYUPCASEFLAG, rv->alen) || + TESTAFF(rv->astr, pAMgr->get_nosuggest(), rv->alen) || + TESTAFF(rv->astr, pAMgr->get_onlyincompound(), rv->alen))) + return 0; + + if (rv) { // XXX obsolote + if ((pAMgr->get_compoundflag()) && + TESTAFF(rv->astr, pAMgr->get_compoundflag(), rv->alen)) + return 2 + nosuffix; + return 1; + } + } + return 0; +} + +int SuggestMgr::check_forbidden(const char* word, int len) { + if (pAMgr) { + struct hentry* rv = pAMgr->lookup(word); + if (rv && rv->astr && + (TESTAFF(rv->astr, pAMgr->get_needaffix(), rv->alen) || + TESTAFF(rv->astr, pAMgr->get_onlyincompound(), rv->alen))) + rv = NULL; + if (!(pAMgr->prefix_check(word, len, 1))) + rv = pAMgr->suffix_check(word, len, 0, NULL, + FLAG_NULL, FLAG_NULL, IN_CPD_NOT); // prefix+suffix, suffix + // check forbidden words + if ((rv) && (rv->astr) && + TESTAFF(rv->astr, pAMgr->get_forbiddenword(), rv->alen)) + return 1; + } + return 0; +} + +std::string SuggestMgr::suggest_morph(const std::string& in_w) { + std::string result; + + struct hentry* rv = NULL; + + if (!pAMgr) + return std::string(); + + std::string w(in_w); + + // word reversing wrapper for complex prefixes + if (complexprefixes) { + if (utf8) + reverseword_utf(w); + else + reverseword(w); + } + + rv = pAMgr->lookup(w.c_str()); + + while (rv) { + if ((!rv->astr) || + !(TESTAFF(rv->astr, pAMgr->get_forbiddenword(), rv->alen) || + TESTAFF(rv->astr, pAMgr->get_needaffix(), rv->alen) || + TESTAFF(rv->astr, pAMgr->get_onlyincompound(), rv->alen))) { + if (!HENTRY_FIND(rv, MORPH_STEM)) { + result.push_back(MSEP_FLD); + result.append(MORPH_STEM); + result.append(w); + } + if (HENTRY_DATA(rv)) { + result.push_back(MSEP_FLD); + result.append(HENTRY_DATA2(rv)); + } + result.push_back(MSEP_REC); + } + rv = rv->next_homonym; + } + + std::string st = pAMgr->affix_check_morph(w.c_str(), w.size()); + if (!st.empty()) { + result.append(st); + } + + if (pAMgr->get_compound() && result.empty()) { + struct hentry* rwords[100]; // buffer for COMPOUND pattern checking + pAMgr->compound_check_morph(w.c_str(), w.size(), 0, 0, 100, 0, NULL, (hentry**)&rwords, 0, result, + NULL); + } + + line_uniq(result, MSEP_REC); + + return result; +} + +static int get_sfxcount(const char* morph) { + if (!morph || !*morph) + return 0; + int n = 0; + const char* old = morph; + morph = strstr(morph, MORPH_DERI_SFX); + if (!morph) + morph = strstr(old, MORPH_INFL_SFX); + if (!morph) + morph = strstr(old, MORPH_TERM_SFX); + while (morph) { + n++; + old = morph; + morph = strstr(morph + 1, MORPH_DERI_SFX); + if (!morph) + morph = strstr(old + 1, MORPH_INFL_SFX); + if (!morph) + morph = strstr(old + 1, MORPH_TERM_SFX); + } + return n; +} + +/* affixation */ +std::string SuggestMgr::suggest_hentry_gen(hentry* rv, const char* pattern) { + std::string result; + int sfxcount = get_sfxcount(pattern); + + if (get_sfxcount(HENTRY_DATA(rv)) > sfxcount) + return result; + + if (HENTRY_DATA(rv)) { + std::string aff = pAMgr->morphgen(HENTRY_WORD(rv), rv->blen, rv->astr, rv->alen, + HENTRY_DATA(rv), pattern, 0); + if (!aff.empty()) { + result.append(aff); + result.push_back(MSEP_REC); + } + } + + // check all allomorphs + char* p = NULL; + if (HENTRY_DATA(rv)) + p = (char*)strstr(HENTRY_DATA2(rv), MORPH_ALLOMORPH); + while (p) { + p += MORPH_TAG_LEN; + int plen = fieldlen(p); + std::string allomorph(p, plen); + struct hentry* rv2 = pAMgr->lookup(allomorph.c_str()); + while (rv2) { + // if (HENTRY_DATA(rv2) && get_sfxcount(HENTRY_DATA(rv2)) <= + // sfxcount) { + if (HENTRY_DATA(rv2)) { + char* st = (char*)strstr(HENTRY_DATA2(rv2), MORPH_STEM); + if (st && (strncmp(st + MORPH_TAG_LEN, HENTRY_WORD(rv), + fieldlen(st + MORPH_TAG_LEN)) == 0)) { + std::string aff = pAMgr->morphgen(HENTRY_WORD(rv2), rv2->blen, rv2->astr, + rv2->alen, HENTRY_DATA(rv2), pattern, 0); + if (!aff.empty()) { + result.append(aff); + result.push_back(MSEP_REC); + } + } + } + rv2 = rv2->next_homonym; + } + p = strstr(p + plen, MORPH_ALLOMORPH); + } + + return result; +} + +std::string SuggestMgr::suggest_gen(const std::vector<std::string>& desc, const std::string& in_pattern) { + if (desc.empty() || !pAMgr) + return std::string(); + + const char* pattern = in_pattern.c_str(); + std::string result2; + std::string newpattern; + struct hentry* rv = NULL; + + // search affixed forms with and without derivational suffixes + while (1) { + for (size_t k = 0; k < desc.size(); ++k) { + std::string result; + + // add compound word parts (except the last one) + const char* s = desc[k].c_str(); + const char* part = strstr(s, MORPH_PART); + if (part) { + const char* nextpart = strstr(part + 1, MORPH_PART); + while (nextpart) { + std::string field; + copy_field(field, part, MORPH_PART); + result.append(field); + part = nextpart; + nextpart = strstr(part + 1, MORPH_PART); + } + s = part; + } + + std::string tok(s); + size_t pos = tok.find(" | "); + while (pos != std::string::npos) { + tok[pos + 1] = MSEP_ALT; + pos = tok.find(" | ", pos); + } + std::vector<std::string> pl = line_tok(tok, MSEP_ALT); + for (size_t i = 0; i < pl.size(); ++i) { + // remove inflectional and terminal suffixes + size_t is = pl[i].find(MORPH_INFL_SFX); + if (is != std::string::npos) + pl[i].resize(is); + size_t ts = pl[i].find(MORPH_TERM_SFX); + while (ts != std::string::npos) { + pl[i][ts] = '_'; + ts = pl[i].find(MORPH_TERM_SFX); + } + const char* st = strstr(s, MORPH_STEM); + if (st) { + copy_field(tok, st, MORPH_STEM); + rv = pAMgr->lookup(tok.c_str()); + while (rv) { + std::string newpat(pl[i]); + newpat.append(pattern); + std::string sg = suggest_hentry_gen(rv, newpat.c_str()); + if (sg.empty()) + sg = suggest_hentry_gen(rv, pattern); + if (!sg.empty()) { + std::vector<std::string> gen = line_tok(sg, MSEP_REC); + for (size_t j = 0; j < gen.size(); ++j) { + result2.push_back(MSEP_REC); + result2.append(result); + if (pl[i].find(MORPH_SURF_PFX) != std::string::npos) { + std::string field; + copy_field(field, pl[i], MORPH_SURF_PFX); + result2.append(field); + } + result2.append(gen[j]); + } + } + rv = rv->next_homonym; + } + } + } + } + + if (!result2.empty() || !strstr(pattern, MORPH_DERI_SFX)) + break; + + newpattern.assign(pattern); + mystrrep(newpattern, MORPH_DERI_SFX, MORPH_TERM_SFX); + pattern = newpattern.c_str(); + } + return result2; +} + +// generate an n-gram score comparing s1 and s2, UTF16 version +int SuggestMgr::ngram(int n, + const std::vector<w_char>& su1, + const std::vector<w_char>& su2, + int opt) { + int nscore = 0; + int ns; + int l1; + int l2; + int test = 0; + + l1 = su1.size(); + l2 = su2.size(); + if (l2 == 0) + return 0; + for (int j = 1; j <= n; j++) { + ns = 0; + for (int i = 0; i <= (l1 - j); i++) { + int k = 0; + for (int l = 0; l <= (l2 - j); l++) { + for (k = 0; k < j; k++) { + const w_char& c1 = su1[i + k]; + const w_char& c2 = su2[l + k]; + if ((c1.l != c2.l) || (c1.h != c2.h)) + break; + } + if (k == j) { + ns++; + break; + } + } + if (k != j && opt & NGRAM_WEIGHTED) { + ns--; + test++; + if (i == 0 || i == l1 - j) + ns--; // side weight + } + } + nscore = nscore + ns; + if (ns < 2 && !(opt & NGRAM_WEIGHTED)) + break; + } + + ns = 0; + if (opt & NGRAM_LONGER_WORSE) + ns = (l2 - l1) - 2; + if (opt & NGRAM_ANY_MISMATCH) + ns = abs(l2 - l1) - 2; + ns = (nscore - ((ns > 0) ? ns : 0)); + return ns; +} + +// generate an n-gram score comparing s1 and s2, non-UTF16 version +int SuggestMgr::ngram(int n, + const std::string& s1, + const std::string& s2, + int opt) { + int nscore = 0; + int ns; + int l1; + int l2; + int test = 0; + + l2 = s2.size(); + if (l2 == 0) + return 0; + l1 = s1.size(); + for (int j = 1; j <= n; j++) { + ns = 0; + for (int i = 0; i <= (l1 - j); i++) { + //s2 is haystack, s1[i..i+j) is needle + if (s2.find(s1.c_str()+i, 0, j) != std::string::npos) { + ns++; + } else if (opt & NGRAM_WEIGHTED) { + ns--; + test++; + if (i == 0 || i == l1 - j) + ns--; // side weight + } + } + nscore = nscore + ns; + if (ns < 2 && !(opt & NGRAM_WEIGHTED)) + break; + } + + ns = 0; + if (opt & NGRAM_LONGER_WORSE) + ns = (l2 - l1) - 2; + if (opt & NGRAM_ANY_MISMATCH) + ns = abs(l2 - l1) - 2; + ns = (nscore - ((ns > 0) ? ns : 0)); + return ns; +} + +// length of the left common substring of s1 and (decapitalised) s2, UTF version +int SuggestMgr::leftcommonsubstring( + const std::vector<w_char>& su1, + const std::vector<w_char>& su2) { + int l1 = su1.size(); + int l2 = su2.size(); + // decapitalize dictionary word + if (complexprefixes) { + if (l1 && l2 && su1[l1 - 1] == su2[l2 - 1]) + return 1; + } else { + unsigned short idx = su2.empty() ? 0 : (su2[0].h << 8) + su2[0].l; + unsigned short otheridx = su1.empty() ? 0 : (su1[0].h << 8) + su1[0].l; + if (otheridx != idx && (otheridx != unicodetolower(idx, langnum))) + return 0; + int i; + for (i = 1; (i < l1) && (i < l2) && (su1[i].l == su2[i].l) && + (su1[i].h == su2[i].h); + i++) + ; + return i; + } + return 0; +} + +// length of the left common substring of s1 and (decapitalised) s2, non-UTF +int SuggestMgr::leftcommonsubstring( + const char* s1, + const char* s2) { + if (complexprefixes) { + int l1 = strlen(s1); + int l2 = strlen(s2); + if (l1 <= l2 && s2[l1 - 1] == s2[l2 - 1]) + return 1; + } else if (csconv) { + const char* olds = s1; + // decapitalise dictionary word + if ((*s1 != *s2) && (*s1 != csconv[((unsigned char)*s2)].clower)) + return 0; + do { + s1++; + s2++; + } while ((*s1 == *s2) && (*s1 != '\0')); + return (int)(s1 - olds); + } + return 0; +} + +int SuggestMgr::commoncharacterpositions(const char* s1, + const char* s2, + int* is_swap) { + int num = 0; + int diff = 0; + int diffpos[2]; + *is_swap = 0; + if (utf8) { + std::vector<w_char> su1; + std::vector<w_char> su2; + int l1 = u8_u16(su1, s1); + int l2 = u8_u16(su2, s2); + + if (l1 <= 0 || l2 <= 0) + return 0; + + // decapitalize dictionary word + if (complexprefixes) { + su2[l2 - 1] = lower_utf(su2[l2 - 1], langnum); + } else { + su2[0] = lower_utf(su2[0], langnum); + } + for (int i = 0; (i < l1) && (i < l2); i++) { + if (su1[i] == su2[i]) { + num++; + } else { + if (diff < 2) + diffpos[diff] = i; + diff++; + } + } + if ((diff == 2) && (l1 == l2) && + (su1[diffpos[0]] == su2[diffpos[1]]) && + (su1[diffpos[1]] == su2[diffpos[0]])) + *is_swap = 1; + } else { + size_t i; + std::string t(s2); + // decapitalize dictionary word + if (complexprefixes) { + size_t l2 = t.size(); + t[l2 - 1] = csconv[(unsigned char)t[l2 - 1]].clower; + } else { + mkallsmall(t, csconv); + } + for (i = 0; i < t.size() && (*(s1 + i) != 0); ++i) { + if (*(s1 + i) == t[i]) { + num++; + } else { + if (diff < 2) + diffpos[diff] = i; + diff++; + } + } + if ((diff == 2) && (*(s1 + i) == 0) && i == t.size() && + (*(s1 + diffpos[0]) == t[diffpos[1]]) && + (*(s1 + diffpos[1]) == t[diffpos[0]])) + *is_swap = 1; + } + return num; +} + +int SuggestMgr::mystrlen(const char* word) { + if (utf8) { + std::vector<w_char> w; + return u8_u16(w, word); + } else + return strlen(word); +} + +// sort in decreasing order of score +void SuggestMgr::bubblesort(char** rword, char** rword2, int* rsc, int n) { + int m = 1; + while (m < n) { + int j = m; + while (j > 0) { + if (rsc[j - 1] < rsc[j]) { + int sctmp = rsc[j - 1]; + char* wdtmp = rword[j - 1]; + rsc[j - 1] = rsc[j]; + rword[j - 1] = rword[j]; + rsc[j] = sctmp; + rword[j] = wdtmp; + if (rword2) { + wdtmp = rword2[j - 1]; + rword2[j - 1] = rword2[j]; + rword2[j] = wdtmp; + } + j--; + } else + break; + } + m++; + } + return; +} + +// longest common subsequence +void SuggestMgr::lcs(const char* s, + const char* s2, + int* l1, + int* l2, + char** result) { + int n, m; + std::vector<w_char> su; + std::vector<w_char> su2; + char* b; + char* c; + int i; + int j; + if (utf8) { + m = u8_u16(su, s); + n = u8_u16(su2, s2); + } else { + m = strlen(s); + n = strlen(s2); + } + c = (char*)malloc((m + 1) * (n + 1)); + b = (char*)malloc((m + 1) * (n + 1)); + if (!c || !b) { + if (c) + free(c); + if (b) + free(b); + *result = NULL; + return; + } + for (i = 1; i <= m; i++) + c[i * (n + 1)] = 0; + for (j = 0; j <= n; j++) + c[j] = 0; + for (i = 1; i <= m; i++) { + for (j = 1; j <= n; j++) { + if (((utf8) && (su[i - 1] == su2[j - 1])) || + ((!utf8) && (s[i - 1] == s2[j - 1]))) { + c[i * (n + 1) + j] = c[(i - 1) * (n + 1) + j - 1] + 1; + b[i * (n + 1) + j] = LCS_UPLEFT; + } else if (c[(i - 1) * (n + 1) + j] >= c[i * (n + 1) + j - 1]) { + c[i * (n + 1) + j] = c[(i - 1) * (n + 1) + j]; + b[i * (n + 1) + j] = LCS_UP; + } else { + c[i * (n + 1) + j] = c[i * (n + 1) + j - 1]; + b[i * (n + 1) + j] = LCS_LEFT; + } + } + } + *result = b; + free(c); + *l1 = m; + *l2 = n; +} + +int SuggestMgr::lcslen(const char* s, const char* s2) { + int m; + int n; + int i; + int j; + char* result; + int len = 0; + lcs(s, s2, &m, &n, &result); + if (!result) + return 0; + i = m; + j = n; + while ((i != 0) && (j != 0)) { + if (result[i * (n + 1) + j] == LCS_UPLEFT) { + len++; + i--; + j--; + } else if (result[i * (n + 1) + j] == LCS_UP) { + i--; + } else + j--; + } + free(result); + return len; +} + +int SuggestMgr::lcslen(const std::string& s, const std::string& s2) { + return lcslen(s.c_str(), s2.c_str()); +} |