Originalreferenz für Huffman-förmige Merge Sort?

8

Was ist die erste Veröffentlichung des Konzepts zur Optimierung der Zusammenführungssortierung nach

  1. Identifizieren von Sequenzen aufeinanderfolgender Positionen in aufsteigender Reihenfolge (auch bekannt als Läufe) in linearer Zeit; dann
  2. wiederholtes Zusammenführen der beiden kürzesten derartigen Sequenzen und Hinzufügen des Ergebnisses dieser Zusammenführung zur Liste der sortierten Fragmente.

In einigen meiner Veröffentlichungen (z. B. http://barbay.cl/publications.html#STACS2009 , http://barbay.cl/publications.html#TCS2013 ) habe ich diesen Trick verwendet, um schneller zu sortieren und eine komprimierte Datenstruktur für zu generieren Permutation.

Es scheint, dass dieser Trick schon früher eingeführt wurde, nur um schneller zu sortieren, aber weder ich noch mein Schüler konnten die Referenz zurückfinden?

reference-request sorting huffman Jeremy
quelle
Hast du Knuth überprüft? Ich erinnere mich, dass in TAOCP einiges los war.
Mikolas
1
n/.2ρn(1+lg⁡ρ)(n1,…,nρ)n(1+2H.(n1,…,nρ))
Ö(n(1+lG(r+1)))

Antworten:

9

Ich fand das Ergebnis in einem obskuren 4p-technischen Bericht versteckt: Ich teile meine Ergebnisse hier, falls andere interessiert sind.

  1. Knuth erwähnt Läufe in seiner Beschreibung der "natürlichen Zusammenführungssorte" (Seite 160 von Band 3 der 3. Ausgabe), analysiert seine Komplexität jedoch nur im Durchschnitt (was n / 2 Läufe ergibt), nicht in Abhängigkeit von der Zahl ρ von läuft
  2. 1985 bewies Mannila, dass Natural Mergesort innerhalb von O (n (1 + lg (r + 1))) Zeit benötigt, um n Elemente zu sortieren, die r Läufe bilden.
  3. 1996 führte Tadao Takaoka ( http://dblp.uni-trier.de/pers/hd/t/Takaoka:Tadao ) den Begriff der Entropie der Verteilung der Größen (n1,…, nρ) der Läufe ein In einem 4-seitigen Artikel mit dem Titel "Minimal MergeSort" wurde eine Komplexität von Vergleichen nachgewiesenn(1+2H.(n1,…,nρ))
  4. 2009 wurde die Technik auf dem Symposium Mathematical Fundation of Computer Science vorgestellt (zusammen mit Ergebnissen zu Sortierung, kürzesten Wegen und minimalen Spannbäumen).
  5. 2010 wurde es im Journal of Information Processing unter dem Titel "Entropy as Computational Complexity" mit dem zusätzlichen Co-Autor Yuji Nakagawa veröffentlicht ( https://www.semanticscholar.org/author/Yuji-Nakagawa/2219943 ). .

Ich verbinde die unten stehenden Bibtex-Referenzen.

@TechReport {1997-TR-MinimalMergesort-Takaoka, Autor = {Tadao Takaoka}, Titel = {Minimal Mergesort}, Institution = {University of Canterbury}, Jahr = 1997, Anmerkung = { http://ir.canterbury.ac. nz / handle / 10092/9666 , zuletzt aufgerufen [23.08.2016 Di]}, abstract = {Wir präsentieren einen neuen adaptiven Sortieralgorithmus namens Minimal Merge Sort, der die aufsteigenden Läufe in der Eingabeliste von kürzer zu länger zusammenführt. Das heißt, jedes Mal werden die kürzesten zwei Listen zusammengeführt. Wir zeigen, dass dieser Algorithmus in Bezug auf das neue Maß der Vorsortierung, Entropie genannt, optimal ist.}}

In diesem Artikel stellen wir das Maß der Entropie H (S) für die Unsicherheit in teilweise gelösten Eingabedaten S (X) = (X 1, ..., X k) vor, wobei X der gesamte Datensatz ist und jedes X i ist bereits gelöst. Wir verwenden das Entropiemaß, um drei Beispielprobleme zu analysieren: Sortieren, kürzeste Wege und minimale Spannbäume. Für das Sortieren von X i ist ein aufsteigender Lauf und für kürzeste Wege ist X i ein azyklischer Teil in dem gegebenen Graphen. Für minimale Spannbäume wird X i als teilweise erhaltener minimaler Spannbaum für einen Teilgraphen interpretiert. Das Entropiemaß H (S) wird unter Berücksichtigung von pi = | X i | / | X | definiert als Wahrscheinlichkeitsmaß, dh H (S) = - nΣki = 1pilogpi, wobei n = Σki = 1 | Xi |. Dann zeigen wir, dass wir die Eingabedaten S (X) in O (H (S)) Zeit sortieren und das Problem des kürzesten Pfades in O (m + H (S)) Zeit lösen können, wobei m die Anzahl der Kanten der ist Graph.

@article {2010-JIP-EntropyAsComputationalComplexity-TakaokaNakagawa, Autor = {Tadao Takaoka und Yuji Nakagawa}, Titel = {Entropy as Computational Complexity}, Journal = Jip, Band = {18}, Seiten = {227--241}, Jahr = {2010}, url = { http://dx.doi.org/10.2197/ipsjjip.18.227 }, doi = {10.2197 / ipsjjip.18.227}, timestamp = {Mi, 14. September 2011 13:30:52 +0200 }, biburl = { http://dblp.uni-trier.de/rec/bib/journals/jip/TakaokaN10 }, bibsource = {dblp Computer Science Bibliography, http://dblp.org}, abstract = {Wenn die angegebene Probleminstanz teilweise gelöst ist, möchten wir unseren Aufwand zur Lösung des Problems mithilfe dieser Informationen minimieren. In diesem Artikel stellen wir das Entropiemaß H (S) für die Unsicherheit in teilweise gelösten Eingabedaten S (X) = (X1, ..., Xk) vor, wobei X der gesamte Datensatz ist und jedes Xi bereits vorhanden ist gelöst. Wir schlagen einen generischen Algorithmus vor, der Xi wiederholt zusammenführt und endet, wenn k zu 1 wird. Wir verwenden das Entropiemaß, um drei Beispielprobleme zu analysieren: Sortieren, kürzeste Pfade und minimale Spannbäume. Zum Sortieren ist Xi ein aufsteigender Lauf, und für minimale Spannbäume wird Xi als teilweise erhaltener minimaler Spannbaum für einen Teilgraphen interpretiert. Für kürzeste Wege ist Xi ein azyklischer Teil in der gegebenen Grafik. Wenn k klein ist, kann der Graph als nahezu azyklisch angesehen werden. Das Entropiemaß H (S), wird definiert, indem pi = ¦Xi¦ / ¦X¦ als Wahrscheinlichkeitsmaß betrachtet wird, dh H (S) = -n (p1 log p1 + ... + pk log pk), wobei n = ¦X1¦ +. . . + ¦Xk¦. Wir zeigen, dass wir die Eingabedaten S (X) in O (H (S)) Zeit sortieren können und dass wir den minimalen Kosten-Spanning Tree in O (m + H (S)) Zeit vervollständigen können, wobei m in der Zahl ist von Kanten. Dann lösen wir das Problem des kürzesten Weges in O (m + H (S)) Zeit. Schließlich definieren wir die doppelte Entropie für den Partitionierungsprozess, wobei wir die Zeitgrenzen für eine generische Quicksortierung und das Problem des kürzesten Pfades für eine andere Art von nahezu azyklischen Graphen angeben.} wo m in der Anzahl der Kanten. Dann lösen wir das Problem des kürzesten Weges in O (m + H (S)) Zeit. Schließlich definieren wir die doppelte Entropie für den Partitionierungsprozess, wobei wir die Zeitgrenzen für eine generische Quicksortierung und das Problem des kürzesten Pfades für eine andere Art von nahezu azyklischen Graphen angeben.} wo m in der Anzahl der Kanten. Dann lösen wir das Problem des kürzesten Weges in O (m + H (S)) Zeit. Schließlich definieren wir die doppelte Entropie für den Partitionierungsprozess, wobei wir die Zeitgrenzen für eine generische Quicksortierung und das Problem des kürzesten Pfades für eine andere Art von nahezu azyklischen Graphen angeben.}
}}

Jeremy
quelle