为近似串匹配或博耶-穆尔示例Java代码延长近似串匹配

Question

我需要找到1.mismatch（不正确地演奏的音符），2.insertion（额外播放），3.deletion（错过音符），在一个乐曲（例如音符音高[字符串值]存储在表中）与参考乐曲。

这是任一能够通过精确的字符串匹配算法或动态编程/近似串匹配交易算法。但是我意识到，近似字符串匹配更适合我的问题，由于鉴定不匹配，插入，删除记录。或博耶 - 穆尔的扩展版本，以约的支持。串匹配。

是否有任何链接，Java代码示例，我可以尝试近似串匹配？我发现复杂的解释和公式 - 但我希望我能有一些示例代码和简单的解释做的很好。或者，我可以找到任何Java代码示例，在博耶 - 穆尔延长约。字符串匹配？据我所知，博耶 - 摩尔的概念，但与调整它烦恼大约支持。串匹配（即，支持的不匹配，插入，缺失）。

还什么是最有效的约串匹配算法（如博耶-摩尔在精确的字符串匹配算法中）？

不胜感激任何见解/建议。 提前非常感谢

Answer 1

这里时，看到第一（Boyer.java）这个结果页的

Answer 2

您可以与近似串匹配维基百科页面开始。

但问题是，这种的为的一个复杂的领域，根本看/复制一些示例代码可能不会帮助您了解正在发生的事情。

修改 - 再说，我没有看到博耶摩尔定律将如何适应近似串匹配

Answer 3

下面是C＃博耶-更多代码，其可以被tweeked到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
        }