Sorting movie search results by similarity

Question

I want to sort "movie search results" to get most probable movie that match "search".

Input example:

CARS.2.2011.720P.AC3.mkv

I have a NameMatcher class which extract "title" and "year" from file name.

Search string: cars 2
Search year : 2011

Results come from many websites like TMDB, Rotten Tomatoes, ... and much more. Only one website (API) is used for search, so the sort is only on what API return.

Info:

• "search year" can be null (0)
• "search string" can have some words that it's not a part of movie title (it's rare, NameMatcher works really well)
• "result year" can be null (0)
• "result string" can be totally different from search, for example if there is only original title and your search is in your language. In this case we need to keep website order
• A movie with an image have more chance to be what the user looking for.
• Year can be different, movies release year are not the same in all countries, I think "year + 1" and "year - 1" is sufficient. There are some movies that have like "10 years" apart but I guess it's difficult to take this into account.
• This sort is used for other media (tvshow, ..) but it doesn't matter, for the moment I'm only focusing on movies.

Current sort:

I use Levenshtein (I think Damerau-Levenshtein is not better for this case) and Jaro Winkler algorithm to get similarity between "search string" and "result string".

I added a "bonus" with arbitrary values if year is almost the same (year +- 1) and if "result" has an image (A film with an image is more likely to be what we are looking), then I get an Integer called "sim" to perform sort.

Similarity: [0-200] (100 for Levenshtein + 100 for Jaro Winkler)
Bonus: [0-60] (0,10,50,60)

For perfect match: 260 -> similarity (200) + year bonus (50) + image bonus (10)

Next I get the best "sim" and if "sim" is greater than a threshold I sort the list. The last part are here because I do not have any database,... so my sort can be worst than current order in some case (E.g: "search string" with bad words, or "result string" in another language).

UI sort result example: (tmdb sort to compare)

Current code:

public static <T extends ISort> void sortAccurate(List<T> list, String str, int year, int threshold) {

  final String toCompare = StringUtils.normaliseClean(str);
  Map<Integer, List<T>> values = new TreeMap<Integer, List<T>>(new IntegerDescending());
  for (T object : list) {

    // If year is (almost) the same, we add a "bonus"
    int bonus = 0;
    if (year >= 1900 && year <= Calendar.getInstance().get(Calendar.YEAR)) {
      final int oYear = object.getYear();
      if (year == oYear) {
        bonus = 50;
      } else if (oYear == (year - 1) || oYear == (year + 1)) {
        bonus = 25;
      }
    }

    // if there is an image we add a "bonus"
    if (object.hasImage()) {
      bonus += 10;
    }

    // Get best similarity between title and orig title
    int sim = getSimilarity(toCompare, object.getName(), bonus);
    if (object.getOriginalName() != null && object.getName().equals(object.getOriginalName()) {
      sim = Math.max(sim, getSimilarity(toCompare, object.getOriginalName(), bonus));
    }
    sim += bonus;

    // We use a list cause 2 (or more) can have the same "sim" number
    List<T> listObj = values.get(sim);
    if (listObj == null) {
      listObj = new ArrayList<T>();
    }

    listObj.add(object);
    values.put(sim, listObj);
  }

  // Get the higher "sim number"
  int maxSim = 0;
  for (Integer sim : values.keySet()) {
    maxSim = sim;
    break;
  }

  // If "sim number" is greater than threshold we sort the list
  if (maxSim >= threshold) {
    list.clear();
    for (List<T> olist : values.values()) {
      list.addAll(olist);
    }
  }
}

Similarity:

private static int getSimilarity(String search, String str) {
  String toCompare = StringUtils.normaliseClean(str);// Clean the string to get best result (search is already cleaned)
  AbstractStringMetric algorithm;

  Float res = 0.0F;
  algorithm = new JaroWinkler();
  res += algorithm.getSimilarity(search, toCompare);// Return a float ([0 - 1] , 1 => exact match)

  algorithm = new Levenshtein();
  res += algorithm.getSimilarity(search, toCompare);// Return a float ([0 - 1] , 1 => exact match)

  return Math.round((res) * 100);
}

This "algorithm" get correct result even if it was written quickly.

How can I improve this sort? I mean, maybe there is an algorithm that can help me to improve this "dirty sort", or someone have an idea for a better sort. Any suggestion to improve sort results are welcome.

This "dirty sort" works well but I think it can be more "smart" but I have no idea how to make it better.

Note: Results list List<T> list is small (never more than 50), so if the sort algorithm is heavy it's not a problem, and there is already a cache on it.

Note2:

If you've got only "little" improvement, this is fine for me.

For example, if two results (or more) have the same "sim" number, maybe a small algorithm can be added here to define which is the best. Or maybe improve "bonus" part with something more stronger than "random values".

The code above is just to understand, mistakes, ... doesn't matter. The main goal of this question is about similarity algorithms which exist and can be useful in a case like that or either a different/better "scoring system". Answer can be generic and not specific for this case (I will adapt it), it can be math, pseudo-code (or code), algorithm or either a suggestion (e.g: don't use levenshtein distance but instead this because ...).

I'm sure this can be really improved, current algorithm is more a "random stuff" than an algorithm thought/thoughtful.

Answer 1

Use a Comparator to sort

The way you implemented the sorting is really convoluted. There is a much more straightforward approach: use a Comparator!

Something along the lines of this:

static class MovieComparator implements Comparator<MovieInfo> {
    private final int targetYear;
    private final int threshold;

    MovieComparator(int targetYear, int threshold) {
        this.targetYear = targetYear;
        this.threshold = threshold;
    }

    @Override
    public int compare(MovieInfo o1, MovieInfo o2) {
        return -Integer.compare(getSimilarity(o1), getSimilarity(o2));
    }

    private int getSimilarity(MovieInfo movieInfo) {
        // TODO
        return 0;
    }
}

Then, given a List of movies, you could sort them with:

Collections.sort(movies, new MovieComparator(....));

Don't Calendar.getInstance in a loop

The Calendar.getInstance call actually creates a new Calendar instance every time. This can be expensive. Don't do this in a loop, get a Calendar once and reuse it.

Even better, if you only need the year, then get just the year once and reuse it.

Simplify

This can be done simpler:

        List<T> listObj = values.get(sim);
        if (listObj == null) {
            listObj = new ArrayList<T>();
        }

        listObj.add(object);
        values.put(sim, listObj);

You can move values inside the if statement, because if it's not null, then the list is already inside the map. Like this:

        List<T> listObj = values.get(sim);
        if (listObj == null) {
            listObj = new ArrayList<T>();
            values.put(sim, listObj);
        }

        listObj.add(object);

---

In this code:

new TreeMap<Integer, List<T>>(new IntegerDescending());

You didn't include the source code of IntegerDescending, but if it is what it sounds like, then this will be equivalent, no need for a custom class:

new TreeMap<Integer, List<T>>(Collections.reverseOrder());

---

This condition:

if (oYear == (year - 1) || oYear == (year + 1)) {

Would be simpler as:

if (Math.abs(oYear - year) == 1) {

Actually you could replace the if-else chain with this:

final int oYear = object.getYear();
int yearDiff = Math.abs(oYear - year);
if (yearDiff < 2) {
    bonus = 50 / (yearDiff + 1);
}

Answer 2

I'll leave the efficient sorting algorithms to the experts. I like your approach of using a descending TreeMap.

for (Integer sim : values.keySet()) {
    maxSim = sim;
    break;
  }

This bit stood out to me. A for loop that doesn't actually loop is considered a bad practice. You can call maxSim = values.keySet().iterator().next(); instead. If values is allowed to be empty, then add an isEmpty check before getting .iterator().next().

The common convention is to use camelCase for variable names. It seems most of your code follows this but in your sortAccurate method tocompare should be toCompare.

If you can use Java 7 or later (strongly recommended), and unless you're using an anonymous inner class, you can employ the diamond operator. So instead of:

Map<Integer, List<T>> values = new TreeMap<Integer, List<T>>(new IntegerDescending());

You can type just:

Map<Integer, List<T>> values = new TreeMap<>(new IntegerDescending());

Answer 3

This appears to be an error (the same getSimilarity() call twice)

int sim = getSimilarity(tocompare, object.getName(), bonus);
if (object.getOriginalName() != null && !ObjectUtils.compare(object.getName(), object.getOriginalName())) {
  sim = Math.max(sim, getSimilarity(tocompare, object.getName(), bonus));
}