Gibt es eine Metrik wie stark ein Datenset sortiert ist?

Hi,

in meinem konkreten Fall habe ich eine Datei mit einem Wort in jeder Zeile, auch Wörterbuch genannt Ohne Unikate enthält die Datei 350000 Wörter und mit Duplikaten 660000 Wörter/Zeilen.

Mich würde nun interessieren wie stark die Datei sortiert/unsortiert ist. Gibt es da ein Standardverfahren? Ist es überhautp sinnvoll? Auß dem Bauch raus würde ich sagen man könnte die Distanz zwischen der Position in der unsortierten Datei und der Sortierten betrachten, davon den Mittelwert und Varianz bilden. Das wäre für den (annähernd) besten/schlechtesten Fall aussagefähig, aber wenn die Datei viele sortierte Blöcke aufweist und einige "Punktwolken" kann man das so kaum auslesen.

Kann man das evt. grafisch darstellen (mit gnuplot)? Oder bin ich ganz auf dem Holzweg und ihr habt eine viel bessere Idee zur Darstellung :-)?

Danke & Grüße

SeppJ

Ach, da gibt es viele. Welche für dich die richtige ist, musst du entscheiden. Ein paar Stichworte:
- inversion distance
- l1 distance
- Ulam distance

scrontch

Hallo,

bist du mit deinen Recherchen irgendwie weiter gekommen?

Ich hab nämlich ein ganz ähnliches Problem:
Ich möchte Mischverfahren bei Kartenspielen analysieren.
Die Idee ist von einem perfekt sortierten Stapel auszugehen (Karten 1..n durchnummeriert), dann das Mischverfahren anzuwenden, und am Schluß den Stapel eben dahingehend zu beurteilen wie stark/schwach er immer noch sortiert ist.

knivil

Wie waere es mit einem Mass abgeleitet von der Entropie? Oder die Anzahl der noetigen Vertauschungen, bis es sortiert ist? Was ist an den Vorschlaegen von SeppJ schlecht?

scrontch

knivil schrieb:

Was ist an den Vorschlaegen von SeppJ schlecht?

Ulam distance hört sich brauchbar an. Muss ich mir noch genauer durchlesen.

Zu "inversion distance" hab ich nichts gefunden(?)

Und wie l1 distance nützlich sein kann versteh ich nicht.
Den original- und gemischten Stapel als Vektoren nehmen und dazwischen den L1 Abstand? Das kann's wohl nicht sein, denn wenn ich nur die erste mit der letzten Karte vertausche wird der L1 Abstand schon sehr groß, obwohl der Stapel praktisch nicht gemischt ist.

SeppJ

Zu "inversion distance" hab ich nichts gefunden(?)

Hier eine kleine Übersicht:
http://www.cs.rutgers.edu/~mlittman/courses/Archive/cps130-97/lectures/lect05/node16.html

Das kann's wohl nicht sein, denn wenn ich nur die erste mit der letzten Karte vertausche wird der L1 Abstand schon sehr groß, obwohl der Stapel praktisch nicht gemischt ist.

Die Maße setzen halt jedes andere Schwerpunkte.