diff options
Diffstat (limited to 'native')
-rw-r--r-- | native/jni/NativeFileList.mk | 4 | ||||
-rw-r--r-- | native/jni/src/defines.h | 8 | ||||
-rw-r--r-- | native/jni/src/suggest/core/dictionary/bloom_filter.h | 39 | ||||
-rw-r--r-- | native/jni/src/suggest/core/layout/normal_distribution_2d.h | 59 | ||||
-rw-r--r-- | native/jni/src/suggest/core/layout/proximity_info_params.cpp | 8 | ||||
-rw-r--r-- | native/jni/src/suggest/core/layout/proximity_info_params.h | 9 | ||||
-rw-r--r-- | native/jni/src/suggest/core/layout/proximity_info_state.cpp | 2 | ||||
-rw-r--r-- | native/jni/src/suggest/core/layout/proximity_info_state_utils.cpp | 113 | ||||
-rw-r--r-- | native/jni/src/suggest/core/layout/proximity_info_state_utils.h | 1 | ||||
-rw-r--r-- | native/jni/tests/defines_test.cpp (renamed from native/jni/src/suggest/core/dictionary/bloom_filter.cpp) | 23 | ||||
-rw-r--r-- | native/jni/tests/suggest/core/dictionary/bloom_filter_test.cpp | 80 | ||||
-rw-r--r-- | native/jni/tests/suggest/core/layout/normal_distribution_2d_test.cpp | 68 |
12 files changed, 306 insertions, 108 deletions
diff --git a/native/jni/NativeFileList.mk b/native/jni/NativeFileList.mk index 1031903f8..70a6638fb 100644 --- a/native/jni/NativeFileList.mk +++ b/native/jni/NativeFileList.mk @@ -27,7 +27,6 @@ LATIN_IME_CORE_SRC_FILES := \ dic_nodes_cache.cpp) \ $(addprefix suggest/core/dictionary/, \ bigram_dictionary.cpp \ - bloom_filter.cpp \ dictionary.cpp \ digraph_utils.cpp \ error_type_utils.cpp \ @@ -101,4 +100,7 @@ LATIN_IME_CORE_SRC_FILES := \ time_keeper.cpp) LATIN_IME_CORE_TEST_FILES := \ + defines_test.cpp \ + suggest/core/layout/normal_distribution_2d_test.cpp \ + suggest/core/dictionary/bloom_filter_test.cpp \ utils/autocorrection_threshold_utils_test.cpp diff --git a/native/jni/src/defines.h b/native/jni/src/defines.h index 1719b1c60..3becc79e8 100644 --- a/native/jni/src/defines.h +++ b/native/jni/src/defines.h @@ -35,7 +35,13 @@ // Must be equal to ProximityInfo.MAX_PROXIMITY_CHARS_SIZE in Java #define MAX_PROXIMITY_CHARS_SIZE 16 #define ADDITIONAL_PROXIMITY_CHAR_DELIMITER_CODE 2 -#define NELEMS(x) (sizeof(x) / sizeof((x)[0])) + +// TODO: Use size_t instead of int. +// Disclaimer: You will see a compile error if you use this macro against a variable-length array. +// Sorry for the inconvenience. It isn't supported. +template <typename T, int N> +char (&ArraySizeHelper(T (&array)[N]))[N]; +#define NELEMS(x) (sizeof(ArraySizeHelper(x))) AK_FORCE_INLINE static int intArrayToCharArray(const int *const source, const int sourceSize, char *dest, const int destSize) { diff --git a/native/jni/src/suggest/core/dictionary/bloom_filter.h b/native/jni/src/suggest/core/dictionary/bloom_filter.h index 85b8fc397..1e60f49ed 100644 --- a/native/jni/src/suggest/core/dictionary/bloom_filter.h +++ b/native/jni/src/suggest/core/dictionary/bloom_filter.h @@ -17,8 +17,7 @@ #ifndef LATINIME_BLOOM_FILTER_H #define LATINIME_BLOOM_FILTER_H -#include <cstdint> -#include <cstring> +#include <bitset> #include "defines.h" @@ -34,41 +33,37 @@ namespace latinime { // Total 148603.14 (sum of others 148579.90) class BloomFilter { public: - BloomFilter() { - ASSERT(BIGRAM_FILTER_BYTE_SIZE * 8 >= BIGRAM_FILTER_MODULO); - memset(mFilter, 0, sizeof(mFilter)); - } + BloomFilter() : mFilter() {} - // TODO: uint32_t position - AK_FORCE_INLINE void setInFilter(const int32_t position) { - const uint32_t bucket = static_cast<uint32_t>(position % BIGRAM_FILTER_MODULO); - mFilter[bucket >> 3] |= static_cast<uint8_t>(1 << (bucket & 0x7)); + AK_FORCE_INLINE void setInFilter(const int position) { + mFilter.set(getIndex(position)); } - // TODO: uint32_t position - AK_FORCE_INLINE bool isInFilter(const int32_t position) const { - const uint32_t bucket = static_cast<uint32_t>(position % BIGRAM_FILTER_MODULO); - return (mFilter[bucket >> 3] & static_cast<uint8_t>(1 << (bucket & 0x7))) != 0; + AK_FORCE_INLINE bool isInFilter(const int position) const { + return mFilter.test(getIndex(position)); } private: DISALLOW_ASSIGNMENT_OPERATOR(BloomFilter); - // Size, in bytes, of the bloom filter index for bigrams - // 128 gives us 1024 buckets. The probability of false positive is (1 - e ** (-kn/m))**k, + AK_FORCE_INLINE size_t getIndex(const int position) const { + return static_cast<size_t>(position) % BIGRAM_FILTER_MODULO; + } + + // Size, in bits, of the bloom filter index for bigrams + // The probability of false positive is (1 - e ** (-kn/m))**k, // where k is the number of hash functions, n the number of bigrams, and m the number of // bits we can test. - // At the moment 100 is the maximum number of bigrams for a word with the current + // At the moment 100 is the maximum number of bigrams for a word with the current main // dictionaries, so n = 100. 1024 buckets give us m = 1024. // With 1 hash function, our false positive rate is about 9.3%, which should be enough for // our uses since we are only using this to increase average performance. For the record, // k = 2 gives 3.1% and k = 3 gives 1.6%. With k = 1, making m = 2048 gives 4.8%, // and m = 4096 gives 2.4%. - // This is assigned here because it is used for array size. - static const int BIGRAM_FILTER_BYTE_SIZE = 128; - static const int BIGRAM_FILTER_MODULO; - - uint8_t mFilter[BIGRAM_FILTER_BYTE_SIZE]; + // This is assigned here because it is used for bitset size. + // 1021 is the largest prime under 1024. + static const size_t BIGRAM_FILTER_MODULO = 1021; + std::bitset<BIGRAM_FILTER_MODULO> mFilter; }; } // namespace latinime #endif // LATINIME_BLOOM_FILTER_H diff --git a/native/jni/src/suggest/core/layout/normal_distribution_2d.h b/native/jni/src/suggest/core/layout/normal_distribution_2d.h new file mode 100644 index 000000000..3bc0a0153 --- /dev/null +++ b/native/jni/src/suggest/core/layout/normal_distribution_2d.h @@ -0,0 +1,59 @@ +/* + * Copyright (C) 2014 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_NORMAL_DISTRIBUTION_2D_H +#define LATINIME_NORMAL_DISTRIBUTION_2D_H + +#include <cmath> + +#include "defines.h" +#include "suggest/core/layout/geometry_utils.h" +#include "suggest/core/layout/normal_distribution.h" + +namespace latinime { + +// Normal distribution on a 2D plane. The covariance is always zero, but the distribution can be +// rotated. +class NormalDistribution2D { + public: + NormalDistribution2D(const float uX, const float sigmaX, const float uY, const float sigmaY, + const float theta) + : mXDistribution(0.0f, sigmaX), mYDistribution(0.0f, sigmaY), mUX(uX), mUY(uY), + mSinTheta(sinf(theta)), mCosTheta(cosf(theta)) {} + + float getProbabilityDensity(const float x, const float y) const { + // Shift + const float shiftedX = x - mUX; + const float shiftedY = y - mUY; + // Rotate + const float rotatedShiftedX = mCosTheta * shiftedX + mSinTheta * shiftedY; + const float rotatedShiftedY = -mSinTheta * shiftedX + mCosTheta * shiftedY; + return mXDistribution.getProbabilityDensity(rotatedShiftedX) + * mYDistribution.getProbabilityDensity(rotatedShiftedY); + } + + private: + DISALLOW_IMPLICIT_CONSTRUCTORS(NormalDistribution2D); + + const NormalDistribution mXDistribution; + const NormalDistribution mYDistribution; + const float mUX; + const float mUY; + const float mSinTheta; + const float mCosTheta; +}; +} // namespace latinime +#endif // LATINIME_NORMAL_DISTRIBUTION_2D_H diff --git a/native/jni/src/suggest/core/layout/proximity_info_params.cpp b/native/jni/src/suggest/core/layout/proximity_info_params.cpp index 597518a4c..a70dd7e34 100644 --- a/native/jni/src/suggest/core/layout/proximity_info_params.cpp +++ b/native/jni/src/suggest/core/layout/proximity_info_params.cpp @@ -76,8 +76,12 @@ const float ProximityInfoParams::MAX_SPEEDxANGLE_RATE_FOR_STANDARD_DEVIATION = 0 const float ProximityInfoParams::SPEEDxNEAREST_WEIGHT_FOR_STANDARD_DEVIATION = 0.5f; const float ProximityInfoParams::MAX_SPEEDxNEAREST_RATE_FOR_STANDARD_DEVIATION = 0.15f; const float ProximityInfoParams::MIN_STANDARD_DEVIATION = 0.37f; -const float ProximityInfoParams::PREV_DISTANCE_WEIGHT = 0.5f; -const float ProximityInfoParams::NEXT_DISTANCE_WEIGHT = 0.6f; +const float ProximityInfoParams::STANDARD_DEVIATION_X_WEIGHT_FOR_FIRST = 1.25f; +const float ProximityInfoParams::STANDARD_DEVIATION_Y_WEIGHT_FOR_FIRST = 0.85f; +const float ProximityInfoParams::STANDARD_DEVIATION_X_WEIGHT_FOR_LAST = 1.4f; +const float ProximityInfoParams::STANDARD_DEVIATION_Y_WEIGHT_FOR_LAST = 0.95f; +const float ProximityInfoParams::STANDARD_DEVIATION_X_WEIGHT = 1.1f; +const float ProximityInfoParams::STANDARD_DEVIATION_Y_WEIGHT = 0.95f; // Used by ProximityInfoStateUtils::suppressCharProbabilities() const float ProximityInfoParams::SUPPRESSION_LENGTH_WEIGHT = 1.5f; diff --git a/native/jni/src/suggest/core/layout/proximity_info_params.h b/native/jni/src/suggest/core/layout/proximity_info_params.h index ae1f82c22..b8e9f5daf 100644 --- a/native/jni/src/suggest/core/layout/proximity_info_params.h +++ b/native/jni/src/suggest/core/layout/proximity_info_params.h @@ -78,8 +78,13 @@ class ProximityInfoParams { static const float SPEEDxNEAREST_WEIGHT_FOR_STANDARD_DEVIATION; static const float MAX_SPEEDxNEAREST_RATE_FOR_STANDARD_DEVIATION; static const float MIN_STANDARD_DEVIATION; - static const float PREV_DISTANCE_WEIGHT; - static const float NEXT_DISTANCE_WEIGHT; + // X means gesture's direction. Y means gesture's orthogonal direction. + static const float STANDARD_DEVIATION_X_WEIGHT_FOR_FIRST; + static const float STANDARD_DEVIATION_Y_WEIGHT_FOR_FIRST; + static const float STANDARD_DEVIATION_X_WEIGHT_FOR_LAST; + static const float STANDARD_DEVIATION_Y_WEIGHT_FOR_LAST; + static const float STANDARD_DEVIATION_X_WEIGHT; + static const float STANDARD_DEVIATION_Y_WEIGHT; // Used by ProximityInfoStateUtils::suppressCharProbabilities() static const float SUPPRESSION_LENGTH_WEIGHT; diff --git a/native/jni/src/suggest/core/layout/proximity_info_state.cpp b/native/jni/src/suggest/core/layout/proximity_info_state.cpp index 2919904e5..b75c2ef67 100644 --- a/native/jni/src/suggest/core/layout/proximity_info_state.cpp +++ b/native/jni/src/suggest/core/layout/proximity_info_state.cpp @@ -134,7 +134,7 @@ void ProximityInfoState::initInputParams(const int pointerId, const float maxPoi mProximityInfo->getKeyCount(), lastSavedInputSize, mSampledInputSize, &mSampledInputXs, &mSampledInputYs, &mSpeedRates, &mSampledLengthCache, &mSampledNormalizedSquaredLengthCache, &mSampledNearKeySets, - &mCharProbabilities); + mProximityInfo, &mCharProbabilities); ProximityInfoStateUtils::updateSampledSearchKeySets(mProximityInfo, mSampledInputSize, lastSavedInputSize, &mSampledLengthCache, &mSampledNearKeySets, &mSampledSearchKeySets, diff --git a/native/jni/src/suggest/core/layout/proximity_info_state_utils.cpp b/native/jni/src/suggest/core/layout/proximity_info_state_utils.cpp index 5a3ff7384..638297eb1 100644 --- a/native/jni/src/suggest/core/layout/proximity_info_state_utils.cpp +++ b/native/jni/src/suggest/core/layout/proximity_info_state_utils.cpp @@ -24,7 +24,7 @@ #include "defines.h" #include "suggest/core/layout/geometry_utils.h" -#include "suggest/core/layout/normal_distribution.h" +#include "suggest/core/layout/normal_distribution_2d.h" #include "suggest/core/layout/proximity_info.h" #include "suggest/core/layout/proximity_info_params.h" @@ -627,6 +627,7 @@ namespace latinime { const std::vector<int> *const sampledLengthCache, const std::vector<float> *const sampledNormalizedSquaredLengthCache, std::vector<NearKeycodesSet> *sampledNearKeySets, + const ProximityInfo *const proximityInfo, std::vector<hash_map_compat<int, float> > *charProbabilities) { charProbabilities->resize(sampledInputSize); // Calculates probabilities of using a point as a correlated point with the character @@ -709,89 +710,57 @@ namespace latinime { // (1.0f - skipProbability). const float inputCharProbability = 1.0f - skipProbability; - const float speedxAngleRate = std::min(speedRate * currentAngle / M_PI_F + const float speedMultipliedByAngleRate = std::min(speedRate * currentAngle / M_PI_F * ProximityInfoParams::SPEEDxANGLE_WEIGHT_FOR_STANDARD_DEVIATION, ProximityInfoParams::MAX_SPEEDxANGLE_RATE_FOR_STANDARD_DEVIATION); - const float speedxNearestKeyDistanceRate = std::min(speedRate * nearestKeyDistance - * ProximityInfoParams::SPEEDxNEAREST_WEIGHT_FOR_STANDARD_DEVIATION, - ProximityInfoParams::MAX_SPEEDxNEAREST_RATE_FOR_STANDARD_DEVIATION); - const float sigma = speedxAngleRate + speedxNearestKeyDistanceRate - + ProximityInfoParams::MIN_STANDARD_DEVIATION; - - NormalDistribution distribution( - ProximityInfoParams::CENTER_VALUE_OF_NORMALIZED_DISTRIBUTION, sigma); + const float speedMultipliedByNearestKeyDistanceRate = std::min( + speedRate * nearestKeyDistance + * ProximityInfoParams::SPEEDxNEAREST_WEIGHT_FOR_STANDARD_DEVIATION, + ProximityInfoParams::MAX_SPEEDxNEAREST_RATE_FOR_STANDARD_DEVIATION); + const float sigma = (speedMultipliedByAngleRate + speedMultipliedByNearestKeyDistanceRate + + ProximityInfoParams::MIN_STANDARD_DEVIATION) * mostCommonKeyWidth; + float theta = 0.0f; + // TODO: Use different metrics to compute sigmas. + float sigmaX = sigma; + float sigmaY = sigma; + if (i == 0 && i != sampledInputSize - 1) { + // First point + theta = getDirection(sampledInputXs, sampledInputYs, i + 1, i); + sigmaX *= ProximityInfoParams::STANDARD_DEVIATION_X_WEIGHT_FOR_FIRST; + sigmaY *= ProximityInfoParams::STANDARD_DEVIATION_Y_WEIGHT_FOR_FIRST; + } else { + if (i == sampledInputSize - 1) { + // Last point + sigmaX *= ProximityInfoParams::STANDARD_DEVIATION_X_WEIGHT_FOR_LAST; + sigmaY *= ProximityInfoParams::STANDARD_DEVIATION_Y_WEIGHT_FOR_LAST; + } else { + sigmaX *= ProximityInfoParams::STANDARD_DEVIATION_X_WEIGHT; + sigmaY *= ProximityInfoParams::STANDARD_DEVIATION_Y_WEIGHT; + } + theta = getDirection(sampledInputXs, sampledInputYs, i, i - 1); + } + NormalDistribution2D distribution((*sampledInputXs)[i], sigmaX, (*sampledInputYs)[i], + sigmaY, theta); // Summing up probability densities of all near keys. float sumOfProbabilityDensities = 0.0f; for (int j = 0; j < keyCount; ++j) { if ((*sampledNearKeySets)[i].test(j)) { - float distance = sqrtf(getPointToKeyByIdLength( - maxPointToKeyLength, sampledNormalizedSquaredLengthCache, keyCount, i, j)); - if (i == 0 && i != sampledInputSize - 1) { - // For the first point, weighted average of distances from first point and the - // next point to the key is used as a point to key distance. - const float nextDistance = sqrtf(getPointToKeyByIdLength( - maxPointToKeyLength, sampledNormalizedSquaredLengthCache, keyCount, - i + 1, j)); - if (nextDistance < distance) { - // The distance of the first point tends to bigger than continuing - // points because the first touch by the user can be sloppy. - // So we promote the first point if the distance of that point is larger - // than the distance of the next point. - distance = (distance - + nextDistance * ProximityInfoParams::NEXT_DISTANCE_WEIGHT) - / (1.0f + ProximityInfoParams::NEXT_DISTANCE_WEIGHT); - } - } else if (i != 0 && i == sampledInputSize - 1) { - // For the first point, weighted average of distances from last point and - // the previous point to the key is used as a point to key distance. - const float previousDistance = sqrtf(getPointToKeyByIdLength( - maxPointToKeyLength, sampledNormalizedSquaredLengthCache, keyCount, - i - 1, j)); - if (previousDistance < distance) { - // The distance of the last point tends to bigger than continuing points - // because the last touch by the user can be sloppy. So we promote the - // last point if the distance of that point is larger than the distance of - // the previous point. - distance = (distance - + previousDistance * ProximityInfoParams::PREV_DISTANCE_WEIGHT) - / (1.0f + ProximityInfoParams::PREV_DISTANCE_WEIGHT); - } - } - // TODO: Promote the first point when the extended line from the next input is near - // from a key. Also, promote the last point as well. - sumOfProbabilityDensities += distribution.getProbabilityDensity(distance); + sumOfProbabilityDensities += distribution.getProbabilityDensity( + proximityInfo->getKeyCenterXOfKeyIdG(j, + NOT_A_COORDINATE /* referencePointX */, true /* isGeometric */), + proximityInfo->getKeyCenterYOfKeyIdG(j, + NOT_A_COORDINATE /* referencePointY */, true /* isGeometric */)); } } // Split the probability of an input point to keys that are close to the input point. for (int j = 0; j < keyCount; ++j) { if ((*sampledNearKeySets)[i].test(j)) { - float distance = sqrtf(getPointToKeyByIdLength( - maxPointToKeyLength, sampledNormalizedSquaredLengthCache, keyCount, i, j)); - if (i == 0 && i != sampledInputSize - 1) { - // For the first point, weighted average of distances from the first point and - // the next point to the key is used as a point to key distance. - const float prevDistance = sqrtf(getPointToKeyByIdLength( - maxPointToKeyLength, sampledNormalizedSquaredLengthCache, keyCount, - i + 1, j)); - if (prevDistance < distance) { - distance = (distance - + prevDistance * ProximityInfoParams::NEXT_DISTANCE_WEIGHT) - / (1.0f + ProximityInfoParams::NEXT_DISTANCE_WEIGHT); - } - } else if (i != 0 && i == sampledInputSize - 1) { - // For the first point, weighted average of distances from last point and - // the previous point to the key is used as a point to key distance. - const float prevDistance = sqrtf(getPointToKeyByIdLength( - maxPointToKeyLength, sampledNormalizedSquaredLengthCache, keyCount, - i - 1, j)); - if (prevDistance < distance) { - distance = (distance - + prevDistance * ProximityInfoParams::PREV_DISTANCE_WEIGHT) - / (1.0f + ProximityInfoParams::PREV_DISTANCE_WEIGHT); - } - } - const float probabilityDensity = distribution.getProbabilityDensity(distance); + const float probabilityDensity = distribution.getProbabilityDensity( + proximityInfo->getKeyCenterXOfKeyIdG(j, + NOT_A_COORDINATE /* referencePointX */, true /* isGeometric */), + proximityInfo->getKeyCenterYOfKeyIdG(j, + NOT_A_COORDINATE /* referencePointY */, true /* isGeometric */)); const float probability = inputCharProbability * probabilityDensity / sumOfProbabilityDensities; (*charProbabilities)[i][j] = probability; diff --git a/native/jni/src/suggest/core/layout/proximity_info_state_utils.h b/native/jni/src/suggest/core/layout/proximity_info_state_utils.h index ea0cd1149..5d7a9c589 100644 --- a/native/jni/src/suggest/core/layout/proximity_info_state_utils.h +++ b/native/jni/src/suggest/core/layout/proximity_info_state_utils.h @@ -72,6 +72,7 @@ class ProximityInfoStateUtils { const std::vector<int> *const sampledLengthCache, const std::vector<float> *const sampledNormalizedSquaredLengthCache, std::vector<NearKeycodesSet> *sampledNearKeySets, + const ProximityInfo *const proximityInfo, std::vector<hash_map_compat<int, float> > *charProbabilities); static void updateSampledSearchKeySets(const ProximityInfo *const proximityInfo, const int sampledInputSize, const int lastSavedInputSize, diff --git a/native/jni/src/suggest/core/dictionary/bloom_filter.cpp b/native/jni/tests/defines_test.cpp index 4ae474e0c..f7b80b2b5 100644 --- a/native/jni/src/suggest/core/dictionary/bloom_filter.cpp +++ b/native/jni/tests/defines_test.cpp @@ -1,11 +1,11 @@ /* - * Copyright (C) 2013, The Android Open Source Project + * Copyright (C) 2014 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 + * 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, @@ -14,12 +14,21 @@ * limitations under the License. */ -#include "suggest/core/dictionary/bloom_filter.h" +#include "defines.h" + +#include <gtest/gtest.h> namespace latinime { +namespace { -// Must be smaller than BIGRAM_FILTER_BYTE_SIZE * 8, and preferably prime. 1021 is the largest -// prime under 128 * 8. -const int BloomFilter::BIGRAM_FILTER_MODULO = 1021; +TEST(DefinesTest, NELEMSForFixedLengthArray) { + const size_t SMALL_ARRAY_SIZE = 1; + const size_t LARGE_ARRAY_SIZE = 100; + int smallArray[SMALL_ARRAY_SIZE]; + int largeArray[LARGE_ARRAY_SIZE]; + EXPECT_EQ(SMALL_ARRAY_SIZE, NELEMS(smallArray)); + EXPECT_EQ(LARGE_ARRAY_SIZE, NELEMS(largeArray)); +} -} // namespace latinime +} // namespace +} // namespace latinime diff --git a/native/jni/tests/suggest/core/dictionary/bloom_filter_test.cpp b/native/jni/tests/suggest/core/dictionary/bloom_filter_test.cpp new file mode 100644 index 000000000..b62021784 --- /dev/null +++ b/native/jni/tests/suggest/core/dictionary/bloom_filter_test.cpp @@ -0,0 +1,80 @@ +/* + * Copyright (C) 2014 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 "suggest/core/dictionary/bloom_filter.h" + +#include <gtest/gtest.h> + +#include <algorithm> +#include <cstdlib> +#include <functional> +#include <random> +#include <unordered_set> +#include <vector> + +namespace latinime { +namespace { + +TEST(BloomFilterTest, TestFilter) { + static const int TEST_RANDOM_DATA_MAX = 65536; + static const int ELEMENT_COUNT = 1000; + std::vector<int> elements; + + // Initialize data set with random integers. + { + // Use the uniform integer distribution [0, TEST_RANDOM_DATA_MAX]. + std::uniform_int_distribution<int> distribution(0, TEST_RANDOM_DATA_MAX); + auto randomNumberGenerator = std::bind(distribution, std::mt19937()); + for (int i = 0; i < ELEMENT_COUNT; ++i) { + elements.push_back(randomNumberGenerator()); + } + } + + // Make sure BloomFilter contains nothing by default. + BloomFilter bloomFilter; + for (const int elem : elements) { + ASSERT_FALSE(bloomFilter.isInFilter(elem)); + } + + // Copy some of the test vector into bloom filter. + std::unordered_set<int> elementsThatHaveBeenSetInFilter; + { + // Use the uniform integer distribution [0, 1]. + std::uniform_int_distribution<int> distribution(0, 1); + auto randomBitGenerator = std::bind(distribution, std::mt19937()); + for (const int elem : elements) { + if (randomBitGenerator() == 0) { + bloomFilter.setInFilter(elem); + elementsThatHaveBeenSetInFilter.insert(elem); + } + } + } + + for (const int elem : elements) { + const bool existsInFilter = bloomFilter.isInFilter(elem); + const bool hasBeenSetInFilter = + elementsThatHaveBeenSetInFilter.find(elem) != elementsThatHaveBeenSetInFilter.end(); + if (hasBeenSetInFilter) { + EXPECT_TRUE(existsInFilter) << "elem: " << elem; + } + if (!existsInFilter) { + EXPECT_FALSE(hasBeenSetInFilter) << "elem: " << elem; + } + } +} + +} // namespace +} // namespace latinime diff --git a/native/jni/tests/suggest/core/layout/normal_distribution_2d_test.cpp b/native/jni/tests/suggest/core/layout/normal_distribution_2d_test.cpp new file mode 100644 index 000000000..1d6a27c4f --- /dev/null +++ b/native/jni/tests/suggest/core/layout/normal_distribution_2d_test.cpp @@ -0,0 +1,68 @@ +/* + * Copyright (C) 2014 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 "suggest/core/layout/normal_distribution_2d.h" + +#include <gtest/gtest.h> + +#include <vector> + +namespace latinime { +namespace { + +static const float ORIGIN_X = 0.0f; +static const float ORIGIN_Y = 0.0f; +static const float LARGE_STANDARD_DEVIATION = 100.0f; +static const float SMALL_STANDARD_DEVIATION = 10.0f; +static const float ZERO_RADIAN = 0.0f; + +TEST(NormalDistribution2DTest, ProbabilityDensity) { + const NormalDistribution2D distribution(ORIGIN_X, LARGE_STANDARD_DEVIATION, ORIGIN_Y, + SMALL_STANDARD_DEVIATION, ZERO_RADIAN); + + static const float SMALL_COORDINATE = 10.0f; + static const float LARGE_COORDINATE = 20.0f; + // The probability density of the point near the distribution center is larger than the + // probability density of the point that is far from distribution center. + EXPECT_GE(distribution.getProbabilityDensity(SMALL_COORDINATE, SMALL_COORDINATE), + distribution.getProbabilityDensity(LARGE_COORDINATE, LARGE_COORDINATE)); + // The probability density of the point shifted toward the direction that has larger standard + // deviation is larger than the probability density of the point shifted towards another + // direction. + EXPECT_GE(distribution.getProbabilityDensity(LARGE_COORDINATE, SMALL_COORDINATE), + distribution.getProbabilityDensity(SMALL_COORDINATE, LARGE_COORDINATE)); +} + +TEST(NormalDistribution2DTest, Rotate) { + static const float COORDINATES[] = {0.0f, 10.0f, 100.0f, -20.0f}; + static const float EPSILON = 0.01f; + const NormalDistribution2D distribution(ORIGIN_X, LARGE_STANDARD_DEVIATION, ORIGIN_Y, + SMALL_STANDARD_DEVIATION, ZERO_RADIAN); + const NormalDistribution2D rotatedDistribution(ORIGIN_X, LARGE_STANDARD_DEVIATION, ORIGIN_Y, + SMALL_STANDARD_DEVIATION, M_PI_4); + for (const float x : COORDINATES) { + for (const float y : COORDINATES) { + // The probability density of the rotated distribution at the point and the probability + // density of the original distribution at the rotated point are the same. + const float probabilityDensity0 = distribution.getProbabilityDensity(x, y); + const float probabilityDensity1 = rotatedDistribution.getProbabilityDensity(-y, x); + EXPECT_NEAR(probabilityDensity0, probabilityDensity1, EPSILON); + } + } +} + +} // namespace +} // namespace latinime |