diff options
author | 2012-03-30 09:53:51 +0900 | |
---|---|---|
committer | 2012-03-30 09:53:51 +0900 | |
commit | 3ef3e24a12ed72204f7a6f2e4b2df8ce7d243746 (patch) | |
tree | 3447bd6522889f98bad07e7212bd69c915106af2 /native/src | |
parent | 0f55e6cbcddb30747fc1b6f0db8ba106fcbd9b6b (diff) | |
download | latinime-3ef3e24a12ed72204f7a6f2e4b2df8ce7d243746.tar.gz latinime-3ef3e24a12ed72204f7a6f2e4b2df8ce7d243746.tar.xz latinime-3ef3e24a12ed72204f7a6f2e4b2df8ce7d243746.zip |
Move the "src" directory as a preparation for Ib4a47342 and I66f6c5b9
Change-Id: I3ab65059f6e356530484bfd0bba26a634a4cba65
Diffstat (limited to 'native/src')
-rw-r--r-- | native/src/additional_proximity_chars.cpp | 41 | ||||
-rw-r--r-- | native/src/additional_proximity_chars.h | 94 | ||||
-rw-r--r-- | native/src/basechars.cpp | 194 | ||||
-rw-r--r-- | native/src/bigram_dictionary.cpp | 165 | ||||
-rw-r--r-- | native/src/bigram_dictionary.h | 56 | ||||
-rw-r--r-- | native/src/binary_format.h | 481 | ||||
-rw-r--r-- | native/src/char_utils.cpp | 899 | ||||
-rw-r--r-- | native/src/char_utils.h | 65 | ||||
-rw-r--r-- | native/src/correction.cpp | 1143 | ||||
-rw-r--r-- | native/src/correction.h | 239 | ||||
-rw-r--r-- | native/src/correction_state.h | 84 | ||||
-rw-r--r-- | native/src/debug.h | 72 | ||||
-rw-r--r-- | native/src/defines.h | 254 | ||||
-rw-r--r-- | native/src/dictionary.cpp | 63 | ||||
-rw-r--r-- | native/src/dictionary.h | 89 | ||||
-rw-r--r-- | native/src/proximity_info.cpp | 466 | ||||
-rw-r--r-- | native/src/proximity_info.h | 134 | ||||
-rw-r--r-- | native/src/terminal_attributes.h | 78 | ||||
-rw-r--r-- | native/src/unigram_dictionary.cpp | 894 | ||||
-rw-r--r-- | native/src/unigram_dictionary.h | 173 | ||||
-rw-r--r-- | native/src/words_priority_queue.h | 195 | ||||
-rw-r--r-- | native/src/words_priority_queue_pool.h | 90 |
22 files changed, 0 insertions, 5969 deletions
diff --git a/native/src/additional_proximity_chars.cpp b/native/src/additional_proximity_chars.cpp deleted file mode 100644 index 224f020f2..000000000 --- a/native/src/additional_proximity_chars.cpp +++ /dev/null @@ -1,41 +0,0 @@ -/* - * Copyright (C) 2012 The Android Open Source Project - * - * Licensed under the Apache License, Version 2.0 (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.apache.org/licenses/LICENSE-2.0 - * - * Unless required by applicable law or agreed to in writing, software - * distributed under the License is distributed on an "AS IS" BASIS, - * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. - * See the License for the specific language governing permissions and - * limitations under the License. - */ - -#include "additional_proximity_chars.h" - -namespace latinime { -const std::string AdditionalProximityChars::LOCALE_EN_US("en"); - -const int32_t AdditionalProximityChars::EN_US_ADDITIONAL_A[EN_US_ADDITIONAL_A_SIZE] = { - 'e', 'i', 'o', 'u' -}; - -const int32_t AdditionalProximityChars::EN_US_ADDITIONAL_E[EN_US_ADDITIONAL_E_SIZE] = { - 'a', 'i', 'o', 'u' -}; - -const int32_t AdditionalProximityChars::EN_US_ADDITIONAL_I[EN_US_ADDITIONAL_I_SIZE] = { - 'a', 'e', 'o', 'u' -}; - -const int32_t AdditionalProximityChars::EN_US_ADDITIONAL_O[EN_US_ADDITIONAL_O_SIZE] = { - 'a', 'e', 'i', 'u' -}; - -const int32_t AdditionalProximityChars::EN_US_ADDITIONAL_U[EN_US_ADDITIONAL_U_SIZE] = { - 'a', 'e', 'i', 'o' -}; -} diff --git a/native/src/additional_proximity_chars.h b/native/src/additional_proximity_chars.h deleted file mode 100644 index e0ecc0e1d..000000000 --- a/native/src/additional_proximity_chars.h +++ /dev/null @@ -1,94 +0,0 @@ -/* - * Copyright (C) 2012 The Android Open Source Project - * - * Licensed under the Apache License, Version 2.0 (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.apache.org/licenses/LICENSE-2.0 - * - * Unless required by applicable law or agreed to in writing, software - * distributed under the License is distributed on an "AS IS" BASIS, - * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. - * See the License for the specific language governing permissions and - * limitations under the License. - */ - -#ifndef LATINIME_ADDITIONAL_PROXIMITY_CHARS_H -#define LATINIME_ADDITIONAL_PROXIMITY_CHARS_H - -#include <stdint.h> -#include <string> - -#include "defines.h" - -namespace latinime { - -class AdditionalProximityChars { - private: - static const std::string LOCALE_EN_US; - static const int EN_US_ADDITIONAL_A_SIZE = 4; - static const int32_t EN_US_ADDITIONAL_A[]; - static const int EN_US_ADDITIONAL_E_SIZE = 4; - static const int32_t EN_US_ADDITIONAL_E[]; - static const int EN_US_ADDITIONAL_I_SIZE = 4; - static const int32_t EN_US_ADDITIONAL_I[]; - static const int EN_US_ADDITIONAL_O_SIZE = 4; - static const int32_t EN_US_ADDITIONAL_O[]; - static const int EN_US_ADDITIONAL_U_SIZE = 4; - static const int32_t EN_US_ADDITIONAL_U[]; - - static bool isEnLocale(const std::string *locale_str) { - return locale_str && locale_str->size() >= LOCALE_EN_US.size() - && LOCALE_EN_US.compare(0, LOCALE_EN_US.size(), *locale_str); - } - - public: - static int getAdditionalCharsSize(const std::string* locale_str, const int32_t c) { - if (!isEnLocale(locale_str)) { - return 0; - } - switch(c) { - case 'a': - return EN_US_ADDITIONAL_A_SIZE; - case 'e': - return EN_US_ADDITIONAL_E_SIZE; - case 'i': - return EN_US_ADDITIONAL_I_SIZE; - case 'o': - return EN_US_ADDITIONAL_O_SIZE; - case 'u': - return EN_US_ADDITIONAL_U_SIZE; - default: - return 0; - } - } - - static const int32_t* getAdditionalChars(const std::string *locale_str, const int32_t c) { - if (!isEnLocale(locale_str)) { - return 0; - } - switch(c) { - case 'a': - return EN_US_ADDITIONAL_A; - case 'e': - return EN_US_ADDITIONAL_E; - case 'i': - return EN_US_ADDITIONAL_I; - case 'o': - return EN_US_ADDITIONAL_O; - case 'u': - return EN_US_ADDITIONAL_U; - default: - return 0; - } - } - - static bool hasAdditionalChars(const std::string *locale_str, const int32_t c) { - return getAdditionalCharsSize(locale_str, c) > 0; - } -}; - -} - -#endif // LATINIME_ADDITIONAL_PROXIMITY_CHARS_H diff --git a/native/src/basechars.cpp b/native/src/basechars.cpp deleted file mode 100644 index 31f1e18a8..000000000 --- a/native/src/basechars.cpp +++ /dev/null @@ -1,194 +0,0 @@ -/* - * Copyright (C) 2011 The Android Open Source Project - * - * Licensed under the Apache License, Version 2.0 (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.apache.org/licenses/LICENSE-2.0 - * - * Unless required by applicable law or agreed to in writing, software - * distributed under the License is distributed on an "AS IS" BASIS, - * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. - * See the License for the specific language governing permissions and - * limitations under the License. - */ - -#include "char_utils.h" - -namespace latinime { - -/** - * Table mapping most combined Latin, Greek, and Cyrillic characters - * to their base characters. If c is in range, BASE_CHARS[c] == c - * if c is not a combined character, or the base character if it - * is combined. - */ -const unsigned short BASE_CHARS[BASE_CHARS_SIZE] = { - 0x0000, 0x0001, 0x0002, 0x0003, 0x0004, 0x0005, 0x0006, 0x0007, - 0x0008, 0x0009, 0x000a, 0x000b, 0x000c, 0x000d, 0x000e, 0x000f, - 0x0010, 0x0011, 0x0012, 0x0013, 0x0014, 0x0015, 0x0016, 0x0017, - 0x0018, 0x0019, 0x001a, 0x001b, 0x001c, 0x001d, 0x001e, 0x001f, - 0x0020, 0x0021, 0x0022, 0x0023, 0x0024, 0x0025, 0x0026, 0x0027, - 0x0028, 0x0029, 0x002a, 0x002b, 0x002c, 0x002d, 0x002e, 0x002f, - 0x0030, 0x0031, 0x0032, 0x0033, 0x0034, 0x0035, 0x0036, 0x0037, - 0x0038, 0x0039, 0x003a, 0x003b, 0x003c, 0x003d, 0x003e, 0x003f, - 0x0040, 0x0041, 0x0042, 0x0043, 0x0044, 0x0045, 0x0046, 0x0047, - 0x0048, 0x0049, 0x004a, 0x004b, 0x004c, 0x004d, 0x004e, 0x004f, - 0x0050, 0x0051, 0x0052, 0x0053, 0x0054, 0x0055, 0x0056, 0x0057, - 0x0058, 0x0059, 0x005a, 0x005b, 0x005c, 0x005d, 0x005e, 0x005f, - 0x0060, 0x0061, 0x0062, 0x0063, 0x0064, 0x0065, 0x0066, 0x0067, - 0x0068, 0x0069, 0x006a, 0x006b, 0x006c, 0x006d, 0x006e, 0x006f, - 0x0070, 0x0071, 0x0072, 0x0073, 0x0074, 0x0075, 0x0076, 0x0077, - 0x0078, 0x0079, 0x007a, 0x007b, 0x007c, 0x007d, 0x007e, 0x007f, - 0x0080, 0x0081, 0x0082, 0x0083, 0x0084, 0x0085, 0x0086, 0x0087, - 0x0088, 0x0089, 0x008a, 0x008b, 0x008c, 0x008d, 0x008e, 0x008f, - 0x0090, 0x0091, 0x0092, 0x0093, 0x0094, 0x0095, 0x0096, 0x0097, - 0x0098, 0x0099, 0x009a, 0x009b, 0x009c, 0x009d, 0x009e, 0x009f, - 0x0020, 0x00a1, 0x00a2, 0x00a3, 0x00a4, 0x00a5, 0x00a6, 0x00a7, - 0x0020, 0x00a9, 0x0061, 0x00ab, 0x00ac, 0x00ad, 0x00ae, 0x0020, - 0x00b0, 0x00b1, 0x0032, 0x0033, 0x0020, 0x03bc, 0x00b6, 0x00b7, - 0x0020, 0x0031, 0x006f, 0x00bb, 0x0031, 0x0031, 0x0033, 0x00bf, - 0x0041, 0x0041, 0x0041, 0x0041, 0x0041, 0x0041, 0x00c6, 0x0043, - 0x0045, 0x0045, 0x0045, 0x0045, 0x0049, 0x0049, 0x0049, 0x0049, - 0x00d0, 0x004e, 0x004f, 0x004f, 0x004f, 0x004f, 0x004f, 0x00d7, - 0x004f, 0x0055, 0x0055, 0x0055, 0x0055, 0x0059, 0x00de, 0x0073, // Manually changed d8 to 4f - // Manually changed df to 73 - 0x0061, 0x0061, 0x0061, 0x0061, 0x0061, 0x0061, 0x00e6, 0x0063, - 0x0065, 0x0065, 0x0065, 0x0065, 0x0069, 0x0069, 0x0069, 0x0069, - 0x00f0, 0x006e, 0x006f, 0x006f, 0x006f, 0x006f, 0x006f, 0x00f7, - 0x006f, 0x0075, 0x0075, 0x0075, 0x0075, 0x0079, 0x00fe, 0x0079, // Manually changed f8 to 6f - 0x0041, 0x0061, 0x0041, 0x0061, 0x0041, 0x0061, 0x0043, 0x0063, - 0x0043, 0x0063, 0x0043, 0x0063, 0x0043, 0x0063, 0x0044, 0x0064, - 0x0110, 0x0111, 0x0045, 0x0065, 0x0045, 0x0065, 0x0045, 0x0065, - 0x0045, 0x0065, 0x0045, 0x0065, 0x0047, 0x0067, 0x0047, 0x0067, - 0x0047, 0x0067, 0x0047, 0x0067, 0x0048, 0x0068, 0x0126, 0x0127, - 0x0049, 0x0069, 0x0049, 0x0069, 0x0049, 0x0069, 0x0049, 0x0069, - 0x0049, 0x0131, 0x0049, 0x0069, 0x004a, 0x006a, 0x004b, 0x006b, - 0x0138, 0x004c, 0x006c, 0x004c, 0x006c, 0x004c, 0x006c, 0x004c, - 0x006c, 0x0141, 0x0142, 0x004e, 0x006e, 0x004e, 0x006e, 0x004e, - 0x006e, 0x02bc, 0x014a, 0x014b, 0x004f, 0x006f, 0x004f, 0x006f, - 0x004f, 0x006f, 0x0152, 0x0153, 0x0052, 0x0072, 0x0052, 0x0072, - 0x0052, 0x0072, 0x0053, 0x0073, 0x0053, 0x0073, 0x0053, 0x0073, - 0x0053, 0x0073, 0x0054, 0x0074, 0x0054, 0x0074, 0x0166, 0x0167, - 0x0055, 0x0075, 0x0055, 0x0075, 0x0055, 0x0075, 0x0055, 0x0075, - 0x0055, 0x0075, 0x0055, 0x0075, 0x0057, 0x0077, 0x0059, 0x0079, - 0x0059, 0x005a, 0x007a, 0x005a, 0x007a, 0x005a, 0x007a, 0x0073, - 0x0180, 0x0181, 0x0182, 0x0183, 0x0184, 0x0185, 0x0186, 0x0187, - 0x0188, 0x0189, 0x018a, 0x018b, 0x018c, 0x018d, 0x018e, 0x018f, - 0x0190, 0x0191, 0x0192, 0x0193, 0x0194, 0x0195, 0x0196, 0x0197, - 0x0198, 0x0199, 0x019a, 0x019b, 0x019c, 0x019d, 0x019e, 0x019f, - 0x004f, 0x006f, 0x01a2, 0x01a3, 0x01a4, 0x01a5, 0x01a6, 0x01a7, - 0x01a8, 0x01a9, 0x01aa, 0x01ab, 0x01ac, 0x01ad, 0x01ae, 0x0055, - 0x0075, 0x01b1, 0x01b2, 0x01b3, 0x01b4, 0x01b5, 0x01b6, 0x01b7, - 0x01b8, 0x01b9, 0x01ba, 0x01bb, 0x01bc, 0x01bd, 0x01be, 0x01bf, - 0x01c0, 0x01c1, 0x01c2, 0x01c3, 0x0044, 0x0044, 0x0064, 0x004c, - 0x004c, 0x006c, 0x004e, 0x004e, 0x006e, 0x0041, 0x0061, 0x0049, - 0x0069, 0x004f, 0x006f, 0x0055, 0x0075, 0x00dc, 0x00fc, 0x00dc, - 0x00fc, 0x00dc, 0x00fc, 0x00dc, 0x00fc, 0x01dd, 0x00c4, 0x00e4, - 0x0226, 0x0227, 0x00c6, 0x00e6, 0x01e4, 0x01e5, 0x0047, 0x0067, - 0x004b, 0x006b, 0x004f, 0x006f, 0x01ea, 0x01eb, 0x01b7, 0x0292, - 0x006a, 0x0044, 0x0044, 0x0064, 0x0047, 0x0067, 0x01f6, 0x01f7, - 0x004e, 0x006e, 0x00c5, 0x00e5, 0x00c6, 0x00e6, 0x00d8, 0x00f8, - 0x0041, 0x0061, 0x0041, 0x0061, 0x0045, 0x0065, 0x0045, 0x0065, - 0x0049, 0x0069, 0x0049, 0x0069, 0x004f, 0x006f, 0x004f, 0x006f, - 0x0052, 0x0072, 0x0052, 0x0072, 0x0055, 0x0075, 0x0055, 0x0075, - 0x0053, 0x0073, 0x0054, 0x0074, 0x021c, 0x021d, 0x0048, 0x0068, - 0x0220, 0x0221, 0x0222, 0x0223, 0x0224, 0x0225, 0x0041, 0x0061, - 0x0045, 0x0065, 0x00d6, 0x00f6, 0x00d5, 0x00f5, 0x004f, 0x006f, - 0x022e, 0x022f, 0x0059, 0x0079, 0x0234, 0x0235, 0x0236, 0x0237, - 0x0238, 0x0239, 0x023a, 0x023b, 0x023c, 0x023d, 0x023e, 0x023f, - 0x0240, 0x0241, 0x0242, 0x0243, 0x0244, 0x0245, 0x0246, 0x0247, - 0x0248, 0x0249, 0x024a, 0x024b, 0x024c, 0x024d, 0x024e, 0x024f, - 0x0250, 0x0251, 0x0252, 0x0253, 0x0254, 0x0255, 0x0256, 0x0257, - 0x0258, 0x0259, 0x025a, 0x025b, 0x025c, 0x025d, 0x025e, 0x025f, - 0x0260, 0x0261, 0x0262, 0x0263, 0x0264, 0x0265, 0x0266, 0x0267, - 0x0268, 0x0269, 0x026a, 0x026b, 0x026c, 0x026d, 0x026e, 0x026f, - 0x0270, 0x0271, 0x0272, 0x0273, 0x0274, 0x0275, 0x0276, 0x0277, - 0x0278, 0x0279, 0x027a, 0x027b, 0x027c, 0x027d, 0x027e, 0x027f, - 0x0280, 0x0281, 0x0282, 0x0283, 0x0284, 0x0285, 0x0286, 0x0287, - 0x0288, 0x0289, 0x028a, 0x028b, 0x028c, 0x028d, 0x028e, 0x028f, - 0x0290, 0x0291, 0x0292, 0x0293, 0x0294, 0x0295, 0x0296, 0x0297, - 0x0298, 0x0299, 0x029a, 0x029b, 0x029c, 0x029d, 0x029e, 0x029f, - 0x02a0, 0x02a1, 0x02a2, 0x02a3, 0x02a4, 0x02a5, 0x02a6, 0x02a7, - 0x02a8, 0x02a9, 0x02aa, 0x02ab, 0x02ac, 0x02ad, 0x02ae, 0x02af, - 0x0068, 0x0266, 0x006a, 0x0072, 0x0279, 0x027b, 0x0281, 0x0077, - 0x0079, 0x02b9, 0x02ba, 0x02bb, 0x02bc, 0x02bd, 0x02be, 0x02bf, - 0x02c0, 0x02c1, 0x02c2, 0x02c3, 0x02c4, 0x02c5, 0x02c6, 0x02c7, - 0x02c8, 0x02c9, 0x02ca, 0x02cb, 0x02cc, 0x02cd, 0x02ce, 0x02cf, - 0x02d0, 0x02d1, 0x02d2, 0x02d3, 0x02d4, 0x02d5, 0x02d6, 0x02d7, - 0x0020, 0x0020, 0x0020, 0x0020, 0x0020, 0x0020, 0x02de, 0x02df, - 0x0263, 0x006c, 0x0073, 0x0078, 0x0295, 0x02e5, 0x02e6, 0x02e7, - 0x02e8, 0x02e9, 0x02ea, 0x02eb, 0x02ec, 0x02ed, 0x02ee, 0x02ef, - 0x02f0, 0x02f1, 0x02f2, 0x02f3, 0x02f4, 0x02f5, 0x02f6, 0x02f7, - 0x02f8, 0x02f9, 0x02fa, 0x02fb, 0x02fc, 0x02fd, 0x02fe, 0x02ff, - 0x0300, 0x0301, 0x0302, 0x0303, 0x0304, 0x0305, 0x0306, 0x0307, - 0x0308, 0x0309, 0x030a, 0x030b, 0x030c, 0x030d, 0x030e, 0x030f, - 0x0310, 0x0311, 0x0312, 0x0313, 0x0314, 0x0315, 0x0316, 0x0317, - 0x0318, 0x0319, 0x031a, 0x031b, 0x031c, 0x031d, 0x031e, 0x031f, - 0x0320, 0x0321, 0x0322, 0x0323, 0x0324, 0x0325, 0x0326, 0x0327, - 0x0328, 0x0329, 0x032a, 0x032b, 0x032c, 0x032d, 0x032e, 0x032f, - 0x0330, 0x0331, 0x0332, 0x0333, 0x0334, 0x0335, 0x0336, 0x0337, - 0x0338, 0x0339, 0x033a, 0x033b, 0x033c, 0x033d, 0x033e, 0x033f, - 0x0300, 0x0301, 0x0342, 0x0313, 0x0308, 0x0345, 0x0346, 0x0347, - 0x0348, 0x0349, 0x034a, 0x034b, 0x034c, 0x034d, 0x034e, 0x034f, - 0x0350, 0x0351, 0x0352, 0x0353, 0x0354, 0x0355, 0x0356, 0x0357, - 0x0358, 0x0359, 0x035a, 0x035b, 0x035c, 0x035d, 0x035e, 0x035f, - 0x0360, 0x0361, 0x0362, 0x0363, 0x0364, 0x0365, 0x0366, 0x0367, - 0x0368, 0x0369, 0x036a, 0x036b, 0x036c, 0x036d, 0x036e, 0x036f, - 0x0370, 0x0371, 0x0372, 0x0373, 0x02b9, 0x0375, 0x0376, 0x0377, - 0x0378, 0x0379, 0x0020, 0x037b, 0x037c, 0x037d, 0x003b, 0x037f, - 0x0380, 0x0381, 0x0382, 0x0383, 0x0020, 0x00a8, 0x0391, 0x00b7, - 0x0395, 0x0397, 0x0399, 0x038b, 0x039f, 0x038d, 0x03a5, 0x03a9, - 0x03ca, 0x0391, 0x0392, 0x0393, 0x0394, 0x0395, 0x0396, 0x0397, - 0x0398, 0x0399, 0x039a, 0x039b, 0x039c, 0x039d, 0x039e, 0x039f, - 0x03a0, 0x03a1, 0x03a2, 0x03a3, 0x03a4, 0x03a5, 0x03a6, 0x03a7, - 0x03a8, 0x03a9, 0x0399, 0x03a5, 0x03b1, 0x03b5, 0x03b7, 0x03b9, - 0x03cb, 0x03b1, 0x03b2, 0x03b3, 0x03b4, 0x03b5, 0x03b6, 0x03b7, - 0x03b8, 0x03b9, 0x03ba, 0x03bb, 0x03bc, 0x03bd, 0x03be, 0x03bf, - 0x03c0, 0x03c1, 0x03c2, 0x03c3, 0x03c4, 0x03c5, 0x03c6, 0x03c7, - 0x03c8, 0x03c9, 0x03b9, 0x03c5, 0x03bf, 0x03c5, 0x03c9, 0x03cf, - 0x03b2, 0x03b8, 0x03a5, 0x03d2, 0x03d2, 0x03c6, 0x03c0, 0x03d7, - 0x03d8, 0x03d9, 0x03da, 0x03db, 0x03dc, 0x03dd, 0x03de, 0x03df, - 0x03e0, 0x03e1, 0x03e2, 0x03e3, 0x03e4, 0x03e5, 0x03e6, 0x03e7, - 0x03e8, 0x03e9, 0x03ea, 0x03eb, 0x03ec, 0x03ed, 0x03ee, 0x03ef, - 0x03ba, 0x03c1, 0x03c2, 0x03f3, 0x0398, 0x03b5, 0x03f6, 0x03f7, - 0x03f8, 0x03a3, 0x03fa, 0x03fb, 0x03fc, 0x03fd, 0x03fe, 0x03ff, - 0x0415, 0x0415, 0x0402, 0x0413, 0x0404, 0x0405, 0x0406, 0x0406, - 0x0408, 0x0409, 0x040a, 0x040b, 0x041a, 0x0418, 0x0423, 0x040f, - 0x0410, 0x0411, 0x0412, 0x0413, 0x0414, 0x0415, 0x0416, 0x0417, - 0x0418, 0x0418, 0x041a, 0x041b, 0x041c, 0x041d, 0x041e, 0x041f, - 0x0420, 0x0421, 0x0422, 0x0423, 0x0424, 0x0425, 0x0426, 0x0427, - 0x0428, 0x0429, 0x042a, 0x042b, 0x042c, 0x042d, 0x042e, 0x042f, - 0x0430, 0x0431, 0x0432, 0x0433, 0x0434, 0x0435, 0x0436, 0x0437, - 0x0438, 0x0438, 0x043a, 0x043b, 0x043c, 0x043d, 0x043e, 0x043f, - 0x0440, 0x0441, 0x0442, 0x0443, 0x0444, 0x0445, 0x0446, 0x0447, - 0x0448, 0x0449, 0x044a, 0x044b, 0x044c, 0x044d, 0x044e, 0x044f, - 0x0435, 0x0435, 0x0452, 0x0433, 0x0454, 0x0455, 0x0456, 0x0456, - 0x0458, 0x0459, 0x045a, 0x045b, 0x043a, 0x0438, 0x0443, 0x045f, - 0x0460, 0x0461, 0x0462, 0x0463, 0x0464, 0x0465, 0x0466, 0x0467, - 0x0468, 0x0469, 0x046a, 0x046b, 0x046c, 0x046d, 0x046e, 0x046f, - 0x0470, 0x0471, 0x0472, 0x0473, 0x0474, 0x0475, 0x0474, 0x0475, - 0x0478, 0x0479, 0x047a, 0x047b, 0x047c, 0x047d, 0x047e, 0x047f, - 0x0480, 0x0481, 0x0482, 0x0483, 0x0484, 0x0485, 0x0486, 0x0487, - 0x0488, 0x0489, 0x048a, 0x048b, 0x048c, 0x048d, 0x048e, 0x048f, - 0x0490, 0x0491, 0x0492, 0x0493, 0x0494, 0x0495, 0x0496, 0x0497, - 0x0498, 0x0499, 0x049a, 0x049b, 0x049c, 0x049d, 0x049e, 0x049f, - 0x04a0, 0x04a1, 0x04a2, 0x04a3, 0x04a4, 0x04a5, 0x04a6, 0x04a7, - 0x04a8, 0x04a9, 0x04aa, 0x04ab, 0x04ac, 0x04ad, 0x04ae, 0x04af, - 0x04b0, 0x04b1, 0x04b2, 0x04b3, 0x04b4, 0x04b5, 0x04b6, 0x04b7, - 0x04b8, 0x04b9, 0x04ba, 0x04bb, 0x04bc, 0x04bd, 0x04be, 0x04bf, - 0x04c0, 0x0416, 0x0436, 0x04c3, 0x04c4, 0x04c5, 0x04c6, 0x04c7, - 0x04c8, 0x04c9, 0x04ca, 0x04cb, 0x04cc, 0x04cd, 0x04ce, 0x04cf, - 0x0410, 0x0430, 0x0410, 0x0430, 0x04d4, 0x04d5, 0x0415, 0x0435, - 0x04d8, 0x04d9, 0x04d8, 0x04d9, 0x0416, 0x0436, 0x0417, 0x0437, - 0x04e0, 0x04e1, 0x0418, 0x0438, 0x0418, 0x0438, 0x041e, 0x043e, - 0x04e8, 0x04e9, 0x04e8, 0x04e9, 0x042d, 0x044d, 0x0423, 0x0443, - 0x0423, 0x0443, 0x0423, 0x0443, 0x0427, 0x0447, 0x04f6, 0x04f7, - 0x042b, 0x044b, 0x04fa, 0x04fb, 0x04fc, 0x04fd, 0x04fe, 0x04ff, -}; - -// generated with: -// cat UnicodeData.txt | perl -e 'while (<>) { @foo = split(/;/); $foo[5] =~ s/<.*> //; $base[hex($foo[0])] = hex($foo[5]);} for ($i = 0; $i < 0x500; $i += 8) { for ($j = $i; $j < $i + 8; $j++) { printf("0x%04x, ", $base[$j] ? $base[$j] : $j)}; print "\n"; }' - -} // namespace latinime diff --git a/native/src/bigram_dictionary.cpp b/native/src/bigram_dictionary.cpp deleted file mode 100644 index f7a3d3e60..000000000 --- a/native/src/bigram_dictionary.cpp +++ /dev/null @@ -1,165 +0,0 @@ -/* -** -** Copyright 2010, The Android Open Source Project -** -** Licensed under the Apache License, Version 2.0 (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.apache.org/licenses/LICENSE-2.0 -** -** Unless required by applicable law or agreed to in writing, software -** distributed under the License is distributed on an "AS IS" BASIS, -** WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. -** See the License for the specific language governing permissions and -** limitations under the License. -*/ - -#include <string.h> - -#define LOG_TAG "LatinIME: bigram_dictionary.cpp" - -#include "bigram_dictionary.h" -#include "dictionary.h" -#include "binary_format.h" - -namespace latinime { - -BigramDictionary::BigramDictionary(const unsigned char *dict, int maxWordLength, - const bool isLatestDictVersion, const bool hasBigram, - Dictionary *parentDictionary) - : DICT(dict), MAX_WORD_LENGTH(maxWordLength), - IS_LATEST_DICT_VERSION(isLatestDictVersion), - HAS_BIGRAM(hasBigram), mParentDictionary(parentDictionary) { - if (DEBUG_DICT) { - AKLOGI("BigramDictionary - constructor"); - AKLOGI("Has Bigram : %d", hasBigram); - } -} - -BigramDictionary::~BigramDictionary() { -} - -bool BigramDictionary::addWordBigram(unsigned short *word, int length, int frequency) { - word[length] = 0; - if (DEBUG_DICT) { -#ifdef FLAG_DBG - char s[length + 1]; - for (int i = 0; i <= length; i++) s[i] = word[i]; - AKLOGI("Bigram: Found word = %s, freq = %d :", s, frequency); -#endif - } - - // Find the right insertion point - int insertAt = 0; - while (insertAt < mMaxBigrams) { - if (frequency > mBigramFreq[insertAt] || (mBigramFreq[insertAt] == frequency - && length < Dictionary::wideStrLen(mBigramChars + insertAt * MAX_WORD_LENGTH))) { - break; - } - insertAt++; - } - if (DEBUG_DICT) { - AKLOGI("Bigram: InsertAt -> %d maxBigrams: %d", insertAt, mMaxBigrams); - } - if (insertAt < mMaxBigrams) { - memmove((char*) mBigramFreq + (insertAt + 1) * sizeof(mBigramFreq[0]), - (char*) mBigramFreq + insertAt * sizeof(mBigramFreq[0]), - (mMaxBigrams - insertAt - 1) * sizeof(mBigramFreq[0])); - mBigramFreq[insertAt] = frequency; - memmove((char*) mBigramChars + (insertAt + 1) * MAX_WORD_LENGTH * sizeof(short), - (char*) mBigramChars + (insertAt ) * MAX_WORD_LENGTH * sizeof(short), - (mMaxBigrams - insertAt - 1) * sizeof(short) * MAX_WORD_LENGTH); - unsigned short *dest = mBigramChars + (insertAt ) * MAX_WORD_LENGTH; - while (length--) { - *dest++ = *word++; - } - *dest = 0; // NULL terminate - if (DEBUG_DICT) { - AKLOGI("Bigram: Added word at %d", insertAt); - } - return true; - } - return false; -} - -/* Parameters : - * prevWord: the word before, the one for which we need to look up bigrams. - * prevWordLength: its length. - * codes: what user typed, in the same format as for UnigramDictionary::getSuggestions. - * codesSize: the size of the codes array. - * bigramChars: an array for output, at the same format as outwords for getSuggestions. - * bigramFreq: an array to output frequencies. - * maxWordLength: the maximum size of a word. - * maxBigrams: the maximum number of bigrams fitting in the bigramChars array. - * This method returns the number of bigrams this word has, for backward compatibility. - * Note: this is not the number of bigrams output in the array, which is the number of - * bigrams this word has WHOSE first letter also matches the letter the user typed. - * TODO: this may not be a sensible thing to do. It makes sense when the bigrams are - * used to match the first letter of the second word, but once the user has typed more - * and the bigrams are used to boost unigram result scores, it makes little sense to - * reduce their scope to the ones that match the first letter. - */ -int BigramDictionary::getBigrams(unsigned short *prevWord, int prevWordLength, int *codes, - int codesSize, unsigned short *bigramChars, int *bigramFreq, int maxWordLength, - int maxBigrams) { - // TODO: remove unused arguments, and refrain from storing stuff in members of this class - // TODO: have "in" arguments before "out" ones, and make out args explicit in the name - mBigramFreq = bigramFreq; - mBigramChars = bigramChars; - mInputCodes = codes; - mMaxBigrams = maxBigrams; - - const uint8_t* const root = DICT; - int pos = BinaryFormat::getTerminalPosition(root, prevWord, prevWordLength); - - if (NOT_VALID_WORD == pos) return 0; - const int flags = BinaryFormat::getFlagsAndForwardPointer(root, &pos); - if (0 == (flags & UnigramDictionary::FLAG_HAS_BIGRAMS)) return 0; - if (0 == (flags & UnigramDictionary::FLAG_HAS_MULTIPLE_CHARS)) { - BinaryFormat::getCharCodeAndForwardPointer(root, &pos); - } else { - pos = BinaryFormat::skipOtherCharacters(root, pos); - } - pos = BinaryFormat::skipChildrenPosition(flags, pos); - pos = BinaryFormat::skipFrequency(flags, pos); - int bigramFlags; - int bigramCount = 0; - do { - bigramFlags = BinaryFormat::getFlagsAndForwardPointer(root, &pos); - uint16_t bigramBuffer[MAX_WORD_LENGTH]; - const int bigramPos = BinaryFormat::getAttributeAddressAndForwardPointer(root, bigramFlags, - &pos); - const int length = BinaryFormat::getWordAtAddress(root, bigramPos, MAX_WORD_LENGTH, - bigramBuffer); - - // codesSize == 0 means we are trying to find bigram predictions. - if (codesSize < 1 || checkFirstCharacter(bigramBuffer)) { - const int frequency = UnigramDictionary::MASK_ATTRIBUTE_FREQUENCY & bigramFlags; - if (addWordBigram(bigramBuffer, length, frequency)) { - ++bigramCount; - } - } - } while (0 != (UnigramDictionary::FLAG_ATTRIBUTE_HAS_NEXT & bigramFlags)); - return bigramCount; -} - -bool BigramDictionary::checkFirstCharacter(unsigned short *word) { - // Checks whether this word starts with same character or neighboring characters of - // what user typed. - - int *inputCodes = mInputCodes; - int maxAlt = MAX_ALTERNATIVES; - const unsigned short firstBaseChar = toBaseLowerCase(*word); - while (maxAlt > 0) { - if (toBaseLowerCase(*inputCodes) == firstBaseChar) { - return true; - } - inputCodes++; - maxAlt--; - } - return false; -} - -// TODO: Move functions related to bigram to here -} // namespace latinime diff --git a/native/src/bigram_dictionary.h b/native/src/bigram_dictionary.h deleted file mode 100644 index 8132fbc59..000000000 --- a/native/src/bigram_dictionary.h +++ /dev/null @@ -1,56 +0,0 @@ -/* - * Copyright (C) 2010 The Android Open Source Project - * - * Licensed under the Apache License, Version 2.0 (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.apache.org/licenses/LICENSE-2.0 - * - * Unless required by applicable law or agreed to in writing, software - * distributed under the License is distributed on an "AS IS" BASIS, - * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. - * See the License for the specific language governing permissions and - * limitations under the License. - */ - -#ifndef LATINIME_BIGRAM_DICTIONARY_H -#define LATINIME_BIGRAM_DICTIONARY_H - -namespace latinime { - -class Dictionary; -class BigramDictionary { - public: - BigramDictionary(const unsigned char *dict, int maxWordLength, - const bool isLatestDictVersion, const bool hasBigram, Dictionary *parentDictionary); - int getBigrams(unsigned short *word, int length, int *codes, int codesSize, - unsigned short *outWords, int *frequencies, int maxWordLength, int maxBigrams); - ~BigramDictionary(); - private: - bool addWordBigram(unsigned short *word, int length, int frequency); - int getBigramAddress(int *pos, bool advance); - int getBigramFreq(int *pos); - void searchForTerminalNode(int addressLookingFor, int frequency); - bool getFirstBitOfByte(int *pos) { return (DICT[*pos] & 0x80) > 0; } - bool getSecondBitOfByte(int *pos) { return (DICT[*pos] & 0x40) > 0; } - bool checkFirstCharacter(unsigned short *word); - - const unsigned char *DICT; - const int MAX_WORD_LENGTH; - // TODO: Re-implement proximity correction for bigram correction - static const int MAX_ALTERNATIVES = 1; - const bool IS_LATEST_DICT_VERSION; - const bool HAS_BIGRAM; - - Dictionary *mParentDictionary; - int *mBigramFreq; - int mMaxBigrams; - unsigned short *mBigramChars; - int *mInputCodes; - int mInputLength; -}; - -} // namespace latinime - -#endif // LATINIME_BIGRAM_DICTIONARY_H diff --git a/native/src/binary_format.h b/native/src/binary_format.h deleted file mode 100644 index ab033ad90..000000000 --- a/native/src/binary_format.h +++ /dev/null @@ -1,481 +0,0 @@ -/* - * Copyright (C) 2011 The Android Open Source Project - * - * Licensed under the Apache License, Version 2.0 (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.apache.org/licenses/LICENSE-2.0 - * - * Unless required by applicable law or agreed to in writing, software - * distributed under the License is distributed on an "AS IS" BASIS, - * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. - * See the License for the specific language governing permissions and - * limitations under the License. - */ - -#ifndef LATINIME_BINARY_FORMAT_H -#define LATINIME_BINARY_FORMAT_H - -#include <limits> -#include "unigram_dictionary.h" - -namespace latinime { - -class BinaryFormat { - private: - const static int32_t MINIMAL_ONE_BYTE_CHARACTER_VALUE = 0x20; - const static int32_t CHARACTER_ARRAY_TERMINATOR = 0x1F; - const static int MULTIPLE_BYTE_CHARACTER_ADDITIONAL_SIZE = 2; - - public: - const static int UNKNOWN_FORMAT = -1; - // Originally, format version 1 had a 16-bit magic number, then the version number `01' - // then options that must be 0. Hence the first 32-bits of the format are always as follow - // and it's okay to consider them a magic number as a whole. - const static uint32_t FORMAT_VERSION_1_MAGIC_NUMBER = 0x78B10100; - const static unsigned int FORMAT_VERSION_1_HEADER_SIZE = 5; - // The versions of Latin IME that only handle format version 1 only test for the magic - // number, so we had to change it so that version 2 files would be rejected by older - // implementations. On this occasion, we made the magic number 32 bits long. - const static uint32_t FORMAT_VERSION_2_MAGIC_NUMBER = 0x9BC13AFE; - - static int detectFormat(const uint8_t* const dict); - static unsigned int getHeaderSize(const uint8_t* const dict); - static int getGroupCountAndForwardPointer(const uint8_t* const dict, int* pos); - static uint8_t getFlagsAndForwardPointer(const uint8_t* const dict, int* pos); - static int32_t getCharCodeAndForwardPointer(const uint8_t* const dict, int* pos); - static int readFrequencyWithoutMovingPointer(const uint8_t* const dict, const int pos); - static int skipOtherCharacters(const uint8_t* const dict, const int pos); - static int skipAttributes(const uint8_t* const dict, const int pos); - static int skipChildrenPosition(const uint8_t flags, const int pos); - static int skipFrequency(const uint8_t flags, const int pos); - static int skipAllAttributes(const uint8_t* const dict, const uint8_t flags, const int pos); - static int skipChildrenPosAndAttributes(const uint8_t* const dict, const uint8_t flags, - const int pos); - static int readChildrenPosition(const uint8_t* const dict, const uint8_t flags, const int pos); - static bool hasChildrenInFlags(const uint8_t flags); - static int getAttributeAddressAndForwardPointer(const uint8_t* const dict, const uint8_t flags, - int *pos); - static int getTerminalPosition(const uint8_t* const root, const uint16_t* const inWord, - const int length); - static int getWordAtAddress(const uint8_t* const root, const int address, const int maxDepth, - uint16_t* outWord); -}; - -inline int BinaryFormat::detectFormat(const uint8_t* const dict) { - // The magic number is stored big-endian. - const uint32_t magicNumber = (dict[0] << 24) + (dict[1] << 16) + (dict[2] << 8) + dict[3]; - switch (magicNumber) { - case FORMAT_VERSION_1_MAGIC_NUMBER: - // Format 1 header is exactly 5 bytes long and looks like: - // Magic number (2 bytes) 0x78 0xB1 - // Version number (1 byte) 0x01 - // Options (2 bytes) must be 0x00 0x00 - return 1; - case FORMAT_VERSION_2_MAGIC_NUMBER: - // Format 2 header is as follows: - // Magic number (4 bytes) 0x9B 0xC1 0x3A 0xFE - // Version number (2 bytes) 0x00 0x02 - // Options (2 bytes) must be 0x00 0x00 - // Header size (4 bytes) : integer, big endian - return (dict[4] << 8) + dict[5]; - default: - return UNKNOWN_FORMAT; - } -} - -inline unsigned int BinaryFormat::getHeaderSize(const uint8_t* const dict) { - switch (detectFormat(dict)) { - case 1: - return FORMAT_VERSION_1_HEADER_SIZE; - case 2: - // See the format of the header in the comment in detectFormat() above - return (dict[8] << 24) + (dict[9] << 16) + (dict[10] << 8) + dict[11]; - default: - return std::numeric_limits<unsigned int>::max(); - } -} - -inline int BinaryFormat::getGroupCountAndForwardPointer(const uint8_t* const dict, int* pos) { - const int msb = dict[(*pos)++]; - if (msb < 0x80) return msb; - return ((msb & 0x7F) << 8) | dict[(*pos)++]; -} - -inline uint8_t BinaryFormat::getFlagsAndForwardPointer(const uint8_t* const dict, int* pos) { - return dict[(*pos)++]; -} - -inline int32_t BinaryFormat::getCharCodeAndForwardPointer(const uint8_t* const dict, int* pos) { - const int origin = *pos; - const int32_t character = dict[origin]; - if (character < MINIMAL_ONE_BYTE_CHARACTER_VALUE) { - if (character == CHARACTER_ARRAY_TERMINATOR) { - *pos = origin + 1; - return NOT_A_CHARACTER; - } else { - *pos = origin + 3; - const int32_t char_1 = character << 16; - const int32_t char_2 = char_1 + (dict[origin + 1] << 8); - return char_2 + dict[origin + 2]; - } - } else { - *pos = origin + 1; - return character; - } -} - -inline int BinaryFormat::readFrequencyWithoutMovingPointer(const uint8_t* const dict, - const int pos) { - return dict[pos]; -} - -inline int BinaryFormat::skipOtherCharacters(const uint8_t* const dict, const int pos) { - int currentPos = pos; - int32_t character = dict[currentPos++]; - while (CHARACTER_ARRAY_TERMINATOR != character) { - if (character < MINIMAL_ONE_BYTE_CHARACTER_VALUE) { - currentPos += MULTIPLE_BYTE_CHARACTER_ADDITIONAL_SIZE; - } - character = dict[currentPos++]; - } - return currentPos; -} - -static inline int attributeAddressSize(const uint8_t flags) { - static const int ATTRIBUTE_ADDRESS_SHIFT = 4; - return (flags & UnigramDictionary::MASK_ATTRIBUTE_ADDRESS_TYPE) >> ATTRIBUTE_ADDRESS_SHIFT; - /* Note: this is a value-dependant optimization of what may probably be - more readably written this way: - switch (flags * UnigramDictionary::MASK_ATTRIBUTE_ADDRESS_TYPE) { - case UnigramDictionary::FLAG_ATTRIBUTE_ADDRESS_TYPE_ONEBYTE: return 1; - case UnigramDictionary::FLAG_ATTRIBUTE_ADDRESS_TYPE_TWOBYTES: return 2; - case UnigramDictionary::FLAG_ATTRIBUTE_ADDRESS_TYPE_THREEBYTE: return 3; - default: return 0; - } - */ -} - -inline int BinaryFormat::skipAttributes(const uint8_t* const dict, const int pos) { - int currentPos = pos; - uint8_t flags = getFlagsAndForwardPointer(dict, ¤tPos); - while (flags & UnigramDictionary::FLAG_ATTRIBUTE_HAS_NEXT) { - currentPos += attributeAddressSize(flags); - flags = getFlagsAndForwardPointer(dict, ¤tPos); - } - currentPos += attributeAddressSize(flags); - return currentPos; -} - -static inline int childrenAddressSize(const uint8_t flags) { - static const int CHILDREN_ADDRESS_SHIFT = 6; - return (UnigramDictionary::MASK_GROUP_ADDRESS_TYPE & flags) >> CHILDREN_ADDRESS_SHIFT; - /* See the note in attributeAddressSize. The same applies here */ -} - -inline int BinaryFormat::skipChildrenPosition(const uint8_t flags, const int pos) { - return pos + childrenAddressSize(flags); -} - -inline int BinaryFormat::skipFrequency(const uint8_t flags, const int pos) { - return UnigramDictionary::FLAG_IS_TERMINAL & flags ? pos + 1 : pos; -} - -inline int BinaryFormat::skipAllAttributes(const uint8_t* const dict, const uint8_t flags, - const int pos) { - // This function skips all attributes: shortcuts and bigrams. - int newPos = pos; - if (UnigramDictionary::FLAG_HAS_SHORTCUT_TARGETS & flags) { - newPos = skipAttributes(dict, newPos); - } - if (UnigramDictionary::FLAG_HAS_BIGRAMS & flags) { - newPos = skipAttributes(dict, newPos); - } - return newPos; -} - -inline int BinaryFormat::skipChildrenPosAndAttributes(const uint8_t* const dict, - const uint8_t flags, const int pos) { - int currentPos = pos; - currentPos = skipChildrenPosition(flags, currentPos); - currentPos = skipAllAttributes(dict, flags, currentPos); - return currentPos; -} - -inline int BinaryFormat::readChildrenPosition(const uint8_t* const dict, const uint8_t flags, - const int pos) { - int offset = 0; - switch (UnigramDictionary::MASK_GROUP_ADDRESS_TYPE & flags) { - case UnigramDictionary::FLAG_GROUP_ADDRESS_TYPE_ONEBYTE: - offset = dict[pos]; - break; - case UnigramDictionary::FLAG_GROUP_ADDRESS_TYPE_TWOBYTES: - offset = dict[pos] << 8; - offset += dict[pos + 1]; - break; - case UnigramDictionary::FLAG_GROUP_ADDRESS_TYPE_THREEBYTES: - offset = dict[pos] << 16; - offset += dict[pos + 1] << 8; - offset += dict[pos + 2]; - break; - default: - // If we come here, it means we asked for the children of a word with - // no children. - return -1; - } - return pos + offset; -} - -inline bool BinaryFormat::hasChildrenInFlags(const uint8_t flags) { - return (UnigramDictionary::FLAG_GROUP_ADDRESS_TYPE_NOADDRESS - != (UnigramDictionary::MASK_GROUP_ADDRESS_TYPE & flags)); -} - -inline int BinaryFormat::getAttributeAddressAndForwardPointer(const uint8_t* const dict, - const uint8_t flags, int *pos) { - int offset = 0; - const int origin = *pos; - switch (UnigramDictionary::MASK_ATTRIBUTE_ADDRESS_TYPE & flags) { - case UnigramDictionary::FLAG_ATTRIBUTE_ADDRESS_TYPE_ONEBYTE: - offset = dict[origin]; - *pos = origin + 1; - break; - case UnigramDictionary::FLAG_ATTRIBUTE_ADDRESS_TYPE_TWOBYTES: - offset = dict[origin] << 8; - offset += dict[origin + 1]; - *pos = origin + 2; - break; - case UnigramDictionary::FLAG_ATTRIBUTE_ADDRESS_TYPE_THREEBYTES: - offset = dict[origin] << 16; - offset += dict[origin + 1] << 8; - offset += dict[origin + 2]; - *pos = origin + 3; - break; - } - if (UnigramDictionary::FLAG_ATTRIBUTE_OFFSET_NEGATIVE & flags) { - return origin - offset; - } else { - return origin + offset; - } -} - -// This function gets the byte position of the last chargroup of the exact matching word in the -// dictionary. If no match is found, it returns NOT_VALID_WORD. -inline int BinaryFormat::getTerminalPosition(const uint8_t* const root, - const uint16_t* const inWord, const int length) { - int pos = 0; - int wordPos = 0; - - while (true) { - // If we already traversed the tree further than the word is long, there means - // there was no match (or we would have found it). - if (wordPos > length) return NOT_VALID_WORD; - int charGroupCount = BinaryFormat::getGroupCountAndForwardPointer(root, &pos); - const uint16_t wChar = inWord[wordPos]; - while (true) { - // If there are no more character groups in this node, it means we could not - // find a matching character for this depth, therefore there is no match. - if (0 >= charGroupCount) return NOT_VALID_WORD; - const int charGroupPos = pos; - const uint8_t flags = BinaryFormat::getFlagsAndForwardPointer(root, &pos); - int32_t character = BinaryFormat::getCharCodeAndForwardPointer(root, &pos); - if (character == wChar) { - // This is the correct node. Only one character group may start with the same - // char within a node, so either we found our match in this node, or there is - // no match and we can return NOT_VALID_WORD. So we will check all the characters - // in this character group indeed does match. - if (UnigramDictionary::FLAG_HAS_MULTIPLE_CHARS & flags) { - character = BinaryFormat::getCharCodeAndForwardPointer(root, &pos); - while (NOT_A_CHARACTER != character) { - ++wordPos; - // If we shoot the length of the word we search for, or if we find a single - // character that does not match, as explained above, it means the word is - // not in the dictionary (by virtue of this chargroup being the only one to - // match the word on the first character, but not matching the whole word). - if (wordPos > length) return NOT_VALID_WORD; - if (inWord[wordPos] != character) return NOT_VALID_WORD; - character = BinaryFormat::getCharCodeAndForwardPointer(root, &pos); - } - } - // If we come here we know that so far, we do match. Either we are on a terminal - // and we match the length, in which case we found it, or we traverse children. - // If we don't match the length AND don't have children, then a word in the - // dictionary fully matches a prefix of the searched word but not the full word. - ++wordPos; - if (UnigramDictionary::FLAG_IS_TERMINAL & flags) { - if (wordPos == length) { - return charGroupPos; - } - pos = BinaryFormat::skipFrequency(UnigramDictionary::FLAG_IS_TERMINAL, pos); - } - if (UnigramDictionary::FLAG_GROUP_ADDRESS_TYPE_NOADDRESS - == (UnigramDictionary::MASK_GROUP_ADDRESS_TYPE & flags)) { - return NOT_VALID_WORD; - } - // We have children and we are still shorter than the word we are searching for, so - // we need to traverse children. Put the pointer on the children position, and - // break - pos = BinaryFormat::readChildrenPosition(root, flags, pos); - break; - } else { - // This chargroup does not match, so skip the remaining part and go to the next. - if (UnigramDictionary::FLAG_HAS_MULTIPLE_CHARS & flags) { - pos = BinaryFormat::skipOtherCharacters(root, pos); - } - pos = BinaryFormat::skipFrequency(flags, pos); - pos = BinaryFormat::skipChildrenPosAndAttributes(root, flags, pos); - } - --charGroupCount; - } - } -} - -// This function searches for a terminal in the dictionary by its address. -// Due to the fact that words are ordered in the dictionary in a strict breadth-first order, -// it is possible to check for this with advantageous complexity. For each node, we search -// for groups with children and compare the children address with the address we look for. -// When we shoot the address we look for, it means the word we look for is in the children -// of the previous group. The only tricky part is the fact that if we arrive at the end of a -// node with the last group's children address still less than what we are searching for, we -// must descend the last group's children (for example, if the word we are searching for starts -// with a z, it's the last group of the root node, so all children addresses will be smaller -// than the address we look for, and we have to descend the z node). -/* Parameters : - * root: the dictionary buffer - * address: the byte position of the last chargroup of the word we are searching for (this is - * what is stored as the "bigram address" in each bigram) - * outword: an array to write the found word, with MAX_WORD_LENGTH size. - * Return value : the length of the word, of 0 if the word was not found. - */ -inline int BinaryFormat::getWordAtAddress(const uint8_t* const root, const int address, - const int maxDepth, uint16_t* outWord) { - int pos = 0; - int wordPos = 0; - - // One iteration of the outer loop iterates through nodes. As stated above, we will only - // traverse nodes that are actually a part of the terminal we are searching, so each time - // we enter this loop we are one depth level further than last time. - // The only reason we count nodes is because we want to reduce the probability of infinite - // looping in case there is a bug. Since we know there is an upper bound to the depth we are - // supposed to traverse, it does not hurt to count iterations. - for (int loopCount = maxDepth; loopCount > 0; --loopCount) { - int lastCandidateGroupPos = 0; - // Let's loop through char groups in this node searching for either the terminal - // or one of its ascendants. - for (int charGroupCount = getGroupCountAndForwardPointer(root, &pos); charGroupCount > 0; - --charGroupCount) { - const int startPos = pos; - const uint8_t flags = getFlagsAndForwardPointer(root, &pos); - const int32_t character = getCharCodeAndForwardPointer(root, &pos); - if (address == startPos) { - // We found the address. Copy the rest of the word in the buffer and return - // the length. - outWord[wordPos] = character; - if (UnigramDictionary::FLAG_HAS_MULTIPLE_CHARS & flags) { - int32_t nextChar = getCharCodeAndForwardPointer(root, &pos); - // We count chars in order to avoid infinite loops if the file is broken or - // if there is some other bug - int charCount = maxDepth; - while (-1 != nextChar && --charCount > 0) { - outWord[++wordPos] = nextChar; - nextChar = getCharCodeAndForwardPointer(root, &pos); - } - } - return ++wordPos; - } - // We need to skip past this char group, so skip any remaining chars after the - // first and possibly the frequency. - if (UnigramDictionary::FLAG_HAS_MULTIPLE_CHARS & flags) { - pos = skipOtherCharacters(root, pos); - } - pos = skipFrequency(flags, pos); - - // The fact that this group has children is very important. Since we already know - // that this group does not match, if it has no children we know it is irrelevant - // to what we are searching for. - const bool hasChildren = (UnigramDictionary::FLAG_GROUP_ADDRESS_TYPE_NOADDRESS != - (UnigramDictionary::MASK_GROUP_ADDRESS_TYPE & flags)); - // We will write in `found' whether we have passed the children address we are - // searching for. For example if we search for "beer", the children of b are less - // than the address we are searching for and the children of c are greater. When we - // come here for c, we realize this is too big, and that we should descend b. - bool found; - if (hasChildren) { - // Here comes the tricky part. First, read the children position. - const int childrenPos = readChildrenPosition(root, flags, pos); - if (childrenPos > address) { - // If the children pos is greater than address, it means the previous chargroup, - // which address is stored in lastCandidateGroupPos, was the right one. - found = true; - } else if (1 >= charGroupCount) { - // However if we are on the LAST group of this node, and we have NOT shot the - // address we should descend THIS node. So we trick the lastCandidateGroupPos - // so that we will descend this node, not the previous one. - lastCandidateGroupPos = startPos; - found = true; - } else { - // Else, we should continue looking. - found = false; - } - } else { - // Even if we don't have children here, we could still be on the last group of this - // node. If this is the case, we should descend the last group that had children, - // and their address is already in lastCandidateGroup. - found = (1 >= charGroupCount); - } - - if (found) { - // Okay, we found the group we should descend. Its address is in - // the lastCandidateGroupPos variable, so we just re-read it. - if (0 != lastCandidateGroupPos) { - const uint8_t lastFlags = - getFlagsAndForwardPointer(root, &lastCandidateGroupPos); - const int32_t lastChar = - getCharCodeAndForwardPointer(root, &lastCandidateGroupPos); - // We copy all the characters in this group to the buffer - outWord[wordPos] = lastChar; - if (UnigramDictionary::FLAG_HAS_MULTIPLE_CHARS & lastFlags) { - int32_t nextChar = - getCharCodeAndForwardPointer(root, &lastCandidateGroupPos); - int charCount = maxDepth; - while (-1 != nextChar && --charCount > 0) { - outWord[++wordPos] = nextChar; - nextChar = getCharCodeAndForwardPointer(root, &lastCandidateGroupPos); - } - } - ++wordPos; - // Now we only need to branch to the children address. Skip the frequency if - // it's there, read pos, and break to resume the search at pos. - lastCandidateGroupPos = skipFrequency(lastFlags, lastCandidateGroupPos); - pos = readChildrenPosition(root, lastFlags, lastCandidateGroupPos); - break; - } else { - // Here is a little tricky part: we come here if we found out that all children - // addresses in this group are bigger than the address we are searching for. - // Should we conclude the word is not in the dictionary? No! It could still be - // one of the remaining chargroups in this node, so we have to keep looking in - // this node until we find it (or we realize it's not there either, in which - // case it's actually not in the dictionary). Pass the end of this group, ready - // to start the next one. - pos = skipChildrenPosAndAttributes(root, flags, pos); - } - } else { - // If we did not find it, we should record the last children address for the next - // iteration. - if (hasChildren) lastCandidateGroupPos = startPos; - // Now skip the end of this group (children pos and the attributes if any) so that - // our pos is after the end of this char group, at the start of the next one. - pos = skipChildrenPosAndAttributes(root, flags, pos); - } - - } - } - // If we have looked through all the chargroups and found no match, the address is - // not the address of a terminal in this dictionary. - return 0; -} - -} // namespace latinime - -#endif // LATINIME_BINARY_FORMAT_H diff --git a/native/src/char_utils.cpp b/native/src/char_utils.cpp deleted file mode 100644 index a31a0632c..000000000 --- a/native/src/char_utils.cpp +++ /dev/null @@ -1,899 +0,0 @@ -/* - * Copyright (C) 2010 The Android Open Source Project - * - * Licensed under the Apache License, Version 2.0 (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.apache.org/licenses/LICENSE-2.0 - * - * Unless required by applicable law or agreed to in writing, software - * distributed under the License is distributed on an "AS IS" BASIS, - * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. - * See the License for the specific language governing permissions and - * limitations under the License. - */ - -#include <stdlib.h> - -namespace latinime { - -struct LatinCapitalSmallPair { - unsigned short capital; - unsigned short small; -}; - -// Generated from http://unicode.org/Public/UNIDATA/UnicodeData.txt -// -// 1. Run the following code. Bascially taken from -// Dictionary::toLowerCase(unsigned short c) in dictionary.cpp. -// Then, get the list of chars where cc != ccc. -// -// unsigned short c, cc, ccc, ccc2; -// for (c = 0; c < 0xFFFF ; c++) { -// if (c < sizeof(BASE_CHARS) / sizeof(BASE_CHARS[0])) { -// cc = BASE_CHARS[c]; -// } else { -// cc = c; -// } -// -// // tolower -// int isBase = 0; -// if (cc >='A' && cc <= 'Z') { -// ccc = (cc | 0x20); -// ccc2 = ccc; -// isBase = 1; -// } else if (cc > 0x7F) { -// ccc = u_tolower(cc); -// ccc2 = latin_tolower(cc); -// } else { -// ccc = cc; -// ccc2 = ccc; -// } -// if (!isBase && cc != ccc) { -// wprintf(L" 0x%04X => 0x%04X => 0x%04X %lc => %lc => %lc \n", -// c, cc, ccc, c, cc, ccc); -// //assert(ccc == ccc2); -// } -// } -// -// Initially, started with an empty latin_tolower() as below. -// -// unsigned short latin_tolower(unsigned short c) { -// return c; -// } -// -// -// 2. Process the list obtained by 1 by the following perl script and apply -// 'sort -u' as well. Get the SORTED_CHAR_MAP[]. -// Note that '$1' in the perl script is 'cc' in the above C code. -// -// while(<>) { -// / 0x\w* => 0x(\w*) =/; -// open(HDL, "grep -iw ^" . $1 . " UnicodeData.txt | "); -// $line = <HDL>; -// chomp $line; -// @cols = split(/;/, $line); -// print " { 0x$1, 0x$cols[13] }, // $cols[1]\n"; -// } -// -// -// 3. Update the latin_tolower() function above with SORTED_CHAR_MAP. Enable -// the assert(ccc == ccc2) above and confirm the function exits successfully. -// -static const struct LatinCapitalSmallPair SORTED_CHAR_MAP[] = { - { 0x00C4, 0x00E4 }, // LATIN CAPITAL LETTER A WITH DIAERESIS - { 0x00C5, 0x00E5 }, // LATIN CAPITAL LETTER A WITH RING ABOVE - { 0x00C6, 0x00E6 }, // LATIN CAPITAL LETTER AE - { 0x00D0, 0x00F0 }, // LATIN CAPITAL LETTER ETH - { 0x00D5, 0x00F5 }, // LATIN CAPITAL LETTER O WITH TILDE - { 0x00D6, 0x00F6 }, // LATIN CAPITAL LETTER O WITH DIAERESIS - { 0x00D8, 0x00F8 }, // LATIN CAPITAL LETTER O WITH STROKE - { 0x00DC, 0x00FC }, // LATIN CAPITAL LETTER U WITH DIAERESIS - { 0x00DE, 0x00FE }, // LATIN CAPITAL LETTER THORN - { 0x0110, 0x0111 }, // LATIN CAPITAL LETTER D WITH STROKE - { 0x0126, 0x0127 }, // LATIN CAPITAL LETTER H WITH STROKE - { 0x0141, 0x0142 }, // LATIN CAPITAL LETTER L WITH STROKE - { 0x014A, 0x014B }, // LATIN CAPITAL LETTER ENG - { 0x0152, 0x0153 }, // LATIN CAPITAL LIGATURE OE - { 0x0166, 0x0167 }, // LATIN CAPITAL LETTER T WITH STROKE - { 0x0181, 0x0253 }, // LATIN CAPITAL LETTER B WITH HOOK - { 0x0182, 0x0183 }, // LATIN CAPITAL LETTER B WITH TOPBAR - { 0x0184, 0x0185 }, // LATIN CAPITAL LETTER TONE SIX - { 0x0186, 0x0254 }, // LATIN CAPITAL LETTER OPEN O - { 0x0187, 0x0188 }, // LATIN CAPITAL LETTER C WITH HOOK - { 0x0189, 0x0256 }, // LATIN CAPITAL LETTER AFRICAN D - { 0x018A, 0x0257 }, // LATIN CAPITAL LETTER D WITH HOOK - { 0x018B, 0x018C }, // LATIN CAPITAL LETTER D WITH TOPBAR - { 0x018E, 0x01DD }, // LATIN CAPITAL LETTER REVERSED E - { 0x018F, 0x0259 }, // LATIN CAPITAL LETTER SCHWA - { 0x0190, 0x025B }, // LATIN CAPITAL LETTER OPEN E - { 0x0191, 0x0192 }, // LATIN CAPITAL LETTER F WITH HOOK - { 0x0193, 0x0260 }, // LATIN CAPITAL LETTER G WITH HOOK - { 0x0194, 0x0263 }, // LATIN CAPITAL LETTER GAMMA - { 0x0196, 0x0269 }, // LATIN CAPITAL LETTER IOTA - { 0x0197, 0x0268 }, // LATIN CAPITAL LETTER I WITH STROKE - { 0x0198, 0x0199 }, // LATIN CAPITAL LETTER K WITH HOOK - { 0x019C, 0x026F }, // LATIN CAPITAL LETTER TURNED M - { 0x019D, 0x0272 }, // LATIN CAPITAL LETTER N WITH LEFT HOOK - { 0x019F, 0x0275 }, // LATIN CAPITAL LETTER O WITH MIDDLE TILDE - { 0x01A2, 0x01A3 }, // LATIN CAPITAL LETTER OI - { 0x01A4, 0x01A5 }, // LATIN CAPITAL LETTER P WITH HOOK - { 0x01A6, 0x0280 }, // LATIN LETTER YR - { 0x01A7, 0x01A8 }, // LATIN CAPITAL LETTER TONE TWO - { 0x01A9, 0x0283 }, // LATIN CAPITAL LETTER ESH - { 0x01AC, 0x01AD }, // LATIN CAPITAL LETTER T WITH HOOK - { 0x01AE, 0x0288 }, // LATIN CAPITAL LETTER T WITH RETROFLEX HOOK - { 0x01B1, 0x028A }, // LATIN CAPITAL LETTER UPSILON - { 0x01B2, 0x028B }, // LATIN CAPITAL LETTER V WITH HOOK - { 0x01B3, 0x01B4 }, // LATIN CAPITAL LETTER Y WITH HOOK - { 0x01B5, 0x01B6 }, // LATIN CAPITAL LETTER Z WITH STROKE - { 0x01B7, 0x0292 }, // LATIN CAPITAL LETTER EZH - { 0x01B8, 0x01B9 }, // LATIN CAPITAL LETTER EZH REVERSED - { 0x01BC, 0x01BD }, // LATIN CAPITAL LETTER TONE FIVE - { 0x01E4, 0x01E5 }, // LATIN CAPITAL LETTER G WITH STROKE - { 0x01EA, 0x01EB }, // LATIN CAPITAL LETTER O WITH OGONEK - { 0x01F6, 0x0195 }, // LATIN CAPITAL LETTER HWAIR - { 0x01F7, 0x01BF }, // LATIN CAPITAL LETTER WYNN - { 0x021C, 0x021D }, // LATIN CAPITAL LETTER YOGH - { 0x0220, 0x019E }, // LATIN CAPITAL LETTER N WITH LONG RIGHT LEG - { 0x0222, 0x0223 }, // LATIN CAPITAL LETTER OU - { 0x0224, 0x0225 }, // LATIN CAPITAL LETTER Z WITH HOOK - { 0x0226, 0x0227 }, // LATIN CAPITAL LETTER A WITH DOT ABOVE - { 0x022E, 0x022F }, // LATIN CAPITAL LETTER O WITH DOT ABOVE - { 0x023A, 0x2C65 }, // LATIN CAPITAL LETTER A WITH STROKE - { 0x023B, 0x023C }, // LATIN CAPITAL LETTER C WITH STROKE - { 0x023D, 0x019A }, // LATIN CAPITAL LETTER L WITH BAR - { 0x023E, 0x2C66 }, // LATIN CAPITAL LETTER T WITH DIAGONAL STROKE - { 0x0241, 0x0242 }, // LATIN CAPITAL LETTER GLOTTAL STOP - { 0x0243, 0x0180 }, // LATIN CAPITAL LETTER B WITH STROKE - { 0x0244, 0x0289 }, // LATIN CAPITAL LETTER U BAR - { 0x0245, 0x028C }, // LATIN CAPITAL LETTER TURNED V - { 0x0246, 0x0247 }, // LATIN CAPITAL LETTER E WITH STROKE - { 0x0248, 0x0249 }, // LATIN CAPITAL LETTER J WITH STROKE - { 0x024A, 0x024B }, // LATIN CAPITAL LETTER SMALL Q WITH HOOK TAIL - { 0x024C, 0x024D }, // LATIN CAPITAL LETTER R WITH STROKE - { 0x024E, 0x024F }, // LATIN CAPITAL LETTER Y WITH STROKE - { 0x0370, 0x0371 }, // GREEK CAPITAL LETTER HETA - { 0x0372, 0x0373 }, // GREEK CAPITAL LETTER ARCHAIC SAMPI - { 0x0376, 0x0377 }, // GREEK CAPITAL LETTER PAMPHYLIAN DIGAMMA - { 0x0391, 0x03B1 }, // GREEK CAPITAL LETTER ALPHA - { 0x0392, 0x03B2 }, // GREEK CAPITAL LETTER BETA - { 0x0393, 0x03B3 }, // GREEK CAPITAL LETTER GAMMA - { 0x0394, 0x03B4 }, // GREEK CAPITAL LETTER DELTA - { 0x0395, 0x03B5 }, // GREEK CAPITAL LETTER EPSILON - { 0x0396, 0x03B6 }, // GREEK CAPITAL LETTER ZETA - { 0x0397, 0x03B7 }, // GREEK CAPITAL LETTER ETA - { 0x0398, 0x03B8 }, // GREEK CAPITAL LETTER THETA - { 0x0399, 0x03B9 }, // GREEK CAPITAL LETTER IOTA - { 0x039A, 0x03BA }, // GREEK CAPITAL LETTER KAPPA - { 0x039B, 0x03BB }, // GREEK CAPITAL LETTER LAMDA - { 0x039C, 0x03BC }, // GREEK CAPITAL LETTER MU - { 0x039D, 0x03BD }, // GREEK CAPITAL LETTER NU - { 0x039E, 0x03BE }, // GREEK CAPITAL LETTER XI - { 0x039F, 0x03BF }, // GREEK CAPITAL LETTER OMICRON - { 0x03A0, 0x03C0 }, // GREEK CAPITAL LETTER PI - { 0x03A1, 0x03C1 }, // GREEK CAPITAL LETTER RHO - { 0x03A3, 0x03C3 }, // GREEK CAPITAL LETTER SIGMA - { 0x03A4, 0x03C4 }, // GREEK CAPITAL LETTER TAU - { 0x03A5, 0x03C5 }, // GREEK CAPITAL LETTER UPSILON - { 0x03A6, 0x03C6 }, // GREEK CAPITAL LETTER PHI - { 0x03A7, 0x03C7 }, // GREEK CAPITAL LETTER CHI - { 0x03A8, 0x03C8 }, // GREEK CAPITAL LETTER PSI - { 0x03A9, 0x03C9 }, // GREEK CAPITAL LETTER OMEGA - { 0x03CF, 0x03D7 }, // GREEK CAPITAL KAI SYMBOL - { 0x03D8, 0x03D9 }, // GREEK LETTER ARCHAIC KOPPA - { 0x03DA, 0x03DB }, // GREEK LETTER STIGMA - { 0x03DC, 0x03DD }, // GREEK LETTER DIGAMMA - { 0x03DE, 0x03DF }, // GREEK LETTER KOPPA - { 0x03E0, 0x03E1 }, // GREEK LETTER SAMPI - { 0x03E2, 0x03E3 }, // COPTIC CAPITAL LETTER SHEI - { 0x03E4, 0x03E5 }, // COPTIC CAPITAL LETTER FEI - { 0x03E6, 0x03E7 }, // COPTIC CAPITAL LETTER KHEI - { 0x03E8, 0x03E9 }, // COPTIC CAPITAL LETTER HORI - { 0x03EA, 0x03EB }, // COPTIC CAPITAL LETTER GANGIA - { 0x03EC, 0x03ED }, // COPTIC CAPITAL LETTER SHIMA - { 0x03EE, 0x03EF }, // COPTIC CAPITAL LETTER DEI - { 0x03F7, 0x03F8 }, // GREEK CAPITAL LETTER SHO - { 0x03FA, 0x03FB }, // GREEK CAPITAL LETTER SAN - { 0x03FD, 0x037B }, // GREEK CAPITAL REVERSED LUNATE SIGMA SYMBOL - { 0x03FE, 0x037C }, // GREEK CAPITAL DOTTED LUNATE SIGMA SYMBOL - { 0x03FF, 0x037D }, // GREEK CAPITAL REVERSED DOTTED LUNATE SIGMA SYMBOL - { 0x0402, 0x0452 }, // CYRILLIC CAPITAL LETTER DJE - { 0x0404, 0x0454 }, // CYRILLIC CAPITAL LETTER UKRAINIAN IE - { 0x0405, 0x0455 }, // CYRILLIC CAPITAL LETTER DZE - { 0x0406, 0x0456 }, // CYRILLIC CAPITAL LETTER BYELORUSSIAN-UKRAINIAN I - { 0x0408, 0x0458 }, // CYRILLIC CAPITAL LETTER JE - { 0x0409, 0x0459 }, // CYRILLIC CAPITAL LETTER LJE - { 0x040A, 0x045A }, // CYRILLIC CAPITAL LETTER NJE - { 0x040B, 0x045B }, // CYRILLIC CAPITAL LETTER TSHE - { 0x040F, 0x045F }, // CYRILLIC CAPITAL LETTER DZHE - { 0x0410, 0x0430 }, // CYRILLIC CAPITAL LETTER A - { 0x0411, 0x0431 }, // CYRILLIC CAPITAL LETTER BE - { 0x0412, 0x0432 }, // CYRILLIC CAPITAL LETTER VE - { 0x0413, 0x0433 }, // CYRILLIC CAPITAL LETTER GHE - { 0x0414, 0x0434 }, // CYRILLIC CAPITAL LETTER DE - { 0x0415, 0x0435 }, // CYRILLIC CAPITAL LETTER IE - { 0x0416, 0x0436 }, // CYRILLIC CAPITAL LETTER ZHE - { 0x0417, 0x0437 }, // CYRILLIC CAPITAL LETTER ZE - { 0x0418, 0x0438 }, // CYRILLIC CAPITAL LETTER I - { 0x041A, 0x043A }, // CYRILLIC CAPITAL LETTER KA - { 0x041B, 0x043B }, // CYRILLIC CAPITAL LETTER EL - { 0x041C, 0x043C }, // CYRILLIC CAPITAL LETTER EM - { 0x041D, 0x043D }, // CYRILLIC CAPITAL LETTER EN - { 0x041E, 0x043E }, // CYRILLIC CAPITAL LETTER O - { 0x041F, 0x043F }, // CYRILLIC CAPITAL LETTER PE - { 0x0420, 0x0440 }, // CYRILLIC CAPITAL LETTER ER - { 0x0421, 0x0441 }, // CYRILLIC CAPITAL LETTER ES - { 0x0422, 0x0442 }, // CYRILLIC CAPITAL LETTER TE - { 0x0423, 0x0443 }, // CYRILLIC CAPITAL LETTER U - { 0x0424, 0x0444 }, // CYRILLIC CAPITAL LETTER EF - { 0x0425, 0x0445 }, // CYRILLIC CAPITAL LETTER HA - { 0x0426, 0x0446 }, // CYRILLIC CAPITAL LETTER TSE - { 0x0427, 0x0447 }, // CYRILLIC CAPITAL LETTER CHE - { 0x0428, 0x0448 }, // CYRILLIC CAPITAL LETTER SHA - { 0x0429, 0x0449 }, // CYRILLIC CAPITAL LETTER SHCHA - { 0x042A, 0x044A }, // CYRILLIC CAPITAL LETTER HARD SIGN - { 0x042B, 0x044B }, // CYRILLIC CAPITAL LETTER YERU - { 0x042C, 0x044C }, // CYRILLIC CAPITAL LETTER SOFT SIGN - { 0x042D, 0x044D }, // CYRILLIC CAPITAL LETTER E - { 0x042E, 0x044E }, // CYRILLIC CAPITAL LETTER YU - { 0x042F, 0x044F }, // CYRILLIC CAPITAL LETTER YA - { 0x0460, 0x0461 }, // CYRILLIC CAPITAL LETTER OMEGA - { 0x0462, 0x0463 }, // CYRILLIC CAPITAL LETTER YAT - { 0x0464, 0x0465 }, // CYRILLIC CAPITAL LETTER IOTIFIED E - { 0x0466, 0x0467 }, // CYRILLIC CAPITAL LETTER LITTLE YUS - { 0x0468, 0x0469 }, // CYRILLIC CAPITAL LETTER IOTIFIED LITTLE YUS - { 0x046A, 0x046B }, // CYRILLIC CAPITAL LETTER BIG YUS - { 0x046C, 0x046D }, // CYRILLIC CAPITAL LETTER IOTIFIED BIG YUS - { 0x046E, 0x046F }, // CYRILLIC CAPITAL LETTER KSI - { 0x0470, 0x0471 }, // CYRILLIC CAPITAL LETTER PSI - { 0x0472, 0x0473 }, // CYRILLIC CAPITAL LETTER FITA - { 0x0474, 0x0475 }, // CYRILLIC CAPITAL LETTER IZHITSA - { 0x0478, 0x0479 }, // CYRILLIC CAPITAL LETTER UK - { 0x047A, 0x047B }, // CYRILLIC CAPITAL LETTER ROUND OMEGA - { 0x047C, 0x047D }, // CYRILLIC CAPITAL LETTER OMEGA WITH TITLO - { 0x047E, 0x047F }, // CYRILLIC CAPITAL LETTER OT - { 0x0480, 0x0481 }, // CYRILLIC CAPITAL LETTER KOPPA - { 0x048A, 0x048B }, // CYRILLIC CAPITAL LETTER SHORT I WITH TAIL - { 0x048C, 0x048D }, // CYRILLIC CAPITAL LETTER SEMISOFT SIGN - { 0x048E, 0x048F }, // CYRILLIC CAPITAL LETTER ER WITH TICK - { 0x0490, 0x0491 }, // CYRILLIC CAPITAL LETTER GHE WITH UPTURN - { 0x0492, 0x0493 }, // CYRILLIC CAPITAL LETTER GHE WITH STROKE - { 0x0494, 0x0495 }, // CYRILLIC CAPITAL LETTER GHE WITH MIDDLE HOOK - { 0x0496, 0x0497 }, // CYRILLIC CAPITAL LETTER ZHE WITH DESCENDER - { 0x0498, 0x0499 }, // CYRILLIC CAPITAL LETTER ZE WITH DESCENDER - { 0x049A, 0x049B }, // CYRILLIC CAPITAL LETTER KA WITH DESCENDER - { 0x049C, 0x049D }, // CYRILLIC CAPITAL LETTER KA WITH VERTICAL STROKE - { 0x049E, 0x049F }, // CYRILLIC CAPITAL LETTER KA WITH STROKE - { 0x04A0, 0x04A1 }, // CYRILLIC CAPITAL LETTER BASHKIR KA - { 0x04A2, 0x04A3 }, // CYRILLIC CAPITAL LETTER EN WITH DESCENDER - { 0x04A4, 0x04A5 }, // CYRILLIC CAPITAL LIGATURE EN GHE - { 0x04A6, 0x04A7 }, // CYRILLIC CAPITAL LETTER PE WITH MIDDLE HOOK - { 0x04A8, 0x04A9 }, // CYRILLIC CAPITAL LETTER ABKHASIAN HA - { 0x04AA, 0x04AB }, // CYRILLIC CAPITAL LETTER ES WITH DESCENDER - { 0x04AC, 0x04AD }, // CYRILLIC CAPITAL LETTER TE WITH DESCENDER - { 0x04AE, 0x04AF }, // CYRILLIC CAPITAL LETTER STRAIGHT U - { 0x04B0, 0x04B1 }, // CYRILLIC CAPITAL LETTER STRAIGHT U WITH STROKE - { 0x04B2, 0x04B3 }, // CYRILLIC CAPITAL LETTER HA WITH DESCENDER - { 0x04B4, 0x04B5 }, // CYRILLIC CAPITAL LIGATURE TE TSE - { 0x04B6, 0x04B7 }, // CYRILLIC CAPITAL LETTER CHE WITH DESCENDER - { 0x04B8, 0x04B9 }, // CYRILLIC CAPITAL LETTER CHE WITH VERTICAL STROKE - { 0x04BA, 0x04BB }, // CYRILLIC CAPITAL LETTER SHHA - { 0x04BC, 0x04BD }, // CYRILLIC CAPITAL LETTER ABKHASIAN CHE - { 0x04BE, 0x04BF }, // CYRILLIC CAPITAL LETTER ABKHASIAN CHE WITH DESCENDER - { 0x04C0, 0x04CF }, // CYRILLIC LETTER PALOCHKA - { 0x04C3, 0x04C4 }, // CYRILLIC CAPITAL LETTER KA WITH HOOK - { 0x04C5, 0x04C6 }, // CYRILLIC CAPITAL LETTER EL WITH TAIL - { 0x04C7, 0x04C8 }, // CYRILLIC CAPITAL LETTER EN WITH HOOK - { 0x04C9, 0x04CA }, // CYRILLIC CAPITAL LETTER EN WITH TAIL - { 0x04CB, 0x04CC }, // CYRILLIC CAPITAL LETTER KHAKASSIAN CHE - { 0x04CD, 0x04CE }, // CYRILLIC CAPITAL LETTER EM WITH TAIL - { 0x04D4, 0x04D5 }, // CYRILLIC CAPITAL LIGATURE A IE - { 0x04D8, 0x04D9 }, // CYRILLIC CAPITAL LETTER SCHWA - { 0x04E0, 0x04E1 }, // CYRILLIC CAPITAL LETTER ABKHASIAN DZE - { 0x04E8, 0x04E9 }, // CYRILLIC CAPITAL LETTER BARRED O - { 0x04F6, 0x04F7 }, // CYRILLIC CAPITAL LETTER GHE WITH DESCENDER - { 0x04FA, 0x04FB }, // CYRILLIC CAPITAL LETTER GHE WITH STROKE AND HOOK - { 0x04FC, 0x04FD }, // CYRILLIC CAPITAL LETTER HA WITH HOOK - { 0x04FE, 0x04FF }, // CYRILLIC CAPITAL LETTER HA WITH STROKE - { 0x0500, 0x0501 }, // CYRILLIC CAPITAL LETTER KOMI DE - { 0x0502, 0x0503 }, // CYRILLIC CAPITAL LETTER KOMI DJE - { 0x0504, 0x0505 }, // CYRILLIC CAPITAL LETTER KOMI ZJE - { 0x0506, 0x0507 }, // CYRILLIC CAPITAL LETTER KOMI DZJE - { 0x0508, 0x0509 }, // CYRILLIC CAPITAL LETTER KOMI LJE - { 0x050A, 0x050B }, // CYRILLIC CAPITAL LETTER KOMI NJE - { 0x050C, 0x050D }, // CYRILLIC CAPITAL LETTER KOMI SJE - { 0x050E, 0x050F }, // CYRILLIC CAPITAL LETTER KOMI TJE - { 0x0510, 0x0511 }, // CYRILLIC CAPITAL LETTER REVERSED ZE - { 0x0512, 0x0513 }, // CYRILLIC CAPITAL LETTER EL WITH HOOK - { 0x0514, 0x0515 }, // CYRILLIC CAPITAL LETTER LHA - { 0x0516, 0x0517 }, // CYRILLIC CAPITAL LETTER RHA - { 0x0518, 0x0519 }, // CYRILLIC CAPITAL LETTER YAE - { 0x051A, 0x051B }, // CYRILLIC CAPITAL LETTER QA - { 0x051C, 0x051D }, // CYRILLIC CAPITAL LETTER WE - { 0x051E, 0x051F }, // CYRILLIC CAPITAL LETTER ALEUT KA - { 0x0520, 0x0521 }, // CYRILLIC CAPITAL LETTER EL WITH MIDDLE HOOK - { 0x0522, 0x0523 }, // CYRILLIC CAPITAL LETTER EN WITH MIDDLE HOOK - { 0x0524, 0x0525 }, // CYRILLIC CAPITAL LETTER PE WITH DESCENDER - { 0x0531, 0x0561 }, // ARMENIAN CAPITAL LETTER AYB - { 0x0532, 0x0562 }, // ARMENIAN CAPITAL LETTER BEN - { 0x0533, 0x0563 }, // ARMENIAN CAPITAL LETTER GIM - { 0x0534, 0x0564 }, // ARMENIAN CAPITAL LETTER DA - { 0x0535, 0x0565 }, // ARMENIAN CAPITAL LETTER ECH - { 0x0536, 0x0566 }, // ARMENIAN CAPITAL LETTER ZA - { 0x0537, 0x0567 }, // ARMENIAN CAPITAL LETTER EH - { 0x0538, 0x0568 }, // ARMENIAN CAPITAL LETTER ET - { 0x0539, 0x0569 }, // ARMENIAN CAPITAL LETTER TO - { 0x053A, 0x056A }, // ARMENIAN CAPITAL LETTER ZHE - { 0x053B, 0x056B }, // ARMENIAN CAPITAL LETTER INI - { 0x053C, 0x056C }, // ARMENIAN CAPITAL LETTER LIWN - { 0x053D, 0x056D }, // ARMENIAN CAPITAL LETTER XEH - { 0x053E, 0x056E }, // ARMENIAN CAPITAL LETTER CA - { 0x053F, 0x056F }, // ARMENIAN CAPITAL LETTER KEN - { 0x0540, 0x0570 }, // ARMENIAN CAPITAL LETTER HO - { 0x0541, 0x0571 }, // ARMENIAN CAPITAL LETTER JA - { 0x0542, 0x0572 }, // ARMENIAN CAPITAL LETTER GHAD - { 0x0543, 0x0573 }, // ARMENIAN CAPITAL LETTER CHEH - { 0x0544, 0x0574 }, // ARMENIAN CAPITAL LETTER MEN - { 0x0545, 0x0575 }, // ARMENIAN CAPITAL LETTER YI - { 0x0546, 0x0576 }, // ARMENIAN CAPITAL LETTER NOW - { 0x0547, 0x0577 }, // ARMENIAN CAPITAL LETTER SHA - { 0x0548, 0x0578 }, // ARMENIAN CAPITAL LETTER VO - { 0x0549, 0x0579 }, // ARMENIAN CAPITAL LETTER CHA - { 0x054A, 0x057A }, // ARMENIAN CAPITAL LETTER PEH - { 0x054B, 0x057B }, // ARMENIAN CAPITAL LETTER JHEH - { 0x054C, 0x057C }, // ARMENIAN CAPITAL LETTER RA - { 0x054D, 0x057D }, // ARMENIAN CAPITAL LETTER SEH - { 0x054E, 0x057E }, // ARMENIAN CAPITAL LETTER VEW - { 0x054F, 0x057F }, // ARMENIAN CAPITAL LETTER TIWN - { 0x0550, 0x0580 }, // ARMENIAN CAPITAL LETTER REH - { 0x0551, 0x0581 }, // ARMENIAN CAPITAL LETTER CO - { 0x0552, 0x0582 }, // ARMENIAN CAPITAL LETTER YIWN - { 0x0553, 0x0583 }, // ARMENIAN CAPITAL LETTER PIWR - { 0x0554, 0x0584 }, // ARMENIAN CAPITAL LETTER KEH - { 0x0555, 0x0585 }, // ARMENIAN CAPITAL LETTER OH - { 0x0556, 0x0586 }, // ARMENIAN CAPITAL LETTER FEH - { 0x10A0, 0x2D00 }, // GEORGIAN CAPITAL LETTER AN - { 0x10A1, 0x2D01 }, // GEORGIAN CAPITAL LETTER BAN - { 0x10A2, 0x2D02 }, // GEORGIAN CAPITAL LETTER GAN - { 0x10A3, 0x2D03 }, // GEORGIAN CAPITAL LETTER DON - { 0x10A4, 0x2D04 }, // GEORGIAN CAPITAL LETTER EN - { 0x10A5, 0x2D05 }, // GEORGIAN CAPITAL LETTER VIN - { 0x10A6, 0x2D06 }, // GEORGIAN CAPITAL LETTER ZEN - { 0x10A7, 0x2D07 }, // GEORGIAN CAPITAL LETTER TAN - { 0x10A8, 0x2D08 }, // GEORGIAN CAPITAL LETTER IN - { 0x10A9, 0x2D09 }, // GEORGIAN CAPITAL LETTER KAN - { 0x10AA, 0x2D0A }, // GEORGIAN CAPITAL LETTER LAS - { 0x10AB, 0x2D0B }, // GEORGIAN CAPITAL LETTER MAN - { 0x10AC, 0x2D0C }, // GEORGIAN CAPITAL LETTER NAR - { 0x10AD, 0x2D0D }, // GEORGIAN CAPITAL LETTER ON - { 0x10AE, 0x2D0E }, // GEORGIAN CAPITAL LETTER PAR - { 0x10AF, 0x2D0F }, // GEORGIAN CAPITAL LETTER ZHAR - { 0x10B0, 0x2D10 }, // GEORGIAN CAPITAL LETTER RAE - { 0x10B1, 0x2D11 }, // GEORGIAN CAPITAL LETTER SAN - { 0x10B2, 0x2D12 }, // GEORGIAN CAPITAL LETTER TAR - { 0x10B3, 0x2D13 }, // GEORGIAN CAPITAL LETTER UN - { 0x10B4, 0x2D14 }, // GEORGIAN CAPITAL LETTER PHAR - { 0x10B5, 0x2D15 }, // GEORGIAN CAPITAL LETTER KHAR - { 0x10B6, 0x2D16 }, // GEORGIAN CAPITAL LETTER GHAN - { 0x10B7, 0x2D17 }, // GEORGIAN CAPITAL LETTER QAR - { 0x10B8, 0x2D18 }, // GEORGIAN CAPITAL LETTER SHIN - { 0x10B9, 0x2D19 }, // GEORGIAN CAPITAL LETTER CHIN - { 0x10BA, 0x2D1A }, // GEORGIAN CAPITAL LETTER CAN - { 0x10BB, 0x2D1B }, // GEORGIAN CAPITAL LETTER JIL - { 0x10BC, 0x2D1C }, // GEORGIAN CAPITAL LETTER CIL - { 0x10BD, 0x2D1D }, // GEORGIAN CAPITAL LETTER CHAR - { 0x10BE, 0x2D1E }, // GEORGIAN CAPITAL LETTER XAN - { 0x10BF, 0x2D1F }, // GEORGIAN CAPITAL LETTER JHAN - { 0x10C0, 0x2D20 }, // GEORGIAN CAPITAL LETTER HAE - { 0x10C1, 0x2D21 }, // GEORGIAN CAPITAL LETTER HE - { 0x10C2, 0x2D22 }, // GEORGIAN CAPITAL LETTER HIE - { 0x10C3, 0x2D23 }, // GEORGIAN CAPITAL LETTER WE - { 0x10C4, 0x2D24 }, // GEORGIAN CAPITAL LETTER HAR - { 0x10C5, 0x2D25 }, // GEORGIAN CAPITAL LETTER HOE - { 0x1E00, 0x1E01 }, // LATIN CAPITAL LETTER A WITH RING BELOW - { 0x1E02, 0x1E03 }, // LATIN CAPITAL LETTER B WITH DOT ABOVE - { 0x1E04, 0x1E05 }, // LATIN CAPITAL LETTER B WITH DOT BELOW - { 0x1E06, 0x1E07 }, // LATIN CAPITAL LETTER B WITH LINE BELOW - { 0x1E08, 0x1E09 }, // LATIN CAPITAL LETTER C WITH CEDILLA AND ACUTE - { 0x1E0A, 0x1E0B }, // LATIN CAPITAL LETTER D WITH DOT ABOVE - { 0x1E0C, 0x1E0D }, // LATIN CAPITAL LETTER D WITH DOT BELOW - { 0x1E0E, 0x1E0F }, // LATIN CAPITAL LETTER D WITH LINE BELOW - { 0x1E10, 0x1E11 }, // LATIN CAPITAL LETTER D WITH CEDILLA - { 0x1E12, 0x1E13 }, // LATIN CAPITAL LETTER D WITH CIRCUMFLEX BELOW - { 0x1E14, 0x1E15 }, // LATIN CAPITAL LETTER E WITH MACRON AND GRAVE - { 0x1E16, 0x1E17 }, // LATIN CAPITAL LETTER E WITH MACRON AND ACUTE - { 0x1E18, 0x1E19 }, // LATIN CAPITAL LETTER E WITH CIRCUMFLEX BELOW - { 0x1E1A, 0x1E1B }, // LATIN CAPITAL LETTER E WITH TILDE BELOW - { 0x1E1C, 0x1E1D }, // LATIN CAPITAL LETTER E WITH CEDILLA AND BREVE - { 0x1E1E, 0x1E1F }, // LATIN CAPITAL LETTER F WITH DOT ABOVE - { 0x1E20, 0x1E21 }, // LATIN CAPITAL LETTER G WITH MACRON - { 0x1E22, 0x1E23 }, // LATIN CAPITAL LETTER H WITH DOT ABOVE - { 0x1E24, 0x1E25 }, // LATIN CAPITAL LETTER H WITH DOT BELOW - { 0x1E26, 0x1E27 }, // LATIN CAPITAL LETTER H WITH DIAERESIS - { 0x1E28, 0x1E29 }, // LATIN CAPITAL LETTER H WITH CEDILLA - { 0x1E2A, 0x1E2B }, // LATIN CAPITAL LETTER H WITH BREVE BELOW - { 0x1E2C, 0x1E2D }, // LATIN CAPITAL LETTER I WITH TILDE BELOW - { 0x1E2E, 0x1E2F }, // LATIN CAPITAL LETTER I WITH DIAERESIS AND ACUTE - { 0x1E30, 0x1E31 }, // LATIN CAPITAL LETTER K WITH ACUTE - { 0x1E32, 0x1E33 }, // LATIN CAPITAL LETTER K WITH DOT BELOW - { 0x1E34, 0x1E35 }, // LATIN CAPITAL LETTER K WITH LINE BELOW - { 0x1E36, 0x1E37 }, // LATIN CAPITAL LETTER L WITH DOT BELOW - { 0x1E38, 0x1E39 }, // LATIN CAPITAL LETTER L WITH DOT BELOW AND MACRON - { 0x1E3A, 0x1E3B }, // LATIN CAPITAL LETTER L WITH LINE BELOW - { 0x1E3C, 0x1E3D }, // LATIN CAPITAL LETTER L WITH CIRCUMFLEX BELOW - { 0x1E3E, 0x1E3F }, // LATIN CAPITAL LETTER M WITH ACUTE - { 0x1E40, 0x1E41 }, // LATIN CAPITAL LETTER M WITH DOT ABOVE - { 0x1E42, 0x1E43 }, // LATIN CAPITAL LETTER M WITH DOT BELOW - { 0x1E44, 0x1E45 }, // LATIN CAPITAL LETTER N WITH DOT ABOVE - { 0x1E46, 0x1E47 }, // LATIN CAPITAL LETTER N WITH DOT BELOW - { 0x1E48, 0x1E49 }, // LATIN CAPITAL LETTER N WITH LINE BELOW - { 0x1E4A, 0x1E4B }, // LATIN CAPITAL LETTER N WITH CIRCUMFLEX BELOW - { 0x1E4C, 0x1E4D }, // LATIN CAPITAL LETTER O WITH TILDE AND ACUTE - { 0x1E4E, 0x1E4F }, // LATIN CAPITAL LETTER O WITH TILDE AND DIAERESIS - { 0x1E50, 0x1E51 }, // LATIN CAPITAL LETTER O WITH MACRON AND GRAVE - { 0x1E52, 0x1E53 }, // LATIN CAPITAL LETTER O WITH MACRON AND ACUTE - { 0x1E54, 0x1E55 }, // LATIN CAPITAL LETTER P WITH ACUTE - { 0x1E56, 0x1E57 }, // LATIN CAPITAL LETTER P WITH DOT ABOVE - { 0x1E58, 0x1E59 }, // LATIN CAPITAL LETTER R WITH DOT ABOVE - { 0x1E5A, 0x1E5B }, // LATIN CAPITAL LETTER R WITH DOT BELOW - { 0x1E5C, 0x1E5D }, // LATIN CAPITAL LETTER R WITH DOT BELOW AND MACRON - { 0x1E5E, 0x1E5F }, // LATIN CAPITAL LETTER R WITH LINE BELOW - { 0x1E60, 0x1E61 }, // LATIN CAPITAL LETTER S WITH DOT ABOVE - { 0x1E62, 0x1E63 }, // LATIN CAPITAL LETTER S WITH DOT BELOW - { 0x1E64, 0x1E65 }, // LATIN CAPITAL LETTER S WITH ACUTE AND DOT ABOVE - { 0x1E66, 0x1E67 }, // LATIN CAPITAL LETTER S WITH CARON AND DOT ABOVE - { 0x1E68, 0x1E69 }, // LATIN CAPITAL LETTER S WITH DOT BELOW AND DOT ABOVE - { 0x1E6A, 0x1E6B }, // LATIN CAPITAL LETTER T WITH DOT ABOVE - { 0x1E6C, 0x1E6D }, // LATIN CAPITAL LETTER T WITH DOT BELOW - { 0x1E6E, 0x1E6F }, // LATIN CAPITAL LETTER T WITH LINE BELOW - { 0x1E70, 0x1E71 }, // LATIN CAPITAL LETTER T WITH CIRCUMFLEX BELOW - { 0x1E72, 0x1E73 }, // LATIN CAPITAL LETTER U WITH DIAERESIS BELOW - { 0x1E74, 0x1E75 }, // LATIN CAPITAL LETTER U WITH TILDE BELOW - { 0x1E76, 0x1E77 }, // LATIN CAPITAL LETTER U WITH CIRCUMFLEX BELOW - { 0x1E78, 0x1E79 }, // LATIN CAPITAL LETTER U WITH TILDE AND ACUTE - { 0x1E7A, 0x1E7B }, // LATIN CAPITAL LETTER U WITH MACRON AND DIAERESIS - { 0x1E7C, 0x1E7D }, // LATIN CAPITAL LETTER V WITH TILDE - { 0x1E7E, 0x1E7F }, // LATIN CAPITAL LETTER V WITH DOT BELOW - { 0x1E80, 0x1E81 }, // LATIN CAPITAL LETTER W WITH GRAVE - { 0x1E82, 0x1E83 }, // LATIN CAPITAL LETTER W WITH ACUTE - { 0x1E84, 0x1E85 }, // LATIN CAPITAL LETTER W WITH DIAERESIS - { 0x1E86, 0x1E87 }, // LATIN CAPITAL LETTER W WITH DOT ABOVE - { 0x1E88, 0x1E89 }, // LATIN CAPITAL LETTER W WITH DOT BELOW - { 0x1E8A, 0x1E8B }, // LATIN CAPITAL LETTER X WITH DOT ABOVE - { 0x1E8C, 0x1E8D }, // LATIN CAPITAL LETTER X WITH DIAERESIS - { 0x1E8E, 0x1E8F }, // LATIN CAPITAL LETTER Y WITH DOT ABOVE - { 0x1E90, 0x1E91 }, // LATIN CAPITAL LETTER Z WITH CIRCUMFLEX - { 0x1E92, 0x1E93 }, // LATIN CAPITAL LETTER Z WITH DOT BELOW - { 0x1E94, 0x1E95 }, // LATIN CAPITAL LETTER Z WITH LINE BELOW - { 0x1E9E, 0x00DF }, // LATIN CAPITAL LETTER SHARP S - { 0x1EA0, 0x1EA1 }, // LATIN CAPITAL LETTER A WITH DOT BELOW - { 0x1EA2, 0x1EA3 }, // LATIN CAPITAL LETTER A WITH HOOK ABOVE - { 0x1EA4, 0x1EA5 }, // LATIN CAPITAL LETTER A WITH CIRCUMFLEX AND ACUTE - { 0x1EA6, 0x1EA7 }, // LATIN CAPITAL LETTER A WITH CIRCUMFLEX AND GRAVE - { 0x1EA8, 0x1EA9 }, // LATIN CAPITAL LETTER A WITH CIRCUMFLEX AND HOOK ABOVE - { 0x1EAA, 0x1EAB }, // LATIN CAPITAL LETTER A WITH CIRCUMFLEX AND TILDE - { 0x1EAC, 0x1EAD }, // LATIN CAPITAL LETTER A WITH CIRCUMFLEX AND DOT BELOW - { 0x1EAE, 0x1EAF }, // LATIN CAPITAL LETTER A WITH BREVE AND ACUTE - { 0x1EB0, 0x1EB1 }, // LATIN CAPITAL LETTER A WITH BREVE AND GRAVE - { 0x1EB2, 0x1EB3 }, // LATIN CAPITAL LETTER A WITH BREVE AND HOOK ABOVE - { 0x1EB4, 0x1EB5 }, // LATIN CAPITAL LETTER A WITH BREVE AND TILDE - { 0x1EB6, 0x1EB7 }, // LATIN CAPITAL LETTER A WITH BREVE AND DOT BELOW - { 0x1EB8, 0x1EB9 }, // LATIN CAPITAL LETTER E WITH DOT BELOW - { 0x1EBA, 0x1EBB }, // LATIN CAPITAL LETTER E WITH HOOK ABOVE - { 0x1EBC, 0x1EBD }, // LATIN CAPITAL LETTER E WITH TILDE - { 0x1EBE, 0x1EBF }, // LATIN CAPITAL LETTER E WITH CIRCUMFLEX AND ACUTE - { 0x1EC0, 0x1EC1 }, // LATIN CAPITAL LETTER E WITH CIRCUMFLEX AND GRAVE - { 0x1EC2, 0x1EC3 }, // LATIN CAPITAL LETTER E WITH CIRCUMFLEX AND HOOK ABOVE - { 0x1EC4, 0x1EC5 }, // LATIN CAPITAL LETTER E WITH CIRCUMFLEX AND TILDE - { 0x1EC6, 0x1EC7 }, // LATIN CAPITAL LETTER E WITH CIRCUMFLEX AND DOT BELOW - { 0x1EC8, 0x1EC9 }, // LATIN CAPITAL LETTER I WITH HOOK ABOVE - { 0x1ECA, 0x1ECB }, // LATIN CAPITAL LETTER I WITH DOT BELOW - { 0x1ECC, 0x1ECD }, // LATIN CAPITAL LETTER O WITH DOT BELOW - { 0x1ECE, 0x1ECF }, // LATIN CAPITAL LETTER O WITH HOOK ABOVE - { 0x1ED0, 0x1ED1 }, // LATIN CAPITAL LETTER O WITH CIRCUMFLEX AND ACUTE - { 0x1ED2, 0x1ED3 }, // LATIN CAPITAL LETTER O WITH CIRCUMFLEX AND GRAVE - { 0x1ED4, 0x1ED5 }, // LATIN CAPITAL LETTER O WITH CIRCUMFLEX AND HOOK ABOVE - { 0x1ED6, 0x1ED7 }, // LATIN CAPITAL LETTER O WITH CIRCUMFLEX AND TILDE - { 0x1ED8, 0x1ED9 }, // LATIN CAPITAL LETTER O WITH CIRCUMFLEX AND DOT BELOW - { 0x1EDA, 0x1EDB }, // LATIN CAPITAL LETTER O WITH HORN AND ACUTE - { 0x1EDC, 0x1EDD }, // LATIN CAPITAL LETTER O WITH HORN AND GRAVE - { 0x1EDE, 0x1EDF }, // LATIN CAPITAL LETTER O WITH HORN AND HOOK ABOVE - { 0x1EE0, 0x1EE1 }, // LATIN CAPITAL LETTER O WITH HORN AND TILDE - { 0x1EE2, 0x1EE3 }, // LATIN CAPITAL LETTER O WITH HORN AND DOT BELOW - { 0x1EE4, 0x1EE5 }, // LATIN CAPITAL LETTER U WITH DOT BELOW - { 0x1EE6, 0x1EE7 }, // LATIN CAPITAL LETTER U WITH HOOK ABOVE - { 0x1EE8, 0x1EE9 }, // LATIN CAPITAL LETTER U WITH HORN AND ACUTE - { 0x1EEA, 0x1EEB }, // LATIN CAPITAL LETTER U WITH HORN AND GRAVE - { 0x1EEC, 0x1EED }, // LATIN CAPITAL LETTER U WITH HORN AND HOOK ABOVE - { 0x1EEE, 0x1EEF }, // LATIN CAPITAL LETTER U WITH HORN AND TILDE - { 0x1EF0, 0x1EF1 }, // LATIN CAPITAL LETTER U WITH HORN AND DOT BELOW - { 0x1EF2, 0x1EF3 }, // LATIN CAPITAL LETTER Y WITH GRAVE - { 0x1EF4, 0x1EF5 }, // LATIN CAPITAL LETTER Y WITH DOT BELOW - { 0x1EF6, 0x1EF7 }, // LATIN CAPITAL LETTER Y WITH HOOK ABOVE - { 0x1EF8, 0x1EF9 }, // LATIN CAPITAL LETTER Y WITH TILDE - { 0x1EFA, 0x1EFB }, // LATIN CAPITAL LETTER MIDDLE-WELSH LL - { 0x1EFC, 0x1EFD }, // LATIN CAPITAL LETTER MIDDLE-WELSH V - { 0x1EFE, 0x1EFF }, // LATIN CAPITAL LETTER Y WITH LOOP - { 0x1F08, 0x1F00 }, // GREEK CAPITAL LETTER ALPHA WITH PSILI - { 0x1F09, 0x1F01 }, // GREEK CAPITAL LETTER ALPHA WITH DASIA - { 0x1F0A, 0x1F02 }, // GREEK CAPITAL LETTER ALPHA WITH PSILI AND VARIA - { 0x1F0B, 0x1F03 }, // GREEK CAPITAL LETTER ALPHA WITH DASIA AND VARIA - { 0x1F0C, 0x1F04 }, // GREEK CAPITAL LETTER ALPHA WITH PSILI AND OXIA - { 0x1F0D, 0x1F05 }, // GREEK CAPITAL LETTER ALPHA WITH DASIA AND OXIA - { 0x1F0E, 0x1F06 }, // GREEK CAPITAL LETTER ALPHA WITH PSILI AND PERISPOMENI - { 0x1F0F, 0x1F07 }, // GREEK CAPITAL LETTER ALPHA WITH DASIA AND PERISPOMENI - { 0x1F18, 0x1F10 }, // GREEK CAPITAL LETTER EPSILON WITH PSILI - { 0x1F19, 0x1F11 }, // GREEK CAPITAL LETTER EPSILON WITH DASIA - { 0x1F1A, 0x1F12 }, // GREEK CAPITAL LETTER EPSILON WITH PSILI AND VARIA - { 0x1F1B, 0x1F13 }, // GREEK CAPITAL LETTER EPSILON WITH DASIA AND VARIA - { 0x1F1C, 0x1F14 }, // GREEK CAPITAL LETTER EPSILON WITH PSILI AND OXIA - { 0x1F1D, 0x1F15 }, // GREEK CAPITAL LETTER EPSILON WITH DASIA AND OXIA - { 0x1F28, 0x1F20 }, // GREEK CAPITAL LETTER ETA WITH PSILI - { 0x1F29, 0x1F21 }, // GREEK CAPITAL LETTER ETA WITH DASIA - { 0x1F2A, 0x1F22 }, // GREEK CAPITAL LETTER ETA WITH PSILI AND VARIA - { 0x1F2B, 0x1F23 }, // GREEK CAPITAL LETTER ETA WITH DASIA AND VARIA - { 0x1F2C, 0x1F24 }, // GREEK CAPITAL LETTER ETA WITH PSILI AND OXIA - { 0x1F2D, 0x1F25 }, // GREEK CAPITAL LETTER ETA WITH DASIA AND OXIA - { 0x1F2E, 0x1F26 }, // GREEK CAPITAL LETTER ETA WITH PSILI AND PERISPOMENI - { 0x1F2F, 0x1F27 }, // GREEK CAPITAL LETTER ETA WITH DASIA AND PERISPOMENI - { 0x1F38, 0x1F30 }, // GREEK CAPITAL LETTER IOTA WITH PSILI - { 0x1F39, 0x1F31 }, // GREEK CAPITAL LETTER IOTA WITH DASIA - { 0x1F3A, 0x1F32 }, // GREEK CAPITAL LETTER IOTA WITH PSILI AND VARIA - { 0x1F3B, 0x1F33 }, // GREEK CAPITAL LETTER IOTA WITH DASIA AND VARIA - { 0x1F3C, 0x1F34 }, // GREEK CAPITAL LETTER IOTA WITH PSILI AND OXIA - { 0x1F3D, 0x1F35 }, // GREEK CAPITAL LETTER IOTA WITH DASIA AND OXIA - { 0x1F3E, 0x1F36 }, // GREEK CAPITAL LETTER IOTA WITH PSILI AND PERISPOMENI - { 0x1F3F, 0x1F37 }, // GREEK CAPITAL LETTER IOTA WITH DASIA AND PERISPOMENI - { 0x1F48, 0x1F40 }, // GREEK CAPITAL LETTER OMICRON WITH PSILI - { 0x1F49, 0x1F41 }, // GREEK CAPITAL LETTER OMICRON WITH DASIA - { 0x1F4A, 0x1F42 }, // GREEK CAPITAL LETTER OMICRON WITH PSILI AND VARIA - { 0x1F4B, 0x1F43 }, // GREEK CAPITAL LETTER OMICRON WITH DASIA AND VARIA - { 0x1F4C, 0x1F44 }, // GREEK CAPITAL LETTER OMICRON WITH PSILI AND OXIA - { 0x1F4D, 0x1F45 }, // GREEK CAPITAL LETTER OMICRON WITH DASIA AND OXIA - { 0x1F59, 0x1F51 }, // GREEK CAPITAL LETTER UPSILON WITH DASIA - { 0x1F5B, 0x1F53 }, // GREEK CAPITAL LETTER UPSILON WITH DASIA AND VARIA - { 0x1F5D, 0x1F55 }, // GREEK CAPITAL LETTER UPSILON WITH DASIA AND OXIA - { 0x1F5F, 0x1F57 }, // GREEK CAPITAL LETTER UPSILON WITH DASIA AND PERISPOMENI - { 0x1F68, 0x1F60 }, // GREEK CAPITAL LETTER OMEGA WITH PSILI - { 0x1F69, 0x1F61 }, // GREEK CAPITAL LETTER OMEGA WITH DASIA - { 0x1F6A, 0x1F62 }, // GREEK CAPITAL LETTER OMEGA WITH PSILI AND VARIA - { 0x1F6B, 0x1F63 }, // GREEK CAPITAL LETTER OMEGA WITH DASIA AND VARIA - { 0x1F6C, 0x1F64 }, // GREEK CAPITAL LETTER OMEGA WITH PSILI AND OXIA - { 0x1F6D, 0x1F65 }, // GREEK CAPITAL LETTER OMEGA WITH DASIA AND OXIA - { 0x1F6E, 0x1F66 }, // GREEK CAPITAL LETTER OMEGA WITH PSILI AND PERISPOMENI - { 0x1F6F, 0x1F67 }, // GREEK CAPITAL LETTER OMEGA WITH DASIA AND PERISPOMENI - { 0x1F88, 0x1F80 }, // GREEK CAPITAL LETTER ALPHA WITH PSILI AND PROSGEGRAMMENI - { 0x1F89, 0x1F81 }, // GREEK CAPITAL LETTER ALPHA WITH DASIA AND PROSGEGRAMMENI - { 0x1F8A, 0x1F82 }, // GREEK CAPITAL LETTER ALPHA WITH PSILI AND VARIA AND PROSGEGRAMMENI - { 0x1F8B, 0x1F83 }, // GREEK CAPITAL LETTER ALPHA WITH DASIA AND VARIA AND PROSGEGRAMMENI - { 0x1F8C, 0x1F84 }, // GREEK CAPITAL LETTER ALPHA WITH PSILI AND OXIA AND PROSGEGRAMMENI - { 0x1F8D, 0x1F85 }, // GREEK CAPITAL LETTER ALPHA WITH DASIA AND OXIA AND PROSGEGRAMMENI - { 0x1F8E, 0x1F86 }, // GREEK CAPITAL LETTER ALPHA WITH PSILI AND PERISPOMENI AND PROSGEGRAMMENI - { 0x1F8F, 0x1F87 }, // GREEK CAPITAL LETTER ALPHA WITH DASIA AND PERISPOMENI AND PROSGEGRAMMENI - { 0x1F98, 0x1F90 }, // GREEK CAPITAL LETTER ETA WITH PSILI AND PROSGEGRAMMENI - { 0x1F99, 0x1F91 }, // GREEK CAPITAL LETTER ETA WITH DASIA AND PROSGEGRAMMENI - { 0x1F9A, 0x1F92 }, // GREEK CAPITAL LETTER ETA WITH PSILI AND VARIA AND PROSGEGRAMMENI - { 0x1F9B, 0x1F93 }, // GREEK CAPITAL LETTER ETA WITH DASIA AND VARIA AND PROSGEGRAMMENI - { 0x1F9C, 0x1F94 }, // GREEK CAPITAL LETTER ETA WITH PSILI AND OXIA AND PROSGEGRAMMENI - { 0x1F9D, 0x1F95 }, // GREEK CAPITAL LETTER ETA WITH DASIA AND OXIA AND PROSGEGRAMMENI - { 0x1F9E, 0x1F96 }, // GREEK CAPITAL LETTER ETA WITH PSILI AND PERISPOMENI AND PROSGEGRAMMENI - { 0x1F9F, 0x1F97 }, // GREEK CAPITAL LETTER ETA WITH DASIA AND PERISPOMENI AND PROSGEGRAMMENI - { 0x1FA8, 0x1FA0 }, // GREEK CAPITAL LETTER OMEGA WITH PSILI AND PROSGEGRAMMENI - { 0x1FA9, 0x1FA1 }, // GREEK CAPITAL LETTER OMEGA WITH DASIA AND PROSGEGRAMMENI - { 0x1FAA, 0x1FA2 }, // GREEK CAPITAL LETTER OMEGA WITH PSILI AND VARIA AND PROSGEGRAMMENI - { 0x1FAB, 0x1FA3 }, // GREEK CAPITAL LETTER OMEGA WITH DASIA AND VARIA AND PROSGEGRAMMENI - { 0x1FAC, 0x1FA4 }, // GREEK CAPITAL LETTER OMEGA WITH PSILI AND OXIA AND PROSGEGRAMMENI - { 0x1FAD, 0x1FA5 }, // GREEK CAPITAL LETTER OMEGA WITH DASIA AND OXIA AND PROSGEGRAMMENI - { 0x1FAE, 0x1FA6 }, // GREEK CAPITAL LETTER OMEGA WITH PSILI AND PERISPOMENI AND PROSGEGRAMMENI - { 0x1FAF, 0x1FA7 }, // GREEK CAPITAL LETTER OMEGA WITH DASIA AND PERISPOMENI AND PROSGEGRAMMENI - { 0x1FB8, 0x1FB0 }, // GREEK CAPITAL LETTER ALPHA WITH VRACHY - { 0x1FB9, 0x1FB1 }, // GREEK CAPITAL LETTER ALPHA WITH MACRON - { 0x1FBA, 0x1F70 }, // GREEK CAPITAL LETTER ALPHA WITH VARIA - { 0x1FBB, 0x1F71 }, // GREEK CAPITAL LETTER ALPHA WITH OXIA - { 0x1FBC, 0x1FB3 }, // GREEK CAPITAL LETTER ALPHA WITH PROSGEGRAMMENI - { 0x1FC8, 0x1F72 }, // GREEK CAPITAL LETTER EPSILON WITH VARIA - { 0x1FC9, 0x1F73 }, // GREEK CAPITAL LETTER EPSILON WITH OXIA - { 0x1FCA, 0x1F74 }, // GREEK CAPITAL LETTER ETA WITH VARIA - { 0x1FCB, 0x1F75 }, // GREEK CAPITAL LETTER ETA WITH OXIA - { 0x1FCC, 0x1FC3 }, // GREEK CAPITAL LETTER ETA WITH PROSGEGRAMMENI - { 0x1FD8, 0x1FD0 }, // GREEK CAPITAL LETTER IOTA WITH VRACHY - { 0x1FD9, 0x1FD1 }, // GREEK CAPITAL LETTER IOTA WITH MACRON - { 0x1FDA, 0x1F76 }, // GREEK CAPITAL LETTER IOTA WITH VARIA - { 0x1FDB, 0x1F77 }, // GREEK CAPITAL LETTER IOTA WITH OXIA - { 0x1FE8, 0x1FE0 }, // GREEK CAPITAL LETTER UPSILON WITH VRACHY - { 0x1FE9, 0x1FE1 }, // GREEK CAPITAL LETTER UPSILON WITH MACRON - { 0x1FEA, 0x1F7A }, // GREEK CAPITAL LETTER UPSILON WITH VARIA - { 0x1FEB, 0x1F7B }, // GREEK CAPITAL LETTER UPSILON WITH OXIA - { 0x1FEC, 0x1FE5 }, // GREEK CAPITAL LETTER RHO WITH DASIA - { 0x1FF8, 0x1F78 }, // GREEK CAPITAL LETTER OMICRON WITH VARIA - { 0x1FF9, 0x1F79 }, // GREEK CAPITAL LETTER OMICRON WITH OXIA - { 0x1FFA, 0x1F7C }, // GREEK CAPITAL LETTER OMEGA WITH VARIA - { 0x1FFB, 0x1F7D }, // GREEK CAPITAL LETTER OMEGA WITH OXIA - { 0x1FFC, 0x1FF3 }, // GREEK CAPITAL LETTER OMEGA WITH PROSGEGRAMMENI - { 0x2126, 0x03C9 }, // OHM SIGN - { 0x212A, 0x006B }, // KELVIN SIGN - { 0x212B, 0x00E5 }, // ANGSTROM SIGN - { 0x2132, 0x214E }, // TURNED CAPITAL F - { 0x2160, 0x2170 }, // ROMAN NUMERAL ONE - { 0x2161, 0x2171 }, // ROMAN NUMERAL TWO - { 0x2162, 0x2172 }, // ROMAN NUMERAL THREE - { 0x2163, 0x2173 }, // ROMAN NUMERAL FOUR - { 0x2164, 0x2174 }, // ROMAN NUMERAL FIVE - { 0x2165, 0x2175 }, // ROMAN NUMERAL SIX - { 0x2166, 0x2176 }, // ROMAN NUMERAL SEVEN - { 0x2167, 0x2177 }, // ROMAN NUMERAL EIGHT - { 0x2168, 0x2178 }, // ROMAN NUMERAL NINE - { 0x2169, 0x2179 }, // ROMAN NUMERAL TEN - { 0x216A, 0x217A }, // ROMAN NUMERAL ELEVEN - { 0x216B, 0x217B }, // ROMAN NUMERAL TWELVE - { 0x216C, 0x217C }, // ROMAN NUMERAL FIFTY - { 0x216D, 0x217D }, // ROMAN NUMERAL ONE HUNDRED - { 0x216E, 0x217E }, // ROMAN NUMERAL FIVE HUNDRED - { 0x216F, 0x217F }, // ROMAN NUMERAL ONE THOUSAND - { 0x2183, 0x2184 }, // ROMAN NUMERAL REVERSED ONE HUNDRED - { 0x24B6, 0x24D0 }, // CIRCLED LATIN CAPITAL LETTER A - { 0x24B7, 0x24D1 }, // CIRCLED LATIN CAPITAL LETTER B - { 0x24B8, 0x24D2 }, // CIRCLED LATIN CAPITAL LETTER C - { 0x24B9, 0x24D3 }, // CIRCLED LATIN CAPITAL LETTER D - { 0x24BA, 0x24D4 }, // CIRCLED LATIN CAPITAL LETTER E - { 0x24BB, 0x24D5 }, // CIRCLED LATIN CAPITAL LETTER F - { 0x24BC, 0x24D6 }, // CIRCLED LATIN CAPITAL LETTER G - { 0x24BD, 0x24D7 }, // CIRCLED LATIN CAPITAL LETTER H - { 0x24BE, 0x24D8 }, // CIRCLED LATIN CAPITAL LETTER I - { 0x24BF, 0x24D9 }, // CIRCLED LATIN CAPITAL LETTER J - { 0x24C0, 0x24DA }, // CIRCLED LATIN CAPITAL LETTER K - { 0x24C1, 0x24DB }, // CIRCLED LATIN CAPITAL LETTER L - { 0x24C2, 0x24DC }, // CIRCLED LATIN CAPITAL LETTER M - { 0x24C3, 0x24DD }, // CIRCLED LATIN CAPITAL LETTER N - { 0x24C4, 0x24DE }, // CIRCLED LATIN CAPITAL LETTER O - { 0x24C5, 0x24DF }, // CIRCLED LATIN CAPITAL LETTER P - { 0x24C6, 0x24E0 }, // CIRCLED LATIN CAPITAL LETTER Q - { 0x24C7, 0x24E1 }, // CIRCLED LATIN CAPITAL LETTER R - { 0x24C8, 0x24E2 }, // CIRCLED LATIN CAPITAL LETTER S - { 0x24C9, 0x24E3 }, // CIRCLED LATIN CAPITAL LETTER T - { 0x24CA, 0x24E4 }, // CIRCLED LATIN CAPITAL LETTER U - { 0x24CB, 0x24E5 }, // CIRCLED LATIN CAPITAL LETTER V - { 0x24CC, 0x24E6 }, // CIRCLED LATIN CAPITAL LETTER W - { 0x24CD, 0x24E7 }, // CIRCLED LATIN CAPITAL LETTER X - { 0x24CE, 0x24E8 }, // CIRCLED LATIN CAPITAL LETTER Y - { 0x24CF, 0x24E9 }, // CIRCLED LATIN CAPITAL LETTER Z - { 0x2C00, 0x2C30 }, // GLAGOLITIC CAPITAL LETTER AZU - { 0x2C01, 0x2C31 }, // GLAGOLITIC CAPITAL LETTER BUKY - { 0x2C02, 0x2C32 }, // GLAGOLITIC CAPITAL LETTER VEDE - { 0x2C03, 0x2C33 }, // GLAGOLITIC CAPITAL LETTER GLAGOLI - { 0x2C04, 0x2C34 }, // GLAGOLITIC CAPITAL LETTER DOBRO - { 0x2C05, 0x2C35 }, // GLAGOLITIC CAPITAL LETTER YESTU - { 0x2C06, 0x2C36 }, // GLAGOLITIC CAPITAL LETTER ZHIVETE - { 0x2C07, 0x2C37 }, // GLAGOLITIC CAPITAL LETTER DZELO - { 0x2C08, 0x2C38 }, // GLAGOLITIC CAPITAL LETTER ZEMLJA - { 0x2C09, 0x2C39 }, // GLAGOLITIC CAPITAL LETTER IZHE - { 0x2C0A, 0x2C3A }, // GLAGOLITIC CAPITAL LETTER INITIAL IZHE - { 0x2C0B, 0x2C3B }, // GLAGOLITIC CAPITAL LETTER I - { 0x2C0C, 0x2C3C }, // GLAGOLITIC CAPITAL LETTER DJERVI - { 0x2C0D, 0x2C3D }, // GLAGOLITIC CAPITAL LETTER KAKO - { 0x2C0E, 0x2C3E }, // GLAGOLITIC CAPITAL LETTER LJUDIJE - { 0x2C0F, 0x2C3F }, // GLAGOLITIC CAPITAL LETTER MYSLITE - { 0x2C10, 0x2C40 }, // GLAGOLITIC CAPITAL LETTER NASHI - { 0x2C11, 0x2C41 }, // GLAGOLITIC CAPITAL LETTER ONU - { 0x2C12, 0x2C42 }, // GLAGOLITIC CAPITAL LETTER POKOJI - { 0x2C13, 0x2C43 }, // GLAGOLITIC CAPITAL LETTER RITSI - { 0x2C14, 0x2C44 }, // GLAGOLITIC CAPITAL LETTER SLOVO - { 0x2C15, 0x2C45 }, // GLAGOLITIC CAPITAL LETTER TVRIDO - { 0x2C16, 0x2C46 }, // GLAGOLITIC CAPITAL LETTER UKU - { 0x2C17, 0x2C47 }, // GLAGOLITIC CAPITAL LETTER FRITU - { 0x2C18, 0x2C48 }, // GLAGOLITIC CAPITAL LETTER HERU - { 0x2C19, 0x2C49 }, // GLAGOLITIC CAPITAL LETTER OTU - { 0x2C1A, 0x2C4A }, // GLAGOLITIC CAPITAL LETTER PE - { 0x2C1B, 0x2C4B }, // GLAGOLITIC CAPITAL LETTER SHTA - { 0x2C1C, 0x2C4C }, // GLAGOLITIC CAPITAL LETTER TSI - { 0x2C1D, 0x2C4D }, // GLAGOLITIC CAPITAL LETTER CHRIVI - { 0x2C1E, 0x2C4E }, // GLAGOLITIC CAPITAL LETTER SHA - { 0x2C1F, 0x2C4F }, // GLAGOLITIC CAPITAL LETTER YERU - { 0x2C20, 0x2C50 }, // GLAGOLITIC CAPITAL LETTER YERI - { 0x2C21, 0x2C51 }, // GLAGOLITIC CAPITAL LETTER YATI - { 0x2C22, 0x2C52 }, // GLAGOLITIC CAPITAL LETTER SPIDERY HA - { 0x2C23, 0x2C53 }, // GLAGOLITIC CAPITAL LETTER YU - { 0x2C24, 0x2C54 }, // GLAGOLITIC CAPITAL LETTER SMALL YUS - { 0x2C25, 0x2C55 }, // GLAGOLITIC CAPITAL LETTER SMALL YUS WITH TAIL - { 0x2C26, 0x2C56 }, // GLAGOLITIC CAPITAL LETTER YO - { 0x2C27, 0x2C57 }, // GLAGOLITIC CAPITAL LETTER IOTATED SMALL YUS - { 0x2C28, 0x2C58 }, // GLAGOLITIC CAPITAL LETTER BIG YUS - { 0x2C29, 0x2C59 }, // GLAGOLITIC CAPITAL LETTER IOTATED BIG YUS - { 0x2C2A, 0x2C5A }, // GLAGOLITIC CAPITAL LETTER FITA - { 0x2C2B, 0x2C5B }, // GLAGOLITIC CAPITAL LETTER IZHITSA - { 0x2C2C, 0x2C5C }, // GLAGOLITIC CAPITAL LETTER SHTAPIC - { 0x2C2D, 0x2C5D }, // GLAGOLITIC CAPITAL LETTER TROKUTASTI A - { 0x2C2E, 0x2C5E }, // GLAGOLITIC CAPITAL LETTER LATINATE MYSLITE - { 0x2C60, 0x2C61 }, // LATIN CAPITAL LETTER L WITH DOUBLE BAR - { 0x2C62, 0x026B }, // LATIN CAPITAL LETTER L WITH MIDDLE TILDE - { 0x2C63, 0x1D7D }, // LATIN CAPITAL LETTER P WITH STROKE - { 0x2C64, 0x027D }, // LATIN CAPITAL LETTER R WITH TAIL - { 0x2C67, 0x2C68 }, // LATIN CAPITAL LETTER H WITH DESCENDER - { 0x2C69, 0x2C6A }, // LATIN CAPITAL LETTER K WITH DESCENDER - { 0x2C6B, 0x2C6C }, // LATIN CAPITAL LETTER Z WITH DESCENDER - { 0x2C6D, 0x0251 }, // LATIN CAPITAL LETTER ALPHA - { 0x2C6E, 0x0271 }, // LATIN CAPITAL LETTER M WITH HOOK - { 0x2C6F, 0x0250 }, // LATIN CAPITAL LETTER TURNED A - { 0x2C70, 0x0252 }, // LATIN CAPITAL LETTER TURNED ALPHA - { 0x2C72, 0x2C73 }, // LATIN CAPITAL LETTER W WITH HOOK - { 0x2C75, 0x2C76 }, // LATIN CAPITAL LETTER HALF H - { 0x2C7E, 0x023F }, // LATIN CAPITAL LETTER S WITH SWASH TAIL - { 0x2C7F, 0x0240 }, // LATIN CAPITAL LETTER Z WITH SWASH TAIL - { 0x2C80, 0x2C81 }, // COPTIC CAPITAL LETTER ALFA - { 0x2C82, 0x2C83 }, // COPTIC CAPITAL LETTER VIDA - { 0x2C84, 0x2C85 }, // COPTIC CAPITAL LETTER GAMMA - { 0x2C86, 0x2C87 }, // COPTIC CAPITAL LETTER DALDA - { 0x2C88, 0x2C89 }, // COPTIC CAPITAL LETTER EIE - { 0x2C8A, 0x2C8B }, // COPTIC CAPITAL LETTER SOU - { 0x2C8C, 0x2C8D }, // COPTIC CAPITAL LETTER ZATA - { 0x2C8E, 0x2C8F }, // COPTIC CAPITAL LETTER HATE - { 0x2C90, 0x2C91 }, // COPTIC CAPITAL LETTER THETHE - { 0x2C92, 0x2C93 }, // COPTIC CAPITAL LETTER IAUDA - { 0x2C94, 0x2C95 }, // COPTIC CAPITAL LETTER KAPA - { 0x2C96, 0x2C97 }, // COPTIC CAPITAL LETTER LAULA - { 0x2C98, 0x2C99 }, // COPTIC CAPITAL LETTER MI - { 0x2C9A, 0x2C9B }, // COPTIC CAPITAL LETTER NI - { 0x2C9C, 0x2C9D }, // COPTIC CAPITAL LETTER KSI - { 0x2C9E, 0x2C9F }, // COPTIC CAPITAL LETTER O - { 0x2CA0, 0x2CA1 }, // COPTIC CAPITAL LETTER PI - { 0x2CA2, 0x2CA3 }, // COPTIC CAPITAL LETTER RO - { 0x2CA4, 0x2CA5 }, // COPTIC CAPITAL LETTER SIMA - { 0x2CA6, 0x2CA7 }, // COPTIC CAPITAL LETTER TAU - { 0x2CA8, 0x2CA9 }, // COPTIC CAPITAL LETTER UA - { 0x2CAA, 0x2CAB }, // COPTIC CAPITAL LETTER FI - { 0x2CAC, 0x2CAD }, // COPTIC CAPITAL LETTER KHI - { 0x2CAE, 0x2CAF }, // COPTIC CAPITAL LETTER PSI - { 0x2CB0, 0x2CB1 }, // COPTIC CAPITAL LETTER OOU - { 0x2CB2, 0x2CB3 }, // COPTIC CAPITAL LETTER DIALECT-P ALEF - { 0x2CB4, 0x2CB5 }, // COPTIC CAPITAL LETTER OLD COPTIC AIN - { 0x2CB6, 0x2CB7 }, // COPTIC CAPITAL LETTER CRYPTOGRAMMIC EIE - { 0x2CB8, 0x2CB9 }, // COPTIC CAPITAL LETTER DIALECT-P KAPA - { 0x2CBA, 0x2CBB }, // COPTIC CAPITAL LETTER DIALECT-P NI - { 0x2CBC, 0x2CBD }, // COPTIC CAPITAL LETTER CRYPTOGRAMMIC NI - { 0x2CBE, 0x2CBF }, // COPTIC CAPITAL LETTER OLD COPTIC OOU - { 0x2CC0, 0x2CC1 }, // COPTIC CAPITAL LETTER SAMPI - { 0x2CC2, 0x2CC3 }, // COPTIC CAPITAL LETTER CROSSED SHEI - { 0x2CC4, 0x2CC5 }, // COPTIC CAPITAL LETTER OLD COPTIC SHEI - { 0x2CC6, 0x2CC7 }, // COPTIC CAPITAL LETTER OLD COPTIC ESH - { 0x2CC8, 0x2CC9 }, // COPTIC CAPITAL LETTER AKHMIMIC KHEI - { 0x2CCA, 0x2CCB }, // COPTIC CAPITAL LETTER DIALECT-P HORI - { 0x2CCC, 0x2CCD }, // COPTIC CAPITAL LETTER OLD COPTIC HORI - { 0x2CCE, 0x2CCF }, // COPTIC CAPITAL LETTER OLD COPTIC HA - { 0x2CD0, 0x2CD1 }, // COPTIC CAPITAL LETTER L-SHAPED HA - { 0x2CD2, 0x2CD3 }, // COPTIC CAPITAL LETTER OLD COPTIC HEI - { 0x2CD4, 0x2CD5 }, // COPTIC CAPITAL LETTER OLD COPTIC HAT - { 0x2CD6, 0x2CD7 }, // COPTIC CAPITAL LETTER OLD COPTIC GANGIA - { 0x2CD8, 0x2CD9 }, // COPTIC CAPITAL LETTER OLD COPTIC DJA - { 0x2CDA, 0x2CDB }, // COPTIC CAPITAL LETTER OLD COPTIC SHIMA - { 0x2CDC, 0x2CDD }, // COPTIC CAPITAL LETTER OLD NUBIAN SHIMA - { 0x2CDE, 0x2CDF }, // COPTIC CAPITAL LETTER OLD NUBIAN NGI - { 0x2CE0, 0x2CE1 }, // COPTIC CAPITAL LETTER OLD NUBIAN NYI - { 0x2CE2, 0x2CE3 }, // COPTIC CAPITAL LETTER OLD NUBIAN WAU - { 0x2CEB, 0x2CEC }, // COPTIC CAPITAL LETTER CRYPTOGRAMMIC SHEI - { 0x2CED, 0x2CEE }, // COPTIC CAPITAL LETTER CRYPTOGRAMMIC GANGIA - { 0xA640, 0xA641 }, // CYRILLIC CAPITAL LETTER ZEMLYA - { 0xA642, 0xA643 }, // CYRILLIC CAPITAL LETTER DZELO - { 0xA644, 0xA645 }, // CYRILLIC CAPITAL LETTER REVERSED DZE - { 0xA646, 0xA647 }, // CYRILLIC CAPITAL LETTER IOTA - { 0xA648, 0xA649 }, // CYRILLIC CAPITAL LETTER DJERV - { 0xA64A, 0xA64B }, // CYRILLIC CAPITAL LETTER MONOGRAPH UK - { 0xA64C, 0xA64D }, // CYRILLIC CAPITAL LETTER BROAD OMEGA - { 0xA64E, 0xA64F }, // CYRILLIC CAPITAL LETTER NEUTRAL YER - { 0xA650, 0xA651 }, // CYRILLIC CAPITAL LETTER YERU WITH BACK YER - { 0xA652, 0xA653 }, // CYRILLIC CAPITAL LETTER IOTIFIED YAT - { 0xA654, 0xA655 }, // CYRILLIC CAPITAL LETTER REVERSED YU - { 0xA656, 0xA657 }, // CYRILLIC CAPITAL LETTER IOTIFIED A - { 0xA658, 0xA659 }, // CYRILLIC CAPITAL LETTER CLOSED LITTLE YUS - { 0xA65A, 0xA65B }, // CYRILLIC CAPITAL LETTER BLENDED YUS - { 0xA65C, 0xA65D }, // CYRILLIC CAPITAL LETTER IOTIFIED CLOSED LITTLE YUS - { 0xA65E, 0xA65F }, // CYRILLIC CAPITAL LETTER YN - { 0xA662, 0xA663 }, // CYRILLIC CAPITAL LETTER SOFT DE - { 0xA664, 0xA665 }, // CYRILLIC CAPITAL LETTER SOFT EL - { 0xA666, 0xA667 }, // CYRILLIC CAPITAL LETTER SOFT EM - { 0xA668, 0xA669 }, // CYRILLIC CAPITAL LETTER MONOCULAR O - { 0xA66A, 0xA66B }, // CYRILLIC CAPITAL LETTER BINOCULAR O - { 0xA66C, 0xA66D }, // CYRILLIC CAPITAL LETTER DOUBLE MONOCULAR O - { 0xA680, 0xA681 }, // CYRILLIC CAPITAL LETTER DWE - { 0xA682, 0xA683 }, // CYRILLIC CAPITAL LETTER DZWE - { 0xA684, 0xA685 }, // CYRILLIC CAPITAL LETTER ZHWE - { 0xA686, 0xA687 }, // CYRILLIC CAPITAL LETTER CCHE - { 0xA688, 0xA689 }, // CYRILLIC CAPITAL LETTER DZZE - { 0xA68A, 0xA68B }, // CYRILLIC CAPITAL LETTER TE WITH MIDDLE HOOK - { 0xA68C, 0xA68D }, // CYRILLIC CAPITAL LETTER TWE - { 0xA68E, 0xA68F }, // CYRILLIC CAPITAL LETTER TSWE - { 0xA690, 0xA691 }, // CYRILLIC CAPITAL LETTER TSSE - { 0xA692, 0xA693 }, // CYRILLIC CAPITAL LETTER TCHE - { 0xA694, 0xA695 }, // CYRILLIC CAPITAL LETTER HWE - { 0xA696, 0xA697 }, // CYRILLIC CAPITAL LETTER SHWE - { 0xA722, 0xA723 }, // LATIN CAPITAL LETTER EGYPTOLOGICAL ALEF - { 0xA724, 0xA725 }, // LATIN CAPITAL LETTER EGYPTOLOGICAL AIN - { 0xA726, 0xA727 }, // LATIN CAPITAL LETTER HENG - { 0xA728, 0xA729 }, // LATIN CAPITAL LETTER TZ - { 0xA72A, 0xA72B }, // LATIN CAPITAL LETTER TRESILLO - { 0xA72C, 0xA72D }, // LATIN CAPITAL LETTER CUATRILLO - { 0xA72E, 0xA72F }, // LATIN CAPITAL LETTER CUATRILLO WITH COMMA - { 0xA732, 0xA733 }, // LATIN CAPITAL LETTER AA - { 0xA734, 0xA735 }, // LATIN CAPITAL LETTER AO - { 0xA736, 0xA737 }, // LATIN CAPITAL LETTER AU - { 0xA738, 0xA739 }, // LATIN CAPITAL LETTER AV - { 0xA73A, 0xA73B }, // LATIN CAPITAL LETTER AV WITH HORIZONTAL BAR - { 0xA73C, 0xA73D }, // LATIN CAPITAL LETTER AY - { 0xA73E, 0xA73F }, // LATIN CAPITAL LETTER REVERSED C WITH DOT - { 0xA740, 0xA741 }, // LATIN CAPITAL LETTER K WITH STROKE - { 0xA742, 0xA743 }, // LATIN CAPITAL LETTER K WITH DIAGONAL STROKE - { 0xA744, 0xA745 }, // LATIN CAPITAL LETTER K WITH STROKE AND DIAGONAL STROKE - { 0xA746, 0xA747 }, // LATIN CAPITAL LETTER BROKEN L - { 0xA748, 0xA749 }, // LATIN CAPITAL LETTER L WITH HIGH STROKE - { 0xA74A, 0xA74B }, // LATIN CAPITAL LETTER O WITH LONG STROKE OVERLAY - { 0xA74C, 0xA74D }, // LATIN CAPITAL LETTER O WITH LOOP - { 0xA74E, 0xA74F }, // LATIN CAPITAL LETTER OO - { 0xA750, 0xA751 }, // LATIN CAPITAL LETTER P WITH STROKE THROUGH DESCENDER - { 0xA752, 0xA753 }, // LATIN CAPITAL LETTER P WITH FLOURISH - { 0xA754, 0xA755 }, // LATIN CAPITAL LETTER P WITH SQUIRREL TAIL - { 0xA756, 0xA757 }, // LATIN CAPITAL LETTER Q WITH STROKE THROUGH DESCENDER - { 0xA758, 0xA759 }, // LATIN CAPITAL LETTER Q WITH DIAGONAL STROKE - { 0xA75A, 0xA75B }, // LATIN CAPITAL LETTER R ROTUNDA - { 0xA75C, 0xA75D }, // LATIN CAPITAL LETTER RUM ROTUNDA - { 0xA75E, 0xA75F }, // LATIN CAPITAL LETTER V WITH DIAGONAL STROKE - { 0xA760, 0xA761 }, // LATIN CAPITAL LETTER VY - { 0xA762, 0xA763 }, // LATIN CAPITAL LETTER VISIGOTHIC Z - { 0xA764, 0xA765 }, // LATIN CAPITAL LETTER THORN WITH STROKE - { 0xA766, 0xA767 }, // LATIN CAPITAL LETTER THORN WITH STROKE THROUGH DESCENDER - { 0xA768, 0xA769 }, // LATIN CAPITAL LETTER VEND - { 0xA76A, 0xA76B }, // LATIN CAPITAL LETTER ET - { 0xA76C, 0xA76D }, // LATIN CAPITAL LETTER IS - { 0xA76E, 0xA76F }, // LATIN CAPITAL LETTER CON - { 0xA779, 0xA77A }, // LATIN CAPITAL LETTER INSULAR D - { 0xA77B, 0xA77C }, // LATIN CAPITAL LETTER INSULAR F - { 0xA77D, 0x1D79 }, // LATIN CAPITAL LETTER INSULAR G - { 0xA77E, 0xA77F }, // LATIN CAPITAL LETTER TURNED INSULAR G - { 0xA780, 0xA781 }, // LATIN CAPITAL LETTER TURNED L - { 0xA782, 0xA783 }, // LATIN CAPITAL LETTER INSULAR R - { 0xA784, 0xA785 }, // LATIN CAPITAL LETTER INSULAR S - { 0xA786, 0xA787 }, // LATIN CAPITAL LETTER INSULAR T - { 0xA78B, 0xA78C }, // LATIN CAPITAL LETTER SALTILLO - { 0xFF21, 0xFF41 }, // FULLWIDTH LATIN CAPITAL LETTER A - { 0xFF22, 0xFF42 }, // FULLWIDTH LATIN CAPITAL LETTER B - { 0xFF23, 0xFF43 }, // FULLWIDTH LATIN CAPITAL LETTER C - { 0xFF24, 0xFF44 }, // FULLWIDTH LATIN CAPITAL LETTER D - { 0xFF25, 0xFF45 }, // FULLWIDTH LATIN CAPITAL LETTER E - { 0xFF26, 0xFF46 }, // FULLWIDTH LATIN CAPITAL LETTER F - { 0xFF27, 0xFF47 }, // FULLWIDTH LATIN CAPITAL LETTER G - { 0xFF28, 0xFF48 }, // FULLWIDTH LATIN CAPITAL LETTER H - { 0xFF29, 0xFF49 }, // FULLWIDTH LATIN CAPITAL LETTER I - { 0xFF2A, 0xFF4A }, // FULLWIDTH LATIN CAPITAL LETTER J - { 0xFF2B, 0xFF4B }, // FULLWIDTH LATIN CAPITAL LETTER K - { 0xFF2C, 0xFF4C }, // FULLWIDTH LATIN CAPITAL LETTER L - { 0xFF2D, 0xFF4D }, // FULLWIDTH LATIN CAPITAL LETTER M - { 0xFF2E, 0xFF4E }, // FULLWIDTH LATIN CAPITAL LETTER N - { 0xFF2F, 0xFF4F }, // FULLWIDTH LATIN CAPITAL LETTER O - { 0xFF30, 0xFF50 }, // FULLWIDTH LATIN CAPITAL LETTER P - { 0xFF31, 0xFF51 }, // FULLWIDTH LATIN CAPITAL LETTER Q - { 0xFF32, 0xFF52 }, // FULLWIDTH LATIN CAPITAL LETTER R - { 0xFF33, 0xFF53 }, // FULLWIDTH LATIN CAPITAL LETTER S - { 0xFF34, 0xFF54 }, // FULLWIDTH LATIN CAPITAL LETTER T - { 0xFF35, 0xFF55 }, // FULLWIDTH LATIN CAPITAL LETTER U - { 0xFF36, 0xFF56 }, // FULLWIDTH LATIN CAPITAL LETTER V - { 0xFF37, 0xFF57 }, // FULLWIDTH LATIN CAPITAL LETTER W - { 0xFF38, 0xFF58 }, // FULLWIDTH LATIN CAPITAL LETTER X - { 0xFF39, 0xFF59 }, // FULLWIDTH LATIN CAPITAL LETTER Y - { 0xFF3A, 0xFF5A } // FULLWIDTH LATIN CAPITAL LETTER Z -}; - -static int compare_pair_capital(const void *a, const void *b) { - return (int)(*(unsigned short *)a) - - (int)((struct LatinCapitalSmallPair*)b)->capital; -} - -unsigned short latin_tolower(unsigned short c) { - struct LatinCapitalSmallPair *p = - (struct LatinCapitalSmallPair *)bsearch(&c, SORTED_CHAR_MAP, - sizeof(SORTED_CHAR_MAP) / sizeof(SORTED_CHAR_MAP[0]), - sizeof(SORTED_CHAR_MAP[0]), - compare_pair_capital); - return p ? p->small : c; -} - -} // namespace latinime diff --git a/native/src/char_utils.h b/native/src/char_utils.h deleted file mode 100644 index 607dc5195..000000000 --- a/native/src/char_utils.h +++ /dev/null @@ -1,65 +0,0 @@ -/* - * Copyright (C) 2010 The Android Open Source Project - * - * Licensed under the Apache License, Version 2.0 (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.apache.org/licenses/LICENSE-2.0 - * - * Unless required by applicable law or agreed to in writing, software - * distributed under the License is distributed on an "AS IS" BASIS, - * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. - * See the License for the specific language governing permissions and - * limitations under the License. - */ - -#ifndef LATINIME_CHAR_UTILS_H -#define LATINIME_CHAR_UTILS_H - -namespace latinime { - -inline static int isAsciiUpper(unsigned short c) { - return c >= 'A' && c <= 'Z'; -} - -inline static unsigned short toAsciiLower(unsigned short c) { - return c - 'A' + 'a'; -} - -inline static int isAscii(unsigned short c) { - return c <= 127; -} - -unsigned short latin_tolower(unsigned short c); - -/** - * Table mapping most combined Latin, Greek, and Cyrillic characters - * to their base characters. If c is in range, BASE_CHARS[c] == c - * if c is not a combined character, or the base character if it - * is combined. - */ - -static const int BASE_CHARS_SIZE = 0x0500; -extern const unsigned short BASE_CHARS[BASE_CHARS_SIZE]; - -inline static unsigned short toBaseChar(unsigned short c) { - if (c < BASE_CHARS_SIZE) { - return BASE_CHARS[c]; - } - return c; -} - -inline static unsigned short toBaseLowerCase(unsigned short c) { - c = toBaseChar(c); - if (isAsciiUpper(c)) { - return toAsciiLower(c); - } else if (isAscii(c)) { - return c; - } - return latin_tolower(c); -} - -} // namespace latinime - -#endif // LATINIME_CHAR_UTILS_H diff --git a/native/src/correction.cpp b/native/src/correction.cpp deleted file mode 100644 index 087219ed4..000000000 --- a/native/src/correction.cpp +++ /dev/null @@ -1,1143 +0,0 @@ -/* - * Copyright (C) 2011 The Android Open Source Project - * - * Licensed under the Apache License, Version 2.0 (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.apache.org/licenses/LICENSE-2.0 - * - * Unless required by applicable law or agreed to in writing, software - * distributed under the License is distributed on an "AS IS" BASIS, - * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. - * See the License for the specific language governing permissions and - * limitations under the License. - */ - -#include <assert.h> -#include <ctype.h> -#include <math.h> -#include <stdio.h> -#include <string.h> - -#define LOG_TAG "LatinIME: correction.cpp" - -#include "char_utils.h" -#include "correction.h" -#include "defines.h" -#include "dictionary.h" -#include "proximity_info.h" - -namespace latinime { - -///////////////////////////// -// edit distance funcitons // -///////////////////////////// - -inline static void initEditDistance(int *editDistanceTable) { - for (int i = 0; i <= MAX_WORD_LENGTH_INTERNAL; ++i) { - editDistanceTable[i] = i; - } -} - -inline static void dumpEditDistance10ForDebug(int *editDistanceTable, - const int editDistanceTableWidth, const int outputLength) { - if (DEBUG_DICT) { - AKLOGI("EditDistanceTable"); - for (int i = 0; i <= 10; ++i) { - int c[11]; - for (int j = 0; j <= 10; ++j) { - if (j < editDistanceTableWidth + 1 && i < outputLength + 1) { - c[j] = (editDistanceTable + i * (editDistanceTableWidth + 1))[j]; - } else { - c[j] = -1; - } - } - AKLOGI("[ %d, %d, %d, %d, %d, %d, %d, %d, %d, %d, %d ]", - c[0], c[1], c[2], c[3], c[4], c[5], c[6], c[7], c[8], c[9], c[10]); - } - } -} - -inline static void calcEditDistanceOneStep(int *editDistanceTable, const unsigned short *input, - const int inputLength, const unsigned short *output, const int outputLength) { - // TODO: Make sure that editDistance[0 ~ MAX_WORD_LENGTH_INTERNAL] is not touched. - // Let dp[i][j] be editDistanceTable[i * (inputLength + 1) + j]. - // Assuming that dp[0][0] ... dp[outputLength - 1][inputLength] are already calculated, - // and calculate dp[ouputLength][0] ... dp[outputLength][inputLength]. - int *const current = editDistanceTable + outputLength * (inputLength + 1); - const int *const prev = editDistanceTable + (outputLength - 1) * (inputLength + 1); - const int *const prevprev = - outputLength >= 2 ? editDistanceTable + (outputLength - 2) * (inputLength + 1) : 0; - current[0] = outputLength; - const uint32_t co = toBaseLowerCase(output[outputLength - 1]); - const uint32_t prevCO = outputLength >= 2 ? toBaseLowerCase(output[outputLength - 2]) : 0; - for (int i = 1; i <= inputLength; ++i) { - const uint32_t ci = toBaseLowerCase(input[i - 1]); - const uint16_t cost = (ci == co) ? 0 : 1; - current[i] = min(current[i - 1] + 1, min(prev[i] + 1, prev[i - 1] + cost)); - if (i >= 2 && prevprev && ci == prevCO && co == toBaseLowerCase(input[i - 2])) { - current[i] = min(current[i], prevprev[i - 2] + 1); - } - } -} - -inline static int getCurrentEditDistance(int *editDistanceTable, const int editDistanceTableWidth, - const int outputLength, const int inputLength) { - if (DEBUG_EDIT_DISTANCE) { - AKLOGI("getCurrentEditDistance %d, %d", inputLength, outputLength); - } - return editDistanceTable[(editDistanceTableWidth + 1) * (outputLength) + inputLength]; -} - -////////////////////// -// inline functions // -////////////////////// -static const char QUOTE = '\''; - -inline bool Correction::isQuote(const unsigned short c) { - const unsigned short userTypedChar = mProximityInfo->getPrimaryCharAt(mInputIndex); - return (c == QUOTE && userTypedChar != QUOTE); -} - -//////////////// -// Correction // -//////////////// - -Correction::Correction(const int typedLetterMultiplier, const int fullWordMultiplier) - : TYPED_LETTER_MULTIPLIER(typedLetterMultiplier), FULL_WORD_MULTIPLIER(fullWordMultiplier) { - initEditDistance(mEditDistanceTable); -} - -void Correction::initCorrection(const ProximityInfo *pi, const int inputLength, - const int maxDepth) { - mProximityInfo = pi; - mInputLength = inputLength; - mMaxDepth = maxDepth; - mMaxEditDistance = mInputLength < 5 ? 2 : mInputLength / 2; - // TODO: This is not supposed to be required. Check what's going wrong with - // editDistance[0 ~ MAX_WORD_LENGTH_INTERNAL] - initEditDistance(mEditDistanceTable); -} - -void Correction::initCorrectionState( - const int rootPos, const int childCount, const bool traverseAll) { - latinime::initCorrectionState(mCorrectionStates, rootPos, childCount, traverseAll); - // TODO: remove - mCorrectionStates[0].mTransposedPos = mTransposedPos; - mCorrectionStates[0].mExcessivePos = mExcessivePos; - mCorrectionStates[0].mSkipPos = mSkipPos; -} - -void Correction::setCorrectionParams(const int skipPos, const int excessivePos, - const int transposedPos, const int spaceProximityPos, const int missingSpacePos, - const bool useFullEditDistance, const bool doAutoCompletion, const int maxErrors) { - // TODO: remove - mTransposedPos = transposedPos; - mExcessivePos = excessivePos; - mSkipPos = skipPos; - // TODO: remove - mCorrectionStates[0].mTransposedPos = transposedPos; - mCorrectionStates[0].mExcessivePos = excessivePos; - mCorrectionStates[0].mSkipPos = skipPos; - - mSpaceProximityPos = spaceProximityPos; - mMissingSpacePos = missingSpacePos; - mUseFullEditDistance = useFullEditDistance; - mDoAutoCompletion = doAutoCompletion; - mMaxErrors = maxErrors; -} - -void Correction::checkState() { - if (DEBUG_DICT) { - int inputCount = 0; - if (mSkipPos >= 0) ++inputCount; - if (mExcessivePos >= 0) ++inputCount; - if (mTransposedPos >= 0) ++inputCount; - // TODO: remove this assert - assert(inputCount <= 1); - } -} - -int Correction::getFreqForSplitMultipleWords(const int *freqArray, const int *wordLengthArray, - const int wordCount, const bool isSpaceProximity, const unsigned short *word) { - return Correction::RankingAlgorithm::calcFreqForSplitMultipleWords(freqArray, wordLengthArray, - wordCount, this, isSpaceProximity, word); -} - -int Correction::getFinalFreq(const int freq, unsigned short **word, int *wordLength) { - return getFinalFreqInternal(freq, word, wordLength, mInputLength); -} - -int Correction::getFinalFreqForSubQueue(const int freq, unsigned short **word, int *wordLength, - const int inputLength) { - return getFinalFreqInternal(freq, word, wordLength, inputLength); -} - -int Correction::getFinalFreqInternal(const int freq, unsigned short **word, int *wordLength, - const int inputLength) { - const int outputIndex = mTerminalOutputIndex; - const int inputIndex = mTerminalInputIndex; - *wordLength = outputIndex + 1; - if (outputIndex < MIN_SUGGEST_DEPTH) { - return NOT_A_FREQUENCY; - } - - *word = mWord; - int finalFreq = Correction::RankingAlgorithm::calculateFinalFreq( - inputIndex, outputIndex, freq, mEditDistanceTable, this, inputLength); - return finalFreq; -} - -bool Correction::initProcessState(const int outputIndex) { - if (mCorrectionStates[outputIndex].mChildCount <= 0) { - return false; - } - mOutputIndex = outputIndex; - --(mCorrectionStates[outputIndex].mChildCount); - mInputIndex = mCorrectionStates[outputIndex].mInputIndex; - mNeedsToTraverseAllNodes = mCorrectionStates[outputIndex].mNeedsToTraverseAllNodes; - - mEquivalentCharCount = mCorrectionStates[outputIndex].mEquivalentCharCount; - mProximityCount = mCorrectionStates[outputIndex].mProximityCount; - mTransposedCount = mCorrectionStates[outputIndex].mTransposedCount; - mExcessiveCount = mCorrectionStates[outputIndex].mExcessiveCount; - mSkippedCount = mCorrectionStates[outputIndex].mSkippedCount; - mLastCharExceeded = mCorrectionStates[outputIndex].mLastCharExceeded; - - mTransposedPos = mCorrectionStates[outputIndex].mTransposedPos; - mExcessivePos = mCorrectionStates[outputIndex].mExcessivePos; - mSkipPos = mCorrectionStates[outputIndex].mSkipPos; - - mMatching = false; - mProximityMatching = false; - mAdditionalProximityMatching = false; - mTransposing = false; - mExceeding = false; - mSkipping = false; - - return true; -} - -int Correction::goDownTree( - const int parentIndex, const int childCount, const int firstChildPos) { - mCorrectionStates[mOutputIndex].mParentIndex = parentIndex; - mCorrectionStates[mOutputIndex].mChildCount = childCount; - mCorrectionStates[mOutputIndex].mSiblingPos = firstChildPos; - return mOutputIndex; -} - -// TODO: remove -int Correction::getInputIndex() { - return mInputIndex; -} - -void Correction::incrementInputIndex() { - ++mInputIndex; -} - -void Correction::incrementOutputIndex() { - ++mOutputIndex; - mCorrectionStates[mOutputIndex].mParentIndex = mCorrectionStates[mOutputIndex - 1].mParentIndex; - mCorrectionStates[mOutputIndex].mChildCount = mCorrectionStates[mOutputIndex - 1].mChildCount; - mCorrectionStates[mOutputIndex].mSiblingPos = mCorrectionStates[mOutputIndex - 1].mSiblingPos; - mCorrectionStates[mOutputIndex].mInputIndex = mInputIndex; - mCorrectionStates[mOutputIndex].mNeedsToTraverseAllNodes = mNeedsToTraverseAllNodes; - - mCorrectionStates[mOutputIndex].mEquivalentCharCount = mEquivalentCharCount; - mCorrectionStates[mOutputIndex].mProximityCount = mProximityCount; - mCorrectionStates[mOutputIndex].mTransposedCount = mTransposedCount; - mCorrectionStates[mOutputIndex].mExcessiveCount = mExcessiveCount; - mCorrectionStates[mOutputIndex].mSkippedCount = mSkippedCount; - - mCorrectionStates[mOutputIndex].mSkipPos = mSkipPos; - mCorrectionStates[mOutputIndex].mTransposedPos = mTransposedPos; - mCorrectionStates[mOutputIndex].mExcessivePos = mExcessivePos; - - mCorrectionStates[mOutputIndex].mLastCharExceeded = mLastCharExceeded; - - mCorrectionStates[mOutputIndex].mMatching = mMatching; - mCorrectionStates[mOutputIndex].mProximityMatching = mProximityMatching; - mCorrectionStates[mOutputIndex].mAdditionalProximityMatching = mAdditionalProximityMatching; - mCorrectionStates[mOutputIndex].mTransposing = mTransposing; - mCorrectionStates[mOutputIndex].mExceeding = mExceeding; - mCorrectionStates[mOutputIndex].mSkipping = mSkipping; -} - -void Correction::startToTraverseAllNodes() { - mNeedsToTraverseAllNodes = true; -} - -bool Correction::needsToPrune() const { - // TODO: use edit distance here - return mOutputIndex - 1 >= mMaxDepth || mProximityCount > mMaxEditDistance - // Allow one char longer word for missing character - || (!mDoAutoCompletion && (mOutputIndex > mInputLength)); -} - -void Correction::addCharToCurrentWord(const int32_t c) { - mWord[mOutputIndex] = c; - const unsigned short *primaryInputWord = mProximityInfo->getPrimaryInputWord(); - calcEditDistanceOneStep(mEditDistanceTable, primaryInputWord, mInputLength, - mWord, mOutputIndex + 1); -} - -Correction::CorrectionType Correction::processSkipChar( - const int32_t c, const bool isTerminal, const bool inputIndexIncremented) { - addCharToCurrentWord(c); - mTerminalInputIndex = mInputIndex - (inputIndexIncremented ? 1 : 0); - mTerminalOutputIndex = mOutputIndex; - if (mNeedsToTraverseAllNodes && isTerminal) { - incrementOutputIndex(); - return TRAVERSE_ALL_ON_TERMINAL; - } else { - incrementOutputIndex(); - return TRAVERSE_ALL_NOT_ON_TERMINAL; - } -} - -Correction::CorrectionType Correction::processUnrelatedCorrectionType() { - // Needs to set mTerminalInputIndex and mTerminalOutputIndex before returning any CorrectionType - mTerminalInputIndex = mInputIndex; - mTerminalOutputIndex = mOutputIndex; - return UNRELATED; -} - -inline bool isEquivalentChar(ProximityInfo::ProximityType type) { - return type == ProximityInfo::EQUIVALENT_CHAR; -} - -inline bool isProximityCharOrEquivalentChar(ProximityInfo::ProximityType type) { - return type == ProximityInfo::EQUIVALENT_CHAR - || type == ProximityInfo::NEAR_PROXIMITY_CHAR; -} - -Correction::CorrectionType Correction::processCharAndCalcState( - const int32_t c, const bool isTerminal) { - const int correctionCount = (mSkippedCount + mExcessiveCount + mTransposedCount); - if (correctionCount > mMaxErrors) { - return processUnrelatedCorrectionType(); - } - - // TODO: Change the limit if we'll allow two or more corrections - const bool noCorrectionsHappenedSoFar = correctionCount == 0; - const bool canTryCorrection = noCorrectionsHappenedSoFar; - int proximityIndex = 0; - mDistances[mOutputIndex] = NOT_A_DISTANCE; - - // Skip checking this node - if (mNeedsToTraverseAllNodes || isQuote(c)) { - bool incremented = false; - if (mLastCharExceeded && mInputIndex == mInputLength - 1) { - // TODO: Do not check the proximity if EditDistance exceeds the threshold - const ProximityInfo::ProximityType matchId = - mProximityInfo->getMatchedProximityId(mInputIndex, c, true, &proximityIndex); - if (isEquivalentChar(matchId)) { - mLastCharExceeded = false; - --mExcessiveCount; - mDistances[mOutputIndex] = - mProximityInfo->getNormalizedSquaredDistance(mInputIndex, 0); - } else if (matchId == ProximityInfo::NEAR_PROXIMITY_CHAR) { - mLastCharExceeded = false; - --mExcessiveCount; - ++mProximityCount; - mDistances[mOutputIndex] = - mProximityInfo->getNormalizedSquaredDistance(mInputIndex, proximityIndex); - } - incrementInputIndex(); - incremented = true; - } - return processSkipChar(c, isTerminal, incremented); - } - - // Check possible corrections. - if (mExcessivePos >= 0) { - if (mExcessiveCount == 0 && mExcessivePos < mOutputIndex) { - mExcessivePos = mOutputIndex; - } - if (mExcessivePos < mInputLength - 1) { - mExceeding = mExcessivePos == mInputIndex && canTryCorrection; - } - } - - if (mSkipPos >= 0) { - if (mSkippedCount == 0 && mSkipPos < mOutputIndex) { - if (DEBUG_DICT) { - assert(mSkipPos == mOutputIndex - 1); - } - mSkipPos = mOutputIndex; - } - mSkipping = mSkipPos == mOutputIndex && canTryCorrection; - } - - if (mTransposedPos >= 0) { - if (mTransposedCount == 0 && mTransposedPos < mOutputIndex) { - mTransposedPos = mOutputIndex; - } - if (mTransposedPos < mInputLength - 1) { - mTransposing = mInputIndex == mTransposedPos && canTryCorrection; - } - } - - bool secondTransposing = false; - if (mTransposedCount % 2 == 1) { - if (isEquivalentChar(mProximityInfo->getMatchedProximityId(mInputIndex - 1, c, false))) { - ++mTransposedCount; - secondTransposing = true; - } else if (mCorrectionStates[mOutputIndex].mExceeding) { - --mTransposedCount; - ++mExcessiveCount; - --mExcessivePos; - incrementInputIndex(); - } else { - --mTransposedCount; - if (DEBUG_CORRECTION - && (INPUTLENGTH_FOR_DEBUG <= 0 || INPUTLENGTH_FOR_DEBUG == mInputLength) - && (MIN_OUTPUT_INDEX_FOR_DEBUG <= 0 - || MIN_OUTPUT_INDEX_FOR_DEBUG < mOutputIndex)) { - DUMP_WORD(mWord, mOutputIndex); - AKLOGI("UNRELATED(0): %d, %d, %d, %d, %c", mProximityCount, mSkippedCount, - mTransposedCount, mExcessiveCount, c); - } - return processUnrelatedCorrectionType(); - } - } - - // TODO: Change the limit if we'll allow two or more proximity chars with corrections - // Work around: When the mMaxErrors is 1, we only allow just one error - // including proximity correction. - const bool checkProximityChars = (mMaxErrors > 1) - ? (noCorrectionsHappenedSoFar || mProximityCount == 0) - : (noCorrectionsHappenedSoFar && mProximityCount == 0); - - ProximityInfo::ProximityType matchedProximityCharId = secondTransposing - ? ProximityInfo::EQUIVALENT_CHAR - : mProximityInfo->getMatchedProximityId( - mInputIndex, c, checkProximityChars, &proximityIndex); - - if (ProximityInfo::UNRELATED_CHAR == matchedProximityCharId - || ProximityInfo::ADDITIONAL_PROXIMITY_CHAR == matchedProximityCharId) { - if (canTryCorrection && mOutputIndex > 0 - && mCorrectionStates[mOutputIndex].mProximityMatching - && mCorrectionStates[mOutputIndex].mExceeding - && isEquivalentChar(mProximityInfo->getMatchedProximityId( - mInputIndex, mWord[mOutputIndex - 1], false))) { - if (DEBUG_CORRECTION - && (INPUTLENGTH_FOR_DEBUG <= 0 || INPUTLENGTH_FOR_DEBUG == mInputLength) - && (MIN_OUTPUT_INDEX_FOR_DEBUG <= 0 - || MIN_OUTPUT_INDEX_FOR_DEBUG < mOutputIndex)) { - AKLOGI("CONVERSION p->e %c", mWord[mOutputIndex - 1]); - } - // Conversion p->e - // Example: - // wearth -> earth - // px -> (E)mmmmm - ++mExcessiveCount; - --mProximityCount; - mExcessivePos = mOutputIndex - 1; - ++mInputIndex; - // Here, we are doing something equivalent to matchedProximityCharId, - // but we already know that "excessive char correction" just happened - // so that we just need to check "mProximityCount == 0". - matchedProximityCharId = mProximityInfo->getMatchedProximityId( - mInputIndex, c, mProximityCount == 0, &proximityIndex); - } - } - - if (ProximityInfo::UNRELATED_CHAR == matchedProximityCharId - || ProximityInfo::ADDITIONAL_PROXIMITY_CHAR == matchedProximityCharId) { - if (ProximityInfo::ADDITIONAL_PROXIMITY_CHAR == matchedProximityCharId) { - mAdditionalProximityMatching = true; - } - // TODO: Optimize - // As the current char turned out to be an unrelated char, - // we will try other correction-types. Please note that mCorrectionStates[mOutputIndex] - // here refers to the previous state. - if (mInputIndex < mInputLength - 1 && mOutputIndex > 0 && mTransposedCount > 0 - && !mCorrectionStates[mOutputIndex].mTransposing - && mCorrectionStates[mOutputIndex - 1].mTransposing - && isEquivalentChar(mProximityInfo->getMatchedProximityId( - mInputIndex, mWord[mOutputIndex - 1], false)) - && isEquivalentChar( - mProximityInfo->getMatchedProximityId(mInputIndex + 1, c, false))) { - // Conversion t->e - // Example: - // occaisional -> occa sional - // mmmmttx -> mmmm(E)mmmmmm - mTransposedCount -= 2; - ++mExcessiveCount; - ++mInputIndex; - } else if (mOutputIndex > 0 && mInputIndex > 0 && mTransposedCount > 0 - && !mCorrectionStates[mOutputIndex].mTransposing - && mCorrectionStates[mOutputIndex - 1].mTransposing - && isEquivalentChar( - mProximityInfo->getMatchedProximityId(mInputIndex - 1, c, false))) { - // Conversion t->s - // Example: - // chcolate -> chocolate - // mmttx -> mmsmmmmmm - mTransposedCount -= 2; - ++mSkippedCount; - --mInputIndex; - } else if (canTryCorrection && mInputIndex > 0 - && mCorrectionStates[mOutputIndex].mProximityMatching - && mCorrectionStates[mOutputIndex].mSkipping - && isEquivalentChar( - mProximityInfo->getMatchedProximityId(mInputIndex - 1, c, false))) { - // Conversion p->s - // Note: This logic tries saving cases like contrst --> contrast -- "a" is one of - // proximity chars of "s", but it should rather be handled as a skipped char. - ++mSkippedCount; - --mProximityCount; - return processSkipChar(c, isTerminal, false); - } else if (mInputIndex - 1 < mInputLength - && mSkippedCount > 0 - && mCorrectionStates[mOutputIndex].mSkipping - && mCorrectionStates[mOutputIndex].mAdditionalProximityMatching - && isProximityCharOrEquivalentChar( - mProximityInfo->getMatchedProximityId(mInputIndex + 1, c, false))) { - // Conversion s->a - incrementInputIndex(); - --mSkippedCount; - mProximityMatching = true; - ++mProximityCount; - mDistances[mOutputIndex] = ADDITIONAL_PROXIMITY_CHAR_DISTANCE_INFO; - } else if ((mExceeding || mTransposing) && mInputIndex - 1 < mInputLength - && isEquivalentChar( - mProximityInfo->getMatchedProximityId(mInputIndex + 1, c, false))) { - // 1.2. Excessive or transpose correction - if (mTransposing) { - ++mTransposedCount; - } else { - ++mExcessiveCount; - incrementInputIndex(); - } - if (DEBUG_CORRECTION - && (INPUTLENGTH_FOR_DEBUG <= 0 || INPUTLENGTH_FOR_DEBUG == mInputLength) - && (MIN_OUTPUT_INDEX_FOR_DEBUG <= 0 - || MIN_OUTPUT_INDEX_FOR_DEBUG < mOutputIndex)) { - DUMP_WORD(mWord, mOutputIndex); - if (mTransposing) { - AKLOGI("TRANSPOSE: %d, %d, %d, %d, %c", mProximityCount, mSkippedCount, - mTransposedCount, mExcessiveCount, c); - } else { - AKLOGI("EXCEED: %d, %d, %d, %d, %c", mProximityCount, mSkippedCount, - mTransposedCount, mExcessiveCount, c); - } - } - } else if (mSkipping) { - // 3. Skip correction - ++mSkippedCount; - if (DEBUG_CORRECTION - && (INPUTLENGTH_FOR_DEBUG <= 0 || INPUTLENGTH_FOR_DEBUG == mInputLength) - && (MIN_OUTPUT_INDEX_FOR_DEBUG <= 0 - || MIN_OUTPUT_INDEX_FOR_DEBUG < mOutputIndex)) { - AKLOGI("SKIP: %d, %d, %d, %d, %c", mProximityCount, mSkippedCount, - mTransposedCount, mExcessiveCount, c); - } - return processSkipChar(c, isTerminal, false); - } else if (ProximityInfo::ADDITIONAL_PROXIMITY_CHAR == matchedProximityCharId) { - // As a last resort, use additional proximity characters - mProximityMatching = true; - ++mProximityCount; - mDistances[mOutputIndex] = ADDITIONAL_PROXIMITY_CHAR_DISTANCE_INFO; - if (DEBUG_CORRECTION - && (INPUTLENGTH_FOR_DEBUG <= 0 || INPUTLENGTH_FOR_DEBUG == mInputLength) - && (MIN_OUTPUT_INDEX_FOR_DEBUG <= 0 - || MIN_OUTPUT_INDEX_FOR_DEBUG < mOutputIndex)) { - AKLOGI("ADDITIONALPROX: %d, %d, %d, %d, %c", mProximityCount, mSkippedCount, - mTransposedCount, mExcessiveCount, c); - } - } else { - if (DEBUG_CORRECTION - && (INPUTLENGTH_FOR_DEBUG <= 0 || INPUTLENGTH_FOR_DEBUG == mInputLength) - && (MIN_OUTPUT_INDEX_FOR_DEBUG <= 0 - || MIN_OUTPUT_INDEX_FOR_DEBUG < mOutputIndex)) { - DUMP_WORD(mWord, mOutputIndex); - AKLOGI("UNRELATED(1): %d, %d, %d, %d, %c", mProximityCount, mSkippedCount, - mTransposedCount, mExcessiveCount, c); - } - return processUnrelatedCorrectionType(); - } - } else if (secondTransposing) { - // If inputIndex is greater than mInputLength, that means there is no - // proximity chars. So, we don't need to check proximity. - mMatching = true; - } else if (isEquivalentChar(matchedProximityCharId)) { - mMatching = true; - ++mEquivalentCharCount; - mDistances[mOutputIndex] = mProximityInfo->getNormalizedSquaredDistance(mInputIndex, 0); - } else if (ProximityInfo::NEAR_PROXIMITY_CHAR == matchedProximityCharId) { - mProximityMatching = true; - ++mProximityCount; - mDistances[mOutputIndex] = - mProximityInfo->getNormalizedSquaredDistance(mInputIndex, proximityIndex); - if (DEBUG_CORRECTION - && (INPUTLENGTH_FOR_DEBUG <= 0 || INPUTLENGTH_FOR_DEBUG == mInputLength) - && (MIN_OUTPUT_INDEX_FOR_DEBUG <= 0 - || MIN_OUTPUT_INDEX_FOR_DEBUG < mOutputIndex)) { - AKLOGI("PROX: %d, %d, %d, %d, %c", mProximityCount, mSkippedCount, - mTransposedCount, mExcessiveCount, c); - } - } - - addCharToCurrentWord(c); - - // 4. Last char excessive correction - mLastCharExceeded = mExcessiveCount == 0 && mSkippedCount == 0 && mTransposedCount == 0 - && mProximityCount == 0 && (mInputIndex == mInputLength - 2); - const bool isSameAsUserTypedLength = (mInputLength == mInputIndex + 1) || mLastCharExceeded; - if (mLastCharExceeded) { - ++mExcessiveCount; - } - - // Start traversing all nodes after the index exceeds the user typed length - if (isSameAsUserTypedLength) { - startToTraverseAllNodes(); - } - - const bool needsToTryOnTerminalForTheLastPossibleExcessiveChar = - mExceeding && mInputIndex == mInputLength - 2; - - // Finally, we are ready to go to the next character, the next "virtual node". - // We should advance the input index. - // We do this in this branch of the 'if traverseAllNodes' because we are still matching - // characters to input; the other branch is not matching them but searching for - // completions, this is why it does not have to do it. - incrementInputIndex(); - // Also, the next char is one "virtual node" depth more than this char. - incrementOutputIndex(); - - if ((needsToTryOnTerminalForTheLastPossibleExcessiveChar - || isSameAsUserTypedLength) && isTerminal) { - mTerminalInputIndex = mInputIndex - 1; - mTerminalOutputIndex = mOutputIndex - 1; - if (DEBUG_CORRECTION - && (INPUTLENGTH_FOR_DEBUG <= 0 || INPUTLENGTH_FOR_DEBUG == mInputLength) - && (MIN_OUTPUT_INDEX_FOR_DEBUG <= 0 || MIN_OUTPUT_INDEX_FOR_DEBUG < mOutputIndex)) { - DUMP_WORD(mWord, mOutputIndex); - AKLOGI("ONTERMINAL(1): %d, %d, %d, %d, %c", mProximityCount, mSkippedCount, - mTransposedCount, mExcessiveCount, c); - } - return ON_TERMINAL; - } else { - mTerminalInputIndex = mInputIndex - 1; - mTerminalOutputIndex = mOutputIndex - 1; - return NOT_ON_TERMINAL; - } -} - -Correction::~Correction() { -} - -inline static int getQuoteCount(const unsigned short* word, const int length) { - int quoteCount = 0; - for (int i = 0; i < length; ++i) { - if(word[i] == '\'') { - ++quoteCount; - } - } - return quoteCount; -} - -inline static bool isUpperCase(unsigned short c) { - return isAsciiUpper(toBaseChar(c)); -} - -////////////////////// -// RankingAlgorithm // -////////////////////// - -/* static */ -int Correction::RankingAlgorithm::calculateFinalFreq(const int inputIndex, const int outputIndex, - const int freq, int* editDistanceTable, const Correction* correction, - const int inputLength) { - const int excessivePos = correction->getExcessivePos(); - const int typedLetterMultiplier = correction->TYPED_LETTER_MULTIPLIER; - const int fullWordMultiplier = correction->FULL_WORD_MULTIPLIER; - const ProximityInfo *proximityInfo = correction->mProximityInfo; - const int skippedCount = correction->mSkippedCount; - const int transposedCount = correction->mTransposedCount / 2; - const int excessiveCount = correction->mExcessiveCount + correction->mTransposedCount % 2; - const int proximityMatchedCount = correction->mProximityCount; - const bool lastCharExceeded = correction->mLastCharExceeded; - const bool useFullEditDistance = correction->mUseFullEditDistance; - const int outputLength = outputIndex + 1; - if (skippedCount >= inputLength || inputLength == 0) { - return -1; - } - - // TODO: find more robust way - bool sameLength = lastCharExceeded ? (inputLength == inputIndex + 2) - : (inputLength == inputIndex + 1); - - // TODO: use mExcessiveCount - const int matchCount = inputLength - correction->mProximityCount - excessiveCount; - - const unsigned short* word = correction->mWord; - const bool skipped = skippedCount > 0; - - const int quoteDiffCount = max(0, getQuoteCount(word, outputLength) - - getQuoteCount(proximityInfo->getPrimaryInputWord(), inputLength)); - - // TODO: Calculate edit distance for transposed and excessive - int ed = 0; - if (DEBUG_DICT_FULL) { - dumpEditDistance10ForDebug(editDistanceTable, correction->mInputLength, outputLength); - } - int adjustedProximityMatchedCount = proximityMatchedCount; - - int finalFreq = freq; - - if (DEBUG_CORRECTION_FREQ - && (INPUTLENGTH_FOR_DEBUG <= 0 || INPUTLENGTH_FOR_DEBUG == inputLength)) { - AKLOGI("FinalFreq0: %d", finalFreq); - } - // TODO: Optimize this. - if (transposedCount > 0 || proximityMatchedCount > 0 || skipped || excessiveCount > 0) { - ed = getCurrentEditDistance(editDistanceTable, correction->mInputLength, outputLength, - inputLength) - transposedCount; - - const int matchWeight = powerIntCapped(typedLetterMultiplier, - max(inputLength, outputLength) - ed); - multiplyIntCapped(matchWeight, &finalFreq); - - // TODO: Demote further if there are two or more excessive chars with longer user input? - if (inputLength > outputLength) { - multiplyRate(INPUT_EXCEEDS_OUTPUT_DEMOTION_RATE, &finalFreq); - } - - ed = max(0, ed - quoteDiffCount); - adjustedProximityMatchedCount = min(max(0, ed - (outputLength - inputLength)), - proximityMatchedCount); - if (transposedCount < 1) { - if (ed == 1 && (inputLength == outputLength - 1 || inputLength == outputLength + 1)) { - // Promote a word with just one skipped or excessive char - if (sameLength) { - multiplyRate(WORDS_WITH_JUST_ONE_CORRECTION_PROMOTION_RATE - + WORDS_WITH_JUST_ONE_CORRECTION_PROMOTION_MULTIPLIER * outputLength, - &finalFreq); - } else { - multiplyIntCapped(typedLetterMultiplier, &finalFreq); - } - } else if (ed == 0) { - multiplyIntCapped(typedLetterMultiplier, &finalFreq); - sameLength = true; - } - } - } else { - const int matchWeight = powerIntCapped(typedLetterMultiplier, matchCount); - multiplyIntCapped(matchWeight, &finalFreq); - } - - if (proximityInfo->getMatchedProximityId(0, word[0], true) - == ProximityInfo::UNRELATED_CHAR) { - multiplyRate(FIRST_CHAR_DIFFERENT_DEMOTION_RATE, &finalFreq); - } - - /////////////////////////////////////////////// - // Promotion and Demotion for each correction - - // Demotion for a word with missing character - if (skipped) { - const int demotionRate = WORDS_WITH_MISSING_CHARACTER_DEMOTION_RATE - * (10 * inputLength - WORDS_WITH_MISSING_CHARACTER_DEMOTION_START_POS_10X) - / (10 * inputLength - - WORDS_WITH_MISSING_CHARACTER_DEMOTION_START_POS_10X + 10); - if (DEBUG_DICT_FULL) { - AKLOGI("Demotion rate for missing character is %d.", demotionRate); - } - multiplyRate(demotionRate, &finalFreq); - } - - // Demotion for a word with transposed character - if (transposedCount > 0) multiplyRate( - WORDS_WITH_TRANSPOSED_CHARACTERS_DEMOTION_RATE, &finalFreq); - - // Demotion for a word with excessive character - if (excessiveCount > 0) { - multiplyRate(WORDS_WITH_EXCESSIVE_CHARACTER_DEMOTION_RATE, &finalFreq); - if (!lastCharExceeded && !proximityInfo->existsAdjacentProximityChars(excessivePos)) { - if (DEBUG_DICT_FULL) { - AKLOGI("Double excessive demotion"); - } - // If an excessive character is not adjacent to the left char or the right char, - // we will demote this word. - multiplyRate(WORDS_WITH_EXCESSIVE_CHARACTER_OUT_OF_PROXIMITY_DEMOTION_RATE, &finalFreq); - } - } - - const bool performTouchPositionCorrection = - CALIBRATE_SCORE_BY_TOUCH_COORDINATES && proximityInfo->touchPositionCorrectionEnabled() - && skippedCount == 0 && excessiveCount == 0 && transposedCount == 0; - // Score calibration by touch coordinates is being done only for pure-fat finger typing error - // cases. - int additionalProximityCount = 0; - // TODO: Remove this constraint. - if (performTouchPositionCorrection) { - for (int i = 0; i < outputLength; ++i) { - const int squaredDistance = correction->mDistances[i]; - if (i < adjustedProximityMatchedCount) { - multiplyIntCapped(typedLetterMultiplier, &finalFreq); - } - if (squaredDistance >= 0) { - // Promote or demote the score according to the distance from the sweet spot - static const float A = ZERO_DISTANCE_PROMOTION_RATE / 100.0f; - static const float B = 1.0f; - static const float C = 0.5f; - static const float MIN = 0.3f; - static const float R1 = NEUTRAL_SCORE_SQUARED_RADIUS; - static const float R2 = HALF_SCORE_SQUARED_RADIUS; - const float x = (float)squaredDistance - / ProximityInfo::NORMALIZED_SQUARED_DISTANCE_SCALING_FACTOR; - const float factor = max((x < R1) - ? (A * (R1 - x) + B * x) / R1 - : (B * (R2 - x) + C * (x - R1)) / (R2 - R1), MIN); - // factor is piecewise linear function like: - // A -_ . - // ^-_ . - // B \ . - // \_ . - // C ------------. - // . - // 0 R1 R2 . - multiplyRate((int)(factor * 100), &finalFreq); - } else if (squaredDistance == PROXIMITY_CHAR_WITHOUT_DISTANCE_INFO) { - multiplyRate(WORDS_WITH_PROXIMITY_CHARACTER_DEMOTION_RATE, &finalFreq); - } else if (squaredDistance == ADDITIONAL_PROXIMITY_CHAR_DISTANCE_INFO) { - ++additionalProximityCount; - multiplyRate(WORDS_WITH_ADDITIONAL_PROXIMITY_CHARACTER_DEMOTION_RATE, &finalFreq); - } - } - } else { - // Demote additional proximity characters - for (int i = 0; i < outputLength; ++i) { - const int squaredDistance = correction->mDistances[i]; - if (squaredDistance == ADDITIONAL_PROXIMITY_CHAR_DISTANCE_INFO) { - ++additionalProximityCount; - } - } - // Promotion for a word with proximity characters - for (int i = 0; i < adjustedProximityMatchedCount; ++i) { - // A word with proximity corrections - if (DEBUG_DICT_FULL) { - AKLOGI("Found a proximity correction."); - } - multiplyIntCapped(typedLetterMultiplier, &finalFreq); - if (i < additionalProximityCount) { - multiplyRate(WORDS_WITH_ADDITIONAL_PROXIMITY_CHARACTER_DEMOTION_RATE, &finalFreq); - } else { - multiplyRate(WORDS_WITH_PROXIMITY_CHARACTER_DEMOTION_RATE, &finalFreq); - } - } - } - - // If the user types too many(three or more) proximity characters with additional proximity - // character,do not treat as the same length word. - if (sameLength && additionalProximityCount > 0 && (adjustedProximityMatchedCount >= 3 - || transposedCount > 0 || skipped || excessiveCount > 0)) { - sameLength = false; - } - - const int errorCount = adjustedProximityMatchedCount > 0 - ? adjustedProximityMatchedCount - : (proximityMatchedCount + transposedCount); - multiplyRate( - 100 - CORRECTION_COUNT_RATE_DEMOTION_RATE_BASE * errorCount / inputLength, &finalFreq); - - // Promotion for an exactly matched word - if (ed == 0) { - // Full exact match - if (sameLength && transposedCount == 0 && !skipped && excessiveCount == 0 - && quoteDiffCount == 0 && additionalProximityCount == 0) { - finalFreq = capped255MultForFullMatchAccentsOrCapitalizationDifference(finalFreq); - } - } - - // Promote a word with no correction - if (proximityMatchedCount == 0 && transposedCount == 0 && !skipped && excessiveCount == 0 - && additionalProximityCount == 0) { - multiplyRate(FULL_MATCHED_WORDS_PROMOTION_RATE, &finalFreq); - } - - // TODO: Check excessive count and transposed count - // TODO: Remove this if possible - /* - If the last character of the user input word is the same as the next character - of the output word, and also all of characters of the user input are matched - to the output word, we'll promote that word a bit because - that word can be considered the combination of skipped and matched characters. - This means that the 'sm' pattern wins over the 'ma' pattern. - e.g.) - shel -> shell [mmmma] or [mmmsm] - hel -> hello [mmmaa] or [mmsma] - m ... matching - s ... skipping - a ... traversing all - t ... transposing - e ... exceeding - p ... proximity matching - */ - if (matchCount == inputLength && matchCount >= 2 && !skipped - && word[matchCount] == word[matchCount - 1]) { - multiplyRate(WORDS_WITH_MATCH_SKIP_PROMOTION_RATE, &finalFreq); - } - - // TODO: Do not use sameLength? - if (sameLength) { - multiplyIntCapped(fullWordMultiplier, &finalFreq); - } - - if (useFullEditDistance && outputLength > inputLength + 1) { - const int diff = outputLength - inputLength - 1; - const int divider = diff < 31 ? 1 << diff : S_INT_MAX; - finalFreq = divider > finalFreq ? 1 : finalFreq / divider; - } - - if (DEBUG_DICT_FULL) { - AKLOGI("calc: %d, %d", outputLength, sameLength); - } - - if (DEBUG_CORRECTION_FREQ - && (INPUTLENGTH_FOR_DEBUG <= 0 || INPUTLENGTH_FOR_DEBUG == inputLength)) { - DUMP_WORD(proximityInfo->getPrimaryInputWord(), inputLength); - DUMP_WORD(correction->mWord, outputLength); - AKLOGI("FinalFreq: [P%d, S%d, T%d, E%d, A%d] %d, %d, %d, %d, %d, %d", proximityMatchedCount, - skippedCount, transposedCount, excessiveCount, additionalProximityCount, - outputLength, lastCharExceeded, sameLength, quoteDiffCount, ed, finalFreq); - } - - return finalFreq; -} - -/* static */ -int Correction::RankingAlgorithm::calcFreqForSplitMultipleWords( - const int *freqArray, const int *wordLengthArray, const int wordCount, - const Correction* correction, const bool isSpaceProximity, const unsigned short *word) { - const int typedLetterMultiplier = correction->TYPED_LETTER_MULTIPLIER; - - bool firstCapitalizedWordDemotion = false; - bool secondCapitalizedWordDemotion = false; - - { - // TODO: Handle multiple capitalized word demotion properly - const int firstWordLength = wordLengthArray[0]; - const int secondWordLength = wordLengthArray[1]; - if (firstWordLength >= 2) { - firstCapitalizedWordDemotion = isUpperCase(word[0]); - } - - if (secondWordLength >= 2) { - // FIXME: word[firstWordLength + 1] is incorrect. - secondCapitalizedWordDemotion = isUpperCase(word[firstWordLength + 1]); - } - } - - - const bool capitalizedWordDemotion = - firstCapitalizedWordDemotion ^ secondCapitalizedWordDemotion; - - int totalLength = 0; - int totalFreq = 0; - for (int i = 0; i < wordCount; ++i){ - const int wordLength = wordLengthArray[i]; - if (wordLength <= 0) { - return 0; - } - totalLength += wordLength; - const int demotionRate = 100 - TWO_WORDS_CORRECTION_DEMOTION_BASE / (wordLength + 1); - int tempFirstFreq = freqArray[i]; - multiplyRate(demotionRate, &tempFirstFreq); - totalFreq += tempFirstFreq; - } - - if (totalLength <= 0 || totalFreq <= 0) { - return 0; - } - - // TODO: Currently totalFreq is adjusted to two word metrix. - // Promote pairFreq with multiplying by 2, because the word length is the same as the typed - // length. - totalFreq = totalFreq * 2 / wordCount; - if (wordCount > 2) { - // Safety net for 3+ words -- Caveats: many heuristics and workarounds here. - int oneLengthCounter = 0; - int twoLengthCounter = 0; - for (int i = 0; i < wordCount; ++i) { - const int wordLength = wordLengthArray[i]; - // TODO: Use bigram instead of this safety net - if (i < wordCount - 1) { - const int nextWordLength = wordLengthArray[i + 1]; - if (wordLength == 1 && nextWordLength == 2) { - // Safety net to filter 1 length and 2 length sequential words - return 0; - } - } - const int freq = freqArray[i]; - // Demote too short weak words - if (wordLength <= 4 && freq <= MAX_FREQ * 2 / 3 /* heuristic... */) { - multiplyRate(100 * freq / MAX_FREQ, &totalFreq); - } - if (wordLength == 1) { - ++oneLengthCounter; - } else if (wordLength == 2) { - ++twoLengthCounter; - } - if (oneLengthCounter >= 2 || (oneLengthCounter + twoLengthCounter) >= 4) { - // Safety net to filter too many short words - return 0; - } - } - multiplyRate(MULTIPLE_WORDS_DEMOTION_RATE, &totalFreq); - } - - // This is a workaround to try offsetting the not-enough-demotion which will be done in - // calcNormalizedScore in Utils.java. - // In calcNormalizedScore the score will be demoted by (1 - 1 / length) - // but we demoted only (1 - 1 / (length + 1)) so we will additionally adjust freq by - // (1 - 1 / length) / (1 - 1 / (length + 1)) = (1 - 1 / (length * length)) - const int normalizedScoreNotEnoughDemotionAdjustment = 100 - 100 / (totalLength * totalLength); - multiplyRate(normalizedScoreNotEnoughDemotionAdjustment, &totalFreq); - - // At this moment, totalFreq is calculated by the following formula: - // (firstFreq * (1 - 1 / (firstWordLength + 1)) + secondFreq * (1 - 1 / (secondWordLength + 1))) - // * (1 - 1 / totalLength) / (1 - 1 / (totalLength + 1)) - - multiplyIntCapped(powerIntCapped(typedLetterMultiplier, totalLength), &totalFreq); - - // This is another workaround to offset the demotion which will be done in - // calcNormalizedScore in Utils.java. - // In calcNormalizedScore the score will be demoted by (1 - 1 / length) so we have to promote - // the same amount because we already have adjusted the synthetic freq of this "missing or - // mistyped space" suggestion candidate above in this method. - const int normalizedScoreDemotionRateOffset = (100 + 100 / totalLength); - multiplyRate(normalizedScoreDemotionRateOffset, &totalFreq); - - if (isSpaceProximity) { - // A word pair with one space proximity correction - if (DEBUG_DICT) { - AKLOGI("Found a word pair with space proximity correction."); - } - multiplyIntCapped(typedLetterMultiplier, &totalFreq); - multiplyRate(WORDS_WITH_PROXIMITY_CHARACTER_DEMOTION_RATE, &totalFreq); - } - - if (isSpaceProximity) { - multiplyRate(WORDS_WITH_MISTYPED_SPACE_DEMOTION_RATE, &totalFreq); - } else { - multiplyRate(WORDS_WITH_MISSING_SPACE_CHARACTER_DEMOTION_RATE, &totalFreq); - } - - if (capitalizedWordDemotion) { - multiplyRate(TWO_WORDS_CAPITALIZED_DEMOTION_RATE, &totalFreq); - } - - if (DEBUG_CORRECTION_FREQ) { - AKLOGI("Multiple words (%d, %d) (%d, %d) %d, %d", freqArray[0], freqArray[1], - wordLengthArray[0], wordLengthArray[1], capitalizedWordDemotion, totalFreq); - DUMP_WORD(word, wordLengthArray[0]); - } - - return totalFreq; -} - -/* Damerau-Levenshtein distance */ -inline static int editDistanceInternal( - int* editDistanceTable, const unsigned short* before, - const int beforeLength, const unsigned short* after, const int afterLength) { - // dp[li][lo] dp[a][b] = dp[ a * lo + b] - int* dp = editDistanceTable; - const int li = beforeLength + 1; - const int lo = afterLength + 1; - for (int i = 0; i < li; ++i) { - dp[lo * i] = i; - } - for (int i = 0; i < lo; ++i) { - dp[i] = i; - } - - for (int i = 0; i < li - 1; ++i) { - for (int j = 0; j < lo - 1; ++j) { - const uint32_t ci = toBaseLowerCase(before[i]); - const uint32_t co = toBaseLowerCase(after[j]); - const uint16_t cost = (ci == co) ? 0 : 1; - dp[(i + 1) * lo + (j + 1)] = min(dp[i * lo + (j + 1)] + 1, - min(dp[(i + 1) * lo + j] + 1, dp[i * lo + j] + cost)); - if (i > 0 && j > 0 && ci == toBaseLowerCase(after[j - 1]) - && co == toBaseLowerCase(before[i - 1])) { - dp[(i + 1) * lo + (j + 1)] = min( - dp[(i + 1) * lo + (j + 1)], dp[(i - 1) * lo + (j - 1)] + cost); - } - } - } - - if (DEBUG_EDIT_DISTANCE) { - AKLOGI("IN = %d, OUT = %d", beforeLength, afterLength); - for (int i = 0; i < li; ++i) { - for (int j = 0; j < lo; ++j) { - AKLOGI("EDIT[%d][%d], %d", i, j, dp[i * lo + j]); - } - } - } - return dp[li * lo - 1]; -} - -int Correction::RankingAlgorithm::editDistance(const unsigned short* before, - const int beforeLength, const unsigned short* after, const int afterLength) { - int table[(beforeLength + 1) * (afterLength + 1)]; - return editDistanceInternal(table, before, beforeLength, after, afterLength); -} - - -// In dictionary.cpp, getSuggestion() method, -// suggestion scores are computed using the below formula. -// original score -// := pow(mTypedLetterMultiplier (this is defined 2), -// (the number of matched characters between typed word and suggested word)) -// * (individual word's score which defined in the unigram dictionary, -// and this score is defined in range [0, 255].) -// Then, the following processing is applied. -// - If the dictionary word is matched up to the point of the user entry -// (full match up to min(before.length(), after.length()) -// => Then multiply by FULL_MATCHED_WORDS_PROMOTION_RATE (this is defined 1.2) -// - If the word is a true full match except for differences in accents or -// capitalization, then treat it as if the score was 255. -// - If before.length() == after.length() -// => multiply by mFullWordMultiplier (this is defined 2)) -// So, maximum original score is pow(2, min(before.length(), after.length())) * 255 * 2 * 1.2 -// For historical reasons we ignore the 1.2 modifier (because the measure for a good -// autocorrection threshold was done at a time when it didn't exist). This doesn't change -// the result. -// So, we can normalize original score by dividing pow(2, min(b.l(),a.l())) * 255 * 2. - -/* static */ -double Correction::RankingAlgorithm::calcNormalizedScore(const unsigned short* before, - const int beforeLength, const unsigned short* after, const int afterLength, - const int score) { - if (0 == beforeLength || 0 == afterLength) { - return 0; - } - const int distance = editDistance(before, beforeLength, after, afterLength); - int spaceCount = 0; - for (int i = 0; i < afterLength; ++i) { - if (after[i] == CODE_SPACE) { - ++spaceCount; - } - } - - if (spaceCount == afterLength) { - return 0; - } - - const double maxScore = score >= S_INT_MAX ? S_INT_MAX : MAX_INITIAL_SCORE - * pow((double)TYPED_LETTER_MULTIPLIER, - (double)min(beforeLength, afterLength - spaceCount)) * FULL_WORD_MULTIPLIER; - - // add a weight based on edit distance. - // distance <= max(afterLength, beforeLength) == afterLength, - // so, 0 <= distance / afterLength <= 1 - const double weight = 1.0 - (double) distance / afterLength; - return (score / maxScore) * weight; -} - -} // namespace latinime diff --git a/native/src/correction.h b/native/src/correction.h deleted file mode 100644 index ee55c9604..000000000 --- a/native/src/correction.h +++ /dev/null @@ -1,239 +0,0 @@ -/* - * Copyright (C) 2011 The Android Open Source Project - * - * Licensed under the Apache License, Version 2.0 (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.apache.org/licenses/LICENSE-2.0 - * - * Unless required by applicable law or agreed to in writing, software - * distributed under the License is distributed on an "AS IS" BASIS, - * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. - * See the License for the specific language governing permissions and - * limitations under the License. - */ - -#ifndef LATINIME_CORRECTION_H -#define LATINIME_CORRECTION_H - -#include <assert.h> -#include <stdint.h> -#include "correction_state.h" - -#include "defines.h" - -namespace latinime { - -class ProximityInfo; - -class Correction { - public: - typedef enum { - TRAVERSE_ALL_ON_TERMINAL, - TRAVERSE_ALL_NOT_ON_TERMINAL, - UNRELATED, - ON_TERMINAL, - NOT_ON_TERMINAL - } CorrectionType; - - ///////////////////////// - // static inline utils // - ///////////////////////// - - static const int TWO_31ST_DIV_255 = S_INT_MAX / 255; - static inline int capped255MultForFullMatchAccentsOrCapitalizationDifference(const int num) { - return (num < TWO_31ST_DIV_255 ? 255 * num : S_INT_MAX); - } - - static const int TWO_31ST_DIV_2 = S_INT_MAX / 2; - inline static void multiplyIntCapped(const int multiplier, int *base) { - const int temp = *base; - if (temp != S_INT_MAX) { - // Branch if multiplier == 2 for the optimization - if (multiplier < 0) { - if (DEBUG_DICT) { - assert(false); - } - AKLOGI("--- Invalid multiplier: %d", multiplier); - } else if (multiplier == 0) { - *base = 0; - } else if (multiplier == 2) { - *base = TWO_31ST_DIV_2 >= temp ? temp << 1 : S_INT_MAX; - } else { - // TODO: This overflow check gives a wrong answer when, for example, - // temp = 2^16 + 1 and multiplier = 2^17 + 1. - // Fix this behavior. - const int tempRetval = temp * multiplier; - *base = tempRetval >= temp ? tempRetval : S_INT_MAX; - } - } - } - - inline static int powerIntCapped(const int base, const int n) { - if (n <= 0) return 1; - if (base == 2) { - return n < 31 ? 1 << n : S_INT_MAX; - } else { - int ret = base; - for (int i = 1; i < n; ++i) multiplyIntCapped(base, &ret); - return ret; - } - } - - inline static void multiplyRate(const int rate, int *freq) { - if (*freq != S_INT_MAX) { - if (*freq > 1000000) { - *freq /= 100; - multiplyIntCapped(rate, freq); - } else { - multiplyIntCapped(rate, freq); - *freq /= 100; - } - } - } - - Correction(const int typedLetterMultiplier, const int fullWordMultiplier); - void initCorrection( - const ProximityInfo *pi, const int inputLength, const int maxWordLength); - void initCorrectionState(const int rootPos, const int childCount, const bool traverseAll); - - // TODO: remove - void setCorrectionParams(const int skipPos, const int excessivePos, const int transposedPos, - const int spaceProximityPos, const int missingSpacePos, const bool useFullEditDistance, - const bool doAutoCompletion, const int maxErrors); - void checkState(); - bool initProcessState(const int index); - - int getInputIndex(); - - virtual ~Correction(); - int getSpaceProximityPos() const { - return mSpaceProximityPos; - } - int getMissingSpacePos() const { - return mMissingSpacePos; - } - - int getSkipPos() const { - return mSkipPos; - } - - int getExcessivePos() const { - return mExcessivePos; - } - - int getTransposedPos() const { - return mTransposedPos; - } - - bool needsToPrune() const; - - int getFreqForSplitMultipleWords( - const int *freqArray, const int *wordLengthArray, const int wordCount, - const bool isSpaceProximity, const unsigned short *word); - int getFinalFreq(const int freq, unsigned short **word, int* wordLength); - int getFinalFreqForSubQueue(const int freq, unsigned short **word, int* wordLength, - const int inputLength); - - CorrectionType processCharAndCalcState(const int32_t c, const bool isTerminal); - - ///////////////////////// - // Tree helper methods - int goDownTree(const int parentIndex, const int childCount, const int firstChildPos); - - inline int getTreeSiblingPos(const int index) const { - return mCorrectionStates[index].mSiblingPos; - } - - inline void setTreeSiblingPos(const int index, const int pos) { - mCorrectionStates[index].mSiblingPos = pos; - } - - inline int getTreeParentIndex(const int index) const { - return mCorrectionStates[index].mParentIndex; - } - - class RankingAlgorithm { - public: - static int calculateFinalFreq(const int inputIndex, const int depth, - const int freq, int *editDistanceTable, const Correction* correction, - const int inputLength); - static int calcFreqForSplitMultipleWords(const int *freqArray, const int *wordLengthArray, - const int wordCount, const Correction* correction, const bool isSpaceProximity, - const unsigned short *word); - static double calcNormalizedScore(const unsigned short* before, const int beforeLength, - const unsigned short* after, const int afterLength, const int score); - static int editDistance(const unsigned short* before, - const int beforeLength, const unsigned short* after, const int afterLength); - private: - static const int CODE_SPACE = ' '; - static const int MAX_INITIAL_SCORE = 255; - static const int TYPED_LETTER_MULTIPLIER = 2; - static const int FULL_WORD_MULTIPLIER = 2; - }; - - private: - inline void incrementInputIndex(); - inline void incrementOutputIndex(); - inline void startToTraverseAllNodes(); - inline bool isQuote(const unsigned short c); - inline CorrectionType processSkipChar( - const int32_t c, const bool isTerminal, const bool inputIndexIncremented); - inline CorrectionType processUnrelatedCorrectionType(); - inline void addCharToCurrentWord(const int32_t c); - inline int getFinalFreqInternal(const int freq, unsigned short **word, int* wordLength, - const int inputLength); - - const int TYPED_LETTER_MULTIPLIER; - const int FULL_WORD_MULTIPLIER; - const ProximityInfo *mProximityInfo; - - bool mUseFullEditDistance; - bool mDoAutoCompletion; - int mMaxEditDistance; - int mMaxDepth; - int mInputLength; - int mSpaceProximityPos; - int mMissingSpacePos; - int mTerminalInputIndex; - int mTerminalOutputIndex; - int mMaxErrors; - - // The following arrays are state buffer. - unsigned short mWord[MAX_WORD_LENGTH_INTERNAL]; - int mDistances[MAX_WORD_LENGTH_INTERNAL]; - - // Edit distance calculation requires a buffer with (N+1)^2 length for the input length N. - // Caveat: Do not create multiple tables per thread as this table eats up RAM a lot. - int mEditDistanceTable[(MAX_WORD_LENGTH_INTERNAL + 1) * (MAX_WORD_LENGTH_INTERNAL + 1)]; - - CorrectionState mCorrectionStates[MAX_WORD_LENGTH_INTERNAL]; - - // The following member variables are being used as cache values of the correction state. - bool mNeedsToTraverseAllNodes; - int mOutputIndex; - int mInputIndex; - - int mEquivalentCharCount; - int mProximityCount; - int mExcessiveCount; - int mTransposedCount; - int mSkippedCount; - - int mTransposedPos; - int mExcessivePos; - int mSkipPos; - - bool mLastCharExceeded; - - bool mMatching; - bool mProximityMatching; - bool mAdditionalProximityMatching; - bool mExceeding; - bool mTransposing; - bool mSkipping; - -}; -} // namespace latinime -#endif // LATINIME_CORRECTION_H diff --git a/native/src/correction_state.h b/native/src/correction_state.h deleted file mode 100644 index 5b2cbd3a2..000000000 --- a/native/src/correction_state.h +++ /dev/null @@ -1,84 +0,0 @@ -/* - * Copyright (C) 2011 The Android Open Source Project - * - * Licensed under the Apache License, Version 2.0 (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.apache.org/licenses/LICENSE-2.0 - * - * Unless required by applicable law or agreed to in writing, software - * distributed under the License is distributed on an "AS IS" BASIS, - * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. - * See the License for the specific language governing permissions and - * limitations under the License. - */ - -#ifndef LATINIME_CORRECTION_STATE_H -#define LATINIME_CORRECTION_STATE_H - -#include <stdint.h> - -#include "defines.h" - -namespace latinime { - -struct CorrectionState { - int mParentIndex; - int mSiblingPos; - uint16_t mChildCount; - uint8_t mInputIndex; - - uint8_t mEquivalentCharCount; - uint8_t mProximityCount; - uint8_t mTransposedCount; - uint8_t mExcessiveCount; - uint8_t mSkippedCount; - - int8_t mTransposedPos; - int8_t mExcessivePos; - int8_t mSkipPos; // should be signed - - // TODO: int? - bool mLastCharExceeded; - - bool mMatching; - bool mTransposing; - bool mExceeding; - bool mSkipping; - bool mProximityMatching; - bool mAdditionalProximityMatching; - - bool mNeedsToTraverseAllNodes; -}; - -inline static void initCorrectionState(CorrectionState *state, const int rootPos, - const uint16_t childCount, const bool traverseAll) { - state->mParentIndex = -1; - state->mChildCount = childCount; - state->mInputIndex = 0; - state->mSiblingPos = rootPos; - state->mNeedsToTraverseAllNodes = traverseAll; - - state->mTransposedPos = -1; - state->mExcessivePos = -1; - state->mSkipPos = -1; - - state->mEquivalentCharCount = 0; - state->mProximityCount = 0; - state->mTransposedCount = 0; - state->mExcessiveCount = 0; - state->mSkippedCount = 0; - - state->mLastCharExceeded = false; - - state->mMatching = false; - state->mProximityMatching = false; - state->mTransposing = false; - state->mExceeding = false; - state->mSkipping = false; - state->mAdditionalProximityMatching = false; -} - -} // namespace latinime -#endif // LATINIME_CORRECTION_STATE_H diff --git a/native/src/debug.h b/native/src/debug.h deleted file mode 100644 index b13052c95..000000000 --- a/native/src/debug.h +++ /dev/null @@ -1,72 +0,0 @@ -/* -** -** Copyright 2011, The Android Open Source Project -** -** Licensed under the Apache License, Version 2.0 (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.apache.org/licenses/LICENSE-2.0 -** -** Unless required by applicable law or agreed to in writing, software -** distributed under the License is distributed on an "AS IS" BASIS, -** WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. -** See the License for the specific language governing permissions and -** limitations under the License. -*/ - -#ifndef LATINIME_DEBUG_H -#define LATINIME_DEBUG_H - -#include "defines.h" - -static inline unsigned char* convertToUnibyteString(unsigned short* input, unsigned char* output, - const unsigned int length) { - int i = 0; - for (; i <= length && input[i] != 0; ++i) - output[i] = input[i] & 0xFF; - output[i] = 0; - return output; -} - -static inline unsigned char* convertToUnibyteStringAndReplaceLastChar(unsigned short* input, - unsigned char* output, const unsigned int length, unsigned char c) { - int i = 0; - for (; i <= length && input[i] != 0; ++i) - output[i] = input[i] & 0xFF; - output[i-1] = c; - output[i] = 0; - return output; -} - -static inline void LOGI_S16(unsigned short* string, const unsigned int length) { - unsigned char tmp_buffer[length]; - convertToUnibyteString(string, tmp_buffer, length); - AKLOGI(">> %s", tmp_buffer); - // The log facility is throwing out log that comes too fast. The following - // is a dirty way of slowing down processing so that we can see all log. - // TODO : refactor this in a blocking log or something. - // usleep(10); -} - -static inline void LOGI_S16_PLUS(unsigned short* string, const unsigned int length, - unsigned char c) { - unsigned char tmp_buffer[length+1]; - convertToUnibyteStringAndReplaceLastChar(string, tmp_buffer, length, c); - AKLOGI(">> %s", tmp_buffer); - // Likewise - // usleep(10); -} - -static inline void printDebug(const char* tag, int* codes, int codesSize, int MAX_PROXIMITY_CHARS) { - unsigned char *buf = (unsigned char*)malloc((1 + codesSize) * sizeof(*buf)); - - buf[codesSize] = 0; - while (--codesSize >= 0) - buf[codesSize] = (unsigned char)codes[codesSize * MAX_PROXIMITY_CHARS]; - AKLOGI("%s, WORD = %s", tag, buf); - - free(buf); -} - -#endif // LATINIME_DEBUG_H diff --git a/native/src/defines.h b/native/src/defines.h deleted file mode 100644 index e882c3714..000000000 --- a/native/src/defines.h +++ /dev/null @@ -1,254 +0,0 @@ -/* -** -** Copyright 2010, The Android Open Source Project -** -** Licensed under the Apache License, Version 2.0 (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.apache.org/licenses/LICENSE-2.0 -** -** Unless required by applicable law or agreed to in writing, software -** distributed under the License is distributed on an "AS IS" BASIS, -** WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. -** See the License for the specific language governing permissions and -** limitations under the License. -*/ - -#ifndef LATINIME_DEFINES_H -#define LATINIME_DEFINES_H - -#if defined(FLAG_DO_PROFILE) || defined(FLAG_DBG) -#include <cutils/log.h> -#define AKLOGE ALOGE -#define AKLOGI ALOGI - -#define DUMP_WORD(word, length) do { dumpWord(word, length); } while(0) - -static inline void dumpWord(const unsigned short* word, const int length) { - static char charBuf[50]; - - for (int i = 0; i < length; ++i) { - charBuf[i] = word[i]; - } - charBuf[length] = 0; - AKLOGI("[ %s ]", charBuf); -} - -#else -#define AKLOGE(fmt, ...) -#define AKLOGI(fmt, ...) -#define DUMP_WORD(word, length) -#endif - -#ifdef FLAG_DO_PROFILE -// Profiler -#include <time.h> - -#define PROF_BUF_SIZE 100 -static double profile_buf[PROF_BUF_SIZE]; -static double profile_old[PROF_BUF_SIZE]; -static unsigned int profile_counter[PROF_BUF_SIZE]; - -#define PROF_RESET prof_reset() -#define PROF_COUNT(prof_buf_id) ++profile_counter[prof_buf_id] -#define PROF_OPEN do { PROF_RESET; PROF_START(PROF_BUF_SIZE - 1); } while(0) -#define PROF_START(prof_buf_id) do { \ - PROF_COUNT(prof_buf_id); profile_old[prof_buf_id] = (clock()); } while(0) -#define PROF_CLOSE do { PROF_END(PROF_BUF_SIZE - 1); PROF_OUTALL; } while(0) -#define PROF_END(prof_buf_id) profile_buf[prof_buf_id] += ((clock()) - profile_old[prof_buf_id]) -#define PROF_CLOCKOUT(prof_buf_id) \ - AKLOGI("%s : clock is %f", __FUNCTION__, (clock() - profile_old[prof_buf_id])) -#define PROF_OUTALL do { AKLOGI("--- %s ---", __FUNCTION__); prof_out(); } while(0) - -static inline void prof_reset(void) { - for (int i = 0; i < PROF_BUF_SIZE; ++i) { - profile_buf[i] = 0; - profile_old[i] = 0; - profile_counter[i] = 0; - } -} - -static inline void prof_out(void) { - if (profile_counter[PROF_BUF_SIZE - 1] != 1) { - AKLOGI("Error: You must call PROF_OPEN before PROF_CLOSE."); - } - AKLOGI("Total time is %6.3f ms.", - profile_buf[PROF_BUF_SIZE - 1] * 1000 / (double)CLOCKS_PER_SEC); - double all = 0; - for (int i = 0; i < PROF_BUF_SIZE - 1; ++i) { - all += profile_buf[i]; - } - if (all == 0) all = 1; - for (int i = 0; i < PROF_BUF_SIZE - 1; ++i) { - if (profile_buf[i] != 0) { - AKLOGI("(%d): Used %4.2f%%, %8.4f ms. Called %d times.", - i, (profile_buf[i] * 100 / all), - profile_buf[i] * 1000 / (double)CLOCKS_PER_SEC, profile_counter[i]); - } - } -} - -#else // FLAG_DO_PROFILE -#define PROF_BUF_SIZE 0 -#define PROF_RESET -#define PROF_COUNT(prof_buf_id) -#define PROF_OPEN -#define PROF_START(prof_buf_id) -#define PROF_CLOSE -#define PROF_END(prof_buf_id) -#define PROF_CLOCK_OUT(prof_buf_id) -#define PROF_CLOCKOUT(prof_buf_id) -#define PROF_OUTALL - -#endif // FLAG_DO_PROFILE - -#ifdef FLAG_DBG -#include <cutils/log.h> -#ifndef LOG_TAG -#define LOG_TAG "LatinIME: " -#endif -#define DEBUG_DICT true -#define DEBUG_DICT_FULL false -#define DEBUG_EDIT_DISTANCE false -#define DEBUG_SHOW_FOUND_WORD false -#define DEBUG_NODE DEBUG_DICT_FULL -#define DEBUG_TRACE DEBUG_DICT_FULL -#define DEBUG_PROXIMITY_INFO false -#define DEBUG_PROXIMITY_CHARS false -#define DEBUG_CORRECTION false -#define DEBUG_CORRECTION_FREQ false -#define DEBUG_WORDS_PRIORITY_QUEUE false - -#else // FLAG_DBG - -#define DEBUG_DICT false -#define DEBUG_DICT_FULL false -#define DEBUG_EDIT_DISTANCE false -#define DEBUG_SHOW_FOUND_WORD false -#define DEBUG_NODE false -#define DEBUG_TRACE false -#define DEBUG_PROXIMITY_INFO false -#define DEBUG_PROXIMITY_CHARS false -#define DEBUG_CORRECTION false -#define DEBUG_CORRECTION_FREQ false -#define DEBUG_WORDS_PRIORITY_QUEUE false - - -#endif // FLAG_DBG - -#ifndef U_SHORT_MAX -#define U_SHORT_MAX 65535 // ((1 << 16) - 1) -#endif -#ifndef S_INT_MAX -#define S_INT_MAX 2147483647 // ((1 << 31) - 1) -#endif - -// Define this to use mmap() for dictionary loading. Undefine to use malloc() instead of mmap(). -// We measured and compared performance of both, and found mmap() is fairly good in terms of -// loading time, and acceptable even for several initial lookups which involve page faults. -#define USE_MMAP_FOR_DICTIONARY - -// 22-bit address = ~4MB dictionary size limit, which on average would be about 200k-300k words -#define ADDRESS_MASK 0x3FFFFF - -// The bit that decides if an address follows in the next 22 bits -#define FLAG_ADDRESS_MASK 0x40 -// The bit that decides if this is a terminal node for a word. The node could still have children, -// if the word has other endings. -#define FLAG_TERMINAL_MASK 0x80 - -#define FLAG_BIGRAM_READ 0x80 -#define FLAG_BIGRAM_CHILDEXIST 0x40 -#define FLAG_BIGRAM_CONTINUED 0x80 -#define FLAG_BIGRAM_FREQ 0x7F - -#define DICTIONARY_VERSION_MIN 200 -#define NOT_VALID_WORD -99 -#define NOT_A_CHARACTER -1 -#define NOT_A_DISTANCE -1 -#define NOT_A_COORDINATE -1 -#define EQUIVALENT_CHAR_WITHOUT_DISTANCE_INFO -2 -#define PROXIMITY_CHAR_WITHOUT_DISTANCE_INFO -3 -#define ADDITIONAL_PROXIMITY_CHAR_DISTANCE_INFO -4 -#define NOT_AN_INDEX -1 -#define NOT_A_FREQUENCY -1 - -#define KEYCODE_SPACE ' ' - -#define CALIBRATE_SCORE_BY_TOUCH_COORDINATES true - -#define SUGGEST_WORDS_WITH_MISSING_CHARACTER true -#define SUGGEST_WORDS_WITH_EXCESSIVE_CHARACTER true -#define SUGGEST_WORDS_WITH_TRANSPOSED_CHARACTERS true -#define SUGGEST_MULTIPLE_WORDS true - -// The following "rate"s are used as a multiplier before dividing by 100, so they are in percent. -#define WORDS_WITH_MISSING_CHARACTER_DEMOTION_RATE 80 -#define WORDS_WITH_MISSING_CHARACTER_DEMOTION_START_POS_10X 12 -#define WORDS_WITH_MISSING_SPACE_CHARACTER_DEMOTION_RATE 58 -#define WORDS_WITH_MISTYPED_SPACE_DEMOTION_RATE 50 -#define WORDS_WITH_EXCESSIVE_CHARACTER_DEMOTION_RATE 75 -#define WORDS_WITH_EXCESSIVE_CHARACTER_OUT_OF_PROXIMITY_DEMOTION_RATE 75 -#define WORDS_WITH_TRANSPOSED_CHARACTERS_DEMOTION_RATE 70 -#define FULL_MATCHED_WORDS_PROMOTION_RATE 120 -#define WORDS_WITH_PROXIMITY_CHARACTER_DEMOTION_RATE 90 -#define WORDS_WITH_ADDITIONAL_PROXIMITY_CHARACTER_DEMOTION_RATE 70 -#define WORDS_WITH_MATCH_SKIP_PROMOTION_RATE 105 -#define WORDS_WITH_JUST_ONE_CORRECTION_PROMOTION_RATE 148 -#define WORDS_WITH_JUST_ONE_CORRECTION_PROMOTION_MULTIPLIER 3 -#define CORRECTION_COUNT_RATE_DEMOTION_RATE_BASE 45 -#define INPUT_EXCEEDS_OUTPUT_DEMOTION_RATE 70 -#define FIRST_CHAR_DIFFERENT_DEMOTION_RATE 96 -#define TWO_WORDS_CAPITALIZED_DEMOTION_RATE 50 -#define TWO_WORDS_CORRECTION_DEMOTION_BASE 80 -#define TWO_WORDS_PLUS_OTHER_ERROR_CORRECTION_DEMOTION_DIVIDER 1 -#define ZERO_DISTANCE_PROMOTION_RATE 110 -#define NEUTRAL_SCORE_SQUARED_RADIUS 8.0f -#define HALF_SCORE_SQUARED_RADIUS 32.0f -#define MAX_FREQ 255 - -// This must be greater than or equal to MAX_WORD_LENGTH defined in BinaryDictionary.java -// This is only used for the size of array. Not to be used in c functions. -#define MAX_WORD_LENGTH_INTERNAL 48 - -// This must be equal to ADDITIONAL_PROXIMITY_CHAR_DELIMITER_CODE in KeyDetector.java -#define ADDITIONAL_PROXIMITY_CHAR_DELIMITER_CODE 2 - -// Word limit for sub queues used in WordsPriorityQueuePool. Sub queues are temporary queues used -// for better performance. -// Holds up to 1 candidate for each word -#define SUB_QUEUE_MAX_WORDS 1 -#define SUB_QUEUE_MAX_COUNT 10 -#define SUB_QUEUE_MIN_WORD_LENGTH 4 -#define MULTIPLE_WORDS_SUGGESTION_MAX_WORDS 10 -#define MULTIPLE_WORDS_DEMOTION_RATE 80 -#define MIN_INPUT_LENGTH_FOR_THREE_OR_MORE_WORDS_CORRECTION 6 - -#define TWO_WORDS_CORRECTION_WITH_OTHER_ERROR_THRESHOLD 0.39 -#define START_TWO_WORDS_CORRECTION_THRESHOLD 0.22 - -#define MAX_DEPTH_MULTIPLIER 3 - -#define FIRST_WORD_INDEX 0 - -// TODO: Reduce this constant if possible; check the maximum number of digraphs in the same -// word in the dictionary for languages with digraphs, like German and French -#define DEFAULT_MAX_DIGRAPH_SEARCH_DEPTH 5 - -// Minimum suggest depth for one word for all cases except for missing space suggestions. -#define MIN_SUGGEST_DEPTH 1 -#define MIN_USER_TYPED_LENGTH_FOR_MULTIPLE_WORD_SUGGESTION 3 -#define MIN_USER_TYPED_LENGTH_FOR_EXCESSIVE_CHARACTER_SUGGESTION 3 - -template<typename T> inline T min(T a, T b) { return a < b ? a : b; } -template<typename T> inline T max(T a, T b) { return a > b ? a : b; } - -// The ratio of neutral area radius to sweet spot radius. -#define NEUTRAL_AREA_RADIUS_RATIO 1.3f - -// DEBUG -#define INPUTLENGTH_FOR_DEBUG -1 -#define MIN_OUTPUT_INDEX_FOR_DEBUG -1 - -#endif // LATINIME_DEFINES_H diff --git a/native/src/dictionary.cpp b/native/src/dictionary.cpp deleted file mode 100644 index 981a983ee..000000000 --- a/native/src/dictionary.cpp +++ /dev/null @@ -1,63 +0,0 @@ -/* -** -** Copyright 2009, The Android Open Source Project -** -** Licensed under the Apache License, Version 2.0 (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.apache.org/licenses/LICENSE-2.0 -** -** Unless required by applicable law or agreed to in writing, software -** distributed under the License is distributed on an "AS IS" BASIS, -** WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. -** See the License for the specific language governing permissions and -** limitations under the License. -*/ - -#include <stdio.h> - -#define LOG_TAG "LatinIME: dictionary.cpp" - -#include "binary_format.h" -#include "dictionary.h" - -namespace latinime { - -// TODO: Change the type of all keyCodes to uint32_t -Dictionary::Dictionary(void *dict, int dictSize, int mmapFd, int dictBufAdjust, - int typedLetterMultiplier, int fullWordMultiplier, - int maxWordLength, int maxWords) - : mDict((unsigned char*) dict), mDictSize(dictSize), - mMmapFd(mmapFd), mDictBufAdjust(dictBufAdjust), - // Checks whether it has the latest dictionary or the old dictionary - IS_LATEST_DICT_VERSION((((unsigned char*) dict)[0] & 0xFF) >= DICTIONARY_VERSION_MIN) { - if (DEBUG_DICT) { - if (MAX_WORD_LENGTH_INTERNAL < maxWordLength) { - AKLOGI("Max word length (%d) is greater than %d", - maxWordLength, MAX_WORD_LENGTH_INTERNAL); - AKLOGI("IN NATIVE SUGGEST Version: %d", (mDict[0] & 0xFF)); - } - } - mCorrection = new Correction(typedLetterMultiplier, fullWordMultiplier); - mWordsPriorityQueuePool = new WordsPriorityQueuePool( - maxWords, SUB_QUEUE_MAX_WORDS, maxWordLength); - const unsigned int headerSize = BinaryFormat::getHeaderSize(mDict); - mUnigramDictionary = new UnigramDictionary(mDict + headerSize, typedLetterMultiplier, - fullWordMultiplier, maxWordLength, maxWords, IS_LATEST_DICT_VERSION); - mBigramDictionary = new BigramDictionary(mDict + headerSize, maxWordLength, - IS_LATEST_DICT_VERSION, true /* hasBigram */, this); -} - -Dictionary::~Dictionary() { - delete mCorrection; - delete mWordsPriorityQueuePool; - delete mUnigramDictionary; - delete mBigramDictionary; -} - -bool Dictionary::isValidWord(unsigned short *word, int length) { - return mUnigramDictionary->isValidWord(word, length); -} - -} // namespace latinime diff --git a/native/src/dictionary.h b/native/src/dictionary.h deleted file mode 100644 index 139d3f0d7..000000000 --- a/native/src/dictionary.h +++ /dev/null @@ -1,89 +0,0 @@ -/* - * Copyright (C) 2009 The Android Open Source Project - * - * Licensed under the Apache License, Version 2.0 (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.apache.org/licenses/LICENSE-2.0 - * - * Unless required by applicable law or agreed to in writing, software - * distributed under the License is distributed on an "AS IS" BASIS, - * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. - * See the License for the specific language governing permissions and - * limitations under the License. - */ - -#ifndef LATINIME_DICTIONARY_H -#define LATINIME_DICTIONARY_H - -#include "bigram_dictionary.h" -#include "char_utils.h" -#include "correction.h" -#include "defines.h" -#include "proximity_info.h" -#include "unigram_dictionary.h" -#include "words_priority_queue_pool.h" - -namespace latinime { - -class Dictionary { - public: - Dictionary(void *dict, int dictSize, int mmapFd, int dictBufAdjust, int typedLetterMultipler, - int fullWordMultiplier, int maxWordLength, int maxWords); - - int getSuggestions(ProximityInfo *proximityInfo, int *xcoordinates, int *ycoordinates, - int *codes, int codesSize, int flags, unsigned short *outWords, int *frequencies) { - return mUnigramDictionary->getSuggestions(proximityInfo, mWordsPriorityQueuePool, - mCorrection, xcoordinates, ycoordinates, codes, - codesSize, flags, outWords, frequencies); - } - - // TODO: Call mBigramDictionary instead of mUnigramDictionary - int getBigrams(unsigned short *word, int length, int *codes, int codesSize, - unsigned short *outWords, int *frequencies, int maxWordLength, int maxBigrams) { - return mBigramDictionary->getBigrams(word, length, codes, codesSize, outWords, frequencies, - maxWordLength, maxBigrams); - } - - bool isValidWord(unsigned short *word, int length); - void *getDict() { return (void *)mDict; } - int getDictSize() { return mDictSize; } - int getMmapFd() { return mMmapFd; } - int getDictBufAdjust() { return mDictBufAdjust; } - ~Dictionary(); - - // public static utility methods - // static inline methods should be defined in the header file - static int wideStrLen(unsigned short *str); - - private: - bool hasBigram(); - - const unsigned char *mDict; - - // Used only for the mmap version of dictionary loading, but we use these as dummy variables - // also for the malloc version. - const int mDictSize; - const int mMmapFd; - const int mDictBufAdjust; - - const bool IS_LATEST_DICT_VERSION; - UnigramDictionary *mUnigramDictionary; - BigramDictionary *mBigramDictionary; - WordsPriorityQueuePool *mWordsPriorityQueuePool; - Correction *mCorrection; -}; - -// public static utility methods -// static inline methods should be defined in the header file -inline int Dictionary::wideStrLen(unsigned short *str) { - if (!str) return 0; - unsigned short *end = str; - while (*end) - end++; - return end - str; -} -} // namespace latinime - -#endif // LATINIME_DICTIONARY_H diff --git a/native/src/proximity_info.cpp b/native/src/proximity_info.cpp deleted file mode 100644 index c00c4c20f..000000000 --- a/native/src/proximity_info.cpp +++ /dev/null @@ -1,466 +0,0 @@ -/* - * Copyright (C) 2011 The Android Open Source Project - * - * Licensed under the Apache License, Version 2.0 (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.apache.org/licenses/LICENSE-2.0 - * - * Unless required by applicable law or agreed to in writing, software - * distributed under the License is distributed on an "AS IS" BASIS, - * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. - * See the License for the specific language governing permissions and - * limitations under the License. - */ - -#include <assert.h> -#include <stdio.h> -#include <string> - -#define LOG_TAG "LatinIME: proximity_info.cpp" - -#include "additional_proximity_chars.h" -#include "dictionary.h" -#include "proximity_info.h" - -namespace latinime { - -inline void copyOrFillZero(void *to, const void *from, size_t size) { - if (from) { - memcpy(to, from, size); - } else { - memset(to, 0, size); - } -} - -ProximityInfo::ProximityInfo(const std::string localeStr, const int maxProximityCharsSize, - const int keyboardWidth, const int keyboardHeight, const int gridWidth, - const int gridHeight, const int mostCommonKeyWidth, - const int32_t *proximityCharsArray, const int keyCount, const int32_t *keyXCoordinates, - const int32_t *keyYCoordinates, const int32_t *keyWidths, const int32_t *keyHeights, - const int32_t *keyCharCodes, const float *sweetSpotCenterXs, const float *sweetSpotCenterYs, - const float *sweetSpotRadii) - : MAX_PROXIMITY_CHARS_SIZE(maxProximityCharsSize), KEYBOARD_WIDTH(keyboardWidth), - KEYBOARD_HEIGHT(keyboardHeight), GRID_WIDTH(gridWidth), GRID_HEIGHT(gridHeight), - MOST_COMMON_KEY_WIDTH_SQUARE(mostCommonKeyWidth * mostCommonKeyWidth), - CELL_WIDTH((keyboardWidth + gridWidth - 1) / gridWidth), - CELL_HEIGHT((keyboardHeight + gridHeight - 1) / gridHeight), - KEY_COUNT(min(keyCount, MAX_KEY_COUNT_IN_A_KEYBOARD)), - HAS_TOUCH_POSITION_CORRECTION_DATA(keyCount > 0 && keyXCoordinates && keyYCoordinates - && keyWidths && keyHeights && keyCharCodes && sweetSpotCenterXs - && sweetSpotCenterYs && sweetSpotRadii), - mLocaleStr(localeStr), - mInputXCoordinates(0), mInputYCoordinates(0), - mTouchPositionCorrectionEnabled(false) { - const int proximityGridLength = GRID_WIDTH * GRID_HEIGHT * MAX_PROXIMITY_CHARS_SIZE; - mProximityCharsArray = new int32_t[proximityGridLength]; - mInputCodes = new int32_t[MAX_PROXIMITY_CHARS_SIZE * MAX_WORD_LENGTH_INTERNAL]; - if (DEBUG_PROXIMITY_INFO) { - AKLOGI("Create proximity info array %d", proximityGridLength); - } - memcpy(mProximityCharsArray, proximityCharsArray, - proximityGridLength * sizeof(mProximityCharsArray[0])); - const int normalizedSquaredDistancesLength = - MAX_PROXIMITY_CHARS_SIZE * MAX_WORD_LENGTH_INTERNAL; - mNormalizedSquaredDistances = new int[normalizedSquaredDistancesLength]; - for (int i = 0; i < normalizedSquaredDistancesLength; ++i) { - mNormalizedSquaredDistances[i] = NOT_A_DISTANCE; - } - - copyOrFillZero(mKeyXCoordinates, keyXCoordinates, KEY_COUNT * sizeof(mKeyXCoordinates[0])); - copyOrFillZero(mKeyYCoordinates, keyYCoordinates, KEY_COUNT * sizeof(mKeyYCoordinates[0])); - copyOrFillZero(mKeyWidths, keyWidths, KEY_COUNT * sizeof(mKeyWidths[0])); - copyOrFillZero(mKeyHeights, keyHeights, KEY_COUNT * sizeof(mKeyHeights[0])); - copyOrFillZero(mKeyCharCodes, keyCharCodes, KEY_COUNT * sizeof(mKeyCharCodes[0])); - copyOrFillZero(mSweetSpotCenterXs, sweetSpotCenterXs, - KEY_COUNT * sizeof(mSweetSpotCenterXs[0])); - copyOrFillZero(mSweetSpotCenterYs, sweetSpotCenterYs, - KEY_COUNT * sizeof(mSweetSpotCenterYs[0])); - copyOrFillZero(mSweetSpotRadii, sweetSpotRadii, KEY_COUNT * sizeof(mSweetSpotRadii[0])); - - initializeCodeToKeyIndex(); -} - -// Build the reversed look up table from the char code to the index in mKeyXCoordinates, -// mKeyYCoordinates, mKeyWidths, mKeyHeights, mKeyCharCodes. -void ProximityInfo::initializeCodeToKeyIndex() { - memset(mCodeToKeyIndex, -1, (MAX_CHAR_CODE + 1) * sizeof(mCodeToKeyIndex[0])); - for (int i = 0; i < KEY_COUNT; ++i) { - const int code = mKeyCharCodes[i]; - if (0 <= code && code <= MAX_CHAR_CODE) { - mCodeToKeyIndex[code] = i; - } - } -} - -ProximityInfo::~ProximityInfo() { - delete[] mNormalizedSquaredDistances; - delete[] mProximityCharsArray; - delete[] mInputCodes; -} - -inline int ProximityInfo::getStartIndexFromCoordinates(const int x, const int y) const { - return ((y / CELL_HEIGHT) * GRID_WIDTH + (x / CELL_WIDTH)) - * MAX_PROXIMITY_CHARS_SIZE; -} - -bool ProximityInfo::hasSpaceProximity(const int x, const int y) const { - if (x < 0 || y < 0) { - if (DEBUG_DICT) { - AKLOGI("HasSpaceProximity: Illegal coordinates (%d, %d)", x, y); - assert(false); - } - return false; - } - - const int startIndex = getStartIndexFromCoordinates(x, y); - if (DEBUG_PROXIMITY_INFO) { - AKLOGI("hasSpaceProximity: index %d, %d, %d", startIndex, x, y); - } - for (int i = 0; i < MAX_PROXIMITY_CHARS_SIZE; ++i) { - if (DEBUG_PROXIMITY_INFO) { - AKLOGI("Index: %d", mProximityCharsArray[startIndex + i]); - } - if (mProximityCharsArray[startIndex + i] == KEYCODE_SPACE) { - return true; - } - } - return false; -} - -bool ProximityInfo::isOnKey(const int keyId, const int x, const int y) const { - if (keyId < 0) return true; // NOT_A_ID is -1, but return whenever < 0 just in case - const int left = mKeyXCoordinates[keyId]; - const int top = mKeyYCoordinates[keyId]; - const int right = left + mKeyWidths[keyId] + 1; - const int bottom = top + mKeyHeights[keyId]; - return left < right && top < bottom && x >= left && x < right && y >= top && y < bottom; -} - -int ProximityInfo::squaredDistanceToEdge(const int keyId, const int x, const int y) const { - if (keyId < 0) return true; // NOT_A_ID is -1, but return whenever < 0 just in case - const int left = mKeyXCoordinates[keyId]; - const int top = mKeyYCoordinates[keyId]; - const int right = left + mKeyWidths[keyId]; - const int bottom = top + mKeyHeights[keyId]; - const int edgeX = x < left ? left : (x > right ? right : x); - const int edgeY = y < top ? top : (y > bottom ? bottom : y); - const int dx = x - edgeX; - const int dy = y - edgeY; - return dx * dx + dy * dy; -} - -void ProximityInfo::calculateNearbyKeyCodes( - const int x, const int y, const int32_t primaryKey, int *inputCodes) const { - int insertPos = 0; - inputCodes[insertPos++] = primaryKey; - const int startIndex = getStartIndexFromCoordinates(x, y); - if (startIndex >= 0) { - for (int i = 0; i < MAX_PROXIMITY_CHARS_SIZE; ++i) { - const int32_t c = mProximityCharsArray[startIndex + i]; - if (c < KEYCODE_SPACE || c == primaryKey) { - continue; - } - const int keyIndex = getKeyIndex(c); - const bool onKey = isOnKey(keyIndex, x, y); - const int distance = squaredDistanceToEdge(keyIndex, x, y); - if (onKey || distance < MOST_COMMON_KEY_WIDTH_SQUARE) { - inputCodes[insertPos++] = c; - if (insertPos >= MAX_PROXIMITY_CHARS_SIZE) { - if (DEBUG_DICT) { - assert(false); - } - return; - } - } - } - const int additionalProximitySize = - AdditionalProximityChars::getAdditionalCharsSize(&mLocaleStr, primaryKey); - if (additionalProximitySize > 0) { - inputCodes[insertPos++] = ADDITIONAL_PROXIMITY_CHAR_DELIMITER_CODE; - if (insertPos >= MAX_PROXIMITY_CHARS_SIZE) { - if (DEBUG_DICT) { - assert(false); - } - return; - } - - const int32_t* additionalProximityChars = - AdditionalProximityChars::getAdditionalChars(&mLocaleStr, primaryKey); - for (int j = 0; j < additionalProximitySize; ++j) { - const int32_t ac = additionalProximityChars[j]; - int k = 0; - for (; k < insertPos; ++k) { - if ((int)ac == inputCodes[k]) { - break; - } - } - if (k < insertPos) { - continue; - } - inputCodes[insertPos++] = ac; - if (insertPos >= MAX_PROXIMITY_CHARS_SIZE) { - if (DEBUG_DICT) { - assert(false); - } - return; - } - } - } - } - // Add a delimiter for the proximity characters - for (int i = insertPos; i < MAX_PROXIMITY_CHARS_SIZE; ++i) { - inputCodes[i] = NOT_A_CODE; - } -} - -void ProximityInfo::setInputParams(const int32_t* inputCodes, const int inputLength, - const int* xCoordinates, const int* yCoordinates) { - memset(mInputCodes, 0, - MAX_WORD_LENGTH_INTERNAL * MAX_PROXIMITY_CHARS_SIZE * sizeof(mInputCodes[0])); - - for (int i = 0; i < inputLength; ++i) { - const int32_t primaryKey = inputCodes[i]; - const int x = xCoordinates[i]; - const int y = yCoordinates[i]; - int *proximities = &mInputCodes[i * MAX_PROXIMITY_CHARS_SIZE]; - calculateNearbyKeyCodes(x, y, primaryKey, proximities); - } - - if (DEBUG_PROXIMITY_CHARS) { - for (int i = 0; i < inputLength; ++i) { - AKLOGI("---"); - for (int j = 0; j < MAX_PROXIMITY_CHARS_SIZE; ++j) { - int icc = mInputCodes[i * MAX_PROXIMITY_CHARS_SIZE + j]; - int icfjc = inputCodes[i * MAX_PROXIMITY_CHARS_SIZE + j]; - icc+= 0; - icfjc += 0; - AKLOGI("--- (%d)%c,%c", i, icc, icfjc); - AKLOGI("--- A<%d>,B<%d>", icc, icfjc); - } - } - } - //Keep for debug, sorry - //for (int i = 0; i < MAX_WORD_LENGTH_INTERNAL * MAX_PROXIMITY_CHARS_SIZE; ++i) { - //if (i < inputLength * MAX_PROXIMITY_CHARS_SIZE) { - //mInputCodes[i] = mInputCodesFromJava[i]; - //} else { - // mInputCodes[i] = 0; - // } - //} - mInputXCoordinates = xCoordinates; - mInputYCoordinates = yCoordinates; - mTouchPositionCorrectionEnabled = - HAS_TOUCH_POSITION_CORRECTION_DATA && xCoordinates && yCoordinates; - mInputLength = inputLength; - for (int i = 0; i < inputLength; ++i) { - mPrimaryInputWord[i] = getPrimaryCharAt(i); - } - mPrimaryInputWord[inputLength] = 0; - if (DEBUG_PROXIMITY_CHARS) { - AKLOGI("--- setInputParams"); - } - for (int i = 0; i < mInputLength; ++i) { - const int *proximityChars = getProximityCharsAt(i); - const int primaryKey = proximityChars[0]; - const int x = xCoordinates[i]; - const int y = yCoordinates[i]; - if (DEBUG_PROXIMITY_CHARS) { - int a = x + y + primaryKey; - a += 0; - AKLOGI("--- Primary = %c, x = %d, y = %d", primaryKey, x, y); - // Keep debug code just in case - //int proximities[50]; - //for (int m = 0; m < 50; ++m) { - //proximities[m] = 0; - //} - //calculateNearbyKeyCodes(x, y, primaryKey, proximities); - //for (int l = 0; l < 50 && proximities[l] > 0; ++l) { - //if (DEBUG_PROXIMITY_CHARS) { - //AKLOGI("--- native Proximity (%d) = %c", l, proximities[l]); - //} - //} - } - for (int j = 0; j < MAX_PROXIMITY_CHARS_SIZE && proximityChars[j] > 0; ++j) { - const int currentChar = proximityChars[j]; - const float squaredDistance = hasInputCoordinates() - ? calculateNormalizedSquaredDistance(getKeyIndex(currentChar), i) - : NOT_A_DISTANCE_FLOAT; - if (squaredDistance >= 0.0f) { - mNormalizedSquaredDistances[i * MAX_PROXIMITY_CHARS_SIZE + j] = - (int)(squaredDistance * NORMALIZED_SQUARED_DISTANCE_SCALING_FACTOR); - } else { - mNormalizedSquaredDistances[i * MAX_PROXIMITY_CHARS_SIZE + j] = (j == 0) - ? EQUIVALENT_CHAR_WITHOUT_DISTANCE_INFO - : PROXIMITY_CHAR_WITHOUT_DISTANCE_INFO; - } - if (DEBUG_PROXIMITY_CHARS) { - AKLOGI("--- Proximity (%d) = %c", j, currentChar); - } - } - } -} - -inline float square(const float x) { return x * x; } - -float ProximityInfo::calculateNormalizedSquaredDistance( - const int keyIndex, const int inputIndex) const { - if (keyIndex == NOT_AN_INDEX) { - return NOT_A_DISTANCE_FLOAT; - } - if (!hasSweetSpotData(keyIndex)) { - return NOT_A_DISTANCE_FLOAT; - } - if (NOT_A_COORDINATE == mInputXCoordinates[inputIndex]) { - return NOT_A_DISTANCE_FLOAT; - } - const float squaredDistance = calculateSquaredDistanceFromSweetSpotCenter(keyIndex, inputIndex); - const float squaredRadius = square(mSweetSpotRadii[keyIndex]); - return squaredDistance / squaredRadius; -} - -bool ProximityInfo::hasInputCoordinates() const { - return mInputXCoordinates && mInputYCoordinates; -} - -int ProximityInfo::getKeyIndex(const int c) const { - if (KEY_COUNT == 0) { - // We do not have the coordinate data - return NOT_AN_INDEX; - } - const unsigned short baseLowerC = toBaseLowerCase(c); - if (baseLowerC > MAX_CHAR_CODE) { - return NOT_AN_INDEX; - } - return mCodeToKeyIndex[baseLowerC]; -} - -float ProximityInfo::calculateSquaredDistanceFromSweetSpotCenter( - const int keyIndex, const int inputIndex) const { - const float sweetSpotCenterX = mSweetSpotCenterXs[keyIndex]; - const float sweetSpotCenterY = mSweetSpotCenterYs[keyIndex]; - const float inputX = (float)mInputXCoordinates[inputIndex]; - const float inputY = (float)mInputYCoordinates[inputIndex]; - return square(inputX - sweetSpotCenterX) + square(inputY - sweetSpotCenterY); -} - -inline const int* ProximityInfo::getProximityCharsAt(const int index) const { - return mInputCodes + (index * MAX_PROXIMITY_CHARS_SIZE); -} - -unsigned short ProximityInfo::getPrimaryCharAt(const int index) const { - return getProximityCharsAt(index)[0]; -} - -inline bool ProximityInfo::existsCharInProximityAt(const int index, const int c) const { - const int *chars = getProximityCharsAt(index); - int i = 0; - while (chars[i] > 0 && i < MAX_PROXIMITY_CHARS_SIZE) { - if (chars[i++] == c) { - return true; - } - } - return false; -} - -bool ProximityInfo::existsAdjacentProximityChars(const int index) const { - if (index < 0 || index >= mInputLength) return false; - const int currentChar = getPrimaryCharAt(index); - const int leftIndex = index - 1; - if (leftIndex >= 0 && existsCharInProximityAt(leftIndex, currentChar)) { - return true; - } - const int rightIndex = index + 1; - if (rightIndex < mInputLength && existsCharInProximityAt(rightIndex, currentChar)) { - return true; - } - return false; -} - -// In the following function, c is the current character of the dictionary word -// currently examined. -// currentChars is an array containing the keys close to the character the -// user actually typed at the same position. We want to see if c is in it: if so, -// then the word contains at that position a character close to what the user -// typed. -// What the user typed is actually the first character of the array. -// proximityIndex is a pointer to the variable where getMatchedProximityId returns -// the index of c in the proximity chars of the input index. -// Notice : accented characters do not have a proximity list, so they are alone -// in their list. The non-accented version of the character should be considered -// "close", but not the other keys close to the non-accented version. -ProximityInfo::ProximityType ProximityInfo::getMatchedProximityId(const int index, - const unsigned short c, const bool checkProximityChars, int *proximityIndex) const { - const int *currentChars = getProximityCharsAt(index); - const int firstChar = currentChars[0]; - const unsigned short baseLowerC = toBaseLowerCase(c); - - // The first char in the array is what user typed. If it matches right away, - // that means the user typed that same char for this pos. - if (firstChar == baseLowerC || firstChar == c) { - return EQUIVALENT_CHAR; - } - - if (!checkProximityChars) return UNRELATED_CHAR; - - // If the non-accented, lowercased version of that first character matches c, - // then we have a non-accented version of the accented character the user - // typed. Treat it as a close char. - if (toBaseLowerCase(firstChar) == baseLowerC) - return NEAR_PROXIMITY_CHAR; - - // Not an exact nor an accent-alike match: search the list of close keys - int j = 1; - while (j < MAX_PROXIMITY_CHARS_SIZE - && currentChars[j] > ADDITIONAL_PROXIMITY_CHAR_DELIMITER_CODE) { - const bool matched = (currentChars[j] == baseLowerC || currentChars[j] == c); - if (matched) { - if (proximityIndex) { - *proximityIndex = j; - } - return NEAR_PROXIMITY_CHAR; - } - ++j; - } - if (j < MAX_PROXIMITY_CHARS_SIZE - && currentChars[j] == ADDITIONAL_PROXIMITY_CHAR_DELIMITER_CODE) { - ++j; - while (j < MAX_PROXIMITY_CHARS_SIZE - && currentChars[j] > ADDITIONAL_PROXIMITY_CHAR_DELIMITER_CODE) { - const bool matched = (currentChars[j] == baseLowerC || currentChars[j] == c); - if (matched) { - if (proximityIndex) { - *proximityIndex = j; - } - return ADDITIONAL_PROXIMITY_CHAR; - } - ++j; - } - } - - // Was not included, signal this as an unrelated character. - return UNRELATED_CHAR; -} - -bool ProximityInfo::sameAsTyped(const unsigned short *word, int length) const { - if (length != mInputLength) { - return false; - } - const int *inputCodes = mInputCodes; - while (length--) { - if ((unsigned int) *inputCodes != (unsigned int) *word) { - return false; - } - inputCodes += MAX_PROXIMITY_CHARS_SIZE; - word++; - } - return true; -} - -const int ProximityInfo::NORMALIZED_SQUARED_DISTANCE_SCALING_FACTOR_LOG_2; -const int ProximityInfo::NORMALIZED_SQUARED_DISTANCE_SCALING_FACTOR; -const int ProximityInfo::MAX_KEY_COUNT_IN_A_KEYBOARD; -const int ProximityInfo::MAX_CHAR_CODE; - -} // namespace latinime diff --git a/native/src/proximity_info.h b/native/src/proximity_info.h deleted file mode 100644 index c1eefeacc..000000000 --- a/native/src/proximity_info.h +++ /dev/null @@ -1,134 +0,0 @@ -/* - * Copyright (C) 2011 The Android Open Source Project - * - * Licensed under the Apache License, Version 2.0 (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.apache.org/licenses/LICENSE-2.0 - * - * Unless required by applicable law or agreed to in writing, software - * distributed under the License is distributed on an "AS IS" BASIS, - * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. - * See the License for the specific language governing permissions and - * limitations under the License. - */ - -#ifndef LATINIME_PROXIMITY_INFO_H -#define LATINIME_PROXIMITY_INFO_H - -#include <stdint.h> -#include <string> - -#include "defines.h" - -namespace latinime { - -class Correction; - -class ProximityInfo { - public: - static const int NORMALIZED_SQUARED_DISTANCE_SCALING_FACTOR_LOG_2 = 10; - static const int NORMALIZED_SQUARED_DISTANCE_SCALING_FACTOR = - 1 << NORMALIZED_SQUARED_DISTANCE_SCALING_FACTOR_LOG_2; - - // Used as a return value for character comparison - typedef enum { - // Same char, possibly with different case or accent - EQUIVALENT_CHAR, - // It is a char located nearby on the keyboard - NEAR_PROXIMITY_CHAR, - // It is an unrelated char - UNRELATED_CHAR, - // Additional proximity char which can differ by language. - ADDITIONAL_PROXIMITY_CHAR - } ProximityType; - - ProximityInfo(const std::string localeStr, const int maxProximityCharsSize, - const int keyboardWidth, const int keybaordHeight, const int gridWidth, - const int gridHeight, const int mostCommonkeyWidth, - const int32_t *proximityCharsArray, const int keyCount, const int32_t *keyXCoordinates, - const int32_t *keyYCoordinates, const int32_t *keyWidths, const int32_t *keyHeights, - const int32_t *keyCharCodes, const float *sweetSpotCenterXs, - const float *sweetSpotCenterYs, const float *sweetSpotRadii); - ~ProximityInfo(); - bool hasSpaceProximity(const int x, const int y) const; - void setInputParams(const int32_t *inputCodes, const int inputLength, - const int *xCoordinates, const int *yCoordinates); - const int* getProximityCharsAt(const int index) const; - unsigned short getPrimaryCharAt(const int index) const; - bool existsCharInProximityAt(const int index, const int c) const; - bool existsAdjacentProximityChars(const int index) const; - ProximityType getMatchedProximityId(const int index, const unsigned short c, - const bool checkProximityChars, int *proximityIndex = 0) const; - int getNormalizedSquaredDistance(const int inputIndex, const int proximityIndex) const { - return mNormalizedSquaredDistances[inputIndex * MAX_PROXIMITY_CHARS_SIZE + proximityIndex]; - } - bool sameAsTyped(const unsigned short *word, int length) const; - const unsigned short* getPrimaryInputWord() const { - return mPrimaryInputWord; - } - bool touchPositionCorrectionEnabled() const { - return mTouchPositionCorrectionEnabled; - } - - private: - // The max number of the keys in one keyboard layout - static const int MAX_KEY_COUNT_IN_A_KEYBOARD = 64; - // The upper limit of the char code in mCodeToKeyIndex - static const int MAX_CHAR_CODE = 127; - static const float NOT_A_DISTANCE_FLOAT = -1.0f; - static const int NOT_A_CODE = -1; - - int getStartIndexFromCoordinates(const int x, const int y) const; - void initializeCodeToKeyIndex(); - float calculateNormalizedSquaredDistance(const int keyIndex, const int inputIndex) const; - float calculateSquaredDistanceFromSweetSpotCenter( - const int keyIndex, const int inputIndex) const; - bool hasInputCoordinates() const; - int getKeyIndex(const int c) const; - bool hasSweetSpotData(const int keyIndex) const { - // When there are no calibration data for a key, - // the radius of the key is assigned to zero. - return mSweetSpotRadii[keyIndex] > 0.0; - } - bool isOnKey(const int keyId, const int x, const int y) const; - int squaredDistanceToEdge(const int keyId, const int x, const int y) const; - void calculateNearbyKeyCodes( - const int x, const int y, const int32_t primaryKey, int *inputCodes) const; - - const int MAX_PROXIMITY_CHARS_SIZE; - const int KEYBOARD_WIDTH; - const int KEYBOARD_HEIGHT; - const int GRID_WIDTH; - const int GRID_HEIGHT; - const int MOST_COMMON_KEY_WIDTH_SQUARE; - const int CELL_WIDTH; - const int CELL_HEIGHT; - const int KEY_COUNT; - const bool HAS_TOUCH_POSITION_CORRECTION_DATA; - const std::string mLocaleStr; - // TODO: remove this - const int *mInputCodesFromJava; - int32_t *mInputCodes; - const int *mInputXCoordinates; - const int *mInputYCoordinates; - bool mTouchPositionCorrectionEnabled; - int32_t *mProximityCharsArray; - int *mNormalizedSquaredDistances; - int32_t mKeyXCoordinates[MAX_KEY_COUNT_IN_A_KEYBOARD]; - int32_t mKeyYCoordinates[MAX_KEY_COUNT_IN_A_KEYBOARD]; - int32_t mKeyWidths[MAX_KEY_COUNT_IN_A_KEYBOARD]; - int32_t mKeyHeights[MAX_KEY_COUNT_IN_A_KEYBOARD]; - int32_t mKeyCharCodes[MAX_KEY_COUNT_IN_A_KEYBOARD]; - float mSweetSpotCenterXs[MAX_KEY_COUNT_IN_A_KEYBOARD]; - float mSweetSpotCenterYs[MAX_KEY_COUNT_IN_A_KEYBOARD]; - float mSweetSpotRadii[MAX_KEY_COUNT_IN_A_KEYBOARD]; - int mInputLength; - unsigned short mPrimaryInputWord[MAX_WORD_LENGTH_INTERNAL]; - int mCodeToKeyIndex[MAX_CHAR_CODE + 1]; -}; - -} // namespace latinime - -#endif // LATINIME_PROXIMITY_INFO_H diff --git a/native/src/terminal_attributes.h b/native/src/terminal_attributes.h deleted file mode 100644 index 1f9815936..000000000 --- a/native/src/terminal_attributes.h +++ /dev/null @@ -1,78 +0,0 @@ -/* - * Copyright (C) 2012 The Android Open Source Project - * - * Licensed under the Apache License, Version 2.0 (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.apache.org/licenses/LICENSE-2.0 - * - * Unless required by applicable law or agreed to in writing, software - * distributed under the License is distributed on an "AS IS" BASIS, - * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. - * See the License for the specific language governing permissions and - * limitations under the License. - */ - -#ifndef LATINIME_TERMINAL_ATTRIBUTES_H -#define LATINIME_TERMINAL_ATTRIBUTES_H - -#include "unigram_dictionary.h" - -namespace latinime { - -/** - * This class encapsulates information about a terminal that allows to - * retrieve local node attributes like the list of shortcuts without - * exposing the format structure to the client. - */ -class TerminalAttributes { - public: - class ShortcutIterator { - const uint8_t* const mDict; - bool mHasNextShortcutTarget; - int mPos; - - public: - ShortcutIterator(const uint8_t* dict, const int pos, const uint8_t flags) : mDict(dict), - mPos(pos) { - mHasNextShortcutTarget = (0 != (flags & UnigramDictionary::FLAG_HAS_SHORTCUT_TARGETS)); - } - - inline bool hasNextShortcutTarget() const { - return mHasNextShortcutTarget; - } - - // Gets the shortcut target itself as a uint16_t string. For parameters and return value - // see BinaryFormat::getWordAtAddress. - inline int getNextShortcutTarget(const int maxDepth, uint16_t* outWord) { - const int shortcutFlags = BinaryFormat::getFlagsAndForwardPointer(mDict, &mPos); - mHasNextShortcutTarget = - 0 != (shortcutFlags & UnigramDictionary::FLAG_ATTRIBUTE_HAS_NEXT); - int shortcutAddress = - BinaryFormat::getAttributeAddressAndForwardPointer(mDict, shortcutFlags, &mPos); - return BinaryFormat::getWordAtAddress(mDict, shortcutAddress, maxDepth, outWord); - } - }; - - private: - const uint8_t* const mDict; - const uint8_t mFlags; - const int mStartPos; - - public: - TerminalAttributes(const uint8_t* const dict, const uint8_t flags, const int pos) : - mDict(dict), mFlags(flags), mStartPos(pos) { - } - - inline bool isShortcutOnly() const { - return 0 != (mFlags & UnigramDictionary::FLAG_IS_SHORTCUT_ONLY); - } - - inline ShortcutIterator getShortcutIterator() const { - return ShortcutIterator(mDict, mStartPos, mFlags); - } -}; -} // namespace latinime - -#endif // LATINIME_TERMINAL_ATTRIBUTES_H diff --git a/native/src/unigram_dictionary.cpp b/native/src/unigram_dictionary.cpp deleted file mode 100644 index ed4c066f3..000000000 --- a/native/src/unigram_dictionary.cpp +++ /dev/null @@ -1,894 +0,0 @@ -/* -** -** Copyright 2010, The Android Open Source Project -** -** Licensed under the Apache License, Version 2.0 (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.apache.org/licenses/LICENSE-2.0 -** -** Unless required by applicable law or agreed to in writing, software -** distributed under the License is distributed on an "AS IS" BASIS, -** WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. -** See the License for the specific language governing permissions and -** limitations under the License. -*/ - -#include <assert.h> -#include <string.h> - -#define LOG_TAG "LatinIME: unigram_dictionary.cpp" - -#include "char_utils.h" -#include "dictionary.h" -#include "unigram_dictionary.h" - -#include "binary_format.h" -#include "terminal_attributes.h" - -namespace latinime { - -const UnigramDictionary::digraph_t UnigramDictionary::GERMAN_UMLAUT_DIGRAPHS[] = - { { 'a', 'e', 0x00E4 }, // U+00E4 : LATIN SMALL LETTER A WITH DIAERESIS - { 'o', 'e', 0x00F6 }, // U+00F6 : LATIN SMALL LETTER O WITH DIAERESIS - { 'u', 'e', 0x00FC } }; // U+00FC : LATIN SMALL LETTER U WITH DIAERESIS - -const UnigramDictionary::digraph_t UnigramDictionary::FRENCH_LIGATURES_DIGRAPHS[] = - { { 'a', 'e', 0x00E6 }, // U+00E6 : LATIN SMALL LETTER AE - { 'o', 'e', 0x0153 } }; // U+0153 : LATIN SMALL LIGATURE OE - -// TODO: check the header -UnigramDictionary::UnigramDictionary(const uint8_t* const streamStart, int typedLetterMultiplier, - int fullWordMultiplier, int maxWordLength, int maxWords, - const bool isLatestDictVersion) - : DICT_ROOT(streamStart), MAX_WORD_LENGTH(maxWordLength), MAX_WORDS(maxWords), - IS_LATEST_DICT_VERSION(isLatestDictVersion), - TYPED_LETTER_MULTIPLIER(typedLetterMultiplier), FULL_WORD_MULTIPLIER(fullWordMultiplier), - // TODO : remove this variable. - ROOT_POS(0), - BYTES_IN_ONE_CHAR(sizeof(int)), - MAX_DIGRAPH_SEARCH_DEPTH(DEFAULT_MAX_DIGRAPH_SEARCH_DEPTH) { - if (DEBUG_DICT) { - AKLOGI("UnigramDictionary - constructor"); - } -} - -UnigramDictionary::~UnigramDictionary() { -} - -static inline unsigned int getCodesBufferSize(const int *codes, const int codesSize) { - return sizeof(*codes) * codesSize; -} - -// TODO: This needs to take a const unsigned short* and not tinker with its contents -static inline void addWord( - unsigned short *word, int length, int frequency, WordsPriorityQueue *queue) { - queue->push(frequency, word, length); -} - -// Return the replacement code point for a digraph, or 0 if none. -int UnigramDictionary::getDigraphReplacement(const int *codes, const int i, const int codesSize, - const digraph_t* const digraphs, const unsigned int digraphsSize) const { - - // There can't be a digraph if we don't have at least 2 characters to examine - if (i + 2 > codesSize) return false; - - // Search for the first char of some digraph - int lastDigraphIndex = -1; - const int thisChar = codes[i]; - for (lastDigraphIndex = digraphsSize - 1; lastDigraphIndex >= 0; --lastDigraphIndex) { - if (thisChar == digraphs[lastDigraphIndex].first) break; - } - // No match: return early - if (lastDigraphIndex < 0) return 0; - - // It's an interesting digraph if the second char matches too. - if (digraphs[lastDigraphIndex].second == codes[i + 1]) { - return digraphs[lastDigraphIndex].replacement; - } else { - return 0; - } -} - -// Mostly the same arguments as the non-recursive version, except: -// codes is the original value. It points to the start of the work buffer, and gets passed as is. -// codesSize is the size of the user input (thus, it is the size of codesSrc). -// codesDest is the current point in the work buffer. -// codesSrc is the current point in the user-input, original, content-unmodified buffer. -// codesRemain is the remaining size in codesSrc. -void UnigramDictionary::getWordWithDigraphSuggestionsRec(ProximityInfo *proximityInfo, - const int *xcoordinates, const int *ycoordinates, const int *codesBuffer, - int *xCoordinatesBuffer, int *yCoordinatesBuffer, - const int codesBufferSize, const int flags, const int *codesSrc, - const int codesRemain, const int currentDepth, int *codesDest, Correction *correction, - WordsPriorityQueuePool *queuePool, - const digraph_t* const digraphs, const unsigned int digraphsSize) { - - const int startIndex = codesDest - codesBuffer; - if (currentDepth < MAX_DIGRAPH_SEARCH_DEPTH) { - for (int i = 0; i < codesRemain; ++i) { - xCoordinatesBuffer[startIndex + i] = xcoordinates[codesBufferSize - codesRemain + i]; - yCoordinatesBuffer[startIndex + i] = ycoordinates[codesBufferSize - codesRemain + i]; - const int replacementCodePoint = - getDigraphReplacement(codesSrc, i, codesRemain, digraphs, digraphsSize); - if (0 != replacementCodePoint) { - // Found a digraph. We will try both spellings. eg. the word is "pruefen" - - // Copy the word up to the first char of the digraph, including proximity chars, - // and overwrite the primary code with the replacement code point. Then, continue - // processing on the remaining part of the word, skipping the second char of the - // digraph. - // In our example, copy "pru", replace "u" with the version with the diaeresis and - // continue running on "fen". - // Make i the index of the second char of the digraph for simplicity. Forgetting - // to do that results in an infinite recursion so take care! - ++i; - memcpy(codesDest, codesSrc, i * BYTES_IN_ONE_CHAR); - codesDest[(i - 1) * (BYTES_IN_ONE_CHAR / sizeof(codesDest[0]))] = - replacementCodePoint; - getWordWithDigraphSuggestionsRec(proximityInfo, xcoordinates, ycoordinates, - codesBuffer, xCoordinatesBuffer, yCoordinatesBuffer, codesBufferSize, flags, - codesSrc + i + 1, codesRemain - i - 1, - currentDepth + 1, codesDest + i, correction, - queuePool, digraphs, digraphsSize); - - // Copy the second char of the digraph in place, then continue processing on - // the remaining part of the word. - // In our example, after "pru" in the buffer copy the "e", and continue on "fen" - memcpy(codesDest + i, codesSrc + i, BYTES_IN_ONE_CHAR); - getWordWithDigraphSuggestionsRec(proximityInfo, xcoordinates, ycoordinates, - codesBuffer, xCoordinatesBuffer, yCoordinatesBuffer, codesBufferSize, flags, - codesSrc + i, codesRemain - i, currentDepth + 1, - codesDest + i, correction, queuePool, - digraphs, digraphsSize); - return; - } - } - } - - // If we come here, we hit the end of the word: let's check it against the dictionary. - // In our example, we'll come here once for "prufen" and then once for "pruefen". - // If the word contains several digraphs, we'll come it for the product of them. - // eg. if the word is "ueberpruefen" we'll test, in order, against - // "uberprufen", "uberpruefen", "ueberprufen", "ueberpruefen". - const unsigned int remainingBytes = BYTES_IN_ONE_CHAR * codesRemain; - if (0 != remainingBytes) { - memcpy(codesDest, codesSrc, remainingBytes); - memcpy(&xCoordinatesBuffer[startIndex], &xcoordinates[codesBufferSize - codesRemain], - sizeof(int) * codesRemain); - memcpy(&yCoordinatesBuffer[startIndex], &ycoordinates[codesBufferSize - codesRemain], - sizeof(int) * codesRemain); - } - - getWordSuggestions(proximityInfo, xCoordinatesBuffer, yCoordinatesBuffer, codesBuffer, - startIndex + codesRemain, flags, correction, - queuePool); -} - -int UnigramDictionary::getSuggestions(ProximityInfo *proximityInfo, - WordsPriorityQueuePool *queuePool, Correction *correction, const int *xcoordinates, - const int *ycoordinates, const int *codes, const int codesSize, const int flags, - unsigned short *outWords, int *frequencies) { - - queuePool->clearAll(); - Correction* masterCorrection = correction; - if (REQUIRES_GERMAN_UMLAUT_PROCESSING & flags) - { // Incrementally tune the word and try all possibilities - int codesBuffer[getCodesBufferSize(codes, codesSize)]; - int xCoordinatesBuffer[codesSize]; - int yCoordinatesBuffer[codesSize]; - getWordWithDigraphSuggestionsRec(proximityInfo, xcoordinates, ycoordinates, codesBuffer, - xCoordinatesBuffer, yCoordinatesBuffer, - codesSize, flags, codes, codesSize, 0, codesBuffer, masterCorrection, queuePool, - GERMAN_UMLAUT_DIGRAPHS, - sizeof(GERMAN_UMLAUT_DIGRAPHS) / sizeof(GERMAN_UMLAUT_DIGRAPHS[0])); - } else if (REQUIRES_FRENCH_LIGATURES_PROCESSING & flags) { - int codesBuffer[getCodesBufferSize(codes, codesSize)]; - int xCoordinatesBuffer[codesSize]; - int yCoordinatesBuffer[codesSize]; - getWordWithDigraphSuggestionsRec(proximityInfo, xcoordinates, ycoordinates, codesBuffer, - xCoordinatesBuffer, yCoordinatesBuffer, - codesSize, flags, codes, codesSize, 0, codesBuffer, masterCorrection, queuePool, - FRENCH_LIGATURES_DIGRAPHS, - sizeof(FRENCH_LIGATURES_DIGRAPHS) / sizeof(FRENCH_LIGATURES_DIGRAPHS[0])); - } else { // Normal processing - getWordSuggestions(proximityInfo, xcoordinates, ycoordinates, codes, codesSize, flags, - masterCorrection, queuePool); - } - - PROF_START(20); - if (DEBUG_DICT) { - double ns = queuePool->getMasterQueue()->getHighestNormalizedScore( - proximityInfo->getPrimaryInputWord(), codesSize, 0, 0, 0); - ns += 0; - AKLOGI("Max normalized score = %f", ns); - } - const int suggestedWordsCount = - queuePool->getMasterQueue()->outputSuggestions(frequencies, outWords); - - if (DEBUG_DICT) { - double ns = queuePool->getMasterQueue()->getHighestNormalizedScore( - proximityInfo->getPrimaryInputWord(), codesSize, 0, 0, 0); - ns += 0; - AKLOGI("Returning %d words", suggestedWordsCount); - /// Print the returned words - for (int j = 0; j < suggestedWordsCount; ++j) { - short unsigned int* w = outWords + j * MAX_WORD_LENGTH; - char s[MAX_WORD_LENGTH]; - for (int i = 0; i <= MAX_WORD_LENGTH; i++) s[i] = w[i]; - AKLOGI("%s %i", s, frequencies[j]); - } - } - PROF_END(20); - PROF_CLOSE; - return suggestedWordsCount; -} - -void UnigramDictionary::getWordSuggestions(ProximityInfo *proximityInfo, - const int *xcoordinates, const int *ycoordinates, const int *codes, - const int inputLength, const int flags, Correction *correction, - WordsPriorityQueuePool *queuePool) { - - PROF_OPEN; - PROF_START(0); - PROF_END(0); - - PROF_START(1); - const bool useFullEditDistance = USE_FULL_EDIT_DISTANCE & flags; - getOneWordSuggestions(proximityInfo, xcoordinates, ycoordinates, codes, useFullEditDistance, - inputLength, correction, queuePool); - PROF_END(1); - - PROF_START(2); - // Note: This line is intentionally left blank - PROF_END(2); - - PROF_START(3); - // Note: This line is intentionally left blank - PROF_END(3); - - PROF_START(4); - bool hasAutoCorrectionCandidate = false; - WordsPriorityQueue* masterQueue = queuePool->getMasterQueue(); - if (masterQueue->size() > 0) { - double nsForMaster = masterQueue->getHighestNormalizedScore( - proximityInfo->getPrimaryInputWord(), inputLength, 0, 0, 0); - hasAutoCorrectionCandidate = (nsForMaster > START_TWO_WORDS_CORRECTION_THRESHOLD); - } - PROF_END(4); - - PROF_START(5); - // Multiple word suggestions - if (SUGGEST_MULTIPLE_WORDS - && inputLength >= MIN_USER_TYPED_LENGTH_FOR_MULTIPLE_WORD_SUGGESTION) { - getSplitMultipleWordsSuggestions(proximityInfo, xcoordinates, ycoordinates, codes, - useFullEditDistance, inputLength, correction, queuePool, - hasAutoCorrectionCandidate); - } - PROF_END(5); - - PROF_START(6); - // Note: This line is intentionally left blank - PROF_END(6); - - if (DEBUG_DICT) { - queuePool->dumpSubQueue1TopSuggestions(); - for (int i = 0; i < SUB_QUEUE_MAX_COUNT; ++i) { - WordsPriorityQueue* queue = queuePool->getSubQueue(FIRST_WORD_INDEX, i); - if (queue->size() > 0) { - WordsPriorityQueue::SuggestedWord* sw = queue->top(); - const int score = sw->mScore; - const unsigned short* word = sw->mWord; - const int wordLength = sw->mWordLength; - double ns = Correction::RankingAlgorithm::calcNormalizedScore( - proximityInfo->getPrimaryInputWord(), i, word, wordLength, score); - ns += 0; - AKLOGI("--- TOP SUB WORDS for %d --- %d %f [%d]", i, score, ns, - (ns > TWO_WORDS_CORRECTION_WITH_OTHER_ERROR_THRESHOLD)); - DUMP_WORD(proximityInfo->getPrimaryInputWord(), i); - DUMP_WORD(word, wordLength); - } - } - } -} - -void UnigramDictionary::initSuggestions(ProximityInfo *proximityInfo, const int *xCoordinates, - const int *yCoordinates, const int *codes, const int inputLength, Correction *correction) { - if (DEBUG_DICT) { - AKLOGI("initSuggest"); - } - proximityInfo->setInputParams(codes, inputLength, xCoordinates, yCoordinates); - const int maxDepth = min(inputLength * MAX_DEPTH_MULTIPLIER, MAX_WORD_LENGTH); - correction->initCorrection(proximityInfo, inputLength, maxDepth); -} - -static const char QUOTE = '\''; -static const char SPACE = ' '; - -void UnigramDictionary::getOneWordSuggestions(ProximityInfo *proximityInfo, - const int *xcoordinates, const int *ycoordinates, const int *codes, - const bool useFullEditDistance, const int inputLength, Correction *correction, - WordsPriorityQueuePool *queuePool) { - initSuggestions(proximityInfo, xcoordinates, ycoordinates, codes, inputLength, correction); - getSuggestionCandidates(useFullEditDistance, inputLength, correction, queuePool, - true /* doAutoCompletion */, DEFAULT_MAX_ERRORS, FIRST_WORD_INDEX); -} - -void UnigramDictionary::getSuggestionCandidates(const bool useFullEditDistance, - const int inputLength, Correction *correction, WordsPriorityQueuePool *queuePool, - const bool doAutoCompletion, const int maxErrors, const int currentWordIndex) { - // TODO: Remove setCorrectionParams - correction->setCorrectionParams(0, 0, 0, - -1 /* spaceProximityPos */, -1 /* missingSpacePos */, useFullEditDistance, - doAutoCompletion, maxErrors); - int rootPosition = ROOT_POS; - // Get the number of children of root, then increment the position - int childCount = BinaryFormat::getGroupCountAndForwardPointer(DICT_ROOT, &rootPosition); - int outputIndex = 0; - - correction->initCorrectionState(rootPosition, childCount, (inputLength <= 0)); - - // Depth first search - while (outputIndex >= 0) { - if (correction->initProcessState(outputIndex)) { - int siblingPos = correction->getTreeSiblingPos(outputIndex); - int firstChildPos; - - const bool needsToTraverseChildrenNodes = processCurrentNode(siblingPos, - correction, &childCount, &firstChildPos, &siblingPos, queuePool, - currentWordIndex); - // Update next sibling pos - correction->setTreeSiblingPos(outputIndex, siblingPos); - - if (needsToTraverseChildrenNodes) { - // Goes to child node - outputIndex = correction->goDownTree(outputIndex, childCount, firstChildPos); - } - } else { - // Goes to parent sibling node - outputIndex = correction->getTreeParentIndex(outputIndex); - } - } -} - -inline void UnigramDictionary::onTerminal(const int freq, - const TerminalAttributes& terminalAttributes, Correction *correction, - WordsPriorityQueuePool *queuePool, const bool addToMasterQueue, - const int currentWordIndex) { - const int inputIndex = correction->getInputIndex(); - const bool addToSubQueue = inputIndex < SUB_QUEUE_MAX_COUNT; - - int wordLength; - unsigned short* wordPointer; - - if ((currentWordIndex == FIRST_WORD_INDEX) && addToMasterQueue) { - WordsPriorityQueue *masterQueue = queuePool->getMasterQueue(); - const int finalFreq = correction->getFinalFreq(freq, &wordPointer, &wordLength); - if (finalFreq != NOT_A_FREQUENCY) { - if (!terminalAttributes.isShortcutOnly()) { - addWord(wordPointer, wordLength, finalFreq, masterQueue); - } - - // Please note that the shortcut candidates will be added to the master queue only. - TerminalAttributes::ShortcutIterator iterator = - terminalAttributes.getShortcutIterator(); - while (iterator.hasNextShortcutTarget()) { - // TODO: addWord only supports weak ordering, meaning we have no means - // to control the order of the shortcuts relative to one another or to the word. - // We need to either modulate the frequency of each shortcut according - // to its own shortcut frequency or to make the queue - // so that the insert order is protected inside the queue for words - // with the same score. - uint16_t shortcutTarget[MAX_WORD_LENGTH_INTERNAL]; - const int shortcutTargetStringLength = iterator.getNextShortcutTarget( - MAX_WORD_LENGTH_INTERNAL, shortcutTarget); - addWord(shortcutTarget, shortcutTargetStringLength, finalFreq, masterQueue); - } - } - } - - // We only allow two words + other error correction for words with SUB_QUEUE_MIN_WORD_LENGTH - // or more length. - if (inputIndex >= SUB_QUEUE_MIN_WORD_LENGTH && addToSubQueue) { - WordsPriorityQueue *subQueue; - subQueue = queuePool->getSubQueue(currentWordIndex, inputIndex); - if (!subQueue) { - return; - } - const int finalFreq = correction->getFinalFreqForSubQueue(freq, &wordPointer, &wordLength, - inputIndex); - addWord(wordPointer, wordLength, finalFreq, subQueue); - } -} - -bool UnigramDictionary::getSubStringSuggestion( - ProximityInfo *proximityInfo, const int *xcoordinates, const int *ycoordinates, - const int *codes, const bool useFullEditDistance, Correction *correction, - WordsPriorityQueuePool* queuePool, const int inputLength, - const bool hasAutoCorrectionCandidate, const int currentWordIndex, - const int inputWordStartPos, const int inputWordLength, - const int outputWordStartPos, const bool isSpaceProximity, int *freqArray, - int*wordLengthArray, unsigned short* outputWord, int *outputWordLength) { - unsigned short* tempOutputWord = 0; - int nextWordLength = 0; - // TODO: Optimize init suggestion - initSuggestions(proximityInfo, xcoordinates, ycoordinates, codes, - inputLength, correction); - - int freq = getMostFrequentWordLike( - inputWordStartPos, inputWordLength, proximityInfo, mWord); - if (freq > 0) { - nextWordLength = inputWordLength; - tempOutputWord = mWord; - } else if (!hasAutoCorrectionCandidate) { - if (inputWordStartPos > 0) { - const int offset = inputWordStartPos; - initSuggestions(proximityInfo, &xcoordinates[offset], &ycoordinates[offset], - codes + offset, inputWordLength, correction); - queuePool->clearSubQueue(currentWordIndex); - getSuggestionCandidates(useFullEditDistance, inputWordLength, correction, - queuePool, false, MAX_ERRORS_FOR_TWO_WORDS, currentWordIndex); - if (DEBUG_DICT) { - if (currentWordIndex < MULTIPLE_WORDS_SUGGESTION_MAX_WORDS) { - AKLOGI("Dump word candidates(%d) %d", currentWordIndex, inputWordLength); - for (int i = 0; i < SUB_QUEUE_MAX_COUNT; ++i) { - queuePool->getSubQueue(currentWordIndex, i)->dumpTopWord(); - } - } - } - } - WordsPriorityQueue* queue = queuePool->getSubQueue(currentWordIndex, inputWordLength); - if (!queue || queue->size() < 1) { - return false; - } - int score = 0; - const double ns = queue->getHighestNormalizedScore( - proximityInfo->getPrimaryInputWord(), inputWordLength, - &tempOutputWord, &score, &nextWordLength); - if (DEBUG_DICT) { - AKLOGI("NS(%d) = %f, Score = %d", currentWordIndex, ns, score); - } - // Two words correction won't be done if the score of the first word doesn't exceed the - // threshold. - if (ns < TWO_WORDS_CORRECTION_WITH_OTHER_ERROR_THRESHOLD - || nextWordLength < SUB_QUEUE_MIN_WORD_LENGTH) { - return false; - } - freq = score >> (nextWordLength + TWO_WORDS_PLUS_OTHER_ERROR_CORRECTION_DEMOTION_DIVIDER); - } - if (DEBUG_DICT) { - AKLOGI("Freq(%d): %d, length: %d, input length: %d, input start: %d (%d)" - , currentWordIndex, freq, nextWordLength, inputWordLength, inputWordStartPos, - wordLengthArray[0]); - } - if (freq <= 0 || nextWordLength <= 0 - || MAX_WORD_LENGTH <= (outputWordStartPos + nextWordLength)) { - return false; - } - for (int i = 0; i < nextWordLength; ++i) { - outputWord[outputWordStartPos + i] = tempOutputWord[i]; - } - - // Put output values - freqArray[currentWordIndex] = freq; - // TODO: put output length instead of input length - wordLengthArray[currentWordIndex] = inputWordLength; - const int tempOutputWordLength = outputWordStartPos + nextWordLength; - if (outputWordLength) { - *outputWordLength = tempOutputWordLength; - } - - if ((inputWordStartPos + inputWordLength) < inputLength) { - if (outputWordStartPos + nextWordLength >= MAX_WORD_LENGTH) { - return false; - } - outputWord[tempOutputWordLength] = SPACE; - if (outputWordLength) { - ++*outputWordLength; - } - } else if (currentWordIndex >= 1) { - // TODO: Handle 3 or more words - const int pairFreq = correction->getFreqForSplitMultipleWords( - freqArray, wordLengthArray, currentWordIndex + 1, isSpaceProximity, outputWord); - if (DEBUG_DICT) { - DUMP_WORD(outputWord, tempOutputWordLength); - AKLOGI("Split two words: %d, %d, %d, %d, (%d) %d", freqArray[0], freqArray[1], pairFreq, - inputLength, wordLengthArray[0], tempOutputWordLength); - } - addWord(outputWord, tempOutputWordLength, pairFreq, queuePool->getMasterQueue()); - } - return true; -} - -void UnigramDictionary::getMultiWordsSuggestionRec(ProximityInfo *proximityInfo, - const int *xcoordinates, const int *ycoordinates, const int *codes, - const bool useFullEditDistance, const int inputLength, - Correction *correction, WordsPriorityQueuePool* queuePool, - const bool hasAutoCorrectionCandidate, const int startInputPos, const int startWordIndex, - const int outputWordLength, int *freqArray, int* wordLengthArray, - unsigned short* outputWord) { - if (startWordIndex >= (MULTIPLE_WORDS_SUGGESTION_MAX_WORDS - 1)) { - // Return if the last word index - return; - } - if (startWordIndex >= 1 - && (hasAutoCorrectionCandidate - || inputLength < MIN_INPUT_LENGTH_FOR_THREE_OR_MORE_WORDS_CORRECTION)) { - // Do not suggest 3+ words if already has auto correction candidate - return; - } - for (int i = startInputPos + 1; i < inputLength; ++i) { - if (DEBUG_CORRECTION_FREQ) { - AKLOGI("Multi words(%d), start in %d sep %d start out %d", - startWordIndex, startInputPos, i, outputWordLength); - DUMP_WORD(outputWord, outputWordLength); - } - int tempOutputWordLength = 0; - // Current word - int inputWordStartPos = startInputPos; - int inputWordLength = i - startInputPos; - if (!getSubStringSuggestion(proximityInfo, xcoordinates, ycoordinates, codes, - useFullEditDistance, correction, queuePool, inputLength, hasAutoCorrectionCandidate, - startWordIndex, inputWordStartPos, inputWordLength, outputWordLength, - true /* not used */, freqArray, wordLengthArray, outputWord, - &tempOutputWordLength)) { - continue; - } - - if (DEBUG_CORRECTION_FREQ) { - AKLOGI("Do missing space correction"); - } - // Next word - // Missing space - inputWordStartPos = i; - inputWordLength = inputLength - i; - if(!getSubStringSuggestion(proximityInfo, xcoordinates, ycoordinates, codes, - useFullEditDistance, correction, queuePool, inputLength, hasAutoCorrectionCandidate, - startWordIndex + 1, inputWordStartPos, inputWordLength, tempOutputWordLength, - false /* missing space */, freqArray, wordLengthArray, outputWord, 0)) { - getMultiWordsSuggestionRec(proximityInfo, xcoordinates, ycoordinates, codes, - useFullEditDistance, inputLength, correction, queuePool, - hasAutoCorrectionCandidate, inputWordStartPos, startWordIndex + 1, - tempOutputWordLength, freqArray, wordLengthArray, outputWord); - } - - // Mistyped space - ++inputWordStartPos; - --inputWordLength; - - if (inputWordLength <= 0) { - continue; - } - - const int x = xcoordinates[inputWordStartPos - 1]; - const int y = ycoordinates[inputWordStartPos - 1]; - if (!proximityInfo->hasSpaceProximity(x, y)) { - continue; - } - - if (DEBUG_CORRECTION_FREQ) { - AKLOGI("Do mistyped space correction"); - } - getSubStringSuggestion(proximityInfo, xcoordinates, ycoordinates, codes, - useFullEditDistance, correction, queuePool, inputLength, hasAutoCorrectionCandidate, - startWordIndex + 1, inputWordStartPos, inputWordLength, tempOutputWordLength, - true /* mistyped space */, freqArray, wordLengthArray, outputWord, 0); - } -} - -void UnigramDictionary::getSplitMultipleWordsSuggestions(ProximityInfo *proximityInfo, - const int *xcoordinates, const int *ycoordinates, const int *codes, - const bool useFullEditDistance, const int inputLength, - Correction *correction, WordsPriorityQueuePool* queuePool, - const bool hasAutoCorrectionCandidate) { - if (inputLength >= MAX_WORD_LENGTH) return; - if (DEBUG_DICT) { - AKLOGI("--- Suggest multiple words"); - } - - // Allocating fixed length array on stack - unsigned short outputWord[MAX_WORD_LENGTH]; - int freqArray[MULTIPLE_WORDS_SUGGESTION_MAX_WORDS]; - int wordLengthArray[MULTIPLE_WORDS_SUGGESTION_MAX_WORDS]; - const int outputWordLength = 0; - const int startInputPos = 0; - const int startWordIndex = 0; - getMultiWordsSuggestionRec(proximityInfo, xcoordinates, ycoordinates, codes, - useFullEditDistance, inputLength, correction, queuePool, hasAutoCorrectionCandidate, - startInputPos, startWordIndex, outputWordLength, freqArray, wordLengthArray, - outputWord); -} - -// Wrapper for getMostFrequentWordLikeInner, which matches it to the previous -// interface. -inline int UnigramDictionary::getMostFrequentWordLike(const int startInputIndex, - const int inputLength, ProximityInfo *proximityInfo, unsigned short *word) { - uint16_t inWord[inputLength]; - - for (int i = 0; i < inputLength; ++i) { - inWord[i] = (uint16_t)proximityInfo->getPrimaryCharAt(startInputIndex + i); - } - return getMostFrequentWordLikeInner(inWord, inputLength, word); -} - -// This function will take the position of a character array within a CharGroup, -// and check it actually like-matches the word in inWord starting at startInputIndex, -// that is, it matches it with case and accents squashed. -// The function returns true if there was a full match, false otherwise. -// The function will copy on-the-fly the characters in the CharGroup to outNewWord. -// It will also place the end position of the array in outPos; in outInputIndex, -// it will place the index of the first char AFTER the match if there was a match, -// and the initial position if there was not. It makes sense because if there was -// a match we want to continue searching, but if there was not, we want to go to -// the next CharGroup. -// In and out parameters may point to the same location. This function takes care -// not to use any input parameters after it wrote into its outputs. -static inline bool testCharGroupForContinuedLikeness(const uint8_t flags, - const uint8_t* const root, const int startPos, - const uint16_t* const inWord, const int startInputIndex, - int32_t* outNewWord, int* outInputIndex, int* outPos) { - const bool hasMultipleChars = (0 != (UnigramDictionary::FLAG_HAS_MULTIPLE_CHARS & flags)); - int pos = startPos; - int32_t character = BinaryFormat::getCharCodeAndForwardPointer(root, &pos); - int32_t baseChar = toBaseLowerCase(character); - const uint16_t wChar = toBaseLowerCase(inWord[startInputIndex]); - - if (baseChar != wChar) { - *outPos = hasMultipleChars ? BinaryFormat::skipOtherCharacters(root, pos) : pos; - *outInputIndex = startInputIndex; - return false; - } - int inputIndex = startInputIndex; - outNewWord[inputIndex] = character; - if (hasMultipleChars) { - character = BinaryFormat::getCharCodeAndForwardPointer(root, &pos); - while (NOT_A_CHARACTER != character) { - baseChar = toBaseLowerCase(character); - if (toBaseLowerCase(inWord[++inputIndex]) != baseChar) { - *outPos = BinaryFormat::skipOtherCharacters(root, pos); - *outInputIndex = startInputIndex; - return false; - } - outNewWord[inputIndex] = character; - character = BinaryFormat::getCharCodeAndForwardPointer(root, &pos); - } - } - *outInputIndex = inputIndex + 1; - *outPos = pos; - return true; -} - -// This function is invoked when a word like the word searched for is found. -// It will compare the frequency to the max frequency, and if greater, will -// copy the word into the output buffer. In output value maxFreq, it will -// write the new maximum frequency if it changed. -static inline void onTerminalWordLike(const int freq, int32_t* newWord, const int length, - short unsigned int* outWord, int* maxFreq) { - if (freq > *maxFreq) { - for (int q = 0; q < length; ++q) - outWord[q] = newWord[q]; - outWord[length] = 0; - *maxFreq = freq; - } -} - -// Will find the highest frequency of the words like the one passed as an argument, -// that is, everything that only differs by case/accents. -int UnigramDictionary::getMostFrequentWordLikeInner(const uint16_t * const inWord, - const int length, short unsigned int* outWord) { - int32_t newWord[MAX_WORD_LENGTH_INTERNAL]; - int depth = 0; - int maxFreq = -1; - const uint8_t* const root = DICT_ROOT; - - int startPos = 0; - mStackChildCount[0] = BinaryFormat::getGroupCountAndForwardPointer(root, &startPos); - mStackInputIndex[0] = 0; - mStackSiblingPos[0] = startPos; - while (depth >= 0) { - const int charGroupCount = mStackChildCount[depth]; - int pos = mStackSiblingPos[depth]; - for (int charGroupIndex = charGroupCount - 1; charGroupIndex >= 0; --charGroupIndex) { - int inputIndex = mStackInputIndex[depth]; - const uint8_t flags = BinaryFormat::getFlagsAndForwardPointer(root, &pos); - // Test whether all chars in this group match with the word we are searching for. If so, - // we want to traverse its children (or if the length match, evaluate its frequency). - // Note that this function will output the position regardless, but will only write - // into inputIndex if there is a match. - const bool isAlike = testCharGroupForContinuedLikeness(flags, root, pos, inWord, - inputIndex, newWord, &inputIndex, &pos); - if (isAlike && (FLAG_IS_TERMINAL & flags) && (inputIndex == length)) { - const int frequency = BinaryFormat::readFrequencyWithoutMovingPointer(root, pos); - onTerminalWordLike(frequency, newWord, inputIndex, outWord, &maxFreq); - } - pos = BinaryFormat::skipFrequency(flags, pos); - const int siblingPos = BinaryFormat::skipChildrenPosAndAttributes(root, flags, pos); - const int childrenNodePos = BinaryFormat::readChildrenPosition(root, flags, pos); - // If we had a match and the word has children, we want to traverse them. We don't have - // to traverse words longer than the one we are searching for, since they will not match - // anyway, so don't traverse unless inputIndex < length. - if (isAlike && (-1 != childrenNodePos) && (inputIndex < length)) { - // Save position for this depth, to get back to this once children are done - mStackChildCount[depth] = charGroupIndex; - mStackSiblingPos[depth] = siblingPos; - // Prepare stack values for next depth - ++depth; - int childrenPos = childrenNodePos; - mStackChildCount[depth] = - BinaryFormat::getGroupCountAndForwardPointer(root, &childrenPos); - mStackSiblingPos[depth] = childrenPos; - mStackInputIndex[depth] = inputIndex; - pos = childrenPos; - // Go to the next depth level. - ++depth; - break; - } else { - // No match, or no children, or word too long to ever match: go the next sibling. - pos = siblingPos; - } - } - --depth; - } - return maxFreq; -} - -bool UnigramDictionary::isValidWord(const uint16_t* const inWord, const int length) const { - return NOT_VALID_WORD != BinaryFormat::getTerminalPosition(DICT_ROOT, inWord, length); -} - -// TODO: remove this function. -int UnigramDictionary::getBigramPosition(int pos, unsigned short *word, int offset, - int length) const { - return -1; -} - -// ProcessCurrentNode returns a boolean telling whether to traverse children nodes or not. -// If the return value is false, then the caller should read in the output "nextSiblingPosition" -// to find out the address of the next sibling node and pass it to a new call of processCurrentNode. -// It is worthy to note that when false is returned, the output values other than -// nextSiblingPosition are undefined. -// If the return value is true, then the caller must proceed to traverse the children of this -// node. processCurrentNode will output the information about the children: their count in -// newCount, their position in newChildrenPosition, the traverseAllNodes flag in -// newTraverseAllNodes, the match weight into newMatchRate, the input index into newInputIndex, the -// diffs into newDiffs, the sibling position in nextSiblingPosition, and the output index into -// newOutputIndex. Please also note the following caveat: processCurrentNode does not know when -// there aren't any more nodes at this level, it merely returns the address of the first byte after -// the current node in nextSiblingPosition. Thus, the caller must keep count of the nodes at any -// given level, as output into newCount when traversing this level's parent. -inline bool UnigramDictionary::processCurrentNode(const int initialPos, - Correction *correction, int *newCount, - int *newChildrenPosition, int *nextSiblingPosition, WordsPriorityQueuePool *queuePool, - const int currentWordIndex) { - if (DEBUG_DICT) { - correction->checkState(); - } - int pos = initialPos; - - // Flags contain the following information: - // - Address type (MASK_GROUP_ADDRESS_TYPE) on two bits: - // - FLAG_GROUP_ADDRESS_TYPE_{ONE,TWO,THREE}_BYTES means there are children and their address - // is on the specified number of bytes. - // - FLAG_GROUP_ADDRESS_TYPE_NOADDRESS means there are no children, and therefore no address. - // - FLAG_HAS_MULTIPLE_CHARS: whether this node has multiple char or not. - // - FLAG_IS_TERMINAL: whether this node is a terminal or not (it may still have children) - // - FLAG_HAS_BIGRAMS: whether this node has bigrams or not - const uint8_t flags = BinaryFormat::getFlagsAndForwardPointer(DICT_ROOT, &pos); - const bool hasMultipleChars = (0 != (FLAG_HAS_MULTIPLE_CHARS & flags)); - const bool isTerminalNode = (0 != (FLAG_IS_TERMINAL & flags)); - - bool needsToInvokeOnTerminal = false; - - // This gets only ONE character from the stream. Next there will be: - // if FLAG_HAS_MULTIPLE CHARS: the other characters of the same node - // else if FLAG_IS_TERMINAL: the frequency - // else if MASK_GROUP_ADDRESS_TYPE is not NONE: the children address - // Note that you can't have a node that both is not a terminal and has no children. - int32_t c = BinaryFormat::getCharCodeAndForwardPointer(DICT_ROOT, &pos); - assert(NOT_A_CHARACTER != c); - - // We are going to loop through each character and make it look like it's a different - // node each time. To do that, we will process characters in this node in order until - // we find the character terminator. This is signalled by getCharCode* returning - // NOT_A_CHARACTER. - // As a special case, if there is only one character in this node, we must not read the - // next bytes so we will simulate the NOT_A_CHARACTER return by testing the flags. - // This way, each loop run will look like a "virtual node". - do { - // We prefetch the next char. If 'c' is the last char of this node, we will have - // NOT_A_CHARACTER in the next char. From this we can decide whether this virtual node - // should behave as a terminal or not and whether we have children. - const int32_t nextc = hasMultipleChars - ? BinaryFormat::getCharCodeAndForwardPointer(DICT_ROOT, &pos) : NOT_A_CHARACTER; - const bool isLastChar = (NOT_A_CHARACTER == nextc); - // If there are more chars in this nodes, then this virtual node is not a terminal. - // If we are on the last char, this virtual node is a terminal if this node is. - const bool isTerminal = isLastChar && isTerminalNode; - - Correction::CorrectionType stateType = correction->processCharAndCalcState( - c, isTerminal); - if (stateType == Correction::TRAVERSE_ALL_ON_TERMINAL - || stateType == Correction::ON_TERMINAL) { - needsToInvokeOnTerminal = true; - } else if (stateType == Correction::UNRELATED || correction->needsToPrune()) { - // We found that this is an unrelated character, so we should give up traversing - // this node and its children entirely. - // However we may not be on the last virtual node yet so we skip the remaining - // characters in this node, the frequency if it's there, read the next sibling - // position to output it, then return false. - // We don't have to output other values because we return false, as in - // "don't traverse children". - if (!isLastChar) { - pos = BinaryFormat::skipOtherCharacters(DICT_ROOT, pos); - } - pos = BinaryFormat::skipFrequency(flags, pos); - *nextSiblingPosition = - BinaryFormat::skipChildrenPosAndAttributes(DICT_ROOT, flags, pos); - return false; - } - - // Prepare for the next character. Promote the prefetched char to current char - the loop - // will take care of prefetching the next. If we finally found our last char, nextc will - // contain NOT_A_CHARACTER. - c = nextc; - } while (NOT_A_CHARACTER != c); - - if (isTerminalNode) { - // The frequency should be here, because we come here only if this is actually - // a terminal node, and we are on its last char. - const int freq = BinaryFormat::readFrequencyWithoutMovingPointer(DICT_ROOT, pos); - const int childrenAddressPos = BinaryFormat::skipFrequency(flags, pos); - const int attributesPos = BinaryFormat::skipChildrenPosition(flags, childrenAddressPos); - TerminalAttributes terminalAttributes(DICT_ROOT, flags, attributesPos); - onTerminal(freq, terminalAttributes, correction, queuePool, needsToInvokeOnTerminal, - currentWordIndex); - - // If there are more chars in this node, then this virtual node has children. - // If we are on the last char, this virtual node has children if this node has. - const bool hasChildren = BinaryFormat::hasChildrenInFlags(flags); - - // This character matched the typed character (enough to traverse the node at least) - // so we just evaluated it. Now we should evaluate this virtual node's children - that - // is, if it has any. If it has no children, we're done here - so we skip the end of - // the node, output the siblings position, and return false "don't traverse children". - // Note that !hasChildren implies isLastChar, so we know we don't have to skip any - // remaining char in this group for there can't be any. - if (!hasChildren) { - pos = BinaryFormat::skipFrequency(flags, pos); - *nextSiblingPosition = - BinaryFormat::skipChildrenPosAndAttributes(DICT_ROOT, flags, pos); - return false; - } - - // Optimization: Prune out words that are too long compared to how much was typed. - if (correction->needsToPrune()) { - pos = BinaryFormat::skipFrequency(flags, pos); - *nextSiblingPosition = - BinaryFormat::skipChildrenPosAndAttributes(DICT_ROOT, flags, pos); - if (DEBUG_DICT_FULL) { - AKLOGI("Traversing was pruned."); - } - return false; - } - } - - // Now we finished processing this node, and we want to traverse children. If there are no - // children, we can't come here. - assert(BinaryFormat::hasChildrenInFlags(flags)); - - // If this node was a terminal it still has the frequency under the pointer (it may have been - // read, but not skipped - see readFrequencyWithoutMovingPointer). - // Next come the children position, then possibly attributes (attributes are bigrams only for - // now, maybe something related to shortcuts in the future). - // Once this is read, we still need to output the number of nodes in the immediate children of - // this node, so we read and output it before returning true, as in "please traverse children". - pos = BinaryFormat::skipFrequency(flags, pos); - int childrenPos = BinaryFormat::readChildrenPosition(DICT_ROOT, flags, pos); - *nextSiblingPosition = BinaryFormat::skipChildrenPosAndAttributes(DICT_ROOT, flags, pos); - *newCount = BinaryFormat::getGroupCountAndForwardPointer(DICT_ROOT, &childrenPos); - *newChildrenPosition = childrenPos; - return true; -} - -} // namespace latinime diff --git a/native/src/unigram_dictionary.h b/native/src/unigram_dictionary.h deleted file mode 100644 index c8f15566c..000000000 --- a/native/src/unigram_dictionary.h +++ /dev/null @@ -1,173 +0,0 @@ -/* - * Copyright (C) 2010 The Android Open Source Project - * - * Licensed under the Apache License, Version 2.0 (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.apache.org/licenses/LICENSE-2.0 - * - * Unless required by applicable law or agreed to in writing, software - * distributed under the License is distributed on an "AS IS" BASIS, - * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. - * See the License for the specific language governing permissions and - * limitations under the License. - */ - -#ifndef LATINIME_UNIGRAM_DICTIONARY_H -#define LATINIME_UNIGRAM_DICTIONARY_H - -#include <stdint.h> -#include "correction.h" -#include "correction_state.h" -#include "defines.h" -#include "proximity_info.h" -#include "words_priority_queue.h" -#include "words_priority_queue_pool.h" - -namespace latinime { - -class TerminalAttributes; -class UnigramDictionary { - typedef struct { int first; int second; int replacement; } digraph_t; - - public: - // Mask and flags for children address type selection. - static const int MASK_GROUP_ADDRESS_TYPE = 0xC0; - static const int FLAG_GROUP_ADDRESS_TYPE_NOADDRESS = 0x00; - static const int FLAG_GROUP_ADDRESS_TYPE_ONEBYTE = 0x40; - static const int FLAG_GROUP_ADDRESS_TYPE_TWOBYTES = 0x80; - static const int FLAG_GROUP_ADDRESS_TYPE_THREEBYTES = 0xC0; - - // Flag for single/multiple char group - static const int FLAG_HAS_MULTIPLE_CHARS = 0x20; - - // Flag for terminal groups - static const int FLAG_IS_TERMINAL = 0x10; - - // Flag for shortcut targets presence - static const int FLAG_HAS_SHORTCUT_TARGETS = 0x08; - // Flag for bigram presence - static const int FLAG_HAS_BIGRAMS = 0x04; - // Flag for shortcut-only words. Some words are shortcut-only, which means they match when - // the user types them but they don't pop in the suggestion strip, only the words they are - // shortcuts for do. - static const int FLAG_IS_SHORTCUT_ONLY = 0x02; - - // Attribute (bigram/shortcut) related flags: - // Flag for presence of more attributes - static const int FLAG_ATTRIBUTE_HAS_NEXT = 0x80; - // Flag for sign of offset. If this flag is set, the offset value must be negated. - static const int FLAG_ATTRIBUTE_OFFSET_NEGATIVE = 0x40; - - // Mask for attribute frequency, stored on 4 bits inside the flags byte. - static const int MASK_ATTRIBUTE_FREQUENCY = 0x0F; - - // Mask and flags for attribute address type selection. - static const int MASK_ATTRIBUTE_ADDRESS_TYPE = 0x30; - static const int FLAG_ATTRIBUTE_ADDRESS_TYPE_ONEBYTE = 0x10; - static const int FLAG_ATTRIBUTE_ADDRESS_TYPE_TWOBYTES = 0x20; - static const int FLAG_ATTRIBUTE_ADDRESS_TYPE_THREEBYTES = 0x30; - - // Error tolerances - static const int DEFAULT_MAX_ERRORS = 2; - static const int MAX_ERRORS_FOR_TWO_WORDS = 1; - - UnigramDictionary(const uint8_t* const streamStart, int typedLetterMultipler, - int fullWordMultiplier, int maxWordLength, int maxWords, - const bool isLatestDictVersion); - bool isValidWord(const uint16_t* const inWord, const int length) const; - int getBigramPosition(int pos, unsigned short *word, int offset, int length) const; - int getSuggestions(ProximityInfo *proximityInfo, WordsPriorityQueuePool *queuePool, - Correction *correction, const int *xcoordinates, - const int *ycoordinates, const int *codes, const int codesSize, const int flags, - unsigned short *outWords, int *frequencies); - virtual ~UnigramDictionary(); - - private: - void getWordSuggestions(ProximityInfo *proximityInfo, const int *xcoordinates, - const int *ycoordinates, const int *codes, const int inputLength, - const int flags, Correction *correction, WordsPriorityQueuePool *queuePool); - int getDigraphReplacement(const int *codes, const int i, const int codesSize, - const digraph_t* const digraphs, const unsigned int digraphsSize) const; - void getWordWithDigraphSuggestionsRec(ProximityInfo *proximityInfo, - const int *xcoordinates, const int* ycoordinates, const int *codesBuffer, - int *xCoordinatesBuffer, int *yCoordinatesBuffer, - const int codesBufferSize, const int flags, const int* codesSrc, - const int codesRemain, const int currentDepth, int* codesDest, Correction *correction, - WordsPriorityQueuePool* queuePool, const digraph_t* const digraphs, - const unsigned int digraphsSize); - void initSuggestions(ProximityInfo *proximityInfo, const int *xcoordinates, - const int *ycoordinates, const int *codes, const int codesSize, Correction *correction); - void getOneWordSuggestions(ProximityInfo *proximityInfo, const int *xcoordinates, - const int *ycoordinates, const int *codes, const bool useFullEditDistance, - const int inputLength, Correction *correction, WordsPriorityQueuePool* queuePool); - void getSuggestionCandidates( - const bool useFullEditDistance, const int inputLength, Correction *correction, - WordsPriorityQueuePool* queuePool, const bool doAutoCompletion, const int maxErrors, - const int currentWordIndex); - void getSplitMultipleWordsSuggestions(ProximityInfo *proximityInfo, - const int *xcoordinates, const int *ycoordinates, const int *codes, - const bool useFullEditDistance, const int inputLength, - Correction *correction, WordsPriorityQueuePool* queuePool, - const bool hasAutoCorrectionCandidate); - void onTerminal(const int freq, const TerminalAttributes& terminalAttributes, - Correction *correction, WordsPriorityQueuePool *queuePool, const bool addToMasterQueue, - const int currentWordIndex); - bool needsToSkipCurrentNode(const unsigned short c, - const int inputIndex, const int skipPos, const int depth); - // Process a node by considering proximity, missing and excessive character - bool processCurrentNode(const int initialPos, Correction *correction, int *newCount, - int *newChildPosition, int *nextSiblingPosition, WordsPriorityQueuePool *queuePool, - const int currentWordIndex); - int getMostFrequentWordLike(const int startInputIndex, const int inputLength, - ProximityInfo *proximityInfo, unsigned short *word); - int getMostFrequentWordLikeInner(const uint16_t* const inWord, const int length, - short unsigned int *outWord); - bool getSubStringSuggestion( - ProximityInfo *proximityInfo, const int *xcoordinates, const int *ycoordinates, - const int *codes, const bool useFullEditDistance, Correction *correction, - WordsPriorityQueuePool* queuePool, const int inputLength, - const bool hasAutoCorrectionCandidate, const int currentWordIndex, - const int inputWordStartPos, const int inputWordLength, - const int outputWordStartPos, const bool isSpaceProximity, int *freqArray, - int *wordLengthArray, unsigned short* outputWord, int *outputWordLength); - void getMultiWordsSuggestionRec(ProximityInfo *proximityInfo, - const int *xcoordinates, const int *ycoordinates, const int *codes, - const bool useFullEditDistance, const int inputLength, - Correction *correction, WordsPriorityQueuePool* queuePool, - const bool hasAutoCorrectionCandidate, const int startPos, const int startWordIndex, - const int outputWordLength, int *freqArray, int* wordLengthArray, - unsigned short* outputWord); - - const uint8_t* const DICT_ROOT; - const int MAX_WORD_LENGTH; - const int MAX_WORDS; - const bool IS_LATEST_DICT_VERSION; - const int TYPED_LETTER_MULTIPLIER; - const int FULL_WORD_MULTIPLIER; - const int ROOT_POS; - const unsigned int BYTES_IN_ONE_CHAR; - const int MAX_DIGRAPH_SEARCH_DEPTH; - - // Flags for special processing - // Those *must* match the flags in BinaryDictionary.Flags.ALL_FLAGS in BinaryDictionary.java - // or something very bad (like, the apocalypse) will happen. - // Please update both at the same time. - enum { - REQUIRES_GERMAN_UMLAUT_PROCESSING = 0x1, - USE_FULL_EDIT_DISTANCE = 0x2, - REQUIRES_FRENCH_LIGATURES_PROCESSING = 0x4 - }; - static const digraph_t GERMAN_UMLAUT_DIGRAPHS[]; - static const digraph_t FRENCH_LIGATURES_DIGRAPHS[]; - - // Still bundled members - unsigned short mWord[MAX_WORD_LENGTH_INTERNAL];// TODO: remove - int mStackChildCount[MAX_WORD_LENGTH_INTERNAL];// TODO: remove - int mStackInputIndex[MAX_WORD_LENGTH_INTERNAL];// TODO: remove - int mStackSiblingPos[MAX_WORD_LENGTH_INTERNAL];// TODO: remove -}; -} // namespace latinime - -#endif // LATINIME_UNIGRAM_DICTIONARY_H diff --git a/native/src/words_priority_queue.h b/native/src/words_priority_queue.h deleted file mode 100644 index 249962eec..000000000 --- a/native/src/words_priority_queue.h +++ /dev/null @@ -1,195 +0,0 @@ -/* - * Copyright (C) 2011 The Android Open Source Project - * - * Licensed under the Apache License, Version 2.0 (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.apache.org/licenses/LICENSE-2.0 - * - * Unless required by applicable law or agreed to in writing, software - * distributed under the License is distributed on an "AS IS" BASIS, - * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. - * See the License for the specific language governing permissions and - * limitations under the License. - */ - -#ifndef LATINIME_WORDS_PRIORITY_QUEUE_H -#define LATINIME_WORDS_PRIORITY_QUEUE_H - -#include <cstring> // for memcpy() -#include <iostream> -#include <queue> -#include "defines.h" - -namespace latinime { - -class WordsPriorityQueue { - public: - class SuggestedWord { - public: - int mScore; - unsigned short mWord[MAX_WORD_LENGTH_INTERNAL]; - int mWordLength; - bool mUsed; - - void setParams(int score, unsigned short* word, int wordLength) { - mScore = score; - mWordLength = wordLength; - memcpy(mWord, word, sizeof(unsigned short) * wordLength); - mUsed = true; - } - }; - - WordsPriorityQueue(int maxWords, int maxWordLength) : - MAX_WORDS((unsigned int) maxWords), MAX_WORD_LENGTH( - (unsigned int) maxWordLength) { - mSuggestedWords = new SuggestedWord[maxWordLength]; - for (int i = 0; i < maxWordLength; ++i) { - mSuggestedWords[i].mUsed = false; - } - mHighestSuggestedWord = 0; - } - - ~WordsPriorityQueue() { - delete[] mSuggestedWords; - } - - void push(int score, unsigned short* word, int wordLength) { - SuggestedWord* sw = 0; - if (mSuggestions.size() >= MAX_WORDS) { - sw = mSuggestions.top(); - const int minScore = sw->mScore; - if (minScore >= score) { - return; - } else { - sw->mUsed = false; - mSuggestions.pop(); - } - } - if (sw == 0) { - sw = getFreeSuggestedWord(score, word, wordLength); - } else { - sw->setParams(score, word, wordLength); - } - if (sw == 0) { - AKLOGE("SuggestedWord is accidentally null."); - return; - } - if (DEBUG_WORDS_PRIORITY_QUEUE) { - AKLOGI("Push word. %d, %d", score, wordLength); - DUMP_WORD(word, wordLength); - } - mSuggestions.push(sw); - if (!mHighestSuggestedWord || mHighestSuggestedWord->mScore < sw->mScore) { - mHighestSuggestedWord = sw; - } - } - - SuggestedWord* top() { - if (mSuggestions.empty()) return 0; - SuggestedWord* sw = mSuggestions.top(); - return sw; - } - - int outputSuggestions(int *frequencies, unsigned short *outputChars) { - mHighestSuggestedWord = 0; - const unsigned int size = min( - MAX_WORDS, static_cast<unsigned int>(mSuggestions.size())); - int index = size - 1; - while (!mSuggestions.empty() && index >= 0) { - SuggestedWord* sw = mSuggestions.top(); - if (DEBUG_WORDS_PRIORITY_QUEUE) { - AKLOGI("dump word. %d", sw->mScore); - DUMP_WORD(sw->mWord, sw->mWordLength); - } - const unsigned int wordLength = sw->mWordLength; - char* targetAdr = (char*) outputChars - + (index) * MAX_WORD_LENGTH * sizeof(short); - frequencies[index] = sw->mScore; - memcpy(targetAdr, sw->mWord, (wordLength) * sizeof(short)); - if (wordLength < MAX_WORD_LENGTH) { - ((unsigned short*) targetAdr)[wordLength] = 0; - } - sw->mUsed = false; - mSuggestions.pop(); - --index; - } - return size; - } - - int size() const { - return mSuggestions.size(); - } - - void clear() { - mHighestSuggestedWord = 0; - while (!mSuggestions.empty()) { - SuggestedWord* sw = mSuggestions.top(); - if (DEBUG_WORDS_PRIORITY_QUEUE) { - AKLOGI("Clear word. %d", sw->mScore); - DUMP_WORD(sw->mWord, sw->mWordLength); - } - sw->mUsed = false; - mSuggestions.pop(); - } - } - - void dumpTopWord() { - if (size() <= 0) { - return; - } - DUMP_WORD(mHighestSuggestedWord->mWord, mHighestSuggestedWord->mWordLength); - } - - double getHighestNormalizedScore(const unsigned short* before, const int beforeLength, - unsigned short** outWord, int *outScore, int *outLength) { - if (!mHighestSuggestedWord) { - return 0.0; - } - SuggestedWord* sw = mHighestSuggestedWord; - const int score = sw->mScore; - unsigned short* word = sw->mWord; - const int wordLength = sw->mWordLength; - if (outScore) { - *outScore = score; - } - if (outWord) { - *outWord = word; - } - if (outLength) { - *outLength = wordLength; - } - return Correction::RankingAlgorithm::calcNormalizedScore( - before, beforeLength, word, wordLength, score); - } - - private: - struct wordComparator { - bool operator ()(SuggestedWord * left, SuggestedWord * right) { - return left->mScore > right->mScore; - } - }; - - SuggestedWord* getFreeSuggestedWord(int score, unsigned short* word, - int wordLength) { - for (unsigned int i = 0; i < MAX_WORD_LENGTH; ++i) { - if (!mSuggestedWords[i].mUsed) { - mSuggestedWords[i].setParams(score, word, wordLength); - return &mSuggestedWords[i]; - } - } - return 0; - } - - typedef std::priority_queue<SuggestedWord*, std::vector<SuggestedWord*>, - wordComparator> Suggestions; - Suggestions mSuggestions; - const unsigned int MAX_WORDS; - const unsigned int MAX_WORD_LENGTH; - SuggestedWord* mSuggestedWords; - SuggestedWord* mHighestSuggestedWord; -}; -} - -#endif // LATINIME_WORDS_PRIORITY_QUEUE_H diff --git a/native/src/words_priority_queue_pool.h b/native/src/words_priority_queue_pool.h deleted file mode 100644 index 5b50e8f4f..000000000 --- a/native/src/words_priority_queue_pool.h +++ /dev/null @@ -1,90 +0,0 @@ -/* - * Copyright (C) 2011 The Android Open Source Project - * - * Licensed under the Apache License, Version 2.0 (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.apache.org/licenses/LICENSE-2.0 - * - * Unless required by applicable law or agreed to in writing, software - * distributed under the License is distributed on an "AS IS" BASIS, - * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. - * See the License for the specific language governing permissions and - * limitations under the License. - */ - -#ifndef LATINIME_WORDS_PRIORITY_QUEUE_POOL_H -#define LATINIME_WORDS_PRIORITY_QUEUE_POOL_H - -#include <assert.h> -#include <new> -#include "words_priority_queue.h" - -namespace latinime { - -class WordsPriorityQueuePool { - public: - WordsPriorityQueuePool(int mainQueueMaxWords, int subQueueMaxWords, int maxWordLength) { - mMasterQueue = new(mMasterQueueBuf) WordsPriorityQueue(mainQueueMaxWords, maxWordLength); - for (int i = 0, subQueueBufOffset = 0; - i < MULTIPLE_WORDS_SUGGESTION_MAX_WORDS * SUB_QUEUE_MAX_COUNT; - ++i, subQueueBufOffset += sizeof(WordsPriorityQueue)) { - mSubQueues[i] = new(mSubQueueBuf + subQueueBufOffset) - WordsPriorityQueue(subQueueMaxWords, maxWordLength); - } - } - - virtual ~WordsPriorityQueuePool() { - } - - WordsPriorityQueue* getMasterQueue() { - return mMasterQueue; - } - - WordsPriorityQueue* getSubQueue(const int wordIndex, const int inputWordLength) { - if (wordIndex >= MULTIPLE_WORDS_SUGGESTION_MAX_WORDS) { - return 0; - } - if (inputWordLength < 0 || inputWordLength >= SUB_QUEUE_MAX_COUNT) { - if (DEBUG_WORDS_PRIORITY_QUEUE) { - assert(false); - } - return 0; - } - return mSubQueues[wordIndex * SUB_QUEUE_MAX_COUNT + inputWordLength]; - } - - inline void clearAll() { - mMasterQueue->clear(); - for (int i = 0; i < MULTIPLE_WORDS_SUGGESTION_MAX_WORDS; ++i) { - clearSubQueue(i); - } - } - - inline void clearSubQueue(const int wordIndex) { - for (int i = 0; i < SUB_QUEUE_MAX_COUNT; ++i) { - WordsPriorityQueue* queue = getSubQueue(wordIndex, i); - if (queue) { - queue->clear(); - } - } - } - - void dumpSubQueue1TopSuggestions() { - AKLOGI("DUMP SUBQUEUE1 TOP SUGGESTIONS"); - for (int i = 0; i < SUB_QUEUE_MAX_COUNT; ++i) { - getSubQueue(0, i)->dumpTopWord(); - } - } - - private: - WordsPriorityQueue* mMasterQueue; - WordsPriorityQueue* mSubQueues[SUB_QUEUE_MAX_COUNT * MULTIPLE_WORDS_SUGGESTION_MAX_WORDS]; - char mMasterQueueBuf[sizeof(WordsPriorityQueue)]; - char mSubQueueBuf[MULTIPLE_WORDS_SUGGESTION_MAX_WORDS - * SUB_QUEUE_MAX_COUNT * sizeof(WordsPriorityQueue)]; -}; -} - -#endif // LATINIME_WORDS_PRIORITY_QUEUE_POOL_H |