Home | History | Annotate | Download | only in recommendation 
      1 /*
      2  * Copyright (C) 2015 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 
     17 package com.android.tv.recommendation;
     18 
     19 import android.support.annotation.Nullable;
     20 import android.support.annotation.VisibleForTesting;
     21 import android.text.TextUtils;
     22 
     23 import com.android.tv.data.Program;
     24 
     25 import java.text.BreakIterator;
     26 import java.util.ArrayList;
     27 import java.util.Calendar;
     28 import java.util.List;
     29 import java.util.concurrent.TimeUnit;
     30 
     31 public class RoutineWatchEvaluator extends Recommender.Evaluator {
     32     // TODO: test and refine constant values in WatchedProgramRecommender in order to
     33     // improve the performance of this recommender.
     34     private static final double REQUIRED_MIN_SCORE = 0.15;
     35     @VisibleForTesting
     36     static final double MULTIPLIER_FOR_UNMATCHED_DAY_OF_WEEK = 0.7;
     37     private static final double TITLE_MATCH_WEIGHT = 0.5;
     38     private static final double TIME_MATCH_WEIGHT = 1 - TITLE_MATCH_WEIGHT;
     39     private static final long DIFF_MS_TOLERANCE_FOR_OLD_PROGRAM = TimeUnit.DAYS.toMillis(14);
     40     private static final long MAX_DIFF_MS_FOR_OLD_PROGRAM = TimeUnit.DAYS.toMillis(56);
     41 
     42     @Override
     43     public double evaluateChannel(long channelId) {
     44         ChannelRecord cr = getRecommender().getChannelRecord(channelId);
     45         if (cr == null) {
     46             return NOT_RECOMMENDED;
     47         }
     48 
     49         Program currentProgram = cr.getCurrentProgram();
     50         if (currentProgram == null) {
     51             return NOT_RECOMMENDED;
     52         }
     53 
     54         WatchedProgram[] watchHistory = cr.getWatchHistory();
     55         if (watchHistory.length < 1) {
     56             return NOT_RECOMMENDED;
     57         }
     58 
     59         Program watchedProgram = watchHistory[watchHistory.length - 1].getProgram();
     60         long startTimeDiffMsWithCurrentProgram = currentProgram.getStartTimeUtcMillis()
     61                 - watchedProgram.getStartTimeUtcMillis();
     62         if (startTimeDiffMsWithCurrentProgram >= MAX_DIFF_MS_FOR_OLD_PROGRAM) {
     63             return NOT_RECOMMENDED;
     64         }
     65 
     66         double maxScore = NOT_RECOMMENDED;
     67         long watchedDurationMs = watchHistory[watchHistory.length - 1].getWatchedDurationMs();
     68         for (int i = watchHistory.length - 2; i >= 0; --i) {
     69             if (watchedProgram.getStartTimeUtcMillis()
     70                     == watchHistory[i].getProgram().getStartTimeUtcMillis()) {
     71                 watchedDurationMs += watchHistory[i].getWatchedDurationMs();
     72             } else {
     73                 double score = calculateRoutineWatchScore(
     74                         currentProgram, watchedProgram, watchedDurationMs);
     75                 if (score >= REQUIRED_MIN_SCORE && score > maxScore) {
     76                     maxScore = score;
     77                 }
     78                 watchedProgram = watchHistory[i].getProgram();
     79                 watchedDurationMs = watchHistory[i].getWatchedDurationMs();
     80                 startTimeDiffMsWithCurrentProgram = currentProgram.getStartTimeUtcMillis()
     81                         - watchedProgram.getStartTimeUtcMillis();
     82                 if (startTimeDiffMsWithCurrentProgram >= MAX_DIFF_MS_FOR_OLD_PROGRAM) {
     83                     return maxScore;
     84                 }
     85             }
     86         }
     87         double score = calculateRoutineWatchScore(
     88                 currentProgram, watchedProgram, watchedDurationMs);
     89         if (score >= REQUIRED_MIN_SCORE && score > maxScore) {
     90             maxScore = score;
     91         }
     92         return maxScore;
     93     }
     94 
     95     private static double calculateRoutineWatchScore(Program currentProgram, Program watchedProgram,
     96             long watchedDurationMs) {
     97         double timeMatchScore = calculateTimeMatchScore(currentProgram, watchedProgram);
     98         double titleMatchScore = calculateTitleMatchScore(
     99                 currentProgram.getTitle(), watchedProgram.getTitle());
    100         double watchDurationScore = calculateWatchDurationScore(watchedProgram, watchedDurationMs);
    101         long diffMs = currentProgram.getStartTimeUtcMillis()
    102                 - watchedProgram.getStartTimeUtcMillis();
    103         double multiplierForOldProgram = (diffMs < MAX_DIFF_MS_FOR_OLD_PROGRAM)
    104                 ? 1.0 - (double) Math.max(diffMs - DIFF_MS_TOLERANCE_FOR_OLD_PROGRAM, 0)
    105                         / (MAX_DIFF_MS_FOR_OLD_PROGRAM - DIFF_MS_TOLERANCE_FOR_OLD_PROGRAM)
    106                 : 0.0;
    107         return (titleMatchScore * TITLE_MATCH_WEIGHT + timeMatchScore * TIME_MATCH_WEIGHT)
    108                 * watchDurationScore * multiplierForOldProgram;
    109     }
    110 
    111     @VisibleForTesting
    112     static double calculateTitleMatchScore(@Nullable String title1, @Nullable String title2) {
    113         if (TextUtils.isEmpty(title1) || TextUtils.isEmpty(title2)) {
    114             return 0;
    115         }
    116         List<String> wordList1 = splitTextToWords(title1);
    117         List<String> wordList2 = splitTextToWords(title2);
    118         if (wordList1.isEmpty() || wordList2.isEmpty()) {
    119             return 0;
    120         }
    121         int maxMatchedWordSeqLen = calculateMaximumMatchedWordSequenceLength(
    122                 wordList1, wordList2);
    123 
    124         // F-measure score
    125         double precision = (double) maxMatchedWordSeqLen / wordList1.size();
    126         double recall = (double) maxMatchedWordSeqLen / wordList2.size();
    127         return 2.0 * precision * recall / (precision + recall);
    128     }
    129 
    130     @VisibleForTesting
    131     static int calculateMaximumMatchedWordSequenceLength(List<String> toSearchWords,
    132             List<String> toMatchWords) {
    133         int[] matchedWordSeqLen = new int[toMatchWords.size()];
    134         int maxMatchedWordSeqLen = 0;
    135         for (String word : toSearchWords) {
    136             for (int j = toMatchWords.size() - 1; j >= 0; --j) {
    137                 if (word.equals(toMatchWords.get(j))) {
    138                     matchedWordSeqLen[j] = j > 0 ? matchedWordSeqLen[j - 1] + 1 : 1;
    139                 } else {
    140                     maxMatchedWordSeqLen = Math.max(maxMatchedWordSeqLen, matchedWordSeqLen[j]);
    141                     matchedWordSeqLen[j] = 0;
    142                 }
    143             }
    144         }
    145         for (int len : matchedWordSeqLen) {
    146             maxMatchedWordSeqLen = Math.max(maxMatchedWordSeqLen, len);
    147         }
    148 
    149         return maxMatchedWordSeqLen;
    150     }
    151 
    152     private static double calculateTimeMatchScore(Program p1, Program p2) {
    153         ProgramTime t1 = ProgramTime.createFromProgram(p1);
    154         ProgramTime t2 = ProgramTime.createFromProgram(p2);
    155 
    156         double dupTimeScore = calculateOverlappedIntervalScore(t1, t2);
    157 
    158         // F-measure score
    159         double precision = dupTimeScore / (t1.endTimeOfDayInSec - t1.startTimeOfDayInSec);
    160         double recall = dupTimeScore / (t2.endTimeOfDayInSec - t2.startTimeOfDayInSec);
    161         return 2.0 * precision * recall / (precision + recall);
    162     }
    163 
    164     @VisibleForTesting
    165     static double calculateOverlappedIntervalScore(ProgramTime t1, ProgramTime t2) {
    166         if (t1.dayChanged && !t2.dayChanged) {
    167             // Swap two values.
    168             return calculateOverlappedIntervalScore(t2, t1);
    169         }
    170 
    171         boolean sameDay = false;
    172         // Handle cases like (00:00 - 02:00) - (01:00 - 03:00) or (22:00 - 25:00) - (23:00 - 26:00).
    173         double score = Math.max(0, Math.min(t1.endTimeOfDayInSec, t2.endTimeOfDayInSec)
    174                 - Math.max(t1.startTimeOfDayInSec, t2.startTimeOfDayInSec));
    175         if (score > 0) {
    176             sameDay = (t1.weekDay == t2.weekDay);
    177         } else if (t1.dayChanged != t2.dayChanged) {
    178             // To handle cases like t1 : (00:00 - 01:00) and t2 : (23:00 - 25:00).
    179             score = Math.max(0, Math.min(t1.endTimeOfDayInSec, t2.endTimeOfDayInSec - 24 * 60 * 60)
    180                     - t1.startTimeOfDayInSec);
    181             // Same day if next day of t2's start day equals to t1's start day. (1 <= weekDay <= 7)
    182             sameDay = (t1.weekDay == ((t2.weekDay % 7) + 1));
    183         }
    184 
    185         if (!sameDay) {
    186             score *= MULTIPLIER_FOR_UNMATCHED_DAY_OF_WEEK;
    187         }
    188         return score;
    189     }
    190 
    191     private static double calculateWatchDurationScore(Program program, long durationMs) {
    192         return (double) durationMs
    193                 / (program.getEndTimeUtcMillis() - program.getStartTimeUtcMillis());
    194     }
    195 
    196     @VisibleForTesting
    197     static int getTimeOfDayInSec(Calendar time) {
    198         return time.get(Calendar.HOUR_OF_DAY) * 60 * 60
    199                 + time.get(Calendar.MINUTE) * 60
    200                 + time.get(Calendar.SECOND);
    201     }
    202 
    203     @VisibleForTesting
    204     static List<String> splitTextToWords(String text) {
    205         List<String> wordList = new ArrayList<>();
    206         BreakIterator boundary = BreakIterator.getWordInstance();
    207         boundary.setText(text);
    208         int start = boundary.first();
    209         for (int end = boundary.next(); end != BreakIterator.DONE;
    210                 start = end, end = boundary.next()) {
    211             String word = text.substring(start, end);
    212             if (Character.isLetterOrDigit(word.charAt(0))) {
    213                 wordList.add(word);
    214             }
    215         }
    216         return wordList;
    217     }
    218 
    219     @VisibleForTesting
    220     static class ProgramTime {
    221         final int startTimeOfDayInSec;
    222         final int endTimeOfDayInSec;
    223         final int weekDay;
    224         final boolean dayChanged;
    225 
    226         public static ProgramTime createFromProgram(Program p) {
    227             Calendar time = Calendar.getInstance();
    228 
    229             time.setTimeInMillis(p.getStartTimeUtcMillis());
    230             int weekDay = time.get(Calendar.DAY_OF_WEEK);
    231             int startTimeOfDayInSec = getTimeOfDayInSec(time);
    232 
    233             time.setTimeInMillis(p.getEndTimeUtcMillis());
    234             boolean dayChanged = (weekDay != time.get(Calendar.DAY_OF_WEEK));
    235             // Set maximum program duration time to 12 hours.
    236             int endTimeOfDayInSec = startTimeOfDayInSec +
    237                     (int) Math.min(p.getEndTimeUtcMillis() - p.getStartTimeUtcMillis(),
    238                             TimeUnit.HOURS.toMillis(12)) / 1000;
    239 
    240             return new ProgramTime(startTimeOfDayInSec, endTimeOfDayInSec, weekDay, dayChanged);
    241         }
    242 
    243         private ProgramTime(int startTimeOfDayInSec, int endTimeOfDayInSec, int weekDay,
    244                 boolean dayChanged) {
    245             this.startTimeOfDayInSec = startTimeOfDayInSec;
    246             this.endTimeOfDayInSec = endTimeOfDayInSec;
    247             this.weekDay = weekDay;
    248             this.dayChanged = dayChanged;
    249         }
    250     }
    251 }
    252