il codice Java di esempio per string matching approssimato o Boyer-Moore ha esteso per la corrispondenza approssimativa stringa

Question

Ho bisogno di trovare 1.mismatch (note in modo non corretto suonate), 2.insertion (aggiuntivo giocato), e 3.deletion (note perse), in un brano musicale (ad esempio piazzole nota [valori di stringa] memorizzata in una tabella) nei confronti di un brano musicale di riferimento.

Questo può essere possibile attraverso algoritmi di matching stringa esatte o programmazione / approssimata dinamiche Algos corrispondente stringa. Tuttavia ho capito che approssimativa string matching è più appropriato per il problema dovuto identificare disadattamento, inserimento, cancellazione di note. O una versione estesa di Boyer-Moore per sostenere circa. stringa corrispondente.

Esiste un collegamento per il codice Java di esempio posso provare approssimativo string matching? Trovo spiegazioni complesse ed equazioni - ma spero di poter fare bene con alcuni esempi di codice e le spiegazioni semplici. Oppure posso trovare alcun codice Java di esempio su Boyer-Moore esteso per circa. stringa corrispondente? Capisco il concetto di Boyer-Moore, ma avere problemi con la regolazione per sostenere circa. stringa corrispondente (cioè a disadattamento supporto, inserimento, cancellazione).

Anche qual è il più efficace circa. algoritmo di matching stringa (come Boyer-Moore in esatta algo string matching)?

apprezziamo molto Tutta la comprensione / suggerimenti. Molte grazie in anticipo

Answer 1

qui , vedere il primo (Boyer.java) di questa pagina dei risultati

Answer 2

Si potrebbe iniziare con la pagina Wikipedia su approssimativo string matching .

Il problema è che questa è un campo complesso, e semplicemente guardando / copia qualche esempio di codice, probabilmente non vi aiuterà a capire cosa sta succedendo.

Modifica -. E poi, io non vedo come Boyer-Moore sarebbe adattarsi a una ricerca per approssimazione stringa

Answer 3

Questa è la C # Boyer-Più di codice, che può essere tweeked a BMH o corrispondenza approssimativa.

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
        }