用於近似字符串匹配的示例java代碼或用於近似字符串匹配的boyer-moore擴展

Question

我需要找到1.mismatch（錯誤地彈奏的音符），2.insertion（額外播放的），& 3.deletion（錯過的音符），in音樂片段（例如存儲在表格中的音符音高[字符串值]）對照參考音樂片段。

這可以通過精確的字符串匹配算法或動態編程/近似字符串匹配算法來實現。但是我意識到，由於識別不匹配，插入，刪除音符，近似字符串匹配更適合我的問題。或Boyer-moore的擴展版本來支持約。字符串匹配。

有沒有樣本java代碼的任何鏈接我可以嘗試近似字符串匹配？我找到了複雜的解釋和方程 - 但我希望我能用一些示例代碼和簡單的解釋做得很好。或者我可以在boyer-moore中找到任何Java代碼示例，字符串匹配？我明白博爾摩爾摩爾的概念，但在調整它以支持約。字符串匹配（即支持不匹配，插入，刪除）。

什麼是最有效的約。字符串匹配算法（如精確字符串匹配算法中的boyer-moore）？

非常感謝任何見解/建議。這種提前

Answer 1

here 非常感謝，看到第一個（Boyer.java）導致

頁

Answer 2

你可以在approximate string matching與維基百科頁面開始。

問題是，這個是一個複雜的領域，只是看着/複製一些示例代碼可能無助於你理解發生了什麼。

編輯 - 此外，我不明白Boyer-Moore如何適應近似字符串匹配。

Answer 3

這裏是C＃Boyer-More代碼，它可以被推送到BMH或近似匹配。

Dictionary<char, int> ShiftSizeTable = new Dictionary<char, int>(); 

     //Calculate Shifit/Skip count for each element in pattern text. So that we can skip that many no of Characters in given text while searching. 
     public void PreProcessBMSBadMatchTable(char[] patternCharacters) 
     { 
      ShiftSizeTable.Clear(); 

      int totalCharacters = patternCharacters.Length; 

      for (int lpIndex = 0; lpIndex < totalCharacters; lpIndex++) 
      { 
       //Calculate the shift size for each character in the string or char array. 
       int ShiftSize = Math.Max(1, (totalCharacters - 1) - lpIndex); 

       //If the charater is already exists in the ShiftSize table then replace it else add it to ShiftSize table. 
       if (ShiftSizeTable.ContainsKey(patternCharacters[lpIndex])) 
       { 
        ShiftSizeTable.Remove(patternCharacters[lpIndex]); 
       } 

       ShiftSizeTable.Add(patternCharacters[lpIndex], ShiftSize); 
      } 
     } 

     //Use the PreProcessed Shift/Skip table to find the pattern Characters in text and skip the bad Characters in the text. 
     public int BoyerMooreSearch1UsingDictionary(char[] textCharacters, char[] patternCharacters) 
     {   
      PreProcessBMSBadMatchTable(patternCharacters); 

      int SkipLength; 
      int patternCharactersLenght = patternCharacters.Length; 
      int textCharactersLenght = textCharacters.Length; 

      // Step2. Use Loop through each character in source text use ShiftArrayTable to skip the elements. 
      for (int lpTextIndex = 0; lpTextIndex <= (textCharactersLenght - patternCharactersLenght); lpTextIndex += SkipLength) 
      { 
       SkipLength = 0; 

       for (int lpPatIndex = patternCharactersLenght - 1; lpPatIndex >= 0; lpPatIndex--) 
       { 
        if (patternCharacters[lpPatIndex] != textCharacters[lpTextIndex + lpPatIndex]) 
        { 
         SkipLength = Math.Max(1, lpPatIndex - ShiftSizeTable[patternCharacters[lpPatIndex]]); 
         break; 
        } 
       } 
       if (SkipLength == 0) 
       { 
        return lpTextIndex; // Found 
       } 
      } 
      return -1; // Not found 
     }