Die Vision eines intelligenten Mediaplayers...

[Mithrandir]

Ich finde, dieser Beitrag gehört nicht in K&T, weil er ja doch definitiv was mit Programmierung zu tun hat. :) Außerdem ist er recht lang. Es könnte passieren, dass ihr während des Lesens einschlaft. Sorry schonmal dafür. :D

Ich hab heute mal aus reinem Interesse die Vita vom Facebook-Mitbegründer Mark Zuckerberg gelesen. Da fand sich unteranderem ein kleiner Satz über Synapse, einen Mediaplayer den Mark zusammen mit Adam D'Angelo geschrieben hat. Irgendwann ist dieser (= der Player) aber in der Versenkung verschwunden, vermutlich, weil er grad an nem Webprojekt gearbeitet hat... :zwinker:

Ich finde jedenfalls die Idee dahinter nicht schlecht, und stelle mir dabei sowas wie eine "intelligente Shuffle-Funktion" vor.

Man kennt das ja. Wenn man die Shufflefunktion seines Mediaplayer nutzt, werden einem zufällig Songs präsentiert. Im Regelfall ist man, gerade bei großen Datenbanken, dann aber eher damit beschäftigt, den Song zu skippen, weil man bspw. nachm Soundtrack von Inception gerade keinen Bock auf die Schmusestimme von James Blunt hat. Wie umgeht man das Problem heutzutage meist? Man erstellt sich Playlists, vielleicht nach Stimmung sortiert, vielleicht nach Künstlern oder Genres. Im Regelfall skippt man aber einfach weiter und nimmt es so hin, denn eigentlich hat man für die Erstellung von Playlists auch keine Zeit. Was könnte man dagegen tun?

Zum einen könnte man gucken, wie oft welche Lieder abgespielt werden. Das mag zwar hilfreich sein, ändert aber nichts daran, dass, wenn ich mir bspw. James Blunt anmache, weil ich gerade in einer traurigen Stimmung bin, ich nun keinen Bock auf Iron Maiden habe, auch wenn es die Tage davor rauf und runterlief, und entsprechen oft gespielt wurde.

Wie wäre es aber, wenn der Mediaplayer in der Lage wäre, zu erkennen, was wir in welcher Stimmung hören wollen und welche Lieder zusammenpassen? Nehmen wir an, wir haben die Lieder A,B,C,D,E,F...Z. Wenn der Player jetzt intelligent wäre, könnte er während der Benutzung dazu lernen. Um einen Startpunkt zu haben, analysiert man erstmal die BPM aller Lieder. Da das bei einer großen Datenbank entsprechen lange dauern wird, kann man dies im Hintergrund tun. Ist man fertig, hat man schonmal ein paar Verknüpfungspaare. So weiß man bspw, dass die Lieder A-E, J-L und X-Z alle im selben BPM Bereich sind, bspw. 120. Es wäre also eine gute Idee, wenn Lied D abgespielt wird, dann im Shuffle Modus ein Lied aus den Blöcken J-L oder X-Z zu benutzen.

Und jetzt kommt der User ins Spiel. Es geht dann darum, Verknüpfungen zwischen den einzelnen Liedern aufzubauen. Wenn der User Lied A spielt, dann Lied C und dann Lied I (und zwar bewusst dahinspringt), dann kann man als Programm davon ausgehen, dass die Lieder für den User eine Einheit bilden. Kommt dies häufiger vor, wird die Bindung zwischen den einzelnen Liedern immer stärker.

Im Prinzip würde die Anforderung an den Player lauten: "Erinnere dich daran, was ich als nächstes gehört habe. Wenn du mir die Lieder liefern sollst, dann erinnerst du dich an meine Auswahl." Denn wenn man mal in sich geht und überlegt, dann weiß man selbst eigentlich immer am Besten, welche Lieder zueinander passen und welche nicht.

Natürlich kann man die Liedgruppen nicht isoliert betrachten. Es könnte bspw sein, dass Lied R nach Lied X und nach Lied A fast gleichoft gehört wurde. Diese Tatsache könnte man aber auch geschickt nutzen, in dem man die Liedgruppen A,C,I und X-Z über das Lied R miteinander verknüpfen könnte, quasi als geschickter Übergang.

Natürlich gibt es noch andere Sachen, die man bedenken muss. Bei so einem System hätten neue Lieder, die neu in die Liste geladen werden, ein Problem. Dem könnte man entgegenwirken, in dem die Bindungen über die Zeit wieder schwächer werden, sodass auch neue Songs die Chance haben, in das System eingebunden zu werden. Außerdem sollte es bspw. bei der Gruppe A,C,I egal sein, in welcher Reihenfolge sie gespielt werden.

Jetzt gibt es nur eine technische Überlegung: Wie setzt man sowas am geschicktesten um? Über ein System ähnlich neuronaler Netze? Und wie speichert man die Verbindungen zwischen den einzelnen Liedern ab. Fragen über Fragen... Und eure Ideen sind mir dazu Willkommen. Mein ihr, sowas wäre sinnvoll?

[Teekeks]

Die Idee finde ich schon einmal total interessant.
Die Wichtigskeitsverknüpfungen (was für ein Wort :lol: ) könnte man ja so aufbauen (nur eine verknüpfung):

Code:

 Track1: integer (die ID des ersten Titels)
 track2: integer (die ID des zweiten Titels)
 Wichtigkeit: integer

Die Wichtigkeit könnte immer höher werden je öfter diese Verknüpfung auftritt.
Die Zeitabhängigkeit könnte z.B. darüber entstehen das man z.B. einmal die Woche oder so da über alle Verknüpfungen ein *2/3 oder ähnliches über die Wichtigkeiten drüber jagt.

Der Nachteil wäre das mit der Zeit ein wirklich gigantischer Baum an Daten entstehen würde.

Das wäre ja im schlimmsten Fall (n-1)^n Verknüpfungen, was bei z.B. nur 1000 Titeln schon 1E+3000 Datensätze wären (gut, es fallen noch ein paar raus weil die ja nicht mit sich selbst verknüpft werden können).

An sich aber eine Idee die man weiter verfolgen sollte (vl als ein Community-Projekt?).

Gruß Teekeks

[BUG]

Ich glaube neuronale Netze liegen nur vom Namen (Netze) her nahe.

Man kann eine solches Netzwerk als Graph darstellen.

Die Lieder sind Knoten.
Die Beziehungen sind (evtl. gerichtete, mehrfache) gewertete Kanten.

Das Finden einer passenden Lieder für eine Playlist könnte man als das Finden eines Teilgraphs darstellen, ein dem die Kanten bestimmte Werte haben haben.

Das Konkretisieren dieser Vorstellung ist vermutlich der größter Teil der eigentlichen Arbeit, eine vermutlich anderer großer Teil das anschließende Finden der Algorithmen zum Finden des Teilgraphs.

[Assarbad]

Mir ist so als hätten sowohl iPod als auch iTunes das eingebaut. Da geht es, wenn ich mich recht entsinne nach Genre und man kann ein Lied auch als "Favorit" markieren. Dann wird es auch bei zufälliger Abspielfolge öfter gespielt. Das ist doch was du meinst, oder?

[Teekeks]

Lese die bitte das von Mithandir bitte noch einmal durch, genau das möchte er halt nicht, sondern das der Player durch das verhalten des Nutzers dazulernt was derjenige gut findet.
Also nicht über das Genre gehen, sondern über die Erfahrung des Players, welchen Titel der Nutzer nach diesem und jenen eigentlich gerne hört oder welcher der Erfahrung nach da an dieser Stelle jetzt gut passen würde.

[Mithrandir]

Zitat:

Zitat von Assarbad (Beitrag 1054945)

Mir ist so als hätten sowohl iPod als auch iTunes das eingebaut. Da geht es, wenn ich mich recht entsinne nach Genre und man kann ein Lied auch als "Favorit" markieren. Dann wird es auch bei zufälliger Abspielfolge öfter gespielt. Das ist doch was du meinst, oder?

Ich bin mir nicht so sicher, ob Genius wirklich das ist, was ich meine. Ich werde mir das aber nochmal genauer ansehen.

@Teekeks und BUG: Gute Ansätze, ich werde sie mal weiterverfolgen. :) Aber es stimmt, man wird vermutlich mit riesigen Datensätzen konfrontiert werden. ;)

[Assarbad]

Zitat:

Zitat von Teekeks (Beitrag 1054947)

Lese die bitte das von Mithandir bitte noch einmal durch, genau das möchte er halt nicht, sondern das der Player durch das verhalten des Nutzers dazulernt was derjenige gut findet.
Also nicht über das Genre gehen, sondern über die Erfahrung des Players, welchen Titel der Nutzer nach diesem und jenen eigentlich gerne hört oder welcher der Erfahrung nach da an dieser Stelle jetzt gut passen würde.

Also nochmal lese ich mir den langen Aufsatz nicht durch. Einerlei, ich denke daß eine Bestimmung von Genre oder ob man ein Lied "mag" oder "nicht mag" einige Metadaten voraussetzt. Entweder in den Dateien selbst oder eben extern. Wenn man so will muß die Distanz (also die Länge eines Vertex) der "Nähe" der Lieder entsprechen. Aber da diese Nähe sehr subjektiv ist, muß man eben auf Metadaten zurückgreifen und diese ggf. je nach Benutzer anders wichten.

Zitat:

Zitat von Mithrandir (Beitrag 1054949)

Ich bin mir nicht so sicher, ob Genius wirklich das ist, was ich meine. Ich werde mir das aber nochmal genauer ansehen.

Stimmt, das war der Name. Eine Wichtung wird dort meines Wissens nach auch vorgenommen. Und BUG hat ja einen gewichteten Graphen vorgeschlagen.

Zitat:

Zitat von Mithrandir (Beitrag 1054949)

Aber es stimmt, man wird vermutlich mit riesigen Datensätzen konfrontiert werden. ;)

Da kann ich nur SQLite empfehlen ;)

[omata]

Die Idee hatte ich auch schon. Ist auch schon im Einsatz. Macht nicht genau das was du dir vorstellst, ist aber vom Anspruch ähnlich. klick

[Mithrandir]

@omata: Danke für den Hinweis, werde ich mir ansehen. :thumb:

@Assarbad: Die einzigen Metadaten für den Einstieg wären tatsächlich nur die ID3-Tags bezgl. Genre, Künstler und die BPM, die ein Song aufweist. Auf Basis dessen würde ich einen Graphen erstellen, mit eben unterschiedlich gewichteten Verbindungen. Der Rest ist erstmal Sache des Users. Ggf. könnte man mit der Zeit diverse Muster versuchen zu finden, die einem helfen, neu hinzugefügte Lieder besser einzuordnen. Aber das ist weite Zukunftsmusik. Interessant ist noch die Überlegung, wie ich diesen Graphen auf die Datenbank abbilde (SQLite ist schon in Verwendung. :) ).

Genius scheint tatsächlich eine ähnliche Methode zu verwenden. Allerdings müssen hier die Daten an einen Server geschickt werden. Das soll bei mir nicht der Fall sein, zumal nichtmal die Infrastruktur dafür vorhanden wäre.

[Hisoka]

Solch eine Funktion wird in den Meisten Music Playern über Last.fm und ähnliche Dienste gemacht. Denn diese haben solche Beziehungen schon analysiert und es klappt auch. Zumindest schlägt mir der Player immer ganz vernünftige Bands vor.

Also alles nichts neues ;)

Aber die Umsetzung über ein Neuronales Netz wäre eine nette Bastelei.

[omata]

Habt ihr eigentlich schon mal darüber nachgedacht was ihr das so schreibt?

Bei einem neuronalen Netz ist eine Lernphase nötig. Wann soll diese durchgeführt werden?
Bei einem Backpropagationnetz wird kontrolliertes Lernen angewendet. Ein Kohonennetz lernt zwar selbst aber wie wollt ihr das dann interpretieren?

Was sollen die Eingangs- und was die Ausgangssynapsen sein?

Siehe auch mein Backpropagation-Netz.

Ein Kohonennetz habe ich auch mal realisiert, aber hier nicht veröffentlicht.

Also Graphen mit gerichteten Kanten ist wohl die bessere Variante.

[Hisoka]

Zitat:

Zitat von omata (Beitrag 1055118)

Habt ihr eigentlich schon mal darüber nachgedacht was ihr das so schreibt?

Bei einem neuronalen Netz ist eine Lernphase nötig. Wann soll diese durchgeführt werden?
Bei einem Backpropagationnetz wird kontrolliertes Lernen angewendet. Ein Kohonennetz lernt zwar selbst aber wie wollt ihr das dann interpretieren?

Was sollen die Eingangs- und was die Ausgangssynapsen sein?

Siehe auch mein Backpropagation-Netz.

Ein Kohonennetz habe ich auch mal realisiert, aber hier nicht veröffentlicht.

Also Graphen mit gerichteten Kanten ist wohl die bessere Variante.

Daher fällt das ganze ja auch unter die Kategorie "Interessante Idee ohne Plan". Also die Idee ein NN für sowas zu nutzen ist ja recht interessant, nur wie man sowas umsetzt ist etwas anderes.

An sich ist ein Problem ja der Anfang. Man hat keine Vergleichsdaten. Also man muss dem Netz erstmal beibringen was zu einander passt( "Like button", "ähnlich button",...) und mit den Ergebnissen könnte man dann ein Netz füttern und dann auf unbekannte Lieder los lassen. Ob das Ganze aber zufriedenstellend funktioniert ist eine andere Sache. Dazu kommen ja noch Sachen wie das zu viel lernen(auswendig lernen), dadurch kann das Ergebnis vielleicht für eine kurze Zeit sehr gut sein aber dann wenn man neue Musik erwirbt kann es total versagen.

Aus der Praxis heraus würde ich daher doch eher einen fertigen Dienst wie Last.fm einbinden. Aber das wäre dann weniger interessant. ;)

[Mithrandir]

Ich hab mal einen kleinen Test gemacht, und ich glaube, ich weiß, warum dieses Feature noch kein Player implementiert hat.

Gehen wir davon aus, dass wir 5000 Lieder auf der Festplatte haben (jahrzehntelange Sammelwut). Baut man für die Initialisierung einen Graphen auf, bei dem jedes Lied mit jedem eine Verknüpfung hat, so kommt man auf die niedliche Datenmenge von insgesamt 25.000.000 Verbindungen. Das bedeutet, dass ich, halte ich diese Menge im Speicher vor, einen Speicherverbrauch von über eine Gigabyte habe. Serialisiere ich meine Liste in eine XML-Datei, ist diese 2,8 Gigabyte groß. Das Hauptproblem ist also weniger die Rechenleistung, sondern eher die riesigen Datenmengen, die anfallen.

Freiwillige bitte zuerst melden, die hier einen Lösungsvorschlag hätten. :)

[Teekeks]

Den Baum nicht im Speicher halten sondern nur dann das passende (aus der DB) laden wenn es gebraucht wird.

[Mithrandir]

Es geht mir auch mehr um die Gesamtdatenmenge. Versuch mal, dem User zu erklären, dass er für seine 5000 Lieder eine Indexdatei mit 3 GB braucht. :mrgreen:

Ich teste das gerade mit SQLite durch... Sollte ja mindestens um den Faktor 10 kleiner werden, wenn ich richtig gerechnet habe. Das ginge ja noch... Ggf. könnte man auch sehen, dass man von vornherein nur die Wahrscheinlichsten Verknüpfungen zulässt, und das Programm dann später eigenständig neue Verknüpfungen hinzufügt...

[Medium]

Nimm statt XML ein ordentliches, natives Format ;). Geht man von sortierten Daten aus, brauchst nu nichtmal mehr Strukturinformationen, und kannst die Bindungsstärken einfach so der Reihe nach auf die Platte streamen. Drückt man die einfach mal in Bytes aus, erscheinen 25MB schon garnicht mehr so fies. Koppel das mit einem einigermaßen sinnvollen read-ahead Algo, und du musst das auch nicht am Stück im Speicher halten.

[jfheins]

Du kannst einen Graphen (fast immer) auch als Matrix darstellen.

In diesem Beispiel also eine 5000x5000 Matrix (wenn jedes Element ein Byte hat, ist das nicht mal allzu groß) und ein Wert stellt dann dar "wie doll" die beiden Lieder (Zeile/Spalte) zusammenhängen. Also z.B. -128 = gar nicht 0=neutral, 127 = quasi identisch
Da diese Zuordnung symmetrsich ist, brauchst du auch nur die Hälfte der Einträge. Wären also 12,5 Megabyte ;)

Und wenn du dann das nächste Lied spielen sollst, gehst du einfach alle Lieder durch, ermittelst die "Ähnlichkeitskomponente" und (nur als Beispiel) nimmst diese als Wahrscheinlichkeit und wählst zufällig eins aus. (Ähnliche Lieder werden wahrscheinlicher ausgewählt als fremde)

[Medium]

Da hatter wahr :). Find's immer schmerzhaft zu sehen, wenn diese XML/DB-Euphorie so simple schlanke Dinge vom Platz der "ersten Einfälle" verdrängt :stupid:

[Sir Rufo]

Es geht noch kleiner wenn man möchte

Stellt man die Beziehungen jetzt auf einer virtuellen Erdkugel dar mit Längen- und Breitengrad, dann brauche ich pro Lied 2 Werte die je nach gewünschter Auflösung nur 5000x2xBewertungsauflösung benötigen
Bei 1Byte sind das gerade mal 10kByte.

(außer acht gelassen haben bislang den Index auf den Titel, der mindestens 2Byte groß sein sollte)

Wären in diesem Falle mit Index also 20kB
Die Matrix-Variante benötigt pro Eintrag 2+2+1 Byte und das genau 4999*5000/2 mal ergibt 59,59MB

Ein weiteren Vorteil wäre die Auswahl der betroffenen Lieder. Einfach alles, was in einem entsprechenden Radius um einen Punkt ist gehört dazu.

Die Errechnung der Koordinaten ist allerdings aufwendiger, weil jedes hinzugefügte Lied alle anderen auf der Kugel wieder verschiebt

[BUG]

Zitat:

Zitat von Sir Rufo (Beitrag 1055157)

Die Errechnung der Koordinaten ist allerdings aufwendiger, weil jedes hinzugefügte Lied alle anderen auf der Kugel wieder verschiebt

Und um das ordentlich zu machen, braucht man evtl. wieder die Beziehungen der Lieder?

Ist interessant, dass alle am Speicherplatz herumrechnen, bevor überhaupt feststeht, wie genau die Daten aussehen, die gespeichert werden sollen/müssen.
Zum Beispiel eignet sich die Matrix besonders dann, wenn es (sehr) viele Kanten gibt. Die Vereinfachung mit "nur die Häfte speichern" geht nur mit ungerichteten Graphen.

Imho braucht man im experimentellem Stadium ja auch nicht mit 5000 Liedern anfangen und dann wären auch größere große Indices zu verkraften.
Bits knausern kann man dann später, wenn man weiß, wie die Daten aussehen.

[Sir Rufo]

Ja, wie beim Aufbau der Matrix muss man die Ähnlichkeit zu jedem Lied ermitteln und dann in die Koordinaten umrechnen.

Mögliche Auswertungskriterien wären (mal gebrainstormt)
- frequenzspektrum (von n Frequenzbereichen die prozentualen Werte ermitteln)
- Dynamikänderungen (laut-leise Wechsel)
- USW.

[Assarbad]

Zitat:

Zitat von Mithrandir (Beitrag 1055138)

Ich hab mal einen kleinen Test gemacht, und ich glaube, ich weiß, warum dieses Feature noch kein Player implementiert hat.

Gehen wir davon aus, dass wir 5000 Lieder auf der Festplatte haben (jahrzehntelange Sammelwut). Baut man für die Initialisierung einen Graphen auf, bei dem jedes Lied mit jedem eine Verknüpfung hat, so kommt man auf die niedliche Datenmenge von insgesamt 25.000.000 Verbindungen. Das bedeutet, dass ich, halte ich diese Menge im Speicher vor, einen Speicherverbrauch von über eine Gigabyte habe. Serialisiere ich meine Liste in eine XML-Datei, ist diese 2,8 Gigabyte groß. Das Hauptproblem ist also weniger die Rechenleistung, sondern eher die riesigen Datenmengen, die anfallen.

Poste mal das aktuelle DB-Schema. Und nebenbei: riesige Datenmengen implizieren meist auch mehr erforderliche Rechenleistung. Man kann das minimieren, aber generell besteht da schon eine Beziehung.

Und laß ab von diesem XML-Fanatismus. XML hat seine Anwendungsbereiche, aber bei der Datenspeicherung sehe ich die absolut nicht. Denn im Gegensatz zu bspw. SQLite ist deine XML-Datei am A.... wenn sich zwischendrin das Programm verabschiedet. Dann validiert die XML nicht mehr weil diverse Tags nicht geschlossen wurden ... naja :roll:

Zu den bisherigen Antworten fällt mir auf, daß sie alle den Spaß etwas zu stark vereinfachen. Denn der Abstand für "Genre" mag X betragen, kann aber für "Stimmung" schon wieder Y sein. Bsp.: Oper und Requiem. Und um eine sinnvolle Wertung vorzunehmen muß mehr als ein Merkmal gewichtet werden.

Ergänzung:

Zitat:

Zitat von Sir Rufo (Beitrag 1055161)

Ja, wie beim Aufbau der Matrix muss man die Ähnlichkeit zu jedem Lied ermitteln und dann in die Koordinaten umrechnen.

Mögliche Auswertungskriterien wären (mal gebrainstormt)
- frequenzspektrum (von n Frequenzbereichen die prozentualen Werte ermitteln)
- Dynamikänderungen (laut-leise Wechsel)
- USW.

Bin mir nicht sicher, daß Beethovens 9te da so anders abschneiden würde als manch "moderne" Musik. Abgesehen davon wäre das ein schutzwürdiger Aufwand, denn sobald sowas gelöst ist (ich entsinne mich einer Meldung auf Heise über ein Programm welches vorgespielte Lieder in Noten übersetzt), kann man auch eine Musiksuchmaschine bauen bei der der Suchende ins Mikrofon pfeift und dann ähnliche Titel angeboten bekommt die er dann kaufen darf. Und nun ratet mal warum iTunes usw. das noch nicht haben ;)

[mkinzler]

Zitat:

Und nebenbei: riesige Datenmengen implizieren meist auch mehr erforderliche Rechenleistung.

Das sollte für ein gescheites DBMS nicht gelten

@Bug: Eine Aufwandsanalyse ist imho wichtig. Sieht man am Anfang schon ein Problem, welches die Realisierung beeinträchtigen/verhindern könnte, wäre es fahrlässig dieses einfach auszublenden

[BUG]

Zitat:

Zitat von mkinzler (Beitrag 1055230)

@Bug: Eine Aufwandsanalyse ist imho wichtig. Sieht man am Anfang schon ein Problem, welches die Realisierung beeinträchtigen/verhindern könnte, wäre es fahrlässig dieses einfach auszublenden

Natürlich ist es wichtig, das man sich im Klarem darüber ist, dass der Index eventuell sehr groß wird.
Allerdings ist es sinnlos, jetzt darüber zu diskutieren ob der Index bei 5000 Liedern bei 20kB, 2MB oder 200 MB liegt.

Man könnte sich zum Beispiel überlegen, dass, wenn man am Anfang alle Lieder mit gleichem BPM verknüpft, man bereits am Anfang sehr viele Kanten hat.
Damit könnte es tatsächlich klug sein, gleich eine Matrix zu nehmen. Allerdings muss man dann in Kauf nehmen, dass bei Hinzufügen eines Liedes der Speicherbedarf quadratisch mit der Anzahl der Knoten steigt.
Wenn die Kanten nach und nach hinzugefügt werden, wäre es dann eventuell besser, eine andere Darstellung zu wählen und das Organisieren der Daten zB. SQLite zu überlassen.

Letztlich gewinnt man bei dieser Überlegung nicht viel, wenn sie am Anfang steht. Wenn die Kantenwerte genau so groß sind wie die Knotenbezeichner (und das wäre dann vermutlich wenig), dann kostet die Speicherung aller möglichen Kanten in einem Graphen als Matrix nur ca. 1/3.
Das ist doch kein so großartiger Faktor, zumal wir noch nicht wissen, wie die Anzahl der Kanten von der Anzahl der Knoten abhängt.

Allein um jedes Lied nach jedem anderem zu anzuspielen (und nach 3 Sekunden weiterzuskippen, ohne Pause) bräuchte man ca. 2,4 Jahre.
Das heißt wenn man die Anzahl der anfänglichen Kanten nicht so hoch setzt, wird sehr lange dauern, bis alle Kanten gesetzt sind.

[Teekeks]

Zitat:

Zitat von BUG (Beitrag 1055283)

Allein um jedes Lied nach jedem anderem zu anzuspielen (und nach 3 Sekunden weiterzuskippen, ohne Pause) bräuchte man ca. 2,4 Jahre.
Das heißt wenn man die Anzahl der anfänglichen Kanten nicht so hoch setzt, wird sehr lange dauern, bis alle Kanten gesetzt sind.

OT:
Falsch:
5000 Lieder * 3sekunden= 15000s

15000s/60s=250m
250m/60m=4,17h

Also ein bisschen über 4 Stunden und nicht 2,4 Jahre...

Aber BTT...

[Sir Rufo]

Er meint alle liedkombinationen

[Assarbad]

Zitat:

Zitat von mkinzler (Beitrag 1055230)

Das sollte für ein gescheites DBMS nicht gelten

Mir scheint du verwechselst DBMS und Implementation. Selbst das DB-Schema spielt eine sehr wichtige Rolle bei der Effizienz der Datenbank. Im Grunde sollten sich ansonsten DBMS nicht großartig unterscheiden.

Hingegen ein richtig oder falsch gesetzter Index kann deutliche Einbußen der Performance hervorrufen.

Das Schema haben wir bisher allerdings nichtmal auszugsweise gesehen :lol:

[Mithrandir]

Hui, da lässt man euch einmal alleine diskutieren... :shock:

Ich habe mir Folgendes überlegt:

Die Gewichtung einer Kante hat die Größe eines Byte, ich habe also 256 Werte. Das ermöglicht in meinen Augen eine recht feine Abstimmung.

Gehen wir davon aus, dass der User eine Sammlung von 100 Liedern hat. Meine Idee ist, die Lieder zu Beginn in einzelne Gruppen (nennt es meinetwegen Teilgraphen) zu organisieren. Hier bin ich noch am Überlegen, welche Gemeinsamkeit geschickt wären. Selber Künstler? Gleiches Album? Ähnliche Beats per Minute?

Angenommen, ich habe jetzt eine Vorauswahl treffen können. Ich gruppiere alle Lieder aus demselben BPM-Bereich. Jetzt verknüpfe ich alle Lieder untereinander, die in derselben Gruppe sind. Die Songs werden dabei so verknüpft, dass das Gewicht auf 0 gesetzt wird (Oder -127, wenn man annimmt, dass das Byte vorzeichenbehaftet ist). Es sind also alle Verbindungen gleichberechtigt. Die Richtung spielt keine Rolle. Das ist der Ausgangspunkt für alle Kanten. Zwischen einzelnen BPM-Gruppen wird noch keine Verbindung erstellt. Jetzt könnte man nach Gemeinsamkeiten im BPM-Block gucken. Bspw. Lieder, die denselben Interpreten haben, oder vom selben Album sind. Hier könnte man das Kantengewicht entsprechend erhöhen.

Jetzt kommt der User ins Spiel. Er hört Song A aus dem BPM-Block 100. Als nächstes käme Song B, dieser wird aber bewusst übersprungen, und es wird C ausgewählt. Jetzt müsste das Programm das Gewicht der Kante A-C erhöhen, denn der User empfindet eine gewisse Bindung zwischen A u. C. Umgekehrt sollte die Bindung zwischen A-B verringert werden, denn dies hat der User übersprungen.

Der Graph ist richtungslos, denn ob ich nun A nach C spiele, oder umgekehrt, sollte im Regelfall eigentlich kein Problem sein. Jetzt ist der User aber ein merkwürdiges Wesen, und findet bspw, dass das Lied aus dem BPM-Block 140 gut nach Lied C kommen könnte. Das führt dazu, dass zwischen dem Block 140 BPM und 100 BPM eine Bindung entsteht, welche in Zukunft als Übergang von 100 nach 140 genutzt werden kann. Da der User diese Bindung selbst erstellt hat, bekommt sie eine höhere Wertung als programmatisch erstellte Bindungen.

Ziel ist also, dass der User den größten Einfluss auf das hat, was das Programm an Zusammenhängen ermittelt. Natürlich kann man überlegen, ob man nicht guckt, wie man die Daten des Users nutzen kann. Denkbar wäre auch eine Liste alà "Vielleicht möchten Sie als nächstes XYZ hören?". Darüber könnte man nachdenken.

Auch müsste zu jedem Knoten ein Timestamp gespeichert werden. So könnte man bspw auch Knoten mal wieder hervorholen, bei denen die letzte Wiedergabe schon länger als X her ist. Oder man verringert die Gewichtung nach einem bestimmten Zeitraum, damit man nicht immer nur denselben Kram hört. ;)

Die Größe der Indexdatei ist in meinen Augen schon ein wichtiger Faktor. Ich meine, wir haben mittlerweile Festplatten im 1 - 2 Terabyte Bereich. Lasst aber mal n Programm mehr Platz als 50 Megabyte belegen. Dann wird Sodom und Gomorrha gebrüllt. Insofern ist der Faktor nicht unwesentlich, auch wenn ich zugeben muss, dass 5000 Lieder schon viel sind. Aber eben nicht unwahrscheinlich. ;)

Assarbad, meine Tabellenstruktur war recht einfach:

SQL-Code:

CREATE TABLE IF NOT EXISTS edges ( id INTEGER NOT NULL PRIMARY KEY AUTOINCREMENT, FirstSong INTEGER NOT NULL, LastSong INTEGER NOT NULL, stLikeIndex DOUBLE NOT NULL, stTimestamp DATETIME);

[Sir Rufo]

Die Platten sind durchaus größer geworden und der Speicherplatz damit quasi vernachlässigter, aber was ist mit dem Zugriff auf diese Daten?

Da ist kleiner halt schneller

[Mithrandir]

Man könnte am Anfang der Daten eine Art Index einfügen - was aber wieder mehr Speicherplatz bräuchte. :)

[Assarbad]

Zitat:

Zitat von Mithrandir (Beitrag 1055403)

Assarbad, meine Tabellenstruktur war recht einfach:

SQL-Code:

CREATE TABLE IF NOT EXISTS edges ( id INTEGER NOT NULL PRIMARY KEY AUTOINCREMENT, FirstSong INTEGER NOT NULL, LastSong INTEGER NOT NULL, stLikeIndex DOUBLE NOT NULL, stTimestamp DATETIME);

Hmm, also nur eine Tabelle. Und das Datum ist das Dateidatum oder Datum der letzten Aktualisierung des Vertex oder Datum der Erstellung des Vertex?

Ich habe nur zwei Probleme damit: 1.) du reduzierst alles auf eine Dimension (kann gehen, kann aber auch danebengehen) und 2.) bleibt das eigentliche Problem unangetastet. Ich denke du solltest SQL benutzen um die Relationen zu ermitteln, nicht nur um sie zu speichern, wenn du verstehst was ich meine.

Ein Index auf einen numerischen Wert ist lächerlich klein. Laß mich dir ein Beispiel geben, weil ich daran erst letztens gearbeitet habe. Wir haben eine Engine die auf 16 verschiedenen Plattformen läuft. Zu den Plattformen kommt dann noch die "Pseudo-Plattform" "alte Engine" (auf einer beliebigen Architektur/OS). Nun haben wir eine bestimmte vordefinierte Menge an Dateien die gutartig, bösartig, in der Grauzone oder unklassifiziert sind. Zwischen den Engine-Versionen sollen selbstverständlich Fehler behoben werden, aber keine Detections verlorengehen. Also muß man die Ergebnisse unseres Kommandozeilenscanners erstmal herunterbrechen. Das geschieht damit, daß ein Perlskript alle Ergebnisse in Einzelteile (Tokens) zerlegt. Diese Einzelteile werden in eine Datenbank eingepflegt (auch SQLite) in der bereits eine Tabelle mit Dateien und eine mit Verzeichnissen existiert. Jedes Verzeichnis hat einen Namen und eine eindeutige Zahl. Grob gesagt hat jede Datei einen Namen und ein Verzeichnis (referenziert die Zahl in der Verzeichnistabelle) sowie eine eindeutige Zahl. Bei mehreren Hunderttausend Dateien in mehreren Zehntausend Verzeichnissen bringt das eine erste Speicherplatzersparnis. Außerdem gestaltet es den Lookup sehr einfach, denn bis zu dem Zeitpunkt wo ich bspw. den Namen der Datei für einen Benutzer anzeigen muß, kann alles über die eindeutigen Zahlen abgewickelt werden. Diese Entscheidung zieht sich denn auch durch alle Tabellen. Dateien können bspw. Objekte enthalten (bspw. gepackte Dateien) und die Namen dieser Objekte sind dann ebenfalls über eine eindeutige Zahl erreichbar. Wann immer ein Ergebnis eine Datei oder ein Objekt innerhalb der Datei usw. referenziert, wird nur eine Zahl gespeichert. Das ist auch bei riesigen Datenmengen sauschnell. Wenn pro Tabelle dann der Index strategisch gewählt wird, was insbesondere bei Indezes über mehrere Spalten wichtig ist, kann dies eine Abfrage deutlich verschnellern. Der nächste Trick ist alles in SQL zu machen (ich kann dir dabei gern helfen), statt in der einbettenden Programmiersprache.

Damit haben wir im Normalfall 17x17 Vergleiche über (zuletzt) eine Tabelle mit 22 Millionen Ergebniseinträgen. Die gesamte Datenbank inklusive der Strings ist zu diesem Zeitpunkt inklusive mehrere Indezes etwa 1 GiB groß. Wenn man die Textform nimmt, läppert es sich schon zu 18 GiB. Nur damit du die Relationen mal siehst. Ich meine, daß es sooo schlimm bei dir nicht werden kann, selbst wenn es eben mal 100,000 Lieder sind ...

(BTW: Die Vergleiche finden auch gegen sich selbst statt um Logikfehler im Programm zu finden und sie finden in beide Richtungen statt, weil sich zwar die Zahl der Dateien nicht unterscheiden sollte, die Zahl der Ergebnisse durch die gefundenen oder nicht gefundenen Objekte hingegen schon.)

[Mithrandir]

Zitat:

Zitat von Assarbad (Beitrag 1055431)

Und das Datum ist das Dateidatum oder Datum der letzten Aktualisierung des Vertex oder Datum der Erstellung des Vertex?

Die Aktualisierung des Vertex :)

Zitat:

Zitat von Assarbad (Beitrag 1055431)

Ich habe nur zwei Probleme damit: 1.) du reduzierst alles auf eine Dimension (kann gehen, kann aber auch danebengehen) und 2.) bleibt das eigentliche Problem unangetastet. Ich denke du solltest SQL benutzen um die Relationen zu ermitteln, nicht nur um sie zu speichern, wenn du verstehst was ich meine.

Ehrlich gesagt bin ich in Sachen Datenbanken noch nicht so fit. Grundbegriffe wie Indizes, PK, FK, SP sind bekannt. Aber wie würde ich solche Relationen abbilden bzw. SQL zu meinem Zweck nutzen? Wie "programmiere" ich mit SQLite?

[Mithrandir]

Ich habe mich mittlerweile ein bisschen weiter mit der Frage beschäftigt, wie ich möglichst viele Informationen über meine Lieder bekomme. Dabei bin ich auf MARSYAS gestoßen. Was soll ich sagen? Ich bekomms nicht kompilliert... :wall:

Ich bin momentan auch noch am Suchen, ob ich weitere Literatur finde zu dem Thema. Imho siehts aber ein bisschen dürftig aus. Was mich ehrlich gesagt ein wenig wundert... :gruebel:

[Assarbad]

Zitat:

Zitat von Mithrandir (Beitrag 1055604)

Ehrlich gesagt bin ich in Sachen Datenbanken noch nicht so fit. Grundbegriffe wie Indizes, PK, FK, SP sind bekannt. Aber wie würde ich solche Relationen abbilden bzw. SQL zu meinem Zweck nutzen? Wie "programmiere" ich mit SQLite?

Also in Sachen SQL kann ich absolut das Buch "The Definitive Guide to SQLite" von Mike Owens empfehlen. Ich hatte schon vorher genügend mit MySQL und auch teils mit PostgreSQL zu tun, aber detailliert verstanden habe ich die Zusammenhänge hinter SQL erst nach der Lektüre dieses Buches. Übrigens ist die Besprechung von SQL im Buch nicht auf SQLite beschränkt sondern es geht mehr um das Grundlagenwissen. Und mit Grundlagenwissen will ich keinesfalls kleinreden wie detailliert die Beschreibung ist - vielmehr wird dort auch auf die mathematischen Grundlagen hinter dem was heute SQL ist eingegangen. Es handelt sich in diesem Sinne also nicht um eine bloße Einführung in das Thema.

"Using SQLite" (erschienen bei O'Reilly, und ich habe es auch noch nicht durchgelesen sondern "drübergeblättert") scheint mehr auf die Anwendung von SQLite fokussiert zu sein - gerade wie der Titel es suggeriert ;)

Okay, nun zu dem was ich meinte. Die Frage ist, ob dies mit einer machinenerstellbaren Metrik (BPM, Metatag auslesen) funktionieren könnte. Meines Erachtens nach werden subjektive Daten des Benutzers wie "Stimmung" eher von Relevanz sein, was dann durch ein Zusammenführen auf einem Server zu ungleich besseren Ergebnissen führen würde. Aber: statt eindimensional einen Vertex abzuspeichern (übrigens macht m.M.n. allein die Eindimensionalität ein späteres Ausbalancieren oder andere Modifikationen am Gesamtgraphen schwer bis unmöglich) stellen wir uns einmal vor wie es aussähe, würden wir "Queen" in Einheiten von "Pink Floyd" abbilden (diese Beziehung wäre automatisch gegenseitig). Ähnlich würde Chopin in Mozarts abgebildet oder Beethoven in Vivaldis. Wenn man einen nicht-NULL-Wert hat, gibt es sozusagen einen Vertex der zwei Titel von "Queen" und "Pink Floyd" verbinden könnte. Eine clevere Datenbank wird entgegen der Aussagen einiger Vorredner eben nicht alle Daten allozieren. Selbst bei Dateisystemen sind "sparse files" seit Jahren Usus. Entsprechend würden nur jene Beziehungen Platz beanspruchen die existieren (plus ein wenig Overhead). Jede Tabelle wäre dabei nur die ID des Liedes und der eigentliche Wert für den Parameter.

Beim Sammeln der Daten könnte man dann die Mastertabelle nach dem Namen aller Tabellen befragen die eine Beziehung zwischen Künstlern abbilden. Ein entsprechendes Schema könnte auch für Melodien und "Stimmung" angewendet werden, wobei man gewisse Parameter (melancholisch vs. lustig usw.) vordefinieren müßte. Zuerst müßte man dann vom aktuellen Lied einige Kennwerte ermitteln (inklusive derer die der Benutzer angibt). Daraufhin kann man dann Lieder ermitteln deren Kennwerte sich gleichen. Zuerst indem man überhaupt Lieder ermittelt die den gleichen oder mindestens x Kennwerte mit dem aktuellen Lied teilt und dann weiter eingrenzend solche innerhalb eines (vermutlich konfigurierbaren) Bereichs.

Zusammenfassend:

die Namen der Tabellen müssen nicht zwangsläufig in deinem Programm vordefiniert sein. Es gibt Metatabellen in SQLite die es erlauben sowas dynamisch zu ermitteln. Habe ich schon gemacht und funktioniert wunderbar. Und solcherlei Dinge kann man ad infinitum schachteln um die Effizienz von SQLite bei dem Verarbeiten der Daten (mithilfe von SQL) zu nutzen anstatt Beziehungen die in SQL leicht und gut darstellbar sind in der Hostsprache nachzumodellieren.

[Mithrandir]

Ok, ich denke, so langsam hab ich verstanden, was du meinst. :gruebel: Das Buch werde ich mir definitiv noch ansehen.

Momentan bin ich dabei, mich ein wenig mit Audioanalyse auseinander zu setzen. Das Thema ist hochkomplex (ach!), aber prinzipiell ist alles lösbar. Es soll auch kein perfektes System werden, den Anspruch habe ich nicht. Je mehr man aber über das Thema liest, umso mehr ist man beeindruckt von dem, was unser Gehirn leistet. ;)

[Mithrandir]

Ich habe das Thema der Audioanalyse mal hierhin ausgelagert.

[DIET3RIX]

Die Idee habe ich schon seit Jahren. Leider habe ich keine Zeit diese in die Tat umzusetzen....

Wäre das nichts für dich?
http://www.mufin.com/de/software/mufinplayer

[Mithrandir]

Ich hab mir das Ding angesehen. Eine Speicherauslastung von fast 300 MB nach einer Stunde hören und die Tatsache, dass offensichtlich nicht rekursiv indiziert werden kann, sprechen dagegen. Außerdem merkt sich das Programm nicht, in welcher Reihenfolge ich meine Songs höre. Desweiteren passt das grad, weil ich mich in C# und WPF einarbeiten muss. :mrgreen:

[DIET3RIX]

Ich hatte den Player auch mal installiert gehabt, aber irgendwie hat der mich in keinster Weise überzeugt. Langsam ist der dazu auch noch.

Ich hätte dann auch mal 'ne Frage an dich.
Nehmen wir mal an, dass die Musiksammlung in der Datenbank gelagert wird. Zudem wirst du mit Sicherheit eine weitere Tabelle anlegen, in der die Playlisten (o.ä.) gespeichert werden (Die Abspielreihenfolge).

Wie willst du die beiden Tabellen referenzieren?
Du könntest das mit einer ID machen, aber was ist wenn sich die IDs ändern (durch neues einlesen, DB Crash, Änderung der Verzeichnisstruktur [wodurch neu eingelesen werden muss], usw.)? Dadurch werden deine Playlisten unbrauchbar.

Oder verstehe ich dein Projekt nicht richtig?

(Eigtl. habe ich auch vor, mich in C# einzuarbeiten...)

[Mithrandir]

Über das Datenbanklayout habe ich mir momentan noch keine weiteren Gedanken gemacht, da ich mich gerade mit der Audioanalyse beschäftige. ;)

Es gibt einige Dinge, die man abfangen kann, andere nicht, stimmt. Die Abspielreihenfolge wird über die IDs der Songs gelöst, alles andere wäre ineffektiv. Die Frage ist allerdings, welche ID man nimmt. Man könnte bspw. nicht die ID des Datenbankeintrages nehmen (die ja uniqe sein sollte), sondern sich eine ID aus Titel,Künstler generieren. Damit wäre man auch vor einem erneuten einlesen sicher. Die Frage ist: Ist der Aufwand gerechtfertigt? Das sind Dinge, über die ich mir noch Gedanken machen muss. Aber ein sehr guter Punkt. :thumb:

Mal ne Gegenfrage: Was genau hat dir an Mufin nicht gefallen?