C# Algorithmus ähnliche Strings

kiname

Cadet 3rd Year
Registriert
Nov. 2014
Beiträge
56
Hallo,

ihr kennt das Vielleicht das wenn man immer mal wieder ein paar GB neue Musik von Freunden bekommt es immer einige Musiktitel gibt die in der Gesamten Musiksammlung öfters vorkommen.
Dazu will ich nun ein kleines Programm entwickeln, dass durch die ganzen Musikordner durchgeht und Musiktitel mit ähnlichen Namen heraussucht und mir anzeigt. Danach kann ich wählen welches Lied von den gleichen gelöscht werden soll.
Und hier kommt das Problem, denn ich weiß absolut nicht wie ich einen Algorithmus aufstelle der in über 30GB Musik möglichst effizient nach Gleichen Liedern sucht. Dazu muss ich sagen dass die Benennung der Musiktitel jeweils komplett unterschiedlich ist.
Ich nenn mal ein Paar beispiele wie es sein könnte:
05 The Game & Skrillex - "El Chapo"
The Game & Skrillex - El Chapo
El Chapo - The Game ft. Skrillex
The Game & Skrillex - El Chapo (Orginal)
The Game & Skrillex - El Chapo [Orginal Mix]
Skrillex ft. The Game - El Chapo

Es gibt so viele mögliche Konbinationen die ich mit dem Algoritmus abgedeckt werden sollen.
Hat irgendjemand eine Idee wie man das macht?

LG
 
Das was du vor hast ist nicht legal ;) Also dein Vorhaben schon, aber die Lieder sind nicht legal ;)
 
Als erstes würde ich die Daten in eine Datenbank schreiben lassen. Mit der DB kannst Du dann entsprechend arbeiten. Oder halt alle Daten in ein TXT-File schreiben und dann analysieren lassen.

Meine Meinung: kommst um eine Datenbank nicht herum
 
Ich verstehe gerade nicht die Notwendigkeit dafür ein eigenes Programm zu schreiben.

Wieso öffnest du nicht den Datenexplorer und gibst in der Suchleiste den Namen El-Chapo ein, dann zeigt der in deinem Bsp. alle Songs an.
 
Sowas ist leider nur sehr schwer bis gar nicht automatisiert umzusetzen. Machs einfach manuell und lass hier wenigstens nicht so offensichtlich den Raubmordundtotaschlagkopierer raushängen.

Track "Super DJ - Remix A" und Track "Super DJ - Remix B" unterscheiden sich nur durch einen Buchstaben, können aber 2 komplett verschiedene Stücke sein. Sowas wirst du automatisiert nicht behandeln können, bzw. wäre hierfür ein manuelles Eingreifen notwendig - was mich wieder zur ersten Zeile meiner Antwort bringt.

mfg,
Max
 
Mal ein wenig fantasieren:

Ich würde alle Namen einlesen und die Strings in ihre Bestandteile zerlegen. Also alles was durch Blanks oder Trennzeichen getrennt ist.
Das dann in einem großen String-Array ablegen mit einer Zeile pro Datei und einem Namensbestandteil pro Spalte.

Dann eine zweites Array anlegen, dass sowohl in Zeilen und Spalten die Dateien hat und später die gemeinsamen Bestandteile zählt.

Dann über verschachtelte Schleifen jeden Bestandteil der Dateinamen mit jedem anderen vergleichen und bei equal oder contain im Zweiten Array im Schnittpunkt der Dateien mit einen Zähler hochaddieren.

Das würde dann eine Ewigkeit rechnen und am Ende hättest du eine Tabelle, die Dir für jede Datei zeigt, wieviele Namensbestandteile sie mit jeder anderen gemeinsam hat.

Diese Anzahl dann mit der Anzahl der Namensbestandteile des jeweiligen Namens ins Verhältnis setzen und du könntest über Kriterien wie: Likeliness > 90% oder so, Kandidaten identifizieren die höchstwahrscheinlich gleich sind. Die musst du dann halt händisch durchgehen. Da kommst du nicht drum herum. Dein Algorithmus könnte nur helfen, das Feld etwas zu Lichten. Und kann natürlich auch dabei Fehler einbauen.

Vllt alternativ, nicht alle Bestandteile vergleichen, sondern für jeden Bestandteil nur prüfen, ob er im Namen der anderen Datei enthalten ist. Das dürfte besser klappen.
 
Zuletzt bearbeitet:
Vielleicht bringt dich das Stichwort Levenshtein weiter: Levenshtein-Distanz

Zumindest etwas halbautomatisches sollte damit hinzubekommen sein. Man wählt einen Titel aus und bekommt alle anderen Titel, sortiert nach Ähnlichkeit, angezeigt. Wenn sich noch andere Aspekte zum Vergleichen finden lassen, wie z.B. identische Spieldauer, funktioniert es vielleicht auch vollautomatisch.
 
Ich meine mich dunkel zu erinnern, VB hat dafür integrierte Funktionen... dann hat C# die vielleicht auch?
 
Nimm Picard (https://picard.musicbrainz.org/) und lass dir alle Dateien mit Tags versehen. Dann schreib ein kurzes Programm, mit dem du nach Duplikaten gemäß Interpret und Titel suchst. Die lässt du dir als Liste ausgeben und sortierst ab da per Hand weiter. Fertig.
 
dominic.e schrieb:
Das was du vor hast ist nicht legal ;) Also dein Vorhaben schon, aber die Lieder sind nicht legal ;)

legal, illegal, sch**ßegal :-)
Da du nicht weißt, welche Dateien er bekommt, solltest du ihn nicht verurteilen. Ich gehe davon aus, dass es sich um gemeinfreie Werke handelt.
Davon abgesehen hilft ihm deine Antwort nicht weiter.

Btt gibt doch genug tools, die das machen, hier mal willkürlich eines rausgesucht:
http://www.tecchannel.de/storage/tools/2019107/anti_twin_dubletten_dateien_bilder_finden/

fhtagn schrieb:
Vielleicht bringt dich das Stichwort Levenshtein weiter: Levenshtein-Distanz

Zumindest etwas halbautomatisches sollte damit hinzubekommen sein. Man wählt einen Titel aus und bekommt alle anderen Titel, sortiert nach Ähnlichkeit, angezeigt. Wenn sich noch andere Aspekte zum Vergleichen finden lassen, wie z.B. identische Spieldauer, funktioniert es vielleicht auch vollautomatisch.

Hatte ich erst auch daran gedacht, aber da er ja so angenommen >10000 Dateien hat, und man jede mit jeder vergleichen muss, würde das, zumindest bei diesem Ansatz, sehr lange dauern.
 
Zuletzt bearbeitet:
Hast du was dagegen, eine text Datei mit allen Dateien hochzuladen?
Ich würde das gerne selbst mal programmieren.
 
Es gibt hier 2 methoden. Wie schon fhtagn sagte ist die Levenshtein-Distanz ein guter Anfang http://stackoverflow.com/a/2344347.

Die zweite Methode wäre jedes Audio file decoden und das Wave-Muster vergleichen (wenn du das implementierst, möchte ich bitte dein Programm haben^^)
 
Code:
    internal class Program
    {
        public static void Main(string[] args)
        {
            string[] strings =
            {
                "The Game & Skrillex - El Chapo",
                "El Chapo - The Game ft. Skrillex",
                "05 The Game & Skrillex - \"El Chapo\"",
                "The Game & Skrillex - El Chapo (Orginal)",
                "The Game & Skrillex - El Chapo [Orginal Mix]",
                "Skrillex ft. The Game - El Chapo"
            };

            foreach (var s in strings)
            {
                Console.WriteLine(Simplify(s));
            }
            Console.WriteLine();
            Console.ReadKey(true);

            for (var i = 0; i < strings.Length; i++)
            {
                for (var j = 0; j < strings.Length; j++)
                {
                    if (i == j)
                        continue;

                    Console.WriteLine(Compute(Simplify(strings[i]), Simplify(strings[j])));
                }
            }

            Console.ReadKey(true);
        }

        public static string Simplify(string s)
        {
            string[] removes = {"ft.", "feat", "-", "&", "(", ")", "[", "]", "orginal", "mix", "\""};

            var temp = s.ToLower();

            foreach (var remove in removes)
                temp = temp.Replace(remove, "");

            var split = temp.Split(' ');
            Array.Sort(split);
            return string.Join("", split);
        }

        public static int Compute(string original, string modified)
        {
            if (original == modified)
                return 0;

            var lenOrig = original.Length;
            var lenDiff = modified.Length;

            if (lenOrig == 0)
                return lenDiff;

            if (lenDiff == 0)
                return lenOrig;

            var matrix = new int[lenOrig + 1, lenDiff + 1];

            for (var i = 1; i <= lenOrig; i++)
            {
                matrix[i, 0] = i;
                for (var j = 1; j <= lenDiff; j++)
                {
                    var cost = modified[j - 1] == original[i - 1] ? 0 : 1;
                    if (i == 1)
                        matrix[0, j] = j;

                    var vals = new[]
                    {
                        matrix[i - 1, j] + 1,
                        matrix[i, j - 1] + 1,
                        matrix[i - 1, j - 1] + cost
                    };
                    matrix[i, j] = vals.Min();
                    if (i > 1 && j > 1 && original[i - 1] == modified[j - 2] && original[i - 2] == modified[j - 1])
                        matrix[i, j] = Math.Min(matrix[i, j], matrix[i - 2, j - 2] + cost);
                }
            }
            return matrix[lenOrig, lenDiff];
        }
    }

Bleibt die Frage, was es bei tausenden von Dateien ausgibt..
 
Zurück
Oben