Okay, ich bin mir sicher, dass irgendjemand irgendwo schon einen Algorithmus dafür entwickelt haben muss, also dachte ich, dass ich fragen würde, bevor ich ihn (neu) erfinde.
Ich habe eine Liste von beliebigen (vom Benutzer eingegebenen) nicht leeren Textzeichenfolgen. Jede Zeichenfolge kann eine beliebige Länge haben (außer 0) und sie sind alle eindeutig. Ich möchte sie dem Benutzer anzeigen, aber ich möchte sie auf eine feste Länge zuschneiden, die ich entscheide, und einen Teil von ihnen durch eine Ellipse (...) ersetzen. Der Catch ist, dass ich möchte, dass alle Ausgabezeichenfolgen eindeutig sind.
Zum Beispiel, wenn ich die Zeichenfolgen habe:
Dann möchte ich nicht die Enden der Strings trimmen, denn das ist der eindeutige Teil (ich möchte "Microsoft Internet ..." nicht dreimal anzeigen), aber es ist OK, den mittleren Teil auszuschneiden:
Andere Male könnte der mittlere Teil einzigartig sein, und ich möchte das Ende trimmen:
könnte werden:
Ich denke, es sollte wahrscheinlich niemals den sehr Anfang der Strings ellipsen, selbst wenn das sonst erlaubt wäre, da das komisch aussehen würde. Und ich denke, es könnte mehr als einen Platz in der Saite ellipsen, aber innerhalb des Grundes - vielleicht 2 mal wäre in Ordnung, aber 3 oder mehr scheint übermäßig. Oder die Anzahl der Male ist nicht so wichtig wie die Größe der verbleibenden Stücke: weniger als etwa 5 Zeichen zwischen Ellipsen wäre ziemlich sinnlos.
Die Eingaben (sowohl Anzahl als auch Größe) sind nicht besonders groß, daher ist die Leistung kein großes Problem (solange der Algorithmus nicht so albern vorgeht wie das Aufzählen aller möglichen Strings, bis ein Satz gefunden ist funktioniert!).
Ich denke, diese Anforderungen scheinen ziemlich spezifisch zu sein, aber ich bin eigentlich ziemlich nachsichtig - ich versuche nur zu beschreiben, was ich vorhabe.
Ist so etwas schon einmal gemacht worden? Gibt es einen vorhandenen Algorithmus oder eine Bibliothek, die das tut? Ich habe einige gegoogelt, aber bis jetzt noch nichts gefunden (aber vielleicht bin ich nur schlecht im googeln). Ich muss glauben, dass irgendjemand irgendwo dieses Problem bereits lösen wollte!
Es klingt wie eine Anwendung des längsten gemeinsamen Substring-Problems.
Ersetzen Sie den längsten Teilstring, der allen Strings gemeinsam ist, mit Ellipsen. Wenn die Zeichenfolge immer noch zu lang ist und Sie eine weitere Ellipse haben dürfen, wiederholen Sie den Vorgang.
Sie müssen feststellen, dass Sie möglicherweise nicht in der Lage sind, eine gegebene Menge von Strings ausreichend zu "ellipsen", um die Längenanforderungen zu erfüllen.
Sortieren Sie die Zeichenfolgen. Behalten Sie die ersten X Zeichen jeder Zeichenfolge bei. Wenn dieses Präfix für die Zeichenfolge vorher und nachher nicht eindeutig ist, wird so lange vorgegangen, bis eindeutige Zeichen (verglichen mit der Zeichenfolge davor und danach) gefunden werden. (Wenn keine eindeutigen Zeichen gefunden werden, hat die Zeichenfolge keinen eindeutigen Teil, siehe unten im Beitrag.) Fügen Sie vor und nach diesen eindeutigen Zeichen Ellipsen hinzu.
Beachten Sie, dass dies immer noch lustig aussehen könnte:
%Vor%Ich weiß nicht, in welcher Sprache Sie dies tun möchten, aber hier ist eine Python-Implementierung.
%Vor%Auch Sie erwähnen die Saite selbst sind einzigartig, aber haben sie alle einzigartige Teile? Zum Beispiel sind "Microsoft" und "Microsoft Internet Explorer 7" zwei verschiedene Zeichenfolgen, aber die erste hat keinen Teil, der von der zweiten eindeutig ist. Wenn dies der Fall ist, müssen Sie Ihrer Spezifikation etwas hinzufügen, um diesen Fall eindeutig zu machen. (Wenn Sie "Xcrosoft", "MXcrosoft", "MiXrosoft" usw. zum Mix mit diesen beiden Strings hinzufügen, gibt es no eindeutigen String, der kürzer ist als der ursprüngliche String, der "Microsoft" darstellt) ( Eine andere Möglichkeit, darüber nachzudenken: Wenn Sie alle möglichen X-Zeichenfolgen haben, können Sie sie nicht alle zu X-1 oder weniger Strings komprimieren, so wie keine Komprimierungsmethode alle Eingaben komprimieren kann im Wesentlichen eine Komprimierungsmethode.)
Ergebnisse vom ursprünglichen Beitrag:
%Vor%