Ich suche nach einem Pfadabkürzungsalgorithmus existign (ähnlich wie das statische Steuerelement Win32 mit SS_PATHELLIPSIS ) für eine Menge von Pfaden, die sich auf die verschiedenen Elemente konzentrieren sollten.
Zum Beispiel, wenn meine Pfade so sind:
%Vor%Wenn nicht genügend Anzeigebereich verfügbar ist, sollten sie auf etwas wie diese abgeschnitten werden:
%Vor%(Angenommen, eine Ellipse ist in der Regel kürzer als drei Buchstaben).
Dies ist nur ein Beispiel für einen ziemlich einfachen, idealen Fall (zB würden sie alle jetzt in unterschiedlichen Längen enden, und ich würde nicht wissen, wie man einen guten Vorschlag macht, wenn ein Pfad "Thingie / Long Test /" wird dem Pool hinzugefügt).
Es gibt keine gegebene Struktur der Pfadelemente, sie werden vom Benutzer zugewiesen, aber oft haben die Elemente ähnliche Segmente. Es sollte für proportionale Schriftarten funktionieren, also sollte der Algorithmus eine Messfunktion nehmen (und nicht zu stark nennen) oder eine Vorschlagsliste erzeugen.
Datenweise würde ein typischer Anwendungsfall 2..4 Pfadsegmente und 20 Elemente pro Segment enthalten.
Ich suche nach früheren Versuchen in diese Richtung, und wenn das mit einer vernünftigen Menge an Code oder Abhängigkeiten lösbar ist.
Ich nehme an, Sie fragen hauptsächlich, wie Sie mit der Menge der Ordnernamen umgehen, die aus derselben Hierarchiestufe extrahiert wurden, da das Teilen nach Zeilen und Pfadseparatoren und das Zusammenfassen nach Hierarchietiefe einfach ist.
Ihr Problem erinnert mich sehr an das längste gemeinsame Teilstring-Problem , mit den Unterschieden, dass:
Diese können wesentlich erscheinen, aber wenn Sie die dynamische Programmierlösung in dem Artikel untersuchen, können Sie sehen, dass es darum geht, eine Tabelle von "Charakterkollisionen" zu erstellen und dann nach der längsten Diagonale in dieser Tabelle zu suchen. Ich denke, dass Sie stattdessen alle Diagonalen in der Tabelle nach der Reihenfolge aufzählen können, in der sie angezeigt werden, und dann für jeden Pfad alle Auftritte dieser Zeichenfolgen mit Ellipsen nach Reihenfolge ersetzen.
Wenn Sie eine minimale Teilstringlänge von 2 erzwingen, erhalten Sie ein Ergebnis, das dem entspricht, was Sie in Ihrer Frage beschrieben haben.
Es sieht so aus, als ob man etwas an den Algorithmus basteln muss (um zum Beispiel sicherzustellen, dass ein bestimmter Teilstring in allen Strings zuerst ist), und dann müssen Sie ihn über Ihren gesamten Satz aufrufen ... Ich hoffe, das gibt Ihnen zumindest eine mögliche Richtung.
Nun, die "natürliche Zahl" Bestellteil ist eigentlich einfach, ersetzen Sie einfach alle Zahlen mit formatierten Zahl, wo genug führende Nullen, z. Test 9V - & gt; Test 000009V und Test 12B - & gt; %Code%. Diese sind jetzt nach Standardmethoden sortierbar.
Für die tatsächliche Ellipse. Wenn das nicht wirklich ein riesiges System ist, würde ich einfach eine manuelle Ellipsenliste (aus Regexen, für Flexibilität und Schmerz) hinzufügen, die bestimmte Wörter in Ellipsen verwandelt. Dies erfordert kontinuierliche Arbeit, aber der Algorithmus braucht auch Ihre Zeit. Es gibt Myriaden von Eckfällen.
Ich würde wahrscheinlich einen "Floodfill" -Ansatz versuchen. Ordne die erste Ebene von Verzeichnissen wie eine Bitmap an, jeder Buchstabe ist ein Pixel. Iteriere alle Zeichen, die sich in Namen von Verzeichnissen befinden. mit allen von ihnen "malen" Sie das gleiche Zeichen, dann "malen" Sie das nächste Zeichen aus der ersten Zeichenfolge, so dass es diesem vorherigen Zeichen folgt (und so weiter usw.) Wählen Sie dann die längste gemalte Zeichenfolge, die Sie finden.
Beispiel (wenn vorangestellt mit *, es ist gemalt)
%Vor%Beachten Sie Folgendes:
%Vor% Und dann kommt man zum zweiten "o" und es wird eine Teilkette von mindestens 2 gefunden.
Sie müssen also über die meisten möglichen Zeichen-Instanzen iterieren (eine Optimierung besteht darin, in jedem String an Position Length-n zu stoppen, wobei n der längste bereits gefundene gemeinsame Teilstring ist. Dann gibt es noch ein weiteres Problem (hier mit Test 000012B )
Was möchten Sie tun? Cut "Beta Beta" oder Alfa Beta Gamma Delta oder Alfa Beta oder Beta Beta ?
Dies ist ein bisschen weitschweifig, aber könnte unterhaltsam sein:).