4
\$\begingroup\$

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)

UI search example

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.

\$\endgroup\$
4
\$\begingroup\$

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);
}
\$\endgroup\$
  • \$\begingroup\$ Thanks. I don't know about Collections.reverseOrder() and I like the "trick" with Math.abs(). Maybe my question is not clear, but I'm not asking on what is wrong in this code, just on "How can I improve sort results". The problem is to find or improve current algorithm to get a better sort results. About Comparator (maybe I'm wrong), I can't do it like this because I only sort if the maxSim is greater or equals to the threshold which is why I have a sortAccurate function instead. \$\endgroup\$ – Duffydake Mar 8 '15 at 11:59
  • \$\begingroup\$ It will work with Comparator. For the items below threshold, make getSimilarity return 0, so that they will be at the end of the list (the comparator example I gave will order from high to low). Strictly speaking, it's true that the solution will be more optimal if the items below threshold are excluded from the sort completely. But I don't think it will make a practical difference in your case. The solution will be elegant and nicely readable. As for "improving your sort results", I'm not sure what that means. A different scoring system maybe? This seems subjective, no one size fits all. \$\endgroup\$ – janos Mar 8 '15 at 12:09
  • \$\begingroup\$ Maybe your are right about comparator I will try it to see if it is "annoying" or not. About sort results I mean I'm trying to get the best results with only what I have (string, year and image), so yes a "different scoring system" is an option, but maybe there is an algorithm or math things than can be implemented that I don't know and yes this question is subjective, I just need help about what exist that can improve this (or a better approach), and I will adapt it for my need. \$\endgroup\$ – Duffydake Mar 8 '15 at 12:43
  • \$\begingroup\$ You mean, a better algorithm for checking what is "similar"? (Or ~ relevant) In that case, that's a very valid question, and I don't know the answer. I would probably just play with the parameters, trial and error, and see what gives the best results for a set of examples. If that's your biggest concern, you might want to make this point bold in your question to make it stand out more. But it's not really a good topic on Code Review. Programmers SE might be a better place to ask about algorithms. \$\endgroup\$ – janos Mar 8 '15 at 12:53
  • \$\begingroup\$ Yes it's that. I already played with parameters,.., and this is actually the best compromise that I found. I think "similar" can be improved but I'm lacking knowledge on this. I asked this on Stack Overflow and I was redirected here but like you said It's maybe not the good place. \$\endgroup\$ – Duffydake Mar 8 '15 at 13:01
4
\$\begingroup\$

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());
\$\endgroup\$
1
\$\begingroup\$

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));
}
\$\endgroup\$
  • \$\begingroup\$ Yes it is. The code is here just to understand, it's not the "real" code. I will change it in question and specify that the code doesn't matter. \$\endgroup\$ – Duffydake Mar 8 '15 at 14:15
  • \$\begingroup\$ Not so much an error as a pointless step, but you're right, it's not good. \$\endgroup\$ – janos Mar 8 '15 at 14:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.