討論 - 尋找/自製 比對數列的方法

[alanniok]

--------------------
閱讀本主題的最佳解答
--------------------


最近做專題需要寫一個方法，功能是比對一長串數字和一個小數字段，如果有“相似”的就說有沒有就說沒有
Ex.
數字串= 1, 5, 7, 3, 6, 6, 8, 3, 5, 3, 7, 5, 5.....
那麼輸入------7, 3, 6, 6, 8
或是-----------6, 2, 5, 5, 7
或是--------------------7, 9, 4, 6, 4 都回答有

其他像是1, 5, 5, 3, 6
或是--------6, 8, 4, 4, 5等等就回答沒有

換句話說，與長數字串對比，如果能找到完全相同或是上下平移後能找到完全相同者就回答有，不知道有沒有人見識過類似的方法或是有什麼建議呢？？？ P.S.我用的是C/C++

[mini]

首先要了解的是
有 與 沒有 的定義

不解~
6, 2, 5, 5, 7
7, 9, 4, 6, 4
為何回答 "有" ?

只有了解 判斷的依據 才能寫出邏輯

=============
如果是用百分比來當 有與沒有 的依據
那簡單
先看你輸入了幾個數字
輸入5個那只要【循序比對】有3個以上就可說"有" (3分之5)
當然也可以不是用【循序比對】當條件 (這又回到問題 看你如何定義了...)

如果是人工智慧的角度
那就不是這麼單純了
必須加上數據分析
人工智慧 與 程式邏輯 的主要差異就是 "數據分析"
人工智慧會有個邏輯判斷 專司 數據的處理
藉由數據的參與、統計 與 修正
讓 人工智慧可以修改輸出邏輯
(目前技術說不上是機器人寫程式，而是機器人拼積木)

當然這個 mini是不會的 ^^"

[mini]

過了一些時候
回頭再看一次原來
6, 2, 5, 5, 7 相似 7, 3, 6, 6, 8
7, 9, 4, 6, 4 相似 6, 8, 3, 5, 3

是差距 "1"
那比對方法就是
先算出前後差距
1, 5, 7, 3, 6, 6, 8, 3, 5, 3, 7, 5, 5..... 的前後差距是
-4,-2, 4,-3, 0,-2, 5,-2, 2,-2, 0...

6, 2, 5, 5, 7的前後差距是
4,-3, 0,-2
經過循序比對 符合前面

用C/C++就是

PHP 語法:

int 數列[N]={1, 5, 7, 3, 6, 6, 8, 3, 5, 3, 7, 5, 5};
int 輸入[4]; //經過輸入後內容是6, 2, 5, 5, 7
int 數列差距[N-1];
int 輸入差距[4-1];

//數列差距
for (int i=0; i<N; i++){
   數列差距[i]=數列[i]-數列[i+1];
}
//輸入差距
for (int i=0; i<4; i++){
   輸入差距[i]=輸入[i]-輸入[i+1];
}
//比對開始
for (int i=0; i<N-4; i++){
   if (數列差距[i] == 輸入差距[0]){
      int x=0;
      for (int j=i+1; x<=4; j++){
         x+=1;
         if (數列差距[j] != 輸入差距[x]){
            break;
         } else if (x == 3) {cout << "相似";}
      }
   }
} 


[alanniok]

這是我後還寫的版本，感覺是可以用，不過方法比較像是暴力解法，之後要用到大量比對的時候猜想可能速度會太慢因此才來問看看有沒有什麼特別的演算法之類。
-------------------------------------------
#include <iostream>
#include <stdlib.h>

using namespace std;

int main()
{

int song[] = {1, 3, 5, 5, 7, 9, 11, 9, 7};// Put the real song fftw result here
int num;
int *a;// used to store fftw of recorded melody

cout << "Enter a number:";
cin >> num;

a = new int[num];

cout << "Please Enter the Number List:";
for(int i =0; i < num; i++)
{

cin >> a[i];

}

int x = a[0];
int yn = 0;
int r[num];
int temp = 0;
for(int i =0; i < num; i++)
{

r[i] = a[i] - x;

}
for(int i =0; i <= sizeof(song)/sizeof(int) - num; i++)
{

for(yn = 0; yn < num; yn++)
{

temp = song[i + yn] - song[i] - r[yn];
if( temp > 1 || temp < -1 )//誤差半音以內沒關係
break;

}
if(yn == num)

break;

}
if(yn == num)

cout << "yes";

else

cout << "no";

return 0;

}

[mini]

原本看似可以用
陣列與陣列的運算函式來縮減傳統運算的效能
比如
http://webcache.googleusercontent.co...&gbv=1&ct=clnk
但實際上硬要使用那些函式
反而所花的準備時間不會帶來多少時間助益
所以
這可以改良的地方已經微乎其微
充其量可以想辦法使用C++內嵌組合語言來改良

如果效能不彰是指
為了保持作業系統不被所寫的軟體弄得卡卡的
可以"分段"執行
也就是把每N筆資料切割(用副程式方式執行)
這樣可以讓所寫的軟體不會陷入長時間假死(無反應)狀態
當然還有很多種方法避免軟體假死
那就要看你所使用的開發軟體(xxx IDE)是哪套
根據開發軟體可使用 分段、多媒體指令集、多執行緒...等方式
但這就...了 (mini不想太深入 C++)
你可以去研究 多執行緒
原則上使用 強制分段 來達到 每隔一段時間就交出執行權給系統
就已經是個不錯選擇了~

[alanniok]

專題持續進行中，最近翻論文時看到了一個很棒的演算法可以實現我需要的功能，甚至比我想像的還完善，產生的結果不只是Y/N這種二元論，而是0123456這種可以分辨有多像/有多不像。

這個演算法叫做 Minimum Edit Distance Dynamic Programming。

這是我看到的一個步驟說明影片，覺得講得蠻清楚的: https://youtu.be/We3YDTzNXEk