教育署署长
实信号的编辑距离。
库::`工程师`
语法
函数调用
-
_=edr([参数:x],[参数:y],[参数:maxsamp])— 限制插入操作，使转换路径保持在[参数:maxsamp]之间的直线计数[参数:x]和[参数:y]. 此语法返回前面语法的任何输出参数。
争论
输入参数
# 公制 — 距离度量
+
"欧几里德" (默认)| "绝对" | "平方" | "symmkl"
Details
设置为值之一的距离度量: "欧几里德", "绝对", "平方" 或 "symmkl". 如果 和 是 -测量信号，然后度量设置 -之间的距离 -m倒计时 和 -m倒计时 . 了解更多关于 请参阅部分 动态时间转换。
-
"欧几里德"-差异平方和的根，也称为欧几里德度量或 : -
"绝对"-绝对差异的总和，也称为城市街区的距离，曼哈顿度量，出租车度量，或 : -
"平方"-欧几里德度量的平方，由差的平方和组成: -
"symmkl"-对称Kullback-Leibler度量。 此度量仅适用于实数和正数。 和 :
例子：
具有不同频率的余弦和具有异常值的正弦之间的编辑距离
Details
我们将产生两个实信号：一个频率变化的余弦和一个正弦。 让我们为每个信号添加一个明显的下拉部分。 让我们在图表上绘制信号。
import EngeeDSP.Functions: edr
x = cos.(2 * pi * (3 * (1:1000) / 1000) .^ 2)
y = cos.(2 * pi * 9 * (1:399) / 400)
x[400:410] .= 7
y[100:115] .= 7
tol = 0.1
p1 = plot(1:length(x), x, linewidth=2, color=:blue)
plot!(1:length(y), y, linewidth=2, color=:red, linestyle=:dash, legend=false)
title!("Original signals")
我们变换信号,使它们之间的距离最小. 指定容差 0.1. 让我们绘制变换后对齐的信号。
d,x1,y1 = edr(x, y, tol)
x_aligned = x[x1]
y_aligned = y[y1]
p2 = plot(1:length(x_aligned), x_aligned, linewidth=2, color=:blue)
plot!(1:length(y_aligned), y_aligned, linewidth=2, color=:red, linestyle=:dash, legend=false)
title!("Aligned signals")
编辑距离和转换路径
Details
我们将产生两个信号，由两个不同的波峰组成，由不同长度的波谷分开。 让我们绘制信号。
x = [0, 1, 0, 1, 0] * 0.95
plot(x)
y = [0, 1, 0, 0, 0, 0, 0, 0, 1, 0] * 0.95
plot(y)
计算信号之间的编辑距离。 让我们设置一个小公差，以便只有相同的样本匹配。
tol = 0.1
d, x1, y1 = edr(x, y, tol)
x_aligned = x[x1]
y_aligned = y[y1]
plot(1:length(x_aligned), x_aligned, linewidth=2, color=:blue)
plot!(1:length(y_aligned), y_aligned, linewidth=2, color=:red, linestyle=:dash, legend=false)
title!("Aligned signals")
信号之间的距离为 7. 要对齐它们，您需要将七个中心零从 y 或者将七个零添加到 x.
计算矩阵 D，其右下元素对应于编辑距离。 定义 D 在真实信号编辑距离部分中给出。
cnd = (abs(x .- y')) .> tol;
D = zeros(length(x)+1, length(y)+1)
D[1, 2:end] = 1:length(y)
D[2:end, 1] = 1:length(x)
for h = 2:(length(x)+1)
for k = 2:(length(y)+1)
D[h, k] = min(D[h-1, k]+1, D[h, k-1]+1, D[h-1, k-1]+cnd[h-1, k-1])
end
end
D6×11 Matrix{Float64}:
0.0 1.0 2.0 3.0 4.0 5.0 6.0 7.0 8.0 9.0 10.0
1.0 0.0 1.0 2.0 3.0 4.0 5.0 6.0 7.0 8.0 9.0
2.0 1.0 0.0 1.0 2.0 3.0 4.0 5.0 6.0 7.0 8.0
3.0 2.0 1.0 0.0 1.0 2.0 3.0 4.0 5.0 6.0 7.0
4.0 3.0 2.0 1.0 1.0 2.0 3.0 4.0 5.0 5.0 6.0
5.0 4.0 3.0 2.0 1.0 1.0 2.0 3.0 4.0 5.0 5.0
计算并显示对齐信号的转换路径。
d, i1, i2 = edr(x, y, tol)
E = zeros(length(x), length(y))
for k = 1:length(i1)
E[i1[k], i2[k]] = NaN
end
E5×10 Matrix{Float64}:
NaN 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0
0.0 NaN 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0
0.0 0.0 NaN NaN NaN NaN NaN NaN 0.0 0.0
0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 NaN 0.0
0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 NaN
此外
真实信号编辑距离
Details
具有相同顺序排列的等效特性的两个信号可能由于其段的持续时间的差异而看起来完全不同。 功能 edr 以这样一种方式变换这些持续时间，即相应的特征出现在公共时间轴上的相同位置，从而强调信号之间的相似性。 用于转换的标准被设计为耐排放。
考虑两个 -三维信号:
和
其中包含 和 分别计数。 当设置在 [参数：公制] 的距离值 之间 -m倒计时 和 -m倒计时 ，功能 edr 伸展运动 和 对于一组共同的时间点，以这样的方式使信号之间的编辑距离最小。
如果可用 ，一个实数，表示在 [参数:tol]，宣布 -倒计时 和 -倒计时 他们匹配，如果 . 如果有两个计数, 和 ，不匹配，它们可以通过三种方式中的任何一种进行匹配:
-
移走 从第一个信号，例如，当下一个倒计时重合 . 此删除相当于添加 到第二信号并接收两个连续匹配。
-
通过向对应于 ，并通过将剩余计数移位一个位置。 此添加相当于删除不匹配的一个。 从第二信号。
-
更换/更换 上 在第一个信号或，等价地，删除和 ，而 .
编辑距离是使两个信号匹配所需的操作总数。 这个数字不是唯一的。 间的最小可能编辑距离来计算 和 我们从以下事实出发:
-
两个空信号彼此之间具有零距离。
-
空信号与带 计数等于 因为这是为了恢复另一个信号需要向空信号添加多少样本。 同样地, —这是必须从信号中删除的样本数 倒数使其空。
创建矩阵 大小 上 以这样的方式
-
;
-
为 ;
-
为 ;
-
为
间的最小编辑距离 和 在这种情况下，它等于 .
通过的转换路径 ，导致这个最小的变换距离，由两个相同长度的序列参数化, ix 和 [参数：ixiy，iy]，并代表"棋王"的组合招式:
*垂直通道: 对应于从 或添加引用到 . 每次移动都会增加编辑距离 1;
*水平移动: 对应于从 或添加引用到 . 每次移动都会增加编辑距离 1;
*对角线移动: 匹配if ，或从每个信号中去除一个样本，如果 . 巧合不会增加距离。 删除会增加它 1.
这种结构确保任何可接受的路径对齐完整的信号，不跳过采样，并且不重复信号特征。 此外，所需的路径运行接近之间绘制的对角线 和 . 这是论证施加的额外限制 [参数:maxsamp]，确保在转换过程中比较相同长度的段。
由于两个样本重合而导致的劣化不依赖于样本之间的值差异。 两个差异略大于公差的计数与两个明显不同的计数受到相同的降级。 因此，编辑距离不受异常值的影响。 相反，重复采样以对齐两个信号有其成本，而动态时间转换则不是这种情况。
文学作品
-
Chen，Lei，M.Tamer Özsu和Vincent Oria。 "运动物体轨迹的鲁棒和快速相似性搜索。 第24届ACM国际数据管理会议（SIGMOD'05）的进程。_2005年，第491-502页。
-
Paliwal，K.K.，Anant Agarwal和Sarvajit S.Sinha。 "对Sakoe和Chiba的动态时间扭曲算法进行了修改，用于孤立的单词识别。"_Signal处理。_卷。 4，1982，第329-333页。
-
Sakoe，Hiroaki和Seibi Chiba。 "口语单词识别的动态规划算法优化。"_ieee®关于声学、语音和信号处理的事务。_卷。 ASSP-26，no.1，1978，第43-49页。