在列表中查找具有不同縮放比例/模糊模式識別的子列表

Question

我有兩個列表，每個列表包含一組有序的數字。

一個列表很小（〜5-20個元素），另一個很大（~5000）。這些列表具有不同的「縮放比例」，並且可能在其中一個或另一個列表中缺少點。一般來說，大多數元素都將在這兩個列表中。

我正在尋找一種方法來檢測位置和兩個列表之間的「縮放」，使得兩個列表之間的距離最小。

一個例子是：

l1 = [ 100., 200., 400.] 
l2 = [ 350., 1000., 2003., 3996., 7500., 23000.] 

規模將是10和在L2 L1的位置是1。

列表10. * L1出現在位置1 L2內;列表的距離爲7（這取決於我選擇的度量，這裏我只是總結了所有元素之間的差異）。

我想知道是否有方法，例如，在模式識別，我可以使用（最好在Python中）。在我看來，在比較具有未知縮放因子的模式時，這可能是一個常見問題。但是我找不到描述我的問題的好關鍵字。

這樣做的應用是通過將測量光譜線與已知線位置的目錄進行比較來識別測量光譜線，並因此將非物理單位「檢測器上的像素」轉換爲實際波長。

原則上，我已經可以提供兩個列表的縮放因子的一個體面的猜測，但我想這不是必要的，因爲解決方案在大多數情況下應該是唯一的。

任何幫助表示讚賞，

朱利安

Answer 1

你試圖解決的問題有兩個度的優化。第一個是規模，第二個是指數。您的問題的廣義意義通常難以有效解決。但是有幾件事可以簡化計算。首先是兩套排序？其次，你是從第二個列表中尋找匹配第一個還是不匹配的連續集？爲了進一步解釋我將用一個例子：1,2,3和2,3,4,6。比2更好（跳過第二個列表中的3）或1.something（不跳過3） ？第三什麼是你想用來衡量兩者之間的差異（線性和，均方根等）的權重？

如果你能提供一些這些細節，我可能會給你一些更好的想法嘗試。

UPDATE

因此，基於您的評論，你可以跳過值。這實際上使得這個問題很難解決O（2^n）。因爲你基本上在查看列表1和列表2的所有組合。

即使你可以優化這個問題的某些方面，因爲它們是排序的，你仍然需要檢查很多組合。