1/*
2 * Copyright (C) 2012 The Android Open Source Project
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 *      http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 */
16
17package com.android.inputmethod.latin.utils;
18
19import android.util.Log;
20
21import java.util.concurrent.TimeUnit;
22
23public final class UserHistoryForgettingCurveUtils {
24    private static final String TAG = UserHistoryForgettingCurveUtils.class.getSimpleName();
25    private static final boolean DEBUG = false;
26    private static final int DEFAULT_FC_FREQ = 127;
27    private static final int BOOSTED_FC_FREQ = 200;
28    private static int FC_FREQ_MAX = DEFAULT_FC_FREQ;
29    /* package */ static final int COUNT_MAX = 3;
30    private static final int FC_LEVEL_MAX = 3;
31    /* package */ static final int ELAPSED_TIME_MAX = 15;
32    private static final int ELAPSED_TIME_INTERVAL_HOURS = 6;
33    private static final long ELAPSED_TIME_INTERVAL_MILLIS =
34            TimeUnit.HOURS.toMillis(ELAPSED_TIME_INTERVAL_HOURS);
35    private static final int HALF_LIFE_HOURS = 48;
36    private static final int MAX_PUSH_ELAPSED = (FC_LEVEL_MAX + 1) * (ELAPSED_TIME_MAX + 1);
37
38    public static void boostMaxFreqForDebug() {
39        FC_FREQ_MAX = BOOSTED_FC_FREQ;
40    }
41
42    public static void resetMaxFreqForDebug() {
43        FC_FREQ_MAX = DEFAULT_FC_FREQ;
44    }
45
46    private UserHistoryForgettingCurveUtils() {
47        // This utility class is not publicly instantiable.
48    }
49
50    public static final class ForgettingCurveParams {
51        private byte mFc;
52        long mLastTouchedTime = 0;
53        private final boolean mIsValid;
54
55        private void updateLastTouchedTime() {
56            mLastTouchedTime = System.currentTimeMillis();
57        }
58
59        public ForgettingCurveParams(boolean isValid) {
60            this(System.currentTimeMillis(), isValid);
61        }
62
63        private ForgettingCurveParams(long now, boolean isValid) {
64            this(pushCount((byte)0, isValid), now, now, isValid);
65        }
66
67        /** This constructor is called when the user history bigram dictionary is being restored. */
68        public ForgettingCurveParams(int fc, long now, long last) {
69            // All words with level >= 1 had been saved.
70            // Invalid words with level == 0 had been saved.
71            // Valid words words with level == 0 had *not* been saved.
72            this(fc, now, last, fcToLevel((byte)fc) > 0);
73        }
74
75        private ForgettingCurveParams(int fc, long now, long last, boolean isValid) {
76            mIsValid = isValid;
77            mFc = (byte)fc;
78            mLastTouchedTime = last;
79            updateElapsedTime(now);
80        }
81
82        public boolean isValid() {
83            return mIsValid;
84        }
85
86        public byte getFc() {
87            updateElapsedTime(System.currentTimeMillis());
88            return mFc;
89        }
90
91        public int getFrequency() {
92            updateElapsedTime(System.currentTimeMillis());
93            return UserHistoryForgettingCurveUtils.fcToFreq(mFc);
94        }
95
96        public int notifyTypedAgainAndGetFrequency() {
97            updateLastTouchedTime();
98            // TODO: Check whether this word is valid or not
99            mFc = pushCount(mFc, false);
100            return UserHistoryForgettingCurveUtils.fcToFreq(mFc);
101        }
102
103        private void updateElapsedTime(long now) {
104            final int elapsedTimeCount =
105                    (int)((now - mLastTouchedTime) / ELAPSED_TIME_INTERVAL_MILLIS);
106            if (elapsedTimeCount <= 0) {
107                return;
108            }
109            if (elapsedTimeCount >= MAX_PUSH_ELAPSED) {
110                mLastTouchedTime = now;
111                mFc = 0;
112                return;
113            }
114            for (int i = 0; i < elapsedTimeCount; ++i) {
115                mLastTouchedTime += ELAPSED_TIME_INTERVAL_MILLIS;
116                mFc = pushElapsedTime(mFc);
117            }
118        }
119    }
120
121    /* package */ static  int fcToElapsedTime(byte fc) {
122        return fc & 0x0F;
123    }
124
125    /* package */ static int fcToCount(byte fc) {
126        return (fc >> 4) & 0x03;
127    }
128
129    /* package */ static int fcToLevel(byte fc) {
130        return (fc >> 6) & 0x03;
131    }
132
133    private static int calcFreq(int elapsedTime, int count, int level) {
134        if (level <= 0) {
135            // Reserved words, just return -1
136            return -1;
137        }
138        if (count == COUNT_MAX) {
139            // Temporary promote because it's frequently typed recently
140            ++level;
141        }
142        final int et = Math.min(FC_FREQ_MAX, Math.max(0, elapsedTime));
143        final int l = Math.min(FC_LEVEL_MAX, Math.max(0, level));
144        return MathUtils.SCORE_TABLE[l - 1][et];
145    }
146
147    /* pakcage */ static byte calcFc(int elapsedTime, int count, int level) {
148        final int et = Math.min(FC_FREQ_MAX, Math.max(0, elapsedTime));
149        final int c = Math.min(COUNT_MAX, Math.max(0, count));
150        final int l = Math.min(FC_LEVEL_MAX, Math.max(0, level));
151        return (byte)(et | (c << 4) | (l << 6));
152    }
153
154    public static int fcToFreq(byte fc) {
155        final int elapsedTime = fcToElapsedTime(fc);
156        final int count = fcToCount(fc);
157        final int level = fcToLevel(fc);
158        return calcFreq(elapsedTime, count, level);
159    }
160
161    public static byte pushElapsedTime(byte fc) {
162        int elapsedTime = fcToElapsedTime(fc);
163        int count = fcToCount(fc);
164        int level = fcToLevel(fc);
165        if (elapsedTime >= ELAPSED_TIME_MAX) {
166            // Downgrade level
167            elapsedTime = 0;
168            count = COUNT_MAX;
169            --level;
170        } else {
171            ++elapsedTime;
172        }
173        return calcFc(elapsedTime, count, level);
174    }
175
176    public static byte pushCount(byte fc, boolean isValid) {
177        final int elapsedTime = fcToElapsedTime(fc);
178        int count = fcToCount(fc);
179        int level = fcToLevel(fc);
180        if ((elapsedTime == 0 && count >= COUNT_MAX) || (isValid && level == 0)) {
181            // Upgrade level
182            ++level;
183            count = 0;
184            if (DEBUG) {
185                Log.d(TAG, "Upgrade level.");
186            }
187        } else {
188            ++count;
189        }
190        return calcFc(0, count, level);
191    }
192
193    // TODO: isValid should be false for a word whose frequency is 0,
194    // or that is not in the dictionary.
195    /**
196     * Check wheather we should save the bigram to the SQL DB or not
197     */
198    public static boolean needsToSave(byte fc, boolean isValid, boolean addLevel0Bigram) {
199        int level = fcToLevel(fc);
200        if (level == 0) {
201            if (isValid || !addLevel0Bigram) {
202                return false;
203            }
204        }
205        final int elapsedTime = fcToElapsedTime(fc);
206        return (elapsedTime < ELAPSED_TIME_MAX - 1 || level > 0);
207    }
208
209    private static final class MathUtils {
210        public static final int[][] SCORE_TABLE = new int[FC_LEVEL_MAX][ELAPSED_TIME_MAX + 1];
211        static {
212            for (int i = 0; i < FC_LEVEL_MAX; ++i) {
213                final float initialFreq;
214                if (i >= 2) {
215                    initialFreq = FC_FREQ_MAX;
216                } else if (i == 1) {
217                    initialFreq = FC_FREQ_MAX / 2;
218                } else if (i == 0) {
219                    initialFreq = FC_FREQ_MAX / 4;
220                } else {
221                    continue;
222                }
223                for (int j = 0; j < ELAPSED_TIME_MAX; ++j) {
224                    final float elapsedHours = j * ELAPSED_TIME_INTERVAL_HOURS;
225                    final float freq = initialFreq
226                            * (float)Math.pow(initialFreq, elapsedHours / HALF_LIFE_HOURS);
227                    final int intFreq = Math.min(FC_FREQ_MAX, Math.max(0, (int)freq));
228                    SCORE_TABLE[i][j] = intFreq;
229                }
230            }
231        }
232    }
233}
234