Два сигнала с эквивалентными функциями, расположенными в том же порядке, могут казаться очень отличающимися из-за различий в длительности их разделов. edr
искажает эту длительность так, чтобы соответствующие функции появились в том же местоположении на общей оси времени, таким образом подсветив общие черты между сигналами. Критерий, используемый, чтобы выполнить искажение, спроектирован, чтобы быть устойчивым к выбросам.
Рассмотрите два K - размерные сигналы
и
которые имеют M и выборки N, соответственно. Учитывая dmn (X, Y), расстояние между m th выборка X и n th выборка Y задано в metric
, edr
функционируйте расширяет X и Y на единый набор моментов, таким образом, что расстояние редактирования между сигналами является наименьшим.
Учитывая ε, вещественное число, которое является допуском, заданным в tol
, объявите, что m th выборка X и n th выборка Y соответствует если dmn (X, Y) < ε. Если две выборки, m и n, не соответствуют, можно заставить их соответствовать любым из трех способов:
Удалите m из первого сигнала, такой как тогда, когда следующая выборка действительно совпадает с n. Это удаление эквивалентно добавлению m к второму сигналу и получению двух последовательных соответствий.
Удлините первый сигнал путем добавления в положении выборки, которая совпадает с n и остальной частью перемещения выборок одним местоположением. Это сложение эквивалентно удалению несопоставленного n от второго сигнала.
Замените m с n в первом сигнале, или, эквивалентно, удалите и m и n.
Расстояние редактирования является общим количеством этих операций, которые необходимы, чтобы заставить два сигнала соответствовать. Этот номер не уникален. Чтобы вычислить наименьшее расстояние редактирования между X и Y, запустите с этих фактов:
Два пустых сигнала имеют нулевое расстояние между ними.
Расстоянием между пустым сигналом и сигналом с выборками L является L, потому что это - количество выборок, которые должны быть добавлены к пустому сигналу восстановить другой. Эквивалентно, L является количеством выборок, которые должны быть удалены из L - демонстрационный сигнал опорожнить его.
Создайте (M + 1) (N + 1) матрица, D, такой что:
D 1,1 = 0.
D m, 1 = m – 1 для m = 2, …, M + 1.
D 1, n = n – 1 для n = 2, …, N + 1.
Для m, n > 1,
Наименьшим расстоянием редактирования между X и Y является затем D M +1, N +1.
Деформирующийся путь через D, который приводит к этому наименьшему расстоянию редактирования, параметрируется двумя последовательностями той же длины, ix
и iy
, и комбинация “шахматного короля” перемещения:
Вертикальные перемещения: (m, n) , (m + 1, n) соответствует удалению выборки от X или добавление выборки к Y. Каждое перемещение увеличивает расстояние редактирования на 1.
Горизонтальные перемещения: (m, n) , (m, n + 1) соответствует удалению выборки от Y или добавления выборки к X. Каждое перемещение увеличивает расстояние редактирования на 1.
Диагональные перемещения: (m, n) , (m + 1, n + 1) соответствует соответствию, если dm,n (X, Y) ≤ ε или соответствует удалению одной выборки от каждого сигнала если dm,n (X, Y) > ε. Соответствия не увеличивают расстояние. Удаления увеличивают его на 1.
Эта структура гарантирует, что любой приемлемый путь выравнивает полные сигналы, не пропускает выборки и не повторяет функции сигнала. Кроме того, привлекательный путь запускается близко к диагональной линии, расширенной между d 1,1 (X, Y) и dM,N (X, Y). Это дополнительное ограничение, настроенное maxsamp
аргумент, гарантирует, что деформирование сравнивает разделы подобной длины.
Штраф за то, что заставили две выборки соответствовать независим от различия в значении между выборками. Две выборки, которые отличаются немного больше, чем допуск, подвергаются тому же штрафу как две выборки, которые заметно отличаются. По этой причине расстояние редактирования не затронуто выбросами. С другой стороны повторение выборок, чтобы выровнять два сигнала имеет стоимость, которая не имеет место с динамической трансформацией временной шкалы.