diff options
Diffstat (limited to 'native/jni/src/binary_format.h')
| -rw-r--r-- | native/jni/src/binary_format.h | 778 |
1 files changed, 0 insertions, 778 deletions
diff --git a/native/jni/src/binary_format.h b/native/jni/src/binary_format.h deleted file mode 100644 index 98241532f..000000000 --- a/native/jni/src/binary_format.h +++ /dev/null @@ -1,778 +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 <cstdlib> -#include <map> -#include <stdint.h> - -#include "bloom_filter.h" -#include "char_utils.h" -#include "hash_map_compat.h" - -namespace latinime { - -class BinaryFormat { - public: - // Mask and flags for children address type selection. - static const int MASK_GROUP_ADDRESS_TYPE = 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 non-words (typically, shortcut only entries) - static const int FLAG_IS_NOT_A_WORD = 0x02; - // Flag for blacklist - static const int FLAG_IS_BLACKLISTED = 0x01; - - // 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 probability, stored on 4 bits inside the flags byte. - static const int MASK_ATTRIBUTE_PROBABILITY = 0x0F; - // The numeric value of the shortcut probability that means 'whitelist'. - static const int WHITELIST_SHORTCUT_PROBABILITY = 15; - - // Mask and flags for attribute address type selection. - static const int MASK_ATTRIBUTE_ADDRESS_TYPE = 0x30; - - static const int UNKNOWN_FORMAT = -1; - static const int SHORTCUT_LIST_SIZE_SIZE = 2; - - static int detectFormat(const uint8_t *const dict, const int dictSize); - static int getHeaderSize(const uint8_t *const dict, const int dictSize); - static int getFlags(const uint8_t *const dict, const int dictSize); - static bool hasBlacklistedOrNotAWordFlag(const int flags); - static void readHeaderValue(const uint8_t *const dict, const int dictSize, - const char *const key, int *outValue, const int outValueSize); - static int readHeaderValueInt(const uint8_t *const dict, const int dictSize, - const char *const key); - static int getGroupCountAndForwardPointer(const uint8_t *const dict, int *pos); - static uint8_t getFlagsAndForwardPointer(const uint8_t *const dict, int *pos); - static int getCodePointAndForwardPointer(const uint8_t *const dict, int *pos); - static int readProbabilityWithoutMovingPointer(const uint8_t *const dict, const int pos); - static int skipOtherCharacters(const uint8_t *const dict, const int pos); - static int skipChildrenPosition(const uint8_t flags, const int pos); - static int skipProbability(const uint8_t flags, const int pos); - static int skipShortcuts(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 getAttributeProbabilityFromFlags(const int flags); - static int getTerminalPosition(const uint8_t *const root, const int *const inWord, - const int length, const bool forceLowerCaseSearch); - static int getWordAtAddress(const uint8_t *const root, const int address, const int maxDepth, - int *outWord, int *outUnigramProbability); - static int computeProbabilityForBigram( - const int unigramProbability, const int bigramProbability); - static int getProbability(const int position, const std::map<int, int> *bigramMap, - const uint8_t *bigramFilter, const int unigramProbability); - static int getBigramProbabilityFromHashMap(const int position, - const hash_map_compat<int, int> *bigramMap, const int unigramProbability); - static float getMultiWordCostMultiplier(const uint8_t *const dict, const int dictSize); - static void fillBigramProbabilityToHashMap(const uint8_t *const root, int position, - hash_map_compat<int, int> *bigramMap); - static int getBigramProbability(const uint8_t *const root, int position, - const int nextPosition, const int unigramProbability); - - // Flags for special processing - // Those *must* match the flags in makedict (BinaryDictInputOutput#*_PROCESSING_FLAG) or - // something very bad (like, the apocalypse) will happen. Please update both at the same time. - enum { - REQUIRES_GERMAN_UMLAUT_PROCESSING = 0x1, - REQUIRES_FRENCH_LIGATURES_PROCESSING = 0x4 - }; - - private: - DISALLOW_IMPLICIT_CONSTRUCTORS(BinaryFormat); - static int getBigramListPositionForWordPosition(const uint8_t *const root, int position); - - 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; - 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; - - // Any file smaller than this is not a dictionary. - static const int DICTIONARY_MINIMUM_SIZE = 4; - // 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. - static const int FORMAT_VERSION_1_MAGIC_NUMBER = 0x78B10100; - static const 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. - static const int FORMAT_VERSION_2_MAGIC_NUMBER = -1681835266; // 0x9BC13AFE - // Magic number (4 bytes), version (2 bytes), options (2 bytes), header size (4 bytes) = 12 - static const int FORMAT_VERSION_2_MINIMUM_SIZE = 12; - - static const int CHARACTER_ARRAY_TERMINATOR_SIZE = 1; - static const int MINIMAL_ONE_BYTE_CHARACTER_VALUE = 0x20; - static const int CHARACTER_ARRAY_TERMINATOR = 0x1F; - static const int MULTIPLE_BYTE_CHARACTER_ADDITIONAL_SIZE = 2; - static const int NO_FLAGS = 0; - static int skipAllAttributes(const uint8_t *const dict, const uint8_t flags, const int pos); - static int skipBigrams(const uint8_t *const dict, const uint8_t flags, const int pos); -}; - -AK_FORCE_INLINE int BinaryFormat::detectFormat(const uint8_t *const dict, const int dictSize) { - // The magic number is stored big-endian. - // If the dictionary is less than 4 bytes, we can't even read the magic number, so we don't - // understand this format. - if (dictSize < DICTIONARY_MINIMUM_SIZE) return UNKNOWN_FORMAT; - const int 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: - // Version 2 dictionaries are at least 12 bytes long (see below details for the header). - // If this dictionary has the version 2 magic number but is less than 12 bytes long, then - // it's an unknown format and we need to avoid confidently reading the next bytes. - if (dictSize < FORMAT_VERSION_2_MINIMUM_SIZE) return UNKNOWN_FORMAT; - // Format 2 header is as follows: - // Magic number (4 bytes) 0x9B 0xC1 0x3A 0xFE - // Version number (2 bytes) 0x00 0x02 - // Options (2 bytes) - // Header size (4 bytes) : integer, big endian - return (dict[4] << 8) + dict[5]; - default: - return UNKNOWN_FORMAT; - } -} - -inline int BinaryFormat::getFlags(const uint8_t *const dict, const int dictSize) { - switch (detectFormat(dict, dictSize)) { - case 1: - return NO_FLAGS; // TODO: NO_FLAGS is unused anywhere else? - default: - return (dict[6] << 8) + dict[7]; - } -} - -inline bool BinaryFormat::hasBlacklistedOrNotAWordFlag(const int flags) { - return (flags & (FLAG_IS_BLACKLISTED | FLAG_IS_NOT_A_WORD)) != 0; -} - -inline int BinaryFormat::getHeaderSize(const uint8_t *const dict, const int dictSize) { - switch (detectFormat(dict, dictSize)) { - 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 S_INT_MAX; - } -} - -inline void BinaryFormat::readHeaderValue(const uint8_t *const dict, const int dictSize, - const char *const key, int *outValue, const int outValueSize) { - int outValueIndex = 0; - // Only format 2 and above have header attributes as {key,value} string pairs. For prior - // formats, we just return an empty string, as if the key wasn't found. - if (2 <= detectFormat(dict, dictSize)) { - const int headerOptionsOffset = 4 /* magic number */ - + 2 /* dictionary version */ + 2 /* flags */; - const int headerSize = - (dict[headerOptionsOffset] << 24) + (dict[headerOptionsOffset + 1] << 16) - + (dict[headerOptionsOffset + 2] << 8) + dict[headerOptionsOffset + 3]; - const int headerEnd = headerOptionsOffset + 4 + headerSize; - int index = headerOptionsOffset + 4; - while (index < headerEnd) { - int keyIndex = 0; - int codePoint = getCodePointAndForwardPointer(dict, &index); - while (codePoint != NOT_A_CODE_POINT) { - if (codePoint != key[keyIndex++]) { - break; - } - codePoint = getCodePointAndForwardPointer(dict, &index); - } - if (codePoint == NOT_A_CODE_POINT && key[keyIndex] == 0) { - // We found the key! Copy and return the value. - codePoint = getCodePointAndForwardPointer(dict, &index); - while (codePoint != NOT_A_CODE_POINT && outValueIndex < outValueSize) { - outValue[outValueIndex++] = codePoint; - codePoint = getCodePointAndForwardPointer(dict, &index); - } - // Finished copying. Break to go to the termination code. - break; - } - // We didn't find the key, skip the remainder of it and its value - while (codePoint != NOT_A_CODE_POINT) { - codePoint = getCodePointAndForwardPointer(dict, &index); - } - codePoint = getCodePointAndForwardPointer(dict, &index); - while (codePoint != NOT_A_CODE_POINT) { - codePoint = getCodePointAndForwardPointer(dict, &index); - } - } - // We couldn't find it - fall through and return an empty value. - } - // Put a terminator 0 if possible at all (always unless outValueSize is <= 0) - if (outValueIndex >= outValueSize) outValueIndex = outValueSize - 1; - if (outValueIndex >= 0) outValue[outValueIndex] = 0; -} - -inline int BinaryFormat::readHeaderValueInt(const uint8_t *const dict, const int dictSize, - const char *const key) { - const int bufferSize = LARGEST_INT_DIGIT_COUNT; - int intBuffer[bufferSize]; - char charBuffer[bufferSize]; - BinaryFormat::readHeaderValue(dict, dictSize, key, intBuffer, bufferSize); - for (int i = 0; i < bufferSize; ++i) { - charBuffer[i] = intBuffer[i]; - } - // If not a number, return S_INT_MIN - if (!isdigit(charBuffer[0])) return S_INT_MIN; - return atoi(charBuffer); -} - -AK_FORCE_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 float BinaryFormat::getMultiWordCostMultiplier(const uint8_t *const dict, - const int dictSize) { - const int headerValue = readHeaderValueInt(dict, dictSize, - "MULTIPLE_WORDS_DEMOTION_RATE"); - if (headerValue == S_INT_MIN) { - return 1.0f; - } - if (headerValue <= 0) { - return static_cast<float>(MAX_VALUE_FOR_WEIGHTING); - } - return 100.0f / static_cast<float>(headerValue); -} - -inline uint8_t BinaryFormat::getFlagsAndForwardPointer(const uint8_t *const dict, int *pos) { - return dict[(*pos)++]; -} - -AK_FORCE_INLINE int BinaryFormat::getCodePointAndForwardPointer(const uint8_t *const dict, - int *pos) { - const int origin = *pos; - const int codePoint = dict[origin]; - if (codePoint < MINIMAL_ONE_BYTE_CHARACTER_VALUE) { - if (codePoint == CHARACTER_ARRAY_TERMINATOR) { - *pos = origin + 1; - return NOT_A_CODE_POINT; - } else { - *pos = origin + 3; - const int char_1 = codePoint << 16; - const int char_2 = char_1 + (dict[origin + 1] << 8); - return char_2 + dict[origin + 2]; - } - } else { - *pos = origin + 1; - return codePoint; - } -} - -inline int BinaryFormat::readProbabilityWithoutMovingPointer(const uint8_t *const dict, - const int pos) { - return dict[pos]; -} - -AK_FORCE_INLINE int BinaryFormat::skipOtherCharacters(const uint8_t *const dict, const int pos) { - int currentPos = pos; - int 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 & BinaryFormat::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 * BinaryFormat::MASK_ATTRIBUTE_ADDRESS_TYPE) { - case FLAG_ATTRIBUTE_ADDRESS_TYPE_ONEBYTE: return 1; - case FLAG_ATTRIBUTE_ADDRESS_TYPE_TWOBYTES: return 2; - case FLAG_ATTRIBUTE_ADDRESS_TYPE_THREEBYTE: return 3; - default: return 0; - } - */ -} - -static AK_FORCE_INLINE int skipExistingBigrams(const uint8_t *const dict, const int pos) { - int currentPos = pos; - uint8_t flags = BinaryFormat::getFlagsAndForwardPointer(dict, ¤tPos); - while (flags & BinaryFormat::FLAG_ATTRIBUTE_HAS_NEXT) { - currentPos += attributeAddressSize(flags); - flags = BinaryFormat::getFlagsAndForwardPointer(dict, ¤tPos); - } - currentPos += attributeAddressSize(flags); - return currentPos; -} - -static inline int childrenAddressSize(const uint8_t flags) { - static const int CHILDREN_ADDRESS_SHIFT = 6; - return (BinaryFormat::MASK_GROUP_ADDRESS_TYPE & flags) >> CHILDREN_ADDRESS_SHIFT; - /* See the note in attributeAddressSize. The same applies here */ -} - -static AK_FORCE_INLINE int shortcutByteSize(const uint8_t *const dict, const int pos) { - return (static_cast<int>(dict[pos] << 8)) + (dict[pos + 1]); -} - -inline int BinaryFormat::skipChildrenPosition(const uint8_t flags, const int pos) { - return pos + childrenAddressSize(flags); -} - -inline int BinaryFormat::skipProbability(const uint8_t flags, const int pos) { - return FLAG_IS_TERMINAL & flags ? pos + 1 : pos; -} - -AK_FORCE_INLINE int BinaryFormat::skipShortcuts(const uint8_t *const dict, const uint8_t flags, - const int pos) { - if (FLAG_HAS_SHORTCUT_TARGETS & flags) { - return pos + shortcutByteSize(dict, pos); - } else { - return pos; - } -} - -AK_FORCE_INLINE int BinaryFormat::skipBigrams(const uint8_t *const dict, const uint8_t flags, - const int pos) { - if (FLAG_HAS_BIGRAMS & flags) { - return skipExistingBigrams(dict, pos); - } else { - return pos; - } -} - -AK_FORCE_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; - newPos = skipShortcuts(dict, flags, newPos); - newPos = skipBigrams(dict, flags, newPos); - return newPos; -} - -AK_FORCE_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; -} - -AK_FORCE_INLINE int BinaryFormat::readChildrenPosition(const uint8_t *const dict, - const uint8_t flags, const int pos) { - int offset = 0; - switch (MASK_GROUP_ADDRESS_TYPE & flags) { - case FLAG_GROUP_ADDRESS_TYPE_ONEBYTE: - offset = dict[pos]; - break; - case FLAG_GROUP_ADDRESS_TYPE_TWOBYTES: - offset = dict[pos] << 8; - offset += dict[pos + 1]; - break; - case 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 (FLAG_GROUP_ADDRESS_TYPE_NOADDRESS != (MASK_GROUP_ADDRESS_TYPE & flags)); -} - -AK_FORCE_INLINE int BinaryFormat::getAttributeAddressAndForwardPointer(const uint8_t *const dict, - const uint8_t flags, int *pos) { - int offset = 0; - const int origin = *pos; - switch (MASK_ATTRIBUTE_ADDRESS_TYPE & flags) { - case FLAG_ATTRIBUTE_ADDRESS_TYPE_ONEBYTE: - offset = dict[origin]; - *pos = origin + 1; - break; - case FLAG_ATTRIBUTE_ADDRESS_TYPE_TWOBYTES: - offset = dict[origin] << 8; - offset += dict[origin + 1]; - *pos = origin + 2; - break; - case FLAG_ATTRIBUTE_ADDRESS_TYPE_THREEBYTES: - offset = dict[origin] << 16; - offset += dict[origin + 1] << 8; - offset += dict[origin + 2]; - *pos = origin + 3; - break; - } - if (FLAG_ATTRIBUTE_OFFSET_NEGATIVE & flags) { - return origin - offset; - } else { - return origin + offset; - } -} - -inline int BinaryFormat::getAttributeProbabilityFromFlags(const int flags) { - return flags & MASK_ATTRIBUTE_PROBABILITY; -} - -// 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. -AK_FORCE_INLINE int BinaryFormat::getTerminalPosition(const uint8_t *const root, - const int *const inWord, const int length, const bool forceLowerCaseSearch) { - 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 int wChar = forceLowerCaseSearch ? toLowerCase(inWord[wordPos]) : 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); - int character = BinaryFormat::getCodePointAndForwardPointer(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 (FLAG_HAS_MULTIPLE_CHARS & flags) { - character = BinaryFormat::getCodePointAndForwardPointer(root, &pos); - while (NOT_A_CODE_POINT != 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::getCodePointAndForwardPointer(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 (FLAG_IS_TERMINAL & flags) { - if (wordPos == length) { - return charGroupPos; - } - pos = BinaryFormat::skipProbability(FLAG_IS_TERMINAL, pos); - } - if (FLAG_GROUP_ADDRESS_TYPE_NOADDRESS == (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 (FLAG_HAS_MULTIPLE_CHARS & flags) { - pos = BinaryFormat::skipOtherCharacters(root, pos); - } - pos = BinaryFormat::skipProbability(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. - * outUnigramProbability: a pointer to an int to write the probability into. - * Return value : the length of the word, of 0 if the word was not found. - */ -AK_FORCE_INLINE int BinaryFormat::getWordAtAddress(const uint8_t *const root, const int address, - const int maxDepth, int *outWord, int *outUnigramProbability) { - 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 int character = getCodePointAndForwardPointer(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 (FLAG_HAS_MULTIPLE_CHARS & flags) { - int nextChar = getCodePointAndForwardPointer(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 (NOT_A_CODE_POINT != nextChar && --charCount > 0) { - outWord[++wordPos] = nextChar; - nextChar = getCodePointAndForwardPointer(root, &pos); - } - } - *outUnigramProbability = readProbabilityWithoutMovingPointer(root, pos); - return ++wordPos; - } - // We need to skip past this char group, so skip any remaining chars after the - // first and possibly the probability. - if (FLAG_HAS_MULTIPLE_CHARS & flags) { - pos = skipOtherCharacters(root, pos); - } - pos = skipProbability(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 = (FLAG_GROUP_ADDRESS_TYPE_NOADDRESS != - (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 int lastChar = - getCodePointAndForwardPointer(root, &lastCandidateGroupPos); - // We copy all the characters in this group to the buffer - outWord[wordPos] = lastChar; - if (FLAG_HAS_MULTIPLE_CHARS & lastFlags) { - int nextChar = getCodePointAndForwardPointer(root, &lastCandidateGroupPos); - int charCount = maxDepth; - while (-1 != nextChar && --charCount > 0) { - outWord[++wordPos] = nextChar; - nextChar = getCodePointAndForwardPointer(root, &lastCandidateGroupPos); - } - } - ++wordPos; - // Now we only need to branch to the children address. Skip the probability if - // it's there, read pos, and break to resume the search at pos. - lastCandidateGroupPos = skipProbability(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; -} - -static inline int backoff(const int unigramProbability) { - return unigramProbability; - // For some reason, applying the backoff weight gives bad results in tests. To apply the - // backoff weight, we divide the probability by 2, which in our storing format means - // decreasing the score by 8. - // TODO: figure out what's wrong with this. - // return unigramProbability > 8 ? unigramProbability - 8 : (0 == unigramProbability ? 0 : 8); -} - -inline int BinaryFormat::computeProbabilityForBigram( - const int unigramProbability, const int bigramProbability) { - // We divide the range [unigramProbability..255] in 16.5 steps - in other words, we want the - // unigram probability to be the median value of the 17th step from the top. A value of - // 0 for the bigram probability represents the middle of the 16th step from the top, - // while a value of 15 represents the middle of the top step. - // See makedict.BinaryDictInputOutput for details. - const float stepSize = static_cast<float>(MAX_PROBABILITY - unigramProbability) - / (1.5f + MAX_BIGRAM_ENCODED_PROBABILITY); - return unigramProbability - + static_cast<int>(static_cast<float>(bigramProbability + 1) * stepSize); -} - -// This returns a probability in log space. -inline int BinaryFormat::getProbability(const int position, const std::map<int, int> *bigramMap, - const uint8_t *bigramFilter, const int unigramProbability) { - if (!bigramMap || !bigramFilter) return backoff(unigramProbability); - if (!isInFilter(bigramFilter, position)) return backoff(unigramProbability); - const std::map<int, int>::const_iterator bigramProbabilityIt = bigramMap->find(position); - if (bigramProbabilityIt != bigramMap->end()) { - const int bigramProbability = bigramProbabilityIt->second; - return computeProbabilityForBigram(unigramProbability, bigramProbability); - } - return backoff(unigramProbability); -} - -// This returns a probability in log space. -inline int BinaryFormat::getBigramProbabilityFromHashMap(const int position, - const hash_map_compat<int, int> *bigramMap, const int unigramProbability) { - if (!bigramMap) return backoff(unigramProbability); - const hash_map_compat<int, int>::const_iterator bigramProbabilityIt = bigramMap->find(position); - if (bigramProbabilityIt != bigramMap->end()) { - const int bigramProbability = bigramProbabilityIt->second; - return computeProbabilityForBigram(unigramProbability, bigramProbability); - } - return backoff(unigramProbability); -} - -AK_FORCE_INLINE void BinaryFormat::fillBigramProbabilityToHashMap( - const uint8_t *const root, int position, hash_map_compat<int, int> *bigramMap) { - position = getBigramListPositionForWordPosition(root, position); - if (0 == position) return; - - uint8_t bigramFlags; - do { - bigramFlags = getFlagsAndForwardPointer(root, &position); - const int probability = MASK_ATTRIBUTE_PROBABILITY & bigramFlags; - const int bigramPos = getAttributeAddressAndForwardPointer(root, bigramFlags, - &position); - (*bigramMap)[bigramPos] = probability; - } while (FLAG_ATTRIBUTE_HAS_NEXT & bigramFlags); -} - -AK_FORCE_INLINE int BinaryFormat::getBigramProbability(const uint8_t *const root, int position, - const int nextPosition, const int unigramProbability) { - position = getBigramListPositionForWordPosition(root, position); - if (0 == position) return backoff(unigramProbability); - - uint8_t bigramFlags; - do { - bigramFlags = getFlagsAndForwardPointer(root, &position); - const int bigramPos = getAttributeAddressAndForwardPointer( - root, bigramFlags, &position); - if (bigramPos == nextPosition) { - const int bigramProbability = MASK_ATTRIBUTE_PROBABILITY & bigramFlags; - return computeProbabilityForBigram(unigramProbability, bigramProbability); - } - } while (FLAG_ATTRIBUTE_HAS_NEXT & bigramFlags); - return backoff(unigramProbability); -} - -// Returns a pointer to the start of the bigram list. -AK_FORCE_INLINE int BinaryFormat::getBigramListPositionForWordPosition( - const uint8_t *const root, int position) { - if (NOT_VALID_WORD == position) return 0; - const uint8_t flags = getFlagsAndForwardPointer(root, &position); - if (!(flags & FLAG_HAS_BIGRAMS)) return 0; - if (flags & FLAG_HAS_MULTIPLE_CHARS) { - position = skipOtherCharacters(root, position); - } else { - getCodePointAndForwardPointer(root, &position); - } - position = skipProbability(flags, position); - position = skipChildrenPosition(flags, position); - position = skipShortcuts(root, flags, position); - return position; -} - -} // namespace latinime -#endif // LATINIME_BINARY_FORMAT_H |