2

What algorithm does a video player use to find the subtitles to show at any given time?

I'm building a video player that displays some notes on different times over a video. Each note has a starting time and an ending time, just like subtitles.

I'm having issues coming up with an algorithm to find the all the "notes" while the video is playing, obviously I want it to be as efficient as possible, and I figured that subtitles work basically the same(If they are ordered by the "start time").

I'm building it with Javascript since the player is intended to work in the browser, and this makes it even more important for it to be performant.

I thought about using a Binary Tree, but I don't think it will work, because a Binary Tree compares against one parameter, and I'm not sure it will be the best option after I modify it.

Robert Harvey
  • 198,589
  • 55
  • 464
  • 673
Samuel E.
  • 203
  • 2
  • 7

3 Answers3

6

Unless your subtitles overlap, the algorithm is pretty simple:

  • keep the subtitles in an ordered list.
  • in your event loop, determine the current time
  • if it is larger than the end time of the current subtitle, unpost it
  • if it is larger than the start of the first subtitle in the list, post it and remove it from the list.

Do you expect anything more complicated in your subtitles than a simple sequence of successive items?

Kilian Foth
  • 107,706
  • 45
  • 295
  • 310
  • Yes, overlapping subtitles must work, that's the main issue(it might be easier than I think, but I have tunnel vision from working on it all day). – Samuel E. Nov 22 '18 at 16:24
  • And can you post multiple items simultaneously? Then it's just a matter of using `while` rather than `if` in the algorithm above. – Kilian Foth Nov 22 '18 at 17:23
  • An interesting related question might be: how to efficiently find the subtitles to show when jumping into the video. The naive implementation would scan through all subtitles until an item is found whose start time is before the current time and whose end time is later than the current time. To get all matches (there may be overlapping subtitles) you would have to proceed until an item is found whose start time is later than the current time. Indexing subtitles into a binary tree might improve search time. Is there a better strategy? – Hero Wanders Nov 23 '18 at 10:18
  • @HeroWanders There's no need to create a specially optimized structure for this. A sorted list allows searching in logarithmic time, which is plenty fast enough for the problem dimension. After all, you'll never have millions of subtitle items in one stream. – Kilian Foth Nov 23 '18 at 11:00
4

Subtitles are ordered: the ones which appear later in the video are stored after the ones which appear earlier.

Therefore, use a simple cursor which points to the next subtitle to show.

In order to make the subtitles disappear (while ensuring that overlapping is possible), either set individual timeouts for every subtitle being shown, or use a second cursor. The first approach is much more straightforward in JavaScript.

Arseni Mourzenko
  • 134,780
  • 31
  • 343
  • 513
  • So overlapping subtitles will still show up, the only problem is removing them? – Samuel E. Nov 22 '18 at 16:27
  • What's the problem with it? When you're displaying an item, you know its start and end time, so you can determine its duration. Had on that, you set a timer for that specific item. Given that you'll rarely show more than two items at once, you'll have one or two, rarely three timers at the same time, which won't have a very big impact on the performance. – Arseni Mourzenko Nov 22 '18 at 18:09
  • Thank you for your answer, I really appreciate it, you and Kilian both gave the same algorithm but he answered first(I just have to decide, and its the only difference between the answers basically), so I marked his as the accepted answer, but thank you very much! – Samuel E. Nov 22 '18 at 18:13
0

It depends on the player you use, but the vast majority can handle this type of "timed" event through cue point, you should aim your thinking towards this path. Basically it just map a relative time event with the time of that video.

Pierre Criulanscy
  • 236
  • 1
  • 4