Я упорядочил списки чисел (например, позиции штрих-кода, спектральные линии), которые я пытаюсь сравнить по сходству. В идеале я хотел бы сравнить два списка, чтобы получить значение от 1,0 (совпадение), постепенно уменьшающееся до 0.
Списки могут быть смещены на произвольную величину, и это не должно ухудшать соответствие. Различия между соседними объектами являются наиболее применимой характеристикой.
Из-за шума в системе некоторые элементы могут отсутствовать (в качестве альтернативы могут быть вставлены дополнительные элементы, в зависимости от точки зрения).
Значения diff могут быть переупорядочены.
Значения различий можно масштабировать.
Можно применить несколько приведенных выше преобразований, и каждое из них должно пропорционально уменьшить сходство.
Вот некоторые тестовые данные:
# deltas
d = [100+(i*10) for i in xrange(10)] # [100, 110, 120, 130, 140, 150, 160, 170, 180, 190]
d_swap = d[:4] + [d[5]] + [d[4]] + d[6:] # [100, 110, 120, 130, 150, 140, 160, 170, 180, 190]
# absolutes
a = [1000+j for j in [0]+[sum(d[:i+1]) for i in xrange(len(d))]] # [1000, 1100, 1210, 1330, 1460, 1600, 1750, 1910, 2080, 2260, 2450]
a_offs = [i+3000 for i in a] # [4000, 4100, 4210, 4330, 4460, 4600, 4750, 4910, 5080, 5260, 5450]
a_rm = a[:2] + a[3:] # [1000, 1100, 1330, 1460, 1600, 1750, 1910, 2080, 2260, 2450]
a_add = a[:7] + [(a[6]+a[7])/2] + a[7:] # [1000, 1100, 1210, 1330, 1460, 1600, 1750, 1830, 1910, 2080, 2260, 2450]
a_swap = [1000+j for j in [0]+[sum(d_swap[:i+1]) for i in xrange(len(d_swap))]] # [1000, 1100, 1210, 1330, 1460, 1610, 1750, 1910, 2080, 2260, 2450]
a_stretch = [1000+j for j in [0]+[int(sum(d[:i+1])*1.1) for i in xrange(len(d))]] # [1000, 1110, 1231, 1363, 1506, 1660, 1825, 2001, 2188, 2386, 2595]
a_squeeze = [1000+j for j in [0]+[int(sum(d[:i+1])*0.9) for i in xrange(len(d))]] # [1000, 1090, 1189, 1297, 1414, 1540, 1675, 1819, 1972, 2134, 2305]
Сим (a, a_offs) должен быть равен 1,0, поскольку смещение не считается штрафом.
Sim (a, a_rm) и Sim (a, a_add) должны быть около 0,91, потому что 10 из 11 или 11 из 12 совпадают.
Значение Sim (a, a_swap) должно быть около 0,96, потому что один различий не на своем месте (возможно, с дополнительным штрафом, основанным на расстоянии, если он перемещен более чем на одну позицию).
Sim (a, a_stretch) и Sim (a, a_squeeze) должны быть около 0,9, потому что различия были масштабированы примерно на 1 часть в 10.
Я думаю о чем-то вроде difflib.SequenceMatcher, но это работает для числовых значений с размытостью вместо жестко сравниваемых хеш-логов. Также необходимо сохранить некоторую осведомленность о соотношении diff (первая производная).
Кажется, это проблема динамического программирования, но я не могу понять, как построить соответствующую метрику стоимости.