D:/work/code_by/CbmrEngine/SongDb.cpp

查看本檔案說明文件.

/*==============================================================================
TSongDb代表的是歌曲的資料庫
==============================================================================*/
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include "SongDb.h"
#include "ListTools.h"
#include "cbmrdtw.h"

#define WARP_NUM 17  //歌聲的伸縮次數，改了這個還要改MIN_WARP_RATE
#define MIN_WARP_RATE 70  //表示最小的伸縮倍率，依WARP_NUM調整，單位是%
#define CONSTA 0.9
#define CONSTB 0.5

/*==============================================================================
功能：將中介格式平移一個值
傳入：mid為中介格式
      size為mid的長度
      level為要平移的距離
==============================================================================*/
static void shiftMid(int *mid, int size, int level)
{
  int i;

  for (i = 0; i < size; i++)
    mid[i] += level;
}
/*==============================================================================
功能：將中介格式平移到平均值為0
傳入：mid為中介格式
      size為mid的長度
==============================================================================*/
static void shiftMidToMeanZero(int *mid, int size)
{
  int i, total;

  for (i = 0, total = 0; i < size; i++)
    total += mid[i];
  shiftMid(mid, size, -total / size);
}
/*==============================================================================
功能：將一個值插入已經排序好的陣列
傳入：array為目標陣列
      size為陣列長度
      value為要插入的值
==============================================================================*/
static void insertArray(int *array, int size, int value)
{
  int i, j;

  for (i = size - 1; i >= 0; i--)
    if (value >= array[i])
      break;
  if (i < size - 1)
  {
    for (j = size - 1; j > i + 1; j--)
      array[j] = array[j - 1];
    array[i + 1] = value;
  }
}

static bool strequal(char *str1, char *str2)
{
  char c1, c2;

  while (*str1 != '\0' && *str2 != '\0')
  {
    c1 = (*str1 >= 'a' && *str1 <= 'z')? *str1 - 32 : *str1;
    c2 = (*str2 >= 'a' && *str2 <= 'z')? *str2 - 32 : *str2;
    if (c1 != c2)
      return false;
    if (c1 < 0 && c2 < 0)  //考慮到雙位元的字
    {
      if (*(++str1) != *(++str2))
        return false;
    }
    ++str1;
    ++str2;
  }
  return *str1 == *str2;
}

static bool strnequal(char *str1, char *str2, int n)
{
  int i;
  char c1, c2;

  i = 0;
  while (*str1 != '\0' && *str2 != '\0' && i++ < n)
  {
    c1 = (*str1 >= 'a' && *str1 <= 'z')? *str1 - 32 : *str1;
    c2 = (*str2 >= 'a' && *str2 <= 'z')? *str2 - 32 : *str2;
    if (c1 != c2)
      return false;
    if (*str1 < 0 && *str2 < 0)  //考慮到雙位元的字
    {
      if (*(++str1) != *(++str2))
        return false;
      ++i;
    }
    ++str1;
    ++str2;
  }
  return i == n || *str1 == *str2;
}

int min(int a, int b)
{
  return a <= b? a : b;
}

/*==============================================================================
功能：建構子
==============================================================================*/
TSongDb::TSongDb()
{
  resampleRate = 4;
  songNumber = 0;
  compareProgress1 = compareProgress2 = 0;
  Song = NULL;
  topSongIndex = NULL;
  SetOption(COMPARE_FROM_ANYWHERE);
}

/*==============================================================================
功能：解構子
==============================================================================*/
TSongDb::~TSongDb()
{
  int i;

  for (i = 0; i < songNumber; i++)  //將所有歌曲釋放掉
    delete Song[i];
  delete[] Song;
  delete[] topSongIndex;
}

void TSongDb::SetOption(int from, char *language, int method)
{
  compareFrom = from;
  //Q:compareLanguage還沒有寫~這裡一開始都是NULL,不會跑進else
  if (language == NULL)
    compareLanguage[0] = '\0';
  else
    strcpy(compareLanguage, language);
  compareMethod = method;
}
/*==============================================================================
功能：從index檔和db檔讀取資料庫，如果已經讀取過了，則會附加在後面
傳入：IndexStream為index檔
      DbStream為db檔
//Q:cbmrmain.cpp呼叫時_expand是設false.
傳出：是否成功
==============================================================================*/
bool TSongDb::Read(TInputStream *IndexStream, TInputStream *DbStream, bool _expand)
{
  TMyList *List;
  TDataInputStream *DIStream;
  bool success;
  char strLine[1000];
  TSongItem *SongItem, **SongTemp;
  int i;

  List = new TMyList();
  DIStream = new TDataInputStream(IndexStream);
  success = true;
  while (DIStream->ReadLine(strLine, 1000) > 0)  //從index檔讀取一行字串
  {
    SongItem = new TSongItem();  //加入一首歌
    SongItem->SetProperty(strLine);
    if (DbStream)
      if (!SongItem->Read(DbStream, resampleRate))  //讀取db檔中的音符
      {
        delete SongItem;
        success = false;
        break;
      }
    List->Add(SongItem);  //先放進linking list
  }
  delete DIStream;

  SongTemp = Song;
  Song = new TSongItem*[songNumber + List->count];  //新的歌曲陣列
  memcpy(Song, SongTemp, songNumber * sizeof(TSongItem *));  //將舊的複製到新的
  for (i = 0; i < List->count; i++)  //從linking list放進陣列
    Song[songNumber + i] = (TSongItem *)List->Items(i);
  songNumber += List->count;
  delete List;
  delete[] SongTemp;  //釋放舊的歌曲陣列

  delete[] topSongIndex;
  topSongIndex = new int[songNumber];  //用來排序歌曲的索引陣列

  expand = _expand;
  if (expand)
    for (i = 0; i < songNumber; i++)
      Song[i]->NoteToMid(resampleRate, INTEGER_SCALE);

  return success;
}
/*==============================================================================
功能：將所有歌曲資料寫入index檔和db檔
傳入：IndexStream為index檔
      DbStream為db檔
傳出：是否成功
==============================================================================*/
bool TSongDb::Write(TOutputStream *IndexStream, TOutputStream *DbStream)
{
  return Write(IndexStream, DbStream, 0, songNumber - 1);
}
/*==============================================================================
功能：將某些歌曲資料寫入index檔和db檔
傳入：IndexStream為index檔
      DbStream為db檔
      fromIndex代表從哪一首歌開始
      toIndex代表到哪一首歌為止
傳出：是否成功
==============================================================================*/
bool TSongDb::Write(TOutputStream *IndexStream, TOutputStream *DbStream, int fromIndex, int toIndex)
{
  int i;

  if (fromIndex < 0)  //檢查索引範圍
    fromIndex = 0;
  if (toIndex > songNumber - 1)  //檢查索引範圍
    toIndex = songNumber - 1;

  for (i = fromIndex; i <= toIndex; i++)  //寫入檔案
    Song[i]->Write(IndexStream, DbStream);

  return true;
}
/*==============================================================================
功能：增加一首歌曲，只新增一個指標連結，並不會將歌曲複製一份
傳入：SongItem為新增的歌
傳出：新增歌曲的索引
==============================================================================*/
int TSongDb::AddSong(TSongItem *SongItem)
{
  TSongItem **SongTemp;

  SongTemp = Song;
  Song = new TSongItem *[songNumber + 1];  //新的歌曲陣列
  memcpy(Song, SongTemp, songNumber * sizeof(TSongItem *));  //將舊的複製到新的
  Song[songNumber] = SongItem;  //增加一首歌
  delete[] SongTemp;  //釋放舊的歌曲陣列

  delete[] topSongIndex;
  topSongIndex = new int[songNumber + 1];

  return songNumber++;
}
/*==============================================================================
功能：刪除一首歌曲
傳入：index為刪除的歌的索引
==============================================================================*/
void TSongDb::DeleteSong(int index)
{
  int i;

  if (index >= 0 && index < songNumber)
  {
    delete Song[index];
    for (i = index; i < songNumber - 1; i++)  //向前遞補
      Song[i] = Song[i + 1];
    delete[] topSongIndex;
    topSongIndex = new int[--songNumber];
  }
}
/*==============================================================================
功能：刪除一首歌曲
傳入：DbEntity為刪除的歌
==============================================================================*/
void TSongDb::DeleteSong(TSongItem *SongItem)
{
  int i;

  for (i = 0; i < songNumber; i++)
    if (Song[i] == SongItem)
    {
      DeleteSong(i);
      break;
    }
}
/*==============================================================================
功能：傳回某一首歌
傳入：index為指定的歌曲索引
傳出：第index首歌
==============================================================================*/
TSongItem *TSongDb::GetSong(int index)
{
  return (index >= 0 && index < songNumber)? Song[index] : NULL;
}
/*==============================================================================
功能：傳回資料庫中的歌曲數目
傳出：資料庫中的歌曲數目
==============================================================================*/
int TSongDb::GetSongNumber(void)
{
  return songNumber;
}
/*==============================================================================
功能：比對所有歌曲
傳入：waveMid為唱進來的中介格式
      waveSize為waveMid的長度
==============================================================================*/
void TSongDb::Compare(int *waveMid, int waveSize)
{
  Compare(waveMid, waveSize, 0, songNumber - 1);
}
/*==============================================================================
功能：比對所部份歌曲
傳入：waveMid為唱進來的中介格式
      waveSize為waveMid的長度
      fromIndex為比對的起始範圍
      toIndex為比對的結束範圍
==============================================================================*/
void TSongDb::Compare(int *waveMid, int waveSize, int fromIndex, int toIndex)
{
  int i, j, k;
  //Q:waveCopy的大小原本是200,有時會不夠,要注意
  int waveCopy[300], *midiCopy;
//  int waveWarp[WARP_NUM][SEGMENT_SIZE];
  int waveWarp[WARP_NUM][1280];
  int waveWarpSize[WARP_NUM];
  int lsDist, lsDistThreshold, lsDistTemp;
  float score;
  int *segmentIndex, segmentIndexSize;
  int maxMidiSize, midiSize;
  int dtwDistance_c, dtwDistance_l, dtwDistance_r, minDtwDistance;
  int dtwStringLength_c, dtwStringLength_l, dtwStringLength_r, minDtwStringLength;
  bool allLanguage, dtwFixLeft;
  TSongItem *CurrentSong;
  int minNum;
  int *minDist;
  int *nonzeroMid;
  int best, fromSegment, toSegment;
  FILE *fTree;
  //Q:topRank = 100?????
  const int topRank = 100;
  const float multiple = 1.4f;//Q:dtw table長寬比是1.4
//Q:fromIndex和toIndex指的是被比對的歌曲index?
  if (fromIndex < 0)
    fromIndex = 0;
  if (toIndex >= songNumber)
    toIndex = songNumber - 1;
  compareProgress1 = compareProgress2 = 0;  //比對進度為0
  if (compareMethod == METHOD_LINEAR_SCALING || compareMethod == METHOD_LSDTW)
  {
    compareNum1 = toIndex - fromIndex + 1;  //第一階段比對數目
    //Q:topRank=100是常數~幹嘛用???
    compareNum2 = compareMethod == METHOD_LINEAR_SCALING? 0 : min(compareNum1, topRank);  //第二階段比對數目
    //Q:如果只有LS則第二階段比對數目為0
  }
  else//Q:沒有做LS,只做DTW,所以第一階段比對數目為0
  {
    compareNum1 = 0;  //第一階段比對數目
    compareNum2 = toIndex - fromIndex + 1;  //第二階段比對數目
  }
  stopCompare = false;
  //Q:compareLanguage[0] == '\0'的話allLanguage=1
  allLanguage = compareLanguage[0] == '\0';  //是否比對全部語言

  for (i = fromIndex; i <= toIndex; i++)  //對比對範圍內的所有歌曲
  {
  //Q:對比對範圍內的所有歌曲做初始值
  //Q:topSongIndex?????它在建構子是NULL.它在Read時被new如下一行(在這裡被給值???)
  //Q:topSongIndex = new int[songNumber];  //用來排序歌曲的索引陣列
    topSongIndex[i - fromIndex] = i;  //在範圍內的index，供排序用
    Song[i]->bestSegment = 0;  //先假設使用者最可能從頭唱
    Song[i]->score = 0.0f;  //先設定分數為0
  }
  if (waveSize < 3)  //讓waveWarpSize至少1
    return;


  //============================================================================
  //第一階段用 linear scaling 的方法 ===========================================
  //============================================================================
//Q:將唱進來的聲音做伸縮,從0.7~1.5每次加5共16個result存在array wavewarp[i][j]裡.
//Q:wavewarp[0]就是0.7倍的那條~將16個result去和db轉出來的中介格式mid比對,看哪段最接近
//Q:mid要比對的index(如果從head比就只有一個,any就是每個音符)去和取出伸縮後最接近的片段比對,
//Q:找出分數最近的 
  if (compareMethod == METHOD_LINEAR_SCALING || compareMethod == METHOD_LSDTW)
  {
    //將歌聲的中介格式複製到waveCopy
    //Q:waveMid是傳進來的pitch
    waveCopy[0] = waveMid[0];   //Q:改成前一個非休止符的音,所以至少waveCopy[0]要先給
                                //Q:這裡是延長前一個音,而非去掉休止符.
    for (i = 1; i < waveSize; i++)  //複製時將休止符改成前一個非休止符的音
      waveCopy[i] = (waveMid[i] == 0)? waveCopy[i - 1] : waveMid[i];

    for (i = 0; i < WARP_NUM; i++)  //伸縮WARP_NUM次
    {//Q:開頭define了WARP_NUM=17,歌聲的伸縮次數,MIN_WARP_RATE=70,表示最小的伸縮倍率%
    //Q:j的最小值是70,最大值是150,在70%~150%中伸縮.0.7倍~1.5倍(每次加5所以有17-1=16次)
      j = MIN_WARP_RATE + i * 5;  //伸縮倍率
      waveWarpSize[i] = (waveSize - 1) * j / 100;  //伸縮後的長度
//      if (waveWarpSize[i] > SEGMENT_SIZE)//Q:因為唱進來八秒,最長不會超過SEGMENT_SIZE
//        waveWarpSize[i] = SEGMENT_SIZE;
      for (k = 0; k < waveWarpSize[i]; k++)  //做resample
      {
        int _m = 100 * k / j;
        float _n = 100.0f * k / j - _m;
        waveWarp[i][k] = floor((1.0 - _n) * waveCopy[_m] + _n * waveCopy[_m + 1] + 0.5);  //內插值
      }
      shiftMidToMeanZero(waveWarp[i], waveWarpSize[i]);  //將waveWarp的平均值調為0
    }
    //Q:開了一個waveWarpSize最大的,最後那個.(就夠了)
 midiCopy = new int[waveWarpSize[WARP_NUM - 1]];
    //Q:如果只有LS,則compareNum2=0.錯.所以if只有LS要取min(compareNum1, topRank)
    //Q:但在前面,compareNum2在LS時=0,在LSDTW時compareNum2=min(compareNum1, topRank),
    //Q:所以這裡為什麼不通通設minNum=min(compareNum1, topRank)???
    minDist = new int[minNum = (compareMethod == METHOD_LSDTW)? compareNum2 : min(compareNum1, topRank)];  //用來記錄前minNum名linear scaling距離最小者
    for (i = 0; i < minNum; i++)  //Q:INFINITE_INT=9999999
      minDist[i] = INFINITE_INT;




    for (compareProgress1 = fromIndex; compareProgress1 <= toIndex && !stopCompare; compareProgress1++)  //比對範圍中每一首midi
    {//Q:compareProgress1表示每首midi~一首一首跑
      CurrentSong = Song[compareProgress1];
      if (!allLanguage && strcmp(CurrentSong->Fields->Values("language"), compareLanguage))  //語言不符合
//Q:語言不合的話這一首就不比了.不比就跳過這一首歌,因此這一次的迴圈結束,使用continue.換下一首.
        continue;


//Q:為了省空間而沒有在Read時就每首歌都NoteToMid.在這裡才NoteToMid,每首歌比完存了該存的以後
//Q:就把空間free出來.
      if (!expand){
        CurrentSong->NoteToMid(resampleRate, INTEGER_SCALE);  //展開成中介格式        
        }
        
      //設定要比對的片段位置和數目
      if (compareFrom == COMPARE_FROM_REFRAIN)  //從複歌比對
      {                                              //Q:midRefrainIndex是"複歌起點在mid中的索引"
        segmentIndex = CurrentSong->midRefrainIndex; //Q:用midRefrainIndex是因為用中介格式比
        segmentIndexSize = CurrentSong->refrainIndexSize + 1;
      }
      else  //從頭或任意處比對
      {
        segmentIndex = CurrentSong->noteIndex; //Q:noteIndex是"每個音符起點在mid中的索引"
        segmentIndexSize = (compareFrom == COMPARE_FROM_HEAD)? min(1, CurrentSong->noteIndexSize) : CurrentSong->noteIndexSize;
      }
      if (segmentIndexSize == 0)  //沒有片段可以比對
        continue;

//Q:mid是從note來,所以還沒有去掉休止符.noteIndex才是扣掉休止符的
//Q:COMPARE_FROM_HEAD的size應該在兩者中取一個小的,以免db檔裡的歌比唱拉長後的短,
//Q:會讀到不該讀的地方(取小的是我改的~原本是用warp的size)
      nonzeroMid = new int[midiSize = (compareFrom == COMPARE_FROM_HEAD)? min(CurrentSong->midSize,waveWarpSize[WARP_NUM - 1]) : CurrentSong->midSize - segmentIndex[0]];
//Q:segmentIndex是從noteIndex來,所以segmentIndex[0]一定是非休止符

      nonzeroMid[0] = CurrentSong->mid[j = segmentIndex[0]];  //第一個非休止符的音

//暫存      for (i = 1; (i < midiSize)&&(j+i)<CurrentSong->midSize; i++)  //將休止符改成前一個非休止符的音

     for (i = 1; i < midiSize; i++)  //將休止符改成前一個非休止符的音
{//Q:(j+i)<CurrentSong->midSize的條件是我加的,因為取消warp上限的話,有時候會爆掉,
 //Q:拉長後的比mid還長,會讀到超過midSize的地方,會爆掉   
                nonzeroMid[i] = (CurrentSong->mid[j + i] == 0)? nonzeroMid[i - 1] : CurrentSong->mid[j + i];

}
      lsDistThreshold = minDist[minNum - 1];
 
      for (i = 0; i < segmentIndexSize; i++)  //比對midi的每一片段
      {
        if (segmentIndex[i] - segmentIndex[0] + waveWarpSize[WARP_NUM - 1] > midiSize)
          break;

        //將midi的中介格式複製到midiCopy，減去segmentIndex[0]是因為它可能不是0
        //Q:減去segmentIndex[0]是因為nonzeroMid是從segmentIndex[0]開始的~所以只要加上offset即可(吧)
        //Q:(offset=segmentIndex[i] - segmentIndex[0])
//        memcpy(midiCopy, nonzeroMid + segmentIndex[i] - segmentIndex[0], waveWarpSize[WARP_NUM - 1] * sizeof(int));
  //Q:應該把waveWarpSize[WARP_NUM - 1]改成midiSize~前面有討論過why
        memcpy(midiCopy, nonzeroMid + segmentIndex[i] - segmentIndex[0], min(midiSize,waveWarpSize[WARP_NUM - 1]) * sizeof(int));

        for (j = WARP_NUM - 1; j >= 0; j--)  //對每一次伸縮。必須倒數是因為waveWarpSize[j]隨著j變大而變大，而midiCopy在平移到平均值為0時會一直改變
        {//Q:倒數是因為才能在每次平移是全部都有移到.如果從前面開始,就只會移前面一小段,
         //Q:後面的不會被移到,等到要做第二次時,前面那一小段跟後面就會有落差,因為後面剛剛沒有平移到
          shiftMidToMeanZero(midiCopy, waveWarpSize[j]);  //將midiCopy的平均值調為0
          //計算waveCopy伸縮後的waveWarp和midiCopy的距離
          //Q:下面除掉這裡又乘回來.why???其實就是lsDistTemp=lsDist.
          //Q:不過一開始lsDist沒有值,lsDist在下兩行才開始算
          lsDistTemp = lsDistThreshold == INFINITE_INT? INFINITE_INT : lsDistThreshold * waveWarpSize[j];

          for (k = 0, lsDist = 0; k < waveWarpSize[j]; k++)  //計算兩向量的距離
            if ((lsDist += abs(waveWarp[j][k] - midiCopy[k])) > lsDistTemp)  //距離超過第minNum名則不再算下去
              break;  //Q:距離超過第minNum名就爆了,不用管它.
                      //Q:在這裡lsDistTemp存著每一個伸縮對mid~做到目前的最小距離(對某個伸縮)
                      //Q:超過最小值就不要了~只要找出這麼多伸縮中最接近的一個即可
                      //Q:而minDist是用來存所有的~每首midi的每個片段的前minNum名最接近的
 
          if (lsDist < lsDistTemp)
          {
            lsDistThreshold = lsDist / waveWarpSize[j]; //Q:除的意思是???算平均每個音差多少?
            CurrentSong->bestSegment = i;  //最接近的片段
          }
//Q:這邊做完waveWarp就沒用了,但每首midi都要跟waveWarp來比對,waveWarp是唱進來的,
//Q:所以唱進來的wave的伸縮存在waveWarp裡,在和每首midi比對的loop中都會用到.
//Q:用來找出伸縮後和要比對的那首midi中介格式距離最小的

        }  //for伸縮

      }  //for每個片段 //Q:每個片段的loop是用來找出這首midi中要比對的片段中最接近的那一個,存在bestSegment裡
      delete[] nonzeroMid;

      if (lsDistThreshold < minDist[minNum - 1])  //算出來的距離比第minNum名還小
      {
//Q:minDist是片段的距離~不是指伸縮~和每首歌的score也無關
//Q:一首歌可能有好幾個片段都很接近query,分數是由lsDistThreshold算出來的,
//Q:在算每個片段時lsDistThreshold都可能變動,最後,一首歌只有一個lsDistThreshold
        CurrentSong->score = 100.0f - (float)lsDistThreshold / INTEGER_SCALE;
        insertArray(minDist, minNum, lsDistThreshold);  //將距離插入前minNum名距離
        //Q:insertArray的做法是,從後往前找出它應該排序的位置,比方說是第五名,
        //Q:然後將最後一個存成最後一個的前一個,以此類推~第七個存原本的第六名,
        //Q:第六個存原本的第五名,再將新的第五名加在array第五項.
        //Q:看不太出來minDist可以幹嘛,好像只為了lsDistThreshold < minDist[minNum - 1]比較用
      }

      if (!expand)
        CurrentSong->FreeMid();

    }  //for每首midi
    delete[] minDist;
    delete[] midiCopy;

    if (stopCompare)  //使用者中斷比對
      return;
    SortByScore(compareNum1, minNum);  //將分數在前minNum名的歌曲排序
 //Q:第一階段比對了compareNum1首,排序出前minNum名,排序後的索引放在topSongIndex
  }  //if使用linear scaling


  //============================================================================
  //第二階段用 dynamic time warping 的方法 =====================================
  //============================================================================
  if (compareMethod == METHOD_DTW || compareMethod == METHOD_LSDTW || compareMethod == METHOD_NOTEBEGIN_DTW)
  {
//Q:waveCopy是唱進來的pitch.這裡是移掉休止符而非延長,因為dtw本身有伸縮的功能.
//Q:又,移掉休止符或延長休止符的前一個音,兩者效果差不多

    for (i = 0, j = 0; i < waveSize; i++)  //複製時移除修止符
      if (waveMid[i] != 0)
        waveCopy[j++] = waveMid[i];
     waveSize = j;

    shiftMidToMeanZero(waveCopy, waveSize);  //將waveCopy的平均值調為0

//Q:DTW是否固定起點:LSDTW,NOTEBEGIN_DTW,COMPARE_FROM_HEAD???why???
 
    dtwFixLeft = (compareMethod == METHOD_LSDTW || compareMethod == METHOD_NOTEBEGIN_DTW || compareFrom == COMPARE_FROM_HEAD);  //DTW是否固定起點
//Q:multiple是常數(dtw table長寬比,切出兩條線,只有兩線中間要比),const float multiple = 1.4f;
    maxMidiSize = dtwFixLeft? (waveSize * multiple) : INFINITE_INT;  //midi的中介格式最多取多長出來計算dtw距離
    minDist = new int[minNum = min(compareNum2, 100)];  //最多只算出前100名的分數
    for (i = 0; i < minNum; i++)  //用來記錄前minNum名dtw距離最小的
      minDist[i] = INFINITE_INT;

    for (compareProgress2 = 0; compareProgress2 < compareNum2 && !stopCompare; compareProgress2++)  //比對前幾名midi
    {
      CurrentSong = Song[topSongIndex[compareProgress2]];
      CurrentSong->score = 0.0f;
      if (!allLanguage && strcmp(CurrentSong->Fields->Values("language"), compareLanguage))  //語言不符合
        continue;

      if (!expand)
        CurrentSong->NoteToMid(resampleRate, INTEGER_SCALE);  //展開成中介格式

      if (compareFrom == COMPARE_FROM_REFRAIN)  //從複歌比對
      {
        segmentIndex = CurrentSong->midRefrainIndex;
        segmentIndexSize = CurrentSong->refrainIndexSize + 1;
      }
      else  //從頭或任意處比對
      {
        segmentIndex = CurrentSong->noteIndex;
        segmentIndexSize = compareFrom == COMPARE_FROM_HEAD? min(1, CurrentSong->noteIndexSize) : CurrentSong->noteIndexSize;
      }
      if (segmentIndexSize == 0)  //沒有片段可以比對
        continue;
//Q:移除休止符的動作在下面的for裡(好像可以像LS一樣提出來在這裡先用nonzeroMid存起來)
      midiCopy = new int[min(CurrentSong->midSize, maxMidiSize)];

      if (compareMethod == METHOD_DTW || compareMethod == METHOD_LSDTW)  //只針對第besstIndex個片段做dtw
        fromSegment = toSegment = CurrentSong->bestSegment;  //如果沒做第一階段則會是0
      else  //if (compareMethod == METHOD_NOTEBEGIN_DTW) 則所有片段都做dtw
      {
        fromSegment = 0;
        toSegment = segmentIndexSize - 1;
      }


      for (best = fromSegment, minDtwDistance = INFINITE_INT; best <= toSegment; best++)  //對CurrentSong每個要做dtw的片段
      {
        //將midi的中介格式複製到midiCopy並移除休止符
        //Q:這裡的midiCopy放進for是因為它的起點會改變,所以不能放在迴圈外.(?!)
        for (j = segmentIndex[best], midiSize = 0; j < CurrentSong->midSize && midiSize < maxMidiSize; j++)
          if (CurrentSong->mid[j] != 0)
            midiCopy[midiSize++] = CurrentSong->mid[j];
        if (midiSize == 0)  //有問題的片段
          continue;

        shiftMidToMeanZero(midiCopy, midiSize);  //將midiCopy的平均值調為0
        //計算waveCopy和midiCopy的距離
        dtwDistance_c = dtw(waveCopy, waveSize, midiCopy, midiSize, dtwFixLeft, &dtwStringLength_c, minDist[minNum - 1]);
        for (j = INTEGER_SCALE; j >= (INTEGER_SCALE >> 1) && j > 0; j >>= 1)  //循環比對四次
        {//Q:INTEGER_SCALE=10,循環比對就好像是用binary search一樣,找出最佳解.
         //Q:先從中間開始,看左邊和右邊先比較近,ex左邊,取中間和左邊那段,從這段的中間再開始往左往右,
         //Q:以此類推.
          shiftMid(midiCopy, midiSize, -j);
          dtwDistance_l = dtw(waveCopy, waveSize, midiCopy, midiSize, dtwFixLeft, &dtwStringLength_l, minDist[minNum - 1]);
          shiftMid(midiCopy, midiSize, j * 2);
          dtwDistance_r = dtw(waveCopy, waveSize, midiCopy, midiSize, dtwFixLeft, &dtwStringLength_r, minDist[minNum - 1]);
          if (dtwDistance_l < dtwDistance_c && dtwDistance_l < dtwDistance_r)
          {
            dtwDistance_c = dtwDistance_l;
            shiftMid(midiCopy, midiSize, -j * 2);
          }
          else if (dtwDistance_r < dtwDistance_c && dtwDistance_r < dtwDistance_l)
            dtwDistance_c = dtwDistance_r;
          else
            shiftMid(midiCopy, midiSize, -j);
        }

        insertArray(minDist, minNum, dtwDistance_c);  //將距離插入前minNum名距離
        if (dtwDistance_c < minDtwDistance)
        {
          minDtwDistance = dtwDistance_c;  //這首歌比對的片段當中最小的dtw距離
          minDtwStringLength = dtwStringLength_c;  //此時的dtw string length
        }
      }  //for片段

      if (minDtwDistance < INFINITE_INT)  //minDtwDistance是這首歌比對後的最小dtw距離
        CurrentSong->score = (CONSTA * pow(CONSTB, (double)minDtwDistance / INTEGER_SCALE / waveSize) + (1.0 - CONSTA) * minDtwStringLength / waveSize) * 100.0;

      if (!expand)
        CurrentSong->FreeMid();

      delete[] midiCopy;
    }  //for每首midi
    delete[] minDist;
    if (!stopCompare)
      SortByScore(compareNum2, minNum);  //第二階段比對完之後最多只排出前minNum名，`所以超出minNum名的歌其分數皆沒有意義
  }  //if使用DTW

}

/*==============================================================================
功能：找出某個欄位符合某個值的歌曲
傳入：fieldName為某一欄位的名稱
      value為期望值
      exactMatch為字串是否要完全符合或部份符合
      result為傳出結果，true代表符合，false代表不符合
傳出：符合的歌曲數目
==============================================================================*/
int TSongDb::Compare(char *fieldName, char *value, bool exactMatch, bool *result)
{
  int i, size, count;
  char *c;

  count = 0;
  if (exactMatch)
  {
    for (i = 0; i < songNumber; i++)  //對資料庫每首歌曲
      if (result[i] = strequal(Song[i]->Fields->Values(fieldName), value))
        ++count;
  }
  else
  {
    size = strlen(value);
    for (i = 0; i < songNumber; i++)  //對資料庫每首歌曲
    {
      result[i] = false;
      c = Song[i]->Fields->Values(fieldName);
      while (*c != '\0')
      {
        if (strnequal(c, value, size))
        {
          result[i] = true;
          ++count;
          break;
        }
        c += *c < 0? 2 : 1;  //考慮到雙位元的字
      }
    }
  }

  return count;
}
/*==============================================================================
功能：找出某個欄位值符合某個長度的歌曲，若值當中有雙位元的字，會當成一個字
傳入：fieldName為某一欄位的名稱
      size為期望值
      operate為-1, 0 或 1，代表小於、等於或大於
      result為傳出結果，true代表符合，false代表不符合
傳出：符合的歌曲數目
==============================================================================*/
int TSongDb::Compare(char *fieldName, int size, int operate, bool *result)
{
  int i, j, count;
  char *c;

  count = 0;
  for (i = 0; i < songNumber; i++)  //對資料庫每首歌曲
  {
    for (c = Song[i]->Fields->Values(fieldName), j = 0; *c != 0;)
    {
      if (*c < 32 || (*c > 47 && *c < 58) || (*c > 64 && *c < 91) || (*c > 96 && *c < 123) || *c < 0)  //判斷是否是英數字或符號
        j++;
      c += *c < 0? 2 : 1;  //考慮到雙位元的字
    }
    if (result[i] = (operate == 0 && j == size) || (j - size) * operate > 0)
      ++count;
  }

  return count;
}
/*==============================================================================
功能：將歌曲依照分數排序，排序後的索引放在topSongIndex陣列中
輸入：sortNum為要排序的歌曲數目
      topNum為只排序出前topNum名即可
==============================================================================*/
void TSongDb::SortByScore(int sortNum, int topNum)
{
  int i, j, k, tempd;
  float tempf;
  float *score;
  
  score = new float[sortNum];
  for (i = 0; i < sortNum; i++)  //將分數複製到score陣列以便排序
    score[i] = Song[topSongIndex[i]]->score;  //此時topSongIndex為排序前的歌曲索引
  for (i = 0; i < topNum; i++)  //泡沫排序法(採大的在上面)，只排出前topNum名分數最高者
  {
    k = i;
    for (j = i + 1; j < sortNum; j++)
      if (score[k] < score[j])
        k = j;
    if (k != i)
    {
      tempd = topSongIndex[i];
      topSongIndex[i] = topSongIndex[k];
      topSongIndex[k] = tempd;
      tempf = score[i];
      score[i] = score[k];
      score[k] = tempf;
    }
  }
  delete[] score;
}
/*==============================================================================
功能：傳回某一個名次的歌曲
傳入：rank為名次，範圍從0到比對的歌曲數-1，否則會傳回無法預期的topSongIndex
傳出：第rank名的歌曲
==============================================================================*/
TSongItem *TSongDb::GetTopSong(int rank)
{
  return Song[topSongIndex[rank]];
}
/*==============================================================================
功能：傳回某一個名次的歌曲索引
傳入：rank為名次，範圍從0到比對的歌曲數-1，否則會傳回無法預期的topSongIndex
傳出：第rank名的歌曲索引
==============================================================================*/
int TSongDb::GetTopSongIndex(int rank)
{
  return topSongIndex[rank];
}
/*==============================================================================
功能：停止比對
==============================================================================*/
void TSongDb::StopCompare(void)
{
  stopCompare = true;
}
/*==============================================================================
功能：傳回比對進度，範圍從0到100
傳出：比對進度
==============================================================================*/
int TSongDb::GetCompareProgress(void)
{
  if (compareNum1 == 0 && compareNum2 == 0)
    return 0;
  if (compareNum1 == 0)  //只用linear scaling
    return compareProgress2 * 100 / compareNum2;
  else if (compareNum2 == 0)  //只用DTW
    return compareProgress1 * 100 / compareNum1;
  else  //兩階段式比對
    return compareProgress1 * 95 / compareNum1 +  //第一階段的進度佔總進度的95%
           compareProgress2 * 5 / compareNum2;  //第二階段的進度佔總進度的5%
}

---