Crates.io | aligner |
lib.rs | aligner |
version | 0.1.6 |
source | src |
created_at | 2017-02-17 19:08:06.994553 |
updated_at | 2017-09-03 18:33:50.064725 |
description | Automatically corrects subtitle timings given a second correct subtitle |
homepage | |
repository | https://github.com/kaegi/aligner |
max_upload_size | |
id | 8559 |
size | 869,979 |
aligner
is a Rust library and command-line tool that corrects a subtitle given
a second "correct" subtitle. It will figure out offsets and where to
introduce or remove advertisement breaks to get the best alignment possible. It does not use
any language information so it even works for image based subtitles like VobSub.
The most basic command is:
$ aligner reference_subtitle.ssa incorrect_subtitle.srt output.srt
You can additionally adjust how much the algorithm tries to avoid introducing or removing a break:
# split-penalty is a value between 0 and 100
$ aligner reference_subtitle.ssa incorrect_subtitle.srt output.srt --split-penalty 2.6
Currently supported are .srt
, .ssa
/.ass
and .idx
files.
Install Rust and Cargo then run:
# this will create ~/.cargo/bin/aligner
$ cargo install aligner
Add this to your Cargo.toml
:
[dependencies]
aligner = "~0.1.6"
At the core of the algorithm is the rating of an alignment. For each pair of subtitles (one from the reference subtitle on from the incorrect subtitle) the rating is
overlapping_time(refsub, incsub) / max(length(refsub), length(incsub))
The maximum of this rating is 1, if and only if refsub = incsub
. The total rating of an alignment is (for the most part) the sum of all ratings of all possible pairs. By moving the incsubs
around, we might get a better alignment. As a basic constraint, the order of the incsubs
will not be changed. So if we have to consecutive subtitles start(incsubN) <= start(incsubN+1)
, the corrected 'incsubs
will still have start('incsubN) <= start('incsubN+1)
.
If only this formula was used, the algorithm will probably create different offsets for each subtitle line. To avoid that, we have to use split_penalty
value. For each consecutive subtitles where start(incsubN) - start(incsubN+1) = start('incsubN) - start('incsubN+1)
we add another split_penalty
to the total rating. That way, with every extra split we lose split_penalty
of rating.
This algorithm computes the alignment which yields the maximum of all possible ratings. The algorithm is powered by the principle of dynamic programming.
To simplify the problem, we assume start(sub)
is the start timestamp in milliseconds of a subtitle line sub
and 0 <= start(sub)
is true. Let's say get_rating(t, n)
computes the best rating/alignment for the first n
incorrect subtitle lines with the additional constraint 0 <= start(sub) <= t
for each of these n
subtitles.
Of course we can now simply set get_rating(t, 0) = 0
because if we have no incorrect subtitles to align, we have a rating of zero (independent of t
).
Now we handle the case get_rating(0, 1)
. We can simply compute the overlapping rating (where the first incorrect subtitle starts at the "zero timepoint") with every reference subtitle and add up these values. With get_rating(1, 1)
things get interesting. We can either have start(sub) = 0
or start(sub) = 1
. Fortunaly we already have get_rating(0, 1)
, so we only need the rating where start(sub) = 1
. This can be computed by adding up all overlapping ratings. Similarly we can compute get_rating(2, 1)
by taking the maximum of get_rating(1, 1)
and the rating where start(sub) = 2
. In this vein we can create get_rating(t+1, 1)
from get_rating(t, 1)
. We can also speed up computing the overlapping rating, because the subtitle line will only be shifted by 1ms from start(sub) = t
to start(sub) = t + 1
. The subtitle will lose the rating for the segment [t, t + 1]
and gain the overlapping rating for the segment [t + length(sub), t + 1 + length(sub)]
on the other side. By creating a lookup-table for reference subtitles for every t
this process has a runtime of O(1)
.
When do we stop? Well, the rating won't change anymore if t
gets big. At the latest when start(sub)
is be greater than any of the reference subtitle lines, because after that the overlapping rating will always be zero. Let's call max_t
the timepoint where all incorrect subtitles have been moved behind the reference subtitles. The best total rating is then get_rating(max_t, number_of_incorrect_subtitles)
.
Now we have all get_rating(0, 1)
to get_rating(max_t, 1)
. To compute get_rating(0, 2)
, which means that 0 <= start(sub0) <= 0
and 0 <= start(sub1) <= 0
. We already have the rating for sub0
in form of get_rating(0, 1)
. We only need to add the overlapping rating for sub1
. To get get_rating(1, 2)
we can either use get_rating(0, 2)
(we leave sub1
where it is), or move start(sub1)
to 1, which allows start(sub0)
to be in 0 <= start(sub0) <= start(sub1) = 1
. The best rating for sub0
for that range has been computed with get_rating(1, 1)
, we only need to add the overlapping rating for start(sub1) == 1
. We proceed similarly to get get_rating(t+1, 2)
: leave the sub1
like it was for get_rating(t,2)
or reposition the subtitle to start(sub1) == t+1
and use get_rating(t+1,1) + overlapping_rating(sub1,t+1)
.
With the same principle we proceed with subN
:
get_rating(0, n) = get_rating(0, n - 1) + overlapping_rating(subN, 0)
get_rating(t+1, n)
the maximum of
get_rating(t, n)
which means "leaving subN
" and
get_rating(t+1, n-1) + overlapping_rating(t+1, subN)
which means repositioning the subN
Until now we didn't use the split_penalty
. We need to add the split penalty when start(subN) - start(subN+1)
is a specific value (the original distance diff(N)
). The trick here is seeing that we only need to consider the "repostion choice". The only time get_rating(_, n-1)
is consulted after the inital phase is when subN
gets repositioned. subN
will then start at t+1
and we consult get_rating(t+1, n-1)
. So if subN-1
were positioned at t+1-diff(N-1)
for get_rating(t+1-diff(N-1), n-1)
we'd be able to get the split_penalty
. This is exactly the thing we will do when we are in a phase n
: We will not only have the "leave choice" or "reposition choice" but also the "nosplit choice". If we compute get_rating(t, n)
, we can also compare the two other values with get_rating(t-diffN, n-1) + overlapping_rating(t-diffN, subN) + split_penalty
. The get_rating(t-diffN, n-1) + overlapping_rating(t-diffN, subN)
is again the best rating where start(subN) = t-diffN
. We are allowed to add the split_penalty
because in the next phase n+1
, subN+1
will start at t
when get_rating(t-diffN, n)
is looked up. So the final rating algorithm is:
get_rating(t, 0)
with 0get_rating(0, n) = get_rating(0, n - 1) + overlapping_rating(subN, 0)
get_rating(t+1, n)
the maximum of
get_rating(t, n)
which means "leaving subN
" and
get_rating(t+1, n-1) + overlapping_rating(t+1, subN)
which means repositioning the subN
and
get_rating(t+1-diffN, n-1) + overlapping_rating(t+1-diffN, subN) + split_penalty
which means doing a nosplit-repositioning for subN
To get the final alignment, we save for each phase n
and t+1
where subN
was positioned (can be t+1
, t+1-diffN
or the previous position). If we look up that value for n = number_of_incorrect_subtitles
and t = max_t
, we know where the last subtitles subN
has to be. We then know start(subN)
. The best alignment of all previous subtitles is then computed with get_rating(start(subN), n-1)
. So we look up the position for subN-1
in that table with n' = n-1
and t' = start(subN)
. That way we get all corrected positions of all incorrect subtitles and are done!
Though this algorithm works (and was implemented in one of the early versions of aligner
) it is neither fast nor space-efficient. Let's take a 45 minutes = 2700000 milliseconds < max_t
subtitle file which has about n = 900 subtitles
(these are realistic values). We build a table of max_t * n = 2430000000
entries. We can discard the ratings of the phase n-1
after phase n
, but we always need to store the positions of the subtitle subN
. Let's assume we need 4 bytes to store them: we then have a table of 2430000000 * 4 bytes = 9720000000 bytes = 9 GB
of data in RAM!!! Even filling the table with zeros might take some noticeable time. But as it turns out we can compress that table in under 2 MB (most of the time; probably the best compression I've ever seen) with delta encoding
. The empirical foundation is that the choices almost never change from one t
to t+1
(about 10 to 1000 times for one phase). If we always take the
t+1
for every t+1
(rise by 1)t+1-diffN
(rise by 1)t - 1
(constant)So if we store values in a (start, delta, length)
tuple, where the first uncompressed value is start + 0 * delta
, the second is start + 1 * delta
, the third is start + 2 * delta
, ..., the last is start + length * delta
, we can compress an entire phase into a few bytes. The same thing is applicable to the ratings. Without going into details: if we take the overlapping rating of a incorrect subtitle to a reference subtitle and "move" the incorrect subtitle from the far left to the far right we will have five segments of compressed values (first the rating will be zero, then rise linearly, then be constant, then fall linearly, then be zero again). The comparisons/choices can then be done for rating segments instead of single t
. This yields a speedup of at least one order of magnitude.