Beispiel-Java-Code für approximate String-Matching oder Boyer-Moore verlängert, um ungefähres String-Matching

Question

Ich brauche 1.mismatch zu finden (falsch gespielte Noten), 2.insertion (zusätzliche gespielt), & 3.deletion (verpasste Noten), in einem Musikstück (zB Tonhöhen [string Werte] in einer Tabelle gespeichert) gegen ein Referenzmusikstück.

Dies ist möglich, entweder durch genaue String-Matching-Algorithmen oder dynamischen Programmierung / ungefähre String-Matching algos. Ich erkannte jedoch, dass ungefähre String-Matching für mein Problem angemessenere ist auf die Identifizierung Mismatch, Insertion, Deletion von Noten. Oder eine erweiterte Version von Boyer-mooren ca. zu unterstützen. String-Matching.

Gibt es einen Link für Probe Java-Code I ungefähres String-Matching ausprobieren kann? Ich finde komplexe Erklärungen und Gleichungen - aber ich hoffe, dass ich mit einigem Beispielcode und einfachen Erklärungen gut tun könnte. Oder kann ich jede Probe Java-Code finden auf Boyer-moore ca. erweitert. String-Matching? Ich verstehe das Boyer-Moore-Konzept, aber mit Schwierigkeiten damit Anpassung ca. zu unterstützen. String-Matching (d.h. zu Unterstützung Mismatch, Einfügen, Löschen).

Auch was ist die effizienteste ca.. String-Matching-Algorithmus (wie Boyer-Moore-in algo genauem String-Matching)?

schätzen keine Einsicht / Anregungen. Vielen Dank im Voraus

Answer 1

hier finden Sie in der ersten (Boyer.java) dieser Ergebnisseite

Answer 2

Sie können mit der Wikipedia-Seite beginnen auf ungefähr String-Matching .

Das Problem ist, dass diese is ein komplexes Feld, und einfach betrachten / Kopieren einige Beispiel-Code wahrscheinlich werden Sie nicht helfen, zu verstehen, was los ist.

Bearbeiten -. Außerdem, ich sehe nicht, wie Boyer-Moore ungefähres String-Matching anpassen würden

Answer 3

Hier ist der C # Boyer-More-Code, der auf BMH oder ungefähre passende tweeked werden kann.

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
        }