Intelligente Pfadabschneidung/Ellipsis für die Anzeige

Question

Ich bin auf der Suche nach einem existierenden Algorithmus zur Pfadkürzung (ähnlich dem, was das statische Win32-Steuerelement mit SS_PATHELLIPSIS ) für eine Reihe von Pfaden, die sich auf die einzelnen Elemente konzentrieren sollten.

Wenn meine Pfade zum Beispiel so aussehen:

 Unit with X/Test 3V/
 Unit with X/Test 4V/
 Unit with X/Test 5V/
 Unit without X/Test 3V/
 Unit without X/Test 6V/
 Unit without X/2nd Test 6V/

Wenn nicht genügend Platz für die Anzeige zur Verfügung steht, sollten sie in etwa so gekürzt werden:

 ...with X/...3V/
 ...with X/...4V/
 ...with X/...5V/
 ...without X/...3V/
 ...without X/...6V/
 ...without X/2nd ...6V/

(Unter der Annahme, dass eine Ellipse im Allgemeinen kürzer als drei Buchstaben ist).

Dies ist nur ein Beispiel für einen ziemlich einfachen Idealfall (z. B. würden sie jetzt alle unterschiedlich lang sein, und ich wüsste nicht, wie ich einen guten Vorschlag erstellen sollte, wenn ein Pfad "Thingie/Long Test/" zum Pool hinzugefügt wird).

Es gibt keine vorgegebene 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 sie nicht zu stark aufrufen) oder eine Vorschlagsliste erzeugen.

Datenmäßig würde ein typischer Anwendungsfall 2..4 Pfadsegmente und 20 Elemente pro Segment enthalten.

Ich bin auf der Suche nach früheren Versuchen in diese Richtung, und ob das mit einer vernünftigen Menge an Code oder Abhängigkeiten lösbar ist.

Answer 1

Ich gehe davon aus, dass Sie hauptsächlich danach fragen, wie man mit der Menge der Ordnernamen umgeht, die aus derselben Hierarchieebene extrahiert wurden, da die Aufteilung nach Zeilen und Pfadseparatoren und die Aggregation nach Hierarchietiefe einfach ist.

Ihr Problem erinnert mich sehr an die Problem der längsten gemeinsamen Teilzeichenkette , mit den Unterschieden, dass:

1. Sie sind an vielen Teilzeichenfolgen interessiert, nicht nur an einer.
2. Ihnen ist die Ordnung wichtig.

Diese mögen umfangreich erscheinen, aber wenn Sie sich die Lösung der dynamischen Programmierung in dem Artikel ansehen, sehen Sie, dass es darum geht, eine Tabelle mit "Zeichenkollisionen" zu erstellen und dann nach der längsten Diagonale in dieser Tabelle zu suchen. Ich denke, man könnte stattdessen alle Diagonalen in der Tabelle in der Reihenfolge ihres Auftretens aufzählen und dann für jeden Pfad alle Vorkommen dieser Zeichenfolgen in der Reihenfolge durch Ellipsen ersetzen.

Die Erzwingung einer minimalen Teilstringlänge von 2 führt zu einem ähnlichen Ergebnis wie in Ihrer Frage beschrieben.

Es scheint, wie es erfordert einige Bastelei mit dem Algorithmus (z. B. Sicherstellen einer bestimmten Teilzeichenfolge ist zuerst in allen Zeichenfolgen), und dann müssen Sie es über Ihren gesamten Satz aufrufen... Ich hoffe, dies gibt Ihnen zumindest eine mögliche Richtung.

Answer 2

Der Teil mit den "natürlichen Zahlen" ist eigentlich ganz einfach: Ersetzen Sie einfach alle Zahlen durch formatierte Zahlen mit genügend führenden Nullen, z. B. Test 9V -> Test 000009V y Test 12B -> Test 000012B . Diese können nun mit Standardmethoden sortiert werden.

Für die eigentliche Ellipsisierung. Wenn es sich nicht gerade um ein riesiges System handelt, würde ich einfach eine manuelle Ellipsisier-"Liste" (aus Regexen, wegen der Flexibilität und der Schmerzen) hinzufügen, die bestimmte Wörter in Ellipsen verwandelt. Das erfordert zwar kontinuierliche Arbeit, aber die Entwicklung des Algorithmus frisst auch Zeit; es gibt unzählige Eckfälle.

Ich würde wahrscheinlich einen "Floodfill"-Ansatz versuchen. Ordnen Sie die erste Ebene der Verzeichnisse, wie Sie eine Bitmap, jeder Buchstabe ist ein Pixel. iterieren über alle Zeichen, die in Namen von Verzeichnissen sind. mit allen von ihnen, "malen" dieses gleiche Zeichen, dann "malen" das nächste Zeichen aus der ersten Zeichenfolge, so dass es dieses vorherige Zeichen folgt (und so weiter usw.) Dann wählen Sie die längste gemalte Zeichenfolge, die Sie finden.

Beispiel (wenn ein * vorangestellt ist, ist es gemalt)

Foo
BarFoo

*Foo
Bar*Foo

*F*oo
Bar*F*oo

...

beachten Sie das:

*ofoo
b*oo

*o*foo
b*oo
.. painting of first 'o' stops since there are no continuing characters.

of*oo
b*oo
...

Dann kommt man zum zweiten "o" und es wird eine Teilzeichenkette von mindestens 2 gefunden. Man muss also über die meisten möglichen Zeicheninstanzen iterieren (eine Optimierung besteht darin, in jeder Zeichenkette an der Position Length-n aufzuhören, wobei n die längste bereits gefundene gemeinsame Teilzeichenkette ist. Aber dann gibt es noch ein weiteres Problem (hier mit "Beta Beta" )

          | <- visibility cutout
Alfa Beta Gamma Delta 1
Alfa Beta Gamma Delta 2
Alfa Beta Beta 1
Alfa Beta Beta 2
Beta Beta 1
Beta Beta 2
Beta Beta 3
Beta Beta 4

Was wollen Sie tun? schneiden. Alfa Beta Gamma Delta ou Alfa Beta ou Beta Beta ou Beta ?

Das ist ein bisschen weit hergeholt, aber vielleicht unterhaltsam :).