Home | History | Annotate | Download | only in src 
      1 /*
      2 **
      3 ** Copyright 2010, The Android Open Source Project
      4 **
      5 ** Licensed under the Apache License, Version 2.0 (the "License");
      6 ** you may not use this file except in compliance with the License.
      7 ** You may obtain a copy of the License at
      8 **
      9 **     http://www.apache.org/licenses/LICENSE-2.0
     10 **
     11 ** Unless required by applicable law or agreed to in writing, software
     12 ** distributed under the License is distributed on an "AS IS" BASIS,
     13 ** WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
     14 ** See the License for the specific language governing permissions and
     15 ** limitations under the License.
     16 */
     17 
     18 #include <string.h>
     19 
     20 #define LOG_TAG "LatinIME: bigram_dictionary.cpp"
     21 
     22 #include "bigram_dictionary.h"
     23 #include "binary_format.h"
     24 #include "bloom_filter.h"
     25 #include "defines.h"
     26 #include "dictionary.h"
     27 
     28 namespace latinime {
     29 
     30 BigramDictionary::BigramDictionary(const unsigned char *dict, int maxWordLength,
     31         Dictionary *parentDictionary)
     32     : DICT(dict), MAX_WORD_LENGTH(maxWordLength), mParentDictionary(parentDictionary) {
     33     if (DEBUG_DICT) {
     34         AKLOGI("BigramDictionary - constructor");
     35     }
     36 }
     37 
     38 BigramDictionary::~BigramDictionary() {
     39 }
     40 
     41 bool BigramDictionary::addWordBigram(unsigned short *word, int length, int frequency) {
     42     word[length] = 0;
     43     if (DEBUG_DICT) {
     44 #ifdef FLAG_DBG
     45         char s[length + 1];
     46         for (int i = 0; i <= length; i++) s[i] = word[i];
     47         AKLOGI("Bigram: Found word = %s, freq = %d :", s, frequency);
     48 #endif
     49     }
     50 
     51     // Find the right insertion point
     52     int insertAt = 0;
     53     while (insertAt < mMaxBigrams) {
     54         if (frequency > mBigramFreq[insertAt] || (mBigramFreq[insertAt] == frequency
     55                 && length < Dictionary::wideStrLen(mBigramChars + insertAt * MAX_WORD_LENGTH))) {
     56             break;
     57         }
     58         insertAt++;
     59     }
     60     if (DEBUG_DICT) {
     61         AKLOGI("Bigram: InsertAt -> %d maxBigrams: %d", insertAt, mMaxBigrams);
     62     }
     63     if (insertAt < mMaxBigrams) {
     64         memmove((char*) mBigramFreq + (insertAt + 1) * sizeof(mBigramFreq[0]),
     65                (char*) mBigramFreq + insertAt * sizeof(mBigramFreq[0]),
     66                (mMaxBigrams - insertAt - 1) * sizeof(mBigramFreq[0]));
     67         mBigramFreq[insertAt] = frequency;
     68         memmove((char*) mBigramChars + (insertAt + 1) * MAX_WORD_LENGTH * sizeof(short),
     69                (char*) mBigramChars + (insertAt    ) * MAX_WORD_LENGTH * sizeof(short),
     70                (mMaxBigrams - insertAt - 1) * sizeof(short) * MAX_WORD_LENGTH);
     71         unsigned short *dest = mBigramChars + (insertAt    ) * MAX_WORD_LENGTH;
     72         while (length--) {
     73             *dest++ = *word++;
     74         }
     75         *dest = 0; // NULL terminate
     76         if (DEBUG_DICT) {
     77             AKLOGI("Bigram: Added word at %d", insertAt);
     78         }
     79         return true;
     80     }
     81     return false;
     82 }
     83 
     84 /* Parameters :
     85  * prevWord: the word before, the one for which we need to look up bigrams.
     86  * prevWordLength: its length.
     87  * codes: what user typed, in the same format as for UnigramDictionary::getSuggestions.
     88  * codesSize: the size of the codes array.
     89  * bigramChars: an array for output, at the same format as outwords for getSuggestions.
     90  * bigramFreq: an array to output frequencies.
     91  * maxWordLength: the maximum size of a word.
     92  * maxBigrams: the maximum number of bigrams fitting in the bigramChars array.
     93  * This method returns the number of bigrams this word has, for backward compatibility.
     94  * Note: this is not the number of bigrams output in the array, which is the number of
     95  * bigrams this word has WHOSE first letter also matches the letter the user typed.
     96  * TODO: this may not be a sensible thing to do. It makes sense when the bigrams are
     97  * used to match the first letter of the second word, but once the user has typed more
     98  * and the bigrams are used to boost unigram result scores, it makes little sense to
     99  * reduce their scope to the ones that match the first letter.
    100  */
    101 int BigramDictionary::getBigrams(const int32_t *prevWord, int prevWordLength, int *codes,
    102         int codesSize, unsigned short *bigramChars, int *bigramFreq, int maxWordLength,
    103         int maxBigrams) {
    104     // TODO: remove unused arguments, and refrain from storing stuff in members of this class
    105     // TODO: have "in" arguments before "out" ones, and make out args explicit in the name
    106     mBigramFreq = bigramFreq;
    107     mBigramChars = bigramChars;
    108     mInputCodes = codes;
    109     mMaxBigrams = maxBigrams;
    110 
    111     const uint8_t* const root = DICT;
    112     int pos = getBigramListPositionForWord(prevWord, prevWordLength);
    113     // getBigramListPositionForWord returns 0 if this word isn't in the dictionary or has no bigrams
    114     if (0 == pos) return 0;
    115     int bigramFlags;
    116     int bigramCount = 0;
    117     do {
    118         bigramFlags = BinaryFormat::getFlagsAndForwardPointer(root, &pos);
    119         uint16_t bigramBuffer[MAX_WORD_LENGTH];
    120         int unigramFreq = 0;
    121         const int bigramPos = BinaryFormat::getAttributeAddressAndForwardPointer(root, bigramFlags,
    122                 &pos);
    123         const int length = BinaryFormat::getWordAtAddress(root, bigramPos, MAX_WORD_LENGTH,
    124                 bigramBuffer, &unigramFreq);
    125 
    126         // codesSize == 0 means we are trying to find bigram predictions.
    127         if (codesSize < 1 || checkFirstCharacter(bigramBuffer)) {
    128             const int bigramFreq = UnigramDictionary::MASK_ATTRIBUTE_FREQUENCY & bigramFlags;
    129             // Due to space constraints, the frequency for bigrams is approximate - the lower the
    130             // unigram frequency, the worse the precision. The theoritical maximum error in
    131             // resulting frequency is 8 - although in the practice it's never bigger than 3 or 4
    132             // in very bad cases. This means that sometimes, we'll see some bigrams interverted
    133             // here, but it can't get too bad.
    134             const int frequency =
    135                     BinaryFormat::computeFrequencyForBigram(unigramFreq, bigramFreq);
    136             if (addWordBigram(bigramBuffer, length, frequency)) {
    137                 ++bigramCount;
    138             }
    139         }
    140     } while (UnigramDictionary::FLAG_ATTRIBUTE_HAS_NEXT & bigramFlags);
    141     return bigramCount;
    142 }
    143 
    144 // Returns a pointer to the start of the bigram list.
    145 // If the word is not found or has no bigrams, this function returns 0.
    146 int BigramDictionary::getBigramListPositionForWord(const int32_t *prevWord,
    147         const int prevWordLength) {
    148     if (0 >= prevWordLength) return 0;
    149     const uint8_t* const root = DICT;
    150     int pos = BinaryFormat::getTerminalPosition(root, prevWord, prevWordLength);
    151 
    152     if (NOT_VALID_WORD == pos) return 0;
    153     const int flags = BinaryFormat::getFlagsAndForwardPointer(root, &pos);
    154     if (0 == (flags & UnigramDictionary::FLAG_HAS_BIGRAMS)) return 0;
    155     if (0 == (flags & UnigramDictionary::FLAG_HAS_MULTIPLE_CHARS)) {
    156         BinaryFormat::getCharCodeAndForwardPointer(root, &pos);
    157     } else {
    158         pos = BinaryFormat::skipOtherCharacters(root, pos);
    159     }
    160     pos = BinaryFormat::skipFrequency(flags, pos);
    161     pos = BinaryFormat::skipChildrenPosition(flags, pos);
    162     pos = BinaryFormat::skipShortcuts(root, flags, pos);
    163     return pos;
    164 }
    165 
    166 void BigramDictionary::fillBigramAddressToFrequencyMapAndFilter(const int32_t *prevWord,
    167         const int prevWordLength, std::map<int, int> *map, uint8_t *filter) {
    168     memset(filter, 0, BIGRAM_FILTER_BYTE_SIZE);
    169     const uint8_t* const root = DICT;
    170     int pos = getBigramListPositionForWord(prevWord, prevWordLength);
    171     if (0 == pos) return;
    172 
    173     int bigramFlags;
    174     do {
    175         bigramFlags = BinaryFormat::getFlagsAndForwardPointer(root, &pos);
    176         const int frequency = UnigramDictionary::MASK_ATTRIBUTE_FREQUENCY & bigramFlags;
    177         const int bigramPos = BinaryFormat::getAttributeAddressAndForwardPointer(root, bigramFlags,
    178                 &pos);
    179         (*map)[bigramPos] = frequency;
    180         setInFilter(filter, bigramPos);
    181     } while (0 != (UnigramDictionary::FLAG_ATTRIBUTE_HAS_NEXT & bigramFlags));
    182 }
    183 
    184 bool BigramDictionary::checkFirstCharacter(unsigned short *word) {
    185     // Checks whether this word starts with same character or neighboring characters of
    186     // what user typed.
    187 
    188     int *inputCodes = mInputCodes;
    189     int maxAlt = MAX_ALTERNATIVES;
    190     const unsigned short firstBaseChar = toBaseLowerCase(*word);
    191     while (maxAlt > 0) {
    192         if (toBaseLowerCase(*inputCodes) == firstBaseChar) {
    193             return true;
    194         }
    195         inputCodes++;
    196         maxAlt--;
    197     }
    198     return false;
    199 }
    200 
    201 bool BigramDictionary::isValidBigram(const int32_t *word1, int length1, const int32_t *word2,
    202         int length2) {
    203     const uint8_t* const root = DICT;
    204     int pos = getBigramListPositionForWord(word1, length1);
    205     // getBigramListPositionForWord returns 0 if this word isn't in the dictionary or has no bigrams
    206     if (0 == pos) return false;
    207     int nextWordPos = BinaryFormat::getTerminalPosition(root, word2, length2);
    208     if (NOT_VALID_WORD == nextWordPos) return false;
    209     int bigramFlags;
    210     do {
    211         bigramFlags = BinaryFormat::getFlagsAndForwardPointer(root, &pos);
    212         const int bigramPos = BinaryFormat::getAttributeAddressAndForwardPointer(root, bigramFlags,
    213                 &pos);
    214         if (bigramPos == nextWordPos) {
    215             return true;
    216         }
    217     } while (UnigramDictionary::FLAG_ATTRIBUTE_HAS_NEXT & bigramFlags);
    218     return false;
    219 }
    220 
    221 // TODO: Move functions related to bigram to here
    222 } // namespace latinime
    223